Списки общего вида

Рис 16. Узел списка общего вида.

Такое определение рекурсивно, и список может содержать в качестве элемента самого себя. Рассмотрим списочную структуру:

L=(a:N,b,c:(d:N),e:L)

N=(f, g:(h:L, j:N))

Запись вида x :Yозначает, что узел x содержит подсписок Y. Узлы списка перечисляются через запятую. Графически списочная структура изображена на рис 17.

Такое представление несёт с собой одну проблему. На рис. 17 видно, что на узел f имеется три ссылки. В действительности, это ссылки на список N, в котором узел f является начальным. Если потребуется удалить узел f из списка N, то придется регулярным образом обходить всю списочную структуру с целью обнаружения всех ссылок на узел f, что, конечно, неприемлемо.

Если потребовать, чтобы каждый список имел голову, то проблема исчезает - на каждый узел, не являющийся головой имеется одна ссылка. Рассмотренная выше структура примет вид как на рис 18.

Рис 18. Список общего вида с головами списков.

Списки, составляющие списочную структуру общего вида могут иметь любую организацию из рассмотренных выше – односвязные или двусвязные, кольцевые или не кольцевые, с головой или без, в зависимости от операций, которые необходимо выполнять над структурой.

Пример. Топологическая сортировка.

Топологической называют сортировку на множестве элементов в случае, когда на множестве элементов задано отношение частичного порядка. Порядок является частичным, если отношение предшествования задано не для всех пар элементов. Множество целых чисел является полностью упорядоченным, так как для любой пары целых чисел a,b определено отношение ‘>’ (больше) или ‘<’ (меньше).

В качестве примера ситуации, когда порядок является частичным, рассмотрим производство следующих работ:

1. сделать болт

2. сделать гайку

3. навернуть гайку на болт

Ясно, что работы 1 и 2 должны предшествовать работе 3. Запишем этот факт как 1í2 (читается: 1 предшествует 2) и 2í3. Работы 1 и 2 не связаны между собой отношением предшествования.

Другим примером, в котором имеется частичный порядок, является учебный план подготовки специалистов в ВУЗе. Курс "Основы алгоритмизации и языки программирования" должен пред­шествовать курсу "Структуры и алгоритмы обработки данных", но ни тот, ни другой никак не связаны с курсом "История государ­ственного управления в России".

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

Топологическая сортировка на основе имеющегося отношения частичного поряд­ка строит линейную последовательность элементов сортируемого мно­жества, в которой для любой пары X_i, X_j не может быть выполнено условие X_i í X_j при i>j. Иными словами, для пары a í b, a не может появиться в выходной последова­тель­ности позже b.

Исходными данными для работы алгоритма является массив пар элементов first, second, таких, что first í second.Одна такая пара представляется структурой:

struct PAIR{

char *first;

char *second;

};

Для реализации алгоритма используются списочная структура, содержащая узлы двух типов: узлы основного списка (MAINS) и узлы подсписков (POD). Основной список двусвязный, с головой, циклический. Подсписок – односвяз­ный, без головы и нецик­ли­ческий.

struct MAINS{ // cтруктура узла основного списка