Понятие динамической структуры данных

 

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

Операции по модификации динамических структур:

¨ создание / разрушение структуры

¨ включение объектов в структуру / исключение объектов из структуры

¨ выделение подмножества объектов структуры по определенным признакам

¨ объединение нескольких подмножеств объектов в определенном порядке в единую структуру.

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

 

Линейные динамические структуры данных (списки)

 

Линейной динамической структурой (списком) называется множество объектов (элементов, узлов) S={ s_i}, i=1,...,n, на котором определены отношения предшествования / следования, причем для любого объекта s_i, i=2,...,n-1 существует единственный “предшественник” s_i-1 и единственный “последователь” s_i+1. Объект s₁ не имеет предшественника и является первым элементом списка, объект s_n не имеет последователя и является “хвостом” списка. Ситуация n=0 определяет особое состояние: “список пуст”.

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

 

Основные виды списков

 

СТЕК – структура, у которой включение / исключение элементов и доступ к элементам производится на одном конце структуры, называемом верхушкой стека (рис. 19). Для стека характерна дисциплина обслуживания “последним пришел – первым обслужен” (LIFO – Last Input First Output).

 

Рис. 19. Структура стека

ОЧЕРЕДЬ – структура, у которой включение элемента производится в хвост, а исключение элемента и доступ к элементам выполняются в начале списка (рис. 20). Для очереди характерна дисциплина обслуживания “первым пришел – первым обслужен” (FIFO – First Input First Output).

 

Рис. 20. Структура очереди

ДЕК (двусторонняя очередь) – операции включения / исключения элементов и доступ к элементам выполняются как в начале, так и в хвосте списка.

СПИСКИ ПРОИЗВОЛЬНОГО ВИДА – операции включения / исключения элементов выполняются в любой точке структуры, возможен доступ к произвольному элементу списка.

 

Односвязные списки

 

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

Элемент хранения односвязного списка описывается следующим образом:

Type Plist=^List;   List= record info: word; link: plist;   end;	{ указатель на узел списка } { описание узла списка } { информационное поле узла } { поле связи узла }
Var first: PList;   p: PList;   x: word;	{ указатель на первый узел списка } { вспомогательный указатель }

 

На рис. 21 представлен пример структуры односвязного списка.

 

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

 

На первый элемент списка указывает указатель first. Если список пуст, то first = nil. Если список не пуст, то к атрибуту любого его элемента (например, первого) можно получить доступ через указатель.

 

x:=first ^.info; p:=first ^.link;

{ значение информационного поля первого элемента } { значение поля связи первого элемента – адрес второго элемента }

 

К атрибутам любого элемента списка, кроме первого, возможен дистанционный доступ.

 

x:=first ^.link ^.info;

{ значение информационного поля второго элемента }

 

Дистанционный доступ ко второму узлу списка эквивалентен следующей последовательности операторов:

 

p:=first ^.link; x:=p^.info;

{ установка вспомогательного указателя на второй узел списка } { значение информационного поля второго узла списка }