Динамические связанные списки. Связанный список – это базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные

 

Связанный список – это базовая динамическая структура данных, состоящая из узлов, каждый из которых содержит как собственно данные, так и одну или две ссылки («связки») на следующий и/или предыдущий узел списка.

Преимуществом связанных списков по сравнению со статическими массивами является отсутствие ограничений на количество динамически добавляемых элементов (в реальности ограничено только объемом доступной памяти).

Также значительно проще, чем в статических массивах, выполняется процедура удаления.

Недостатком связанных списков является отсутствие возможности произвольного доступа к узлам, т.е. необходимость просмотра всех узлов, предшествующих заданному. Поэтому, в общем случае, работа со списками медленнее, чем с массивами.

К тому же, для хранения указателей на соседние элементы расходуется дополнительное количество памяти.

 

Базы данных.

База данных – это информационная модель, позволяющая упорядоченно хранить данные о группе объектов, обладающих одинаковым набором свойств.

 

Преимуществом использования баз данных является удобство и относительная простота работы с данными, т.к. компоненты среды Delphi предоставляют для этого достаточно полные и гибкие возможности.

Множество операций над данными, таких как поиск и фильтрация, с помощью них описываются и выполняются быстрее.

Недостатком баз данных является более низкая скорость работы, т.к. физически база данных представляет собой файл или совокупность файлов, хранимых на внешнем носителе.

Поэтому использование базы данных требует большегообъемапамяти, в т.ч. для хранения служебной информации.

В условиях поставленной задачи, нет необходимости в использовании базы данных, т.к. она эффективна лишь при достаточно большом объеме хранимой информации. В противном случае, использование базы данных приведет к существенному снижению производительности программы и неоправданным затратам памяти.

 

1.1.4 Вывод.

 

Таким образом, проанализировав вышеописанные структуры данных, можно сделать вывод, что в случае поставленной задачи оптимальным решением является использование динамических связанных списков.

 

В программе используются динамические списки. С целью экономии памяти каждая запись списка содержит указатель только на следующий элемент списка, т.к. используемые алгоритмы позволяют решить задачу с помощью односвязных списков.

 

Рассмотрим подробнее абстрактный тип данных «список».

В математике список представляет собой последовательность элементов определенного типа: а ₁, а ₂, ….. а_n, где n ≥0 и все а_i имеют один тип. Количество, n – длина списка, если n ≥ 1, то а ₁ – первый элемент, а а_n – последний, в случае n = 0 имеем пустой список.

Списки являются чрезвычайно гибкой структурой: их легко сделать большими или меньшими; их элементы доступны для вставки или удаления в любой позиции списка. Списки можно объединять или разбивать на меньшие списки.

При реализации списков с помощью массивов их элементы располагаются в смежных ячейках массива. Это представление позволяет легко просматривать содержимое списка и вставлять новые элементы в его конец. Однако вставка нового элемента в середину списка требует перемещения всех последующих элементов на одну позицию к концу массива. Операция удаления также требует перемещения элементов списка с целью освобождения ячейки.

Рассмотрим реализацию однонаправленного связанного списка с использованием указателей, связывающих последовательные элементы списка. Однонаправленный связанный список представляет собой динамическую структуру данных, число элементов которой может изменяться по мере того, как данные помещаются в список или удаляются из него. Эта реализация освобождает от непрерывной области памяти для хранения списка и, следовательно, от необходимости перемещения элементов списка при вставке или удалении элементов. Однако ценой за это удобство становится использование дополнительной памяти для хранения указателей.

В этой реализации список состоит из ячеек, каждая из которых содержит элемент списка и указатель на следующую ячейку списка. Если список состоит из элементов то для i=1, 2,…, n-1 ячейка, содержащая элемент , имеет также указатель на ячейку, содержащую элемент . Ячейка, содержащая элемент , имеет указатель nil (нуль). Имеется также ячейка header (заголовок), которая указывает на ячейку, содержащую . Ячейка header не содержит элементов списка. В случае пустого списка заголовок имеет указатель nil, не указывающий ни на какую ячейку. Список, не содержащий элементов, называется пустым или нулевым. На рис. 1.1 показан однонаправленный связанный список.

 

 

Рис. 1.1 - Связанный список

 

Для однонаправленных списков удобно использовать следующее определение позиций элементов. Здесь для i=2, 3, …, n позиция i определяется как указатель на ячейку, содержащую указатель на элемент . Позиция 1 – это указатель в ячейке заголовка, а позиция end (L) – указатель в последней ячейке списка L. Формально структуру связанного списка можно определить следующим образом(рис. 1.2):

 

 

Рис. 1.2 - Структура связанного списка

 

Основные операции, выполняемые с элементами списка: просмотр, вставка, удаление.