Иерархические и ассоциативные списки.

Используются тогда, когда объединяют информационные записи в списки, тем самым образуя группу записи с определенным внутренним порядком.

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

Такие списки принято называть иерархическими.

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

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

 

Ассоциативные списки.

Часто одни и те же объекты представляют интерес с различных точек зрения. И возникает потребность включать информацию об этих объектах в различные списки.

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

Каждое звено имеет для каждого ассоциативного списка свою ссылку.

 

Стеки.

Стеком называется динамическая структура данных, добавление компоненты в которую и исключение компоненты из которой производится из одного конца, называемого вершиной стека. Стек работает по принципу LIFO (Last-In, First-Out) поступивший последним, обслуживается первым.

 

Обычно над стеками выполняется три операции:

-начальное формирование стека (запись первой компоненты);

-добавление компоненты в стек;

-выборка компоненты (удаление).

 

Очереди.

Очередью называется динамическая структура данных, добавление компоненты в которую производится в один конец, а выборка осуществляется с другого конца. Очередь работает по принципу FIFO (First-In, First-Out) поступивший первым, обслуживается первым.

 

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

 

Описание компоненты очереди и переменных типа указатель дадим следующим образом:

 

Type

PComp=^Comp;

Comp=record

D:T;

pNext:PComp

end;

Var

pBegin, pEnd, pAux: PComp;

где pBegin - указатель начала очереди, pEnd - указатель конца очереди, pAux - вспомогательный указатель.

Тип Т определяет тип данных компоненты очереди.

 

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

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

 

Деревья - как структуры данных. Двоичные деревья. Методы их просмотра.

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

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

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

Частным случаем деревьев являются двоичные деревья.

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

Над двоичным деревом определена операция просмотра его узлов. Эту операцию можно производить рекурсивно.