Списочные структуры

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

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

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

Рис. 6.10. Списочная структура данных: линейная (а), двухсвязная (б), циклическая (в)

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

1. между узлами имеет место отношение типа «исходный - порожденный».

2. Есть только один узел, не имеющий исходного – корень.

3. Все узлы, за исключением корня, имеют только один исходный.

4. Ни один порожденный узел не может стать исходным.

На рис. 6.11 представлено две формы моделирования иерархических отношений: иерархическое дерево, отражающее отношение соподчиненности (а) и структура данных, позволяющая отразить эти отношения в памяти компьютера (б).

Узел иерархической структуры данных в данном случае содержит три поля: одно для размещения собственно данных и два для указателей (на подчиненный и на соседний узел).

В информатике существует ряд разновидностей деревьев.

Рис. 6.11. Древовидная структура: а) иерархическая структура, б) древовидная структура данных