Нелинейный трехсвязный список
Несложно представить трехсвязный список, содержащий информацию об абитуриентах, в котором две структурных ссылки объединяют узлы так же, как на рисунках 6.10 и 6.11, а третья ссылка Р3 связывает те элементы (в алфавитном порядке), которые относятся к абитуриентам, обладающим правами преимущественного поступления в ВУЗ. Логическая структура такого списка показана на рисунке 6.12. На этом рисунке штриховыми линиями показаны структурные ссылки, объединяющие элементы с помощью поля Р3. Назовем этот цепной список Р3-списком.
В цепном списке, организованном с помощью структурного указателя Р3, очевидно, будет содержать не все элементы. В нашем примере (см. рисунок 6.12) в Р3-списке содержится три элемента, которые упорядочены ссылкой Р3 следующим образом:
Бойко Фокин Яшина
Указателем Р3-списка является внешний указатель List3. Этот пример показывает, что необязательно, чтобы каждый элемент общей списковой структуры непременно входил во все цепные списки одновременно.
Рисунок 6.12 Логическая структура нелинейного трехсвязного списка
Определение плекса и его общие признаки
В общем случае возможно создание многосвязного списка, каждый элемент которого может содержать К полей (К = 2, 3, 4 …) структурных указателей. Как показывают логические структуры нелинейных связных списков, изображенные на рисунках 6.10 6.12, многосвязный список как бы «прошит» в разных направлениях многими указателями. Поэтому такие списки называют прошитыми списками или плексами (plexus сплетение, переплетение).
Сформулируем общие признаки плексов:
все элементы такой структуры содержат одинаковое количество полей структурных указателей, число которых К степень связности является важной характеристикой структуры;
не обязательно, чтобы каждый элемент общей структуры входил во все К цепных списков одновременно;
каждый отдельный список, организованный с помощью одной и той же ссылки, поле для которой имеется во всех элементах, является односвязным цепным, а значит и линейным списком, если не принимать во внимание другие связи;
на каждый элемент может ссылаться произвольное число других элементов структуры, и от любого элемента к другим элементам может быть направлено произвольное число указателей, но в обоих случаях число таких указателей-ссылок не превышает К;
вся структура в целом не линейна, поскольку, если учитывать все связки, для каждого элемента не может быть определен единственный элемент-предшественник и единственный элемент-последователь.
Иерархическая списковая структура. Сетевая структура
Многосвязный нелинейный список может быть организован как иерархическая списковая структура (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) или сетевая структура. Она характеризуется следующими свойствами:
различные элементы сети могут иметь различные форматы, т.е. состоять из разного количества полей;
каждый элемент сетевой структуры содержит произвольное количество структурных ссылок на другие элементы;
на любой элемент может ссылаться произвольное число других элементов;
каждая связка в сети может иметь не только направление, но и вес.
Логически сеть эквивалентна взвешенному ориентированному графу общего вида. Поэтому названия «сетевая структура» или «сеть» обычно заменяют термином «графовая структура», и вместо названий «элемент» и «структурная ссылка» используют названия «узел» и «ребро».