Связанные динамические данные

Основные определения

Линейные списки - это данные динамической структуры, которые представляют собой совокупность линейно связанных однородных элементов и для которых разрешены следующие действия:

- добавление элемента в начало (голову) списка;

- вставка элемента между двумя любыми другими элементами списка;

- удаление любого, как крайнего, так и среднего, элемента списка.

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

Очередь - частный случай линейного односвязного списка, для которого разрешены только два действия: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.

Стек - частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной (головой) стека.

Деревья - это динамические данные иерархической структуры произвольной конфигурации. Элементы дерева называются вершинами (узлами).

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

Организация взаимосвязей в связанных динамических данных

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

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

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

Объявление будет иметь такой вид:

type

cptr=^zap;

zap=record

inf:integer;

link:cptr;

end;

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

Работа с очередью

Для создания очереди и работы с ней необходимо иметь как минимум два указателя:

- на начало очереди (возьмем идентификатор begp)

- на конец очереди (возьмем идентификатор тор)

Кроме того, для освобождения памяти удаляемых элементов требуется дополнительный временный указатель (возьмем идентификатор Р).

Создание очереди

1. Исходное состояние:

begp:=nil;

endp:=nil;

2. Выделение памяти под первый элемент очереди:

new(p);

3. Занесение информации в первый элемент очереди:

p^.inf:=x;

p^.link:=nil

4. Установка указателей begp и endp на созданный первый элемент:

begp:=p;

endp:=p;

Добавление элемента очереди

1. Исходное состояние.

2. Выделение памяти под новый элемент и занесение в него информации:

new(p);

p^.inf:=x;

p^.link:=nil;

3. Установка связи между последним элементом очереди и новым, а также перемещение указателя конца очереди endp на новый элемент:

endp^.link:=p;

endp:=p;

Удаление элемента очереди

1. Исходное состояние.

2. Извлечение информации из удаляемого элемента в переменную x и установка на него вспомогательного указателя Р:

x:=begp^.inf;

p:=begp;

3. Перестановка указателя начала очереди begp на следующий элемент, используя значение поля p^.link, которое хранится в первом элементе. После этого освобождается память начального элемента очереди, используя дополнительный указатель Р:

begp:=p^.link;

dispose(p);