Списки
Связанные динамические данные
Основные определения
Линейные списки - это данные динамической структуры, которые представляют собой совокупность линейно связанных однородных элементов и для которых разрешены следующие действия:
добавление элемента в начало (голову) списка;
вставка элемента между двумя любыми другими элементами списка;
удаление любого, как крайнего, так и среднего, элемента списка.
Кольцевые списки - это такие же данные, как и линейные списки, но имеющие дополнительную связь между последним и первым элементом списка.
Очередь - частный случай линейного односвязного списка, для которого разрешены только два действия: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.
Стек - частный случай линейного односвязного списка, для которого разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной (головой) стека.
Деревья - это динамические данные иерархической структуры произвольной конфигурации. Элементы дерева называются вершинами (узлами).
Пирамидой (упорядоченным деревом) называется дерево, в котором значения вершин (узлов) всегда возрастает или убывает при переходе на следующий уровень.
Организация взаимосвязей в связанных динамических данных
Связанные динамические данные характеризуются высокой гибкостью создания структур данных различной конфигурации. Это достигается благодаря возможности выделять и освобождать память под эти элементы в любой момент времени работы программы и возможности установить связь между любыми двумя элементами с помощью указателей.
Для организации связей между элементами динамической структуры данных требуется, чтобы каждый элемент содержал креме информационных значений как минимум один указатель. Отсюда следует, что в качестве элементов таких структур необходимо использовать записи, которые могут объединять в единое целое разнородные элементы.
В простейшем случае элемент динамической структуры данных должен состоять из двух полей: информационного и указательного.
Объявление будет иметь такой вид:
type
cptr=^zap;
zap=record
inf:integer;
link:cptr;
end;
Тип указателя на элемент динамической структуры данных может и должен быть описан перед описанием типа этого элемента.
Р абота с очередью
Для создания очереди и работы с ней необходимо иметь как минимум два указателя:
- на начало очереди (возьмем идентификатор begp)
- на конец очереди (возьмем идентификатор тор)
Кроме того, для освобождения памяти удаляемых элементов требуется дополнительный временный указатель (возьмем идентификатор Р).
Создание очереди
Исходное состояние:
begp:=nil;
endp:=nil;
Выделение памяти под первый элемент очереди:
new(p);
Занесение информации в первый элемент очереди:
p^.inf:=x;
p^.link:=nil
Установка указателей begp и endp на созданный первый элемент:
begp:=p;
endp:=p;
Добавление элемента очереди
Исходное состояние.
Выделение памяти под новый элемент и занесение в него информации:
new(p);
p^.inf:=x;
p^.link:=nil;
Установка связи между последним элементом очереди и новым, а также перемещение указателя конца очереди endp на новый элемент:
endp^.link:=p;
endp:=p;
Удаление элемента очереди
Исходное состояние.
Извлечение информации из удаляемого элемента в переменную x и установка на него вспомогательного указателя Р:
x:=begp^.inf;
p:=begp;
Перестановка указателя начала очереди begp на следующий элемент, используя значение поля p^.link, которое хранится в первом элементе. После этого освобождается память начального элемента очереди, используя дополнительный указатель Р:
begp:=p^.link;
dispose(p);