Иерархическая списковая структура. Сетевая структура

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

Пусть на факультете высшего учебного заведения имеется 5 групп. Кроме того, каждая группа состоит из множества студентов, причем группы различаются количеством студентов. Для представления информации о группах и студентах можно предложить следующую информационную модель:

- формируется список (назовем его Main-списком), элементы которого содержат информацию о группах: номер группы, число студентов, староста и т. д.,

- каждый элемент Main-списка «дает начало» дополнительному списку (Sub-списку), состоящему из элементов, каждый из которых содержит информацию об отдельном студенте группы.

Очевидно, эта модель предполагает существование такого количества Sub-списков, которое равно числу групп. Каждый Sub-список как бы подчиняется Main-списку.

Для представления описанной модели в памяти можно использовать следующую структуру. Пусть указатель Faculty адресует начало главного цепного списка, каждый элемент которого, кроме информации о группах факультета, содержит два указателя Main и Sub. Указатель Main связывает элементы главного списка, а указатель Sub каждого элемента главного списка ссылается на начало другого списка, который содержит информацию о студентах соответствующей группы. Такая структура показана на рисунке 6.13.

Рисунок 6.13 - Двухуровневый иерархический связный список

Как видно из рисунка 6.13, каждый список, адресуемый указателем Sub как бы «подчиняется» элементу главного списка; такой список, «ответвляющийся» от главного списка, называется подсписком (sublist). Очевидно, в каждом подсписке может располагаться произвольное число элементов, в общем случае не равное для всех подсписков.

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

Нетрудно представить себе увеличение количества уровней, причем как со стороны верхнего уровня, так и со стороны нижнего уровня. Например, для информационной системы ВУЗа целесообразно создать список, объединяющий информацию всех факультетов; тогда «над» Main‑списком появится новый список, который становится главным, а вся структура в целом будет иметь три уровня. Если в дополнение к этому пользователя интересует информация о членах семьи каждого студента, то каждый элемент нашего Sub-списка должен стать началом подсписка, содержащего в своих элементах данные о родственниках соответствующего студента. Тогда структура станет четырехуровневой.

В общем случае структура, элементы которой размещены на двух или более уровнях иерархии, называется многоуровневой структурой (multilevel structure). К классу таких структур относятся, в частности, многоуровневая запись или дерево.

Нетрудно представить себе такую иерархическую структуру, в которой на верхнем уровне «расположен» многосвязный нелинейный список, а элементами подсписков являются деревья или векторы. Поскольку общая структура, образованная таким образом, будет получена путем композиции разных структур, она называется комбинированной структурой (combined structure).

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

- различные элементы сети могут иметь различные форматы, т.е. состоять из разного количества полей;

- каждый элемент сетевой структуры содержит произвольное количество структурных ссылок на другие элементы;

- на любой элемент может ссылаться произвольное число других элементов;

- каждая связка в сети может иметь не только направление, но и вес.

Логически сеть эквивалентна взвешенному ориентированному графу общего вида. Поэтому названия «сетевая структура» или «сеть» обычно заменяют термином «графовая структура», и вместо названий «элемент» и «структурная ссылка» используют названия «узел» и «ребро».