На этом шаге мы рассмотрим структуру ортогональных списков.
До сих пор мы рассматривали линейные структуры динамических переменных. Добавление к динамической переменной двух и более полей указателей создает возможность построения нелинейных структур. Дело в том, что при решении практических задач обычно не удается обойтись только линейными динамическими структурами данных (список, очередь, стек, дек и т.д.): приходится создавать структуры данных, максимально отражающие существо выполняемой исполнителем задачи.
Мы рассмотрим только простейшие нелинейные динамические структуры, которые называются ортогональными списочными структурами (ортогональными списками, многосвязными списками).
Более точно, ортогональными списками называется списочная структура данных, в которой узлы могут принадлежать более чем одному списку и содержать более одного указателя [1, с.241].
На рисунке изображено графическое представление ортогональных списков:
Рис.1. "Гирлянды" и "висюльки"
Горизонтальный линейный однонаправленный список с заглавным звеном мы будем называть гирляндой. Каждое звено этого списка содержит три поля, причем, если указатель P указывает на звено гирлянды, то:
- поле (*P).Key является информационным полем узла гирлянды;
- поле (*P).Next содержит указатель на следующее звено гирлянды;
- поле (*P).Trail содержит указатель на линейный однонаправленный список с заглавным звеном, который называется висюлькой (английское слово Trail переводится как "тащиться, свисать, волочиться").
Звено каждой висюльки содержит два поля: Id и Next, причем, если указатель Q указывает на элемент висюльки, то:
- поле (*Q).Id является информационным полем звена висюльки;
- поле (*Q).Next указывает на следующее звено данной висюльки.
(1)Tenenbaum A., Augenstein M. Data Structures Using Pascal. Englewood Cliffs. - N.Y.: Prentice-Hall, Inc. 1981.
На следующем шаге мы приведем реализвцию простейших операций над ортогональными списками.
