Фрагмент теории

Варкалось. Хливкие шорьки

Пырялись по наве,

И хлюкотали зелюки,

Как мамзюки в мове.

Л.Кэррол, Бармаглот

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

На рисунке, приведенном ниже, приведено графическое представ­ление ортогональных списков:

Горизонтальный линейный однонаправленный список с заглавным звеном мы будем называть гирляндой. Каждое звено этого списка содержит три поля, причем, если указатель P указывает на звено гирлянды, то:

q поле (*P).Key является информационным полем узла гирлянды;

q поле (*P).Next содержит указатель на следующее звено гирлянды;

q поле (*P).Trail содержит указатель на линейный однонаправленный список с заглавным звеном, который называется висюлькой (английское слово trail переводится как "тащиться, свисать, волочиться").

Звено каждой висюльки содержит два поля: Id и Next, причем, если указатель Q указывает на элемент висюльки, то:

q поле (*Q).Id является информационным полем звена висюльки;

q поле (*Q).Next указывает на следующее звено данной висюльки.

Опишем типы данных:

struct nodeGir //Описание типа звена гирлянды

{

int elem; // Информационное поле звена гирлянды.

nodeVis *vniz; // Указатель на звено висюльки.

nodeGir *sled; // Указатель на звено гирлянды.

};

struct nodeVis //Описание типа звена висюльки

{

int elem; // Информационное поле звена висюльки.

nodeVis *vniz; // Указатель на звено висюльки.

};