Алгоритмы и структуры данныхНовая версия для Оберона cdмосква, 2010Никлаус ВиртПеревод с английского под редакцией
 Скачать 2.67 Mb.
|
|
4.3. Линейные списки 4.3.1. Основные операции Простейший способ связать набор элементов – выстроить их в простой список (list) или очередь. Ибо в этом случае каждому элементу нужен единственный ука% затель на элемент, следующий за ним. Пусть типы Node (узел) и NodeDesc (desc от descriptor) определены, как пока% зано ниже. Каждая переменная типа NodeDesc содержит три компоненты, а имен% но идентифицирующий ключ key , указатель на следующий элемент next и, воз% можно, другую информацию. Для дальнейшего нам понадобятся только key и next : Линейные списки Динамические структуры данных 176 TYPE Node = POINTER TO NodeDesc; TYPE NodeDesc = RECORD key: INTEGER; next: Node; data: ... END; VAR p, q: Node (* *) На рис. 4.6 показан список узлов, причем указатель на его первый элемент хра% нится в переменной p . Вероятно, простейшая операция со списком, показанным на рис. 4.6, – это вставка элемента вголову списка. Сначала размещается элемент типа NodeDesc , при этом ссылка (указатель) на него записывается во вспомога% тельную переменную, скажем q . Затем простые присваивания указателей завер% шают операцию. Отметим, что порядок этих трех операторов менять нельзя. NEW(q); q.next := p; p := q Рис. 4.6. Пример связного списка Операция вставки элемента в голову списка сразу подсказывает, как такой список можно создать: начиная с пустого списка, нужно повторно добавлять в го% лову новые элементы. Процесс создания списка показан в следующем программ% ном фрагменте; здесь n – число элементов, которые нужно связать в список: p := NIL; (* # *) WHILE n > 0 DO NEW(q); q.next := p; p := q; q.key := n; DEC(n) END Это простейший способ создания списка. Однако здесь получается, что эле% менты стоят в обратном порядке по сравнению с порядком их добавления в спи% сок. В некоторых задачах это нежелательлно, и поэтому новые элементы должны присоединяться в конце, а не в начале списка. Хотя конец списка легко найти про% стым просмотром, такой наивный подход приводит к вычислительным затратам, которых можно избежать, используя второй указатель, скажем q , который всегда указывает на последний элемент. Этот метод применяется, например, в програм% ме CrossRef (раздел 4.4.3), где создаются перекрестные ссылки для некоторого текста. Его недостаток – в том, что первый элемент должен вставляться по%друго% му, чем все остальные. 177 Явное наличие указателей сильно упрощает некоторые операции, которые в п% ротивном случае оказываются громоздкими. Среди элементарных операций со списками – вставка и удаление элементов (частичное изменение списка), а также, разумеется, проход по списку. Мы сначала рассмотрим вставку (insertion) в список. Предположим, что элемент, на который ссылается указатель q , нужно вставить в список после элемента, на который ссылается указатель p . Нужные присваива% ния указателей выражаются следующим образом, а их эффект показан на рис. 4.7. q.next := p.next; p.next := q Рис. 4.7. Вставка после p^ Если нужна вставка перед указанным элементом p^ , а не после него, то, каза% лось бы, возникает затруднение, так как в однонаправленной цепочке ссылок нет никакого пути от элемента к его предшественникам. Однако здесь может выру% чить простой прием. Он проиллюстрирован на рис. 4.8. Предполагается, что ключ нового элемента равен 8. NEW(q); q^ := p^; p.key := k; p.next := q Рис. 4.8. Вставка перед p^ Линейные списки Динамические структуры данных 178 Очевидно, трюк состоит в том, чтобы вставить новую компоненту после p^ , а потом произвести обмен значениями между новым элементом и p^ Теперь рассмотрим удаление из списка (list deletion). Нетрудно удалить эле% мент, стоящий сразу за p^ . Эта операция показана здесь вместе с повторной встав% кой удаленного элемента в начало другого списка (обозначенного переменной q ). Ситуация показана на рис. 4.9, из которого видно, что имеет место циклический обмен значений трех указателей. r := p.next; p.next := r.next; r.next := q; q := r Рис. 4.9. Удаление и повторная вставка Удаление самого элемента, на который указывает ссылка (а не следующего), труднее, так как здесь возникает та же проблема, что и со вставкой: невозможно просто так перейти назад от элемента к предшествующему. Но удаление следую% щего элемента после копирования его значения вперед – довольно очевидное и простое решение. Его можно применить, когда за p^ стоит некоторый элемент, то есть p^ не является последним элементом в списке. Однако необходимо гаранти% ровать, что нет других переменных, ссылающихся на удаляемый элемент. Обратимся теперь к фундаментальной операции прохода по списку. Предполо% жим, что для каждого элемента списка, у которого первый элемент p^ , нужно вы% полнить некоторую операцию P(x) . Эту задачу можно выполнить так: WHILE , p, DO P; END Детали этой операции выглядят следующим образом: WHILE p # NIL DO P(p); p := p.next END 179 Из определения оператора while и структуры связей следует, что P применяет% ся ко всем элементам списка и ни к каким другим. Очень часто используемая операция со списками – поиск в списке элемента с заданным ключом x . В отличие от массивов, поиск здесь должен быть чисто по% следовательным. Поиск прекращается, либо когда элемент найден, либо когда до% стигнут конец списка. Это выражается логической конъюнкцией двух термов. Снова предположим, что сначала p указывает на голову списка. WHILE (p # NIL) & (p.key # x) DO p := p.next END Равенство p = NIL означает, что записи p^ не существует, так что выражение p.key # x не определено. Поэтому порядок двух термов важен. 4.3.2. Упорядоченные списки и перестройка списков Представленный алгоритм поиска в линейном списке очень похож на поиск в мас% сиве или последовательности. На самом деле последовательность – это в точности линейный список, для которого способ связи с последующим элементом скрыт. Поскольку основные операции для последовательностей не допускают вставку новых элементов (разве что в конце) или удаления (кроме удаления всех элемен% тов), выбор представления отдается полностью на откуп проектировщику, и он может выбрать последовательное размещение в памяти, располагая последо% вательные компоненты в непрерывных областях памяти. Линейные списки с яв% ными указателями дают больше гибкости, и поэтому их следует использовать, когда в такой гибкости есть необходимость. Чтобы показать различные приемы, рассмотрим в качестве примера задачу, которая будет возникать на протяжении этой главы. Задача состоит в том, чтобы прочесть текст, определить все слова в нем и подсчитать частоту их появления в тексте. То есть построить алфавитный частотный словарь. Очевидное решение – строить список слов, обнаруживаемых в тексте. Список просматривается для каждого слова. Если слово в нем найдено, соответствующий счетчик увеличивается; в противном случае слово добавляется в список. Для про% стоты будем называть этот процесс просто поиском, хотя на самом деле здесь мо% жет иметь место и вставка. Чтобы сосредоточиться на существенных для нас здесь аспектах работы со списками, предположим, что слова из обрабатываемого текста уже извлечены и закодированы целыми числами, из которых и состоит входная последовательность. Ниже дана самая прямолинейная формулировка процедуры поиска (процеду% ра search) . Переменная root ссылается на голову списка, в который новые слова вставляются по мере необходимости. Полная программа представлена ниже; в нее включена процедура печати построенного списка в виде таблицы. Печать табли% цы – пример операции, в которой некоторая операция выполняется ровно один раз для каждого элемента списка. Линейные списки Динамические структуры данных 180 TYPE Word = POINTER TO (* ADruS432_List *) RECORD key, count: INTEGER; next: Word END; PROCEDURE search (x: INTEGER; VAR root: Word); VAR w: Word; BEGIN w := root; WHILE (w # NIL) & (w.key # x) DO w := w.next END; (* (w = NIL) OR (w.key = x) *) IF w = NIL THEN (* *) w := root; NEW(root); root.key := x; root.count := 1; root.next := w ELSE INC(w.count) END END search; PROCEDURE PrintList (w: Word); (* # W*) BEGIN WHILE w # NIL DO Texts.WriteInt(W, w.key, 8); Texts.WriteInt(W, w.count, 8); Texts.WriteLn(W); w := w.next END END PrintList; Алгоритм линейного поиска здесь похож на процедуру поиска для массива, так что можно вспомнить простой прием для упрощения условия завершения цикла – использование барьера. Этот прием можно применить и при поиске по списку; тогда барьер представляется вспомогательным элементом в конце списка. Новая процедура приведена ниже. Мы должны предположить, что добавлена глобаль% ная переменная sentinel и что инициализация root := NIL заменена операторами NEW(sentinel); root := sentinel порождающими элемент, который будет использоваться в качестве барьера. PROCEDURE search (x: INTEGER; VAR root: Word); (* ADruS432_List2 *) VAR w: Word; BEGIN w := root; sentinel.key := x; WHILE w.key # x DO w := w.next END; IF w = sentinel THEN (* *) w := root; NEW(root); root.key := x; root.count := 1; root.next := w ELSE INC(w.count) END END search 181 Очевидно, что мощь и гибкость связного списка в данном примере использу% ются плохо и что последовательный просмотр всего списка приемлем, только если число элементов невелико. Однако легко сделать простое улучшение: поиск в упо рядоченном списке. Если список упорядочен (скажем, по возрастанию ключей), то поиск может быть прекращен, как только встретился первый ключ, больший но% вого. Упорядочение списка достигается вставкой новых элементов в надлежащем месте, а не в начале списка. При этом упорядоченность получается практически бесплатно. Это достигается благодаря легкости вставки элемента в связный спи% сок, то есть благодаря полному использованию его гибкости. Такой возможности нет ни при работе с массивами, ни с последовательностями. (Однако заметим, что даже упорядоченные списки не дают возможности реализовать аналог двоичного поиска для массивов.) Рис. 4.10. Вставка в упорядоченный список Поиск в упорядоченном списке дает типичный пример ситуации, когда новый элемент нужно вставить перед заданным, в данном случае перед первым элемен% том, чей ключ оказался слишком большим. Однако мы применим здесь новый прием, который отличается от показанного ранее. Вместо копирования значений вдоль списка проходят два указателя; w2 отстает на шаг от w1 и поэтому указыва% ет на правильное место вставки, когда w1 обнаруживает слишком большой ключ. Общий шаг вставки показан на рис. 4.10. Указатель на новый элемент ( w3 ) дол% жен быть присвоен полю w2.next , за исключением того случая, когда список еще пуст. Из соображений простоты и эффективности нежелательно отслеживать этот особый случай с помощью условного оператора. Единственный способ избе% жать этого – ввести фиктивный элемент в начале списка. Соответственно, опера% тор инициализации root := NIL заменяется на NEW(root); root.next := NIL Рассматривая рис. 4.10, можно записать условие перехода к следующему эле% менту; оно состоит из двух термов, а именно (w1 # NIL) & (w1.key < x) Линейные списки Динамические структуры данных 182 Получается такая процедура поиска: PROCEDURE search (x: INTEGER; VAR root: Word); (* ADruS432_List3 *) VAR w1, w2, w3: Word; BEGIN (*w2 # NIL*) w2 := root; w1 := w2.next; WHILE (w1 # NIL) & (w1.key < x) DO w2 := w1; w1 := w2.next END; (* (w1 = NIL) OR (w1.key >= x) *) IF (w1 = NIL) OR (w1.key > x) THEN (* *) NEW(w3); w2.next := w3; w3.key := x; w3.count := 1; w3.next := w1 ELSE INC(w1.count) END END search Чтобы ускорить поиск, охрану оператора while опять можно упростить, ис% пользуя барьер. Тогда с самого начала нужен как фиктивный элемент в начале списка, так и барьер в конце. Теперь пора спросить, какой выигрыш нам даст поиск в упорядоченном спис% ке. Помня о том, что дополнительные усложнения оказались малы, не стоит ожи% дать чуда. Предположим, что все слова в тексте встречаются с одинаковой частотой. В этом случае выигрыш от лексикографического упорядочения – после того как все слова включены в список – тоже нулевой, так как положение слова не играет роли, если только полное число всех операций поиска велико и если все слова встречаются с одинаковой частотой. Однако выигрыш имеет место при вставке нового слова. Ведь тогда вместо прохода по всему списку в среднем просматри% вается только половина списка. Поэтому вставка в упорядоченный список оправ% дывает себя, только если в обрабатываемом тексте число различных слов велико по сравнению с частотами их появления. И поэтому предыдущие примеры про% грамм хороши только как упражнения в программировании, но не для практиче% ского использования. Организацию данных в связный список можно рекомендовать, когда число элементов относительно мало (< 50), меняется и, более того, когда нет информа% ции о частоте обращения к ним. Типичный пример – таблица имен в компилято% рах языков программирования. Каждое объявление добавляет новое имя, которое удаляется из списка после выхода из его области видимости. Использование про% стых связных списков уместно в приложениях с относительно короткими про% граммами. Но даже в этом случае можно добиться значительного ускорения дос% тупа к данным с помощью очень простого приема, который упоминается здесь прежде всего потому, что он представляет собой удачную иллюстрацию гибкости связных списков. 183 Типичное свойство программ состоит в том, что появления одного и того же идентификатора очень часто группируются таким образом, что за одним его появ% лением то же слово часто появляется еще один или несколько раз. Это обстоя% тельство наводит на мысль реорганизовывать список после каждой операции по% иска перемещением найденного слова в голову списка, чтобы уменьшить длину пути поиска, когда это слово нужно будет снова найти. Такой способ доступа на% зывают поиском с переупорядочением списка, или, несколько помпезно, поиском в самоорганизующемся списке. Представляя соответствующий алгоритм в виде процедуры, воспользуемся уже приобретенным опытом и с самого начала введем барьер. На самом деле наличие барьера не только ускоряет поиск, но в данном слу% чае еще и упрощает программу. В исходном состоянии список не должен быть пуст, но уже должен содержать элемент%барьер. Операторы инициализации таковы: NEW(sentinel); root := sentinel Заметим, что главное отличие нового алгоритма от простого поиска в списке – это действия по переупорядочиванию при обнаружении элемента. В этом случае он удаляется со старой позиции и вставляется в голову списка. Такое удаление снова требует пары следующих друг за другом указателей, чтобы помнить поло% жение предшественника w2 найденного элемента w1 . Это, в свою очередь, требует особой обработки первого элемента (то есть пустого списка). Чтобы стало понят% ней, какие здесь нужны манипуляции с указателями, на рис. 4.11 показаны два указателя в тот момент, когда w1 был идентифицирован как искомый элемент. Конфигурация после корректного переупорядочения показана на рис. 4.12 PROCEDURE search (x: INTEGER; VAR root: Word); (* ADruS432_List4 *) VAR w1, w2: Word; BEGIN w1 := root; sentinel.key := x; IF w1 = sentinel THEN (* *) NEW(root); root.key := x; root.count := 1; root.next := sentinel ELSIF w1.key = x THEN INC(w1.count) ELSE (**) REPEAT w2 := w1; w1 := w2.next UNTIL w1.key = x; IF w1 = sentinel THEN (* *) w2 := root; NEW(root); root.key := x; root.count := 1; root.next := w2 ELSE (* v, *) INC(w1.count); w2.next := w1.next; w1.next := root; root := w1 END END END search Выигрыш в этом методе поиска сильно зависит от степени группировки слов во входных данных. При фиксированной степени группировки выигрыш будет Линейные списки Динамические структуры данных 184 тем больше, чем длинней список. Чтобы получить представление об ожидаемом выигрыше, были выполнены эмпирические измерения с использованием выше% приведенной программы для одного короткого и одного относительно длинного текста, и затем сравнивались методы поиска в упорядоченном списке и поиск с переупорядочиванием. Данные измерений собраны в табл. 4.2. К сожалению, наибольший выигрыш достигается в том случае, когда данные все равно нужно организовывать по%другому. Мы вернемся к этому примеру в разделе 4.4. Таблица 4.2. Таблица 4.2. Таблица 4.2. Таблица 4.2. Таблица 4.2. Сравнение методов поиска в списке Тест 1 Тест 1 Тест 1 Тест 1 Тест 1 Тест 2 Тест 2 Тест 2 Тест 2 Тест 2 Число разных ключей 53 582 Число появлений ключей 315 14341 Время поиска с упорядочением 6207 3200622 Время поиска с перегруппировкой 4529 681584 Фактор ускорения 1.37 4.70 Рис. 4.12. Список после переупорядочения Рис. 4.11. Список до переупорядочения 185 4.3.3. Применение: топологическая сортировка Хороший пример использования гибкой динамической структуры данных – то пологическая сортировка. Это сортировка элементов, для которых определен частичный порядок, то есть отношение порядка задано для некоторых, но не для всех пар элементов. Вот примеры частичного упорядочения: 1. В словаре одни слова могут быть определены через другие. Если слово v используется в определении слова w , то будем писать v 〈 w . Топологическая сортировка слов означает такую их расстановку, чтобы каждое слово сто% яло после всех тех слов, которые нужны для его определения. 2. Задача (например, инженерный проект) разбита на подзадачи. Обычно одни подзадачи должны быть выполнены до выполнения других. Если подзадача v должна быть выполнена до подзадачи w , то мы пишем v 〈 w . Топологическая сортировка означает такую их расстановку, чтобы при начале выполнения каждой подзадачи все нужные подзадачи были бы уже выполнены. 3. В программе университетского обучения некоторые курсы предполагают владение материалом других курсов, которые поэтому должны изучаться раньше первых. Если курс v должен быть прослушан до курса w , то мы пи% шем v 〈 w . Топологическая сортировка означает расстановку курсов в таком порядке, чтобы все курсы, которые нужно прослушать до некоторого курса, всегда стояли в списке до него. 4. В программе некоторые процедуры могут содержать вызовы других процедур. Если процедура v вызывается в процедуре w , то пишем v 〈 w . Топологическая сортировка подразумевает такую расстановку объявлений процедур, чтобы никакая процедура не вызывала еще не объявленные процедуры. В общем случае частичный порядок на множестве S – это некоторое отношение между элементами S . Будем обозначать его символом 〈 (читается «предшест% вует») и требовать выполнения следующих трех свойств (аксиом) для любых раз% ных элементов x , y , z из S : 1) если x 〈 y и y 〈 z , то x 〈 z (транзитивность); 2) если x 〈 y , то неверно, что y 〈 x (антисимметрия); 3) неверно, что z 〈 z (нерефлексивность). По очевидным причинам будем предполагать, что множества S , к которым бу% дет применяться топологическая сортировка, конечны. Поэтому частичная сор% тировка может быть проиллюстрирована диаграммой или графом, в котором вер% шины обозначают элементы S , а направленные ребра представляют отношения упорядоченности. Пример показан на рис. 4.13. Задача топологической сортировки – погрузить отношение частичного поряд% ка в линейный порядок. Графически это подразумевает расположение вершин графа в линию так, чтобы все стрелки указывали вправо, как показано на рис. 4.14. Свойства (1) и (2) частичного упорядочения гарантируют, что граф не содержит петель. Это в точности то условие, при котором погружение в линейный порядок возможно. Линейные списки Динамические структуры данных 186 Как приступить к поиску одного из возможных линейных упорядочений? Ре% цепт довольно прост. Начнем с выбора любого элемента, у которого нет пред% шественников (должен существовать хотя бы один такой элемент, иначе в графе будет петля). Этот элемент помещается в начало будущего списка и удаляется из множества S . Остаток множества по%прежнему частично упорядочен, и тот же ал% горитм может применяться снова – до тех пор, пока множество не станет пустым. Чтобы описать алгоритм более строго, нужно выбрать структуру данных и представление для S и для его частичного порядка. Выбор такого представления определяется операциями, которые нужно с ним производить, в частности речь идет об операции выбора элементов, не имеющих предшественников. Поэтому каждый элемент должен представляться тремя характеристиками: своим идентифи% цирующим ключом, множеством элементов%«последователей» и числом элементов% «предшественников». Так как число n элементов в S не фиксировано заранее, множество удобно организовать как связный список. Следовательно, дополни% тельной компонентой описания каждого элемента будет указатель на следующий элемент списка. Будем считать, что ключи являются целыми (но не обязательно идущими подряд от 1 до n ). Аналогично, множество последователей каждого эле% мента удобно представить связным списком. Каждый элемент списка последова% телей описывается своим ключом и указателем на следующий элемент в этом списке. Если дескрипторы главного списка, в котором каждый элемент множества S встречается в точности один раз, назвать ведущими ( leader ), а дескрипторы эле% Рис. 4.13. Частично упорядоченное множество Рис. 4.14. Расположение в линию частично упорядоченного множества из рис. 4.13 187 ментов в списках последователей – ведомыми ( trailer ), то придем к следующим объявлениям типов данных: TYPE Leader = POINTER TO LeaderDesc; Trailer = POINTER TO TrailerDesc; LeaderDesc = RECORD key, count: INTEGER; trail: Trailer; next: Leader END; TrailerDesc = RECORD id: Leader; next: Trailer END Предположим, что множество S и отношения порядка между его элементами изначально представлены как последовательность пар ключей во входном файле. Такие входные данные для примера на рис. 4.13 представлены ниже, где для ясно% сти явно указаны символы б , обозначающие отношение частичного порядка: 1 〈 2 2 〈 4 4 〈 6 2 〈 10 4 〈 8 6 〈 3 1 〈 3 3 〈 5 5 〈 8 7 〈 5 7 〈 9 9 〈 4 9 〈 10 Первая часть программы топологической сортировки должна прочесть вход% ные данные и преобразовать их в некую списковую структуру. Это делается последовательным чтением пар ключей x и y ( x 〈 y ). Обозначим указатели на их представления в связном списке ведущих как p и q . Эти записи нужно найти в списке, а если их там еще нет, вставить в этот список. Данная задача решается процедурой%функцией find . Затем к списку ведомых для x нужно добавить новый дескриптор, содержащий ссылку на q ; счетчик предшественников для y увели% чивается на 1. Этот алгоритм называется фазой ввода. Рисунок 4.15 показывает списочную структуру, порождаемую при обработке вышеприведенных входных данных. Функция find(w) выдает указатель на элемент списка с ключом w В следующем фрагменте программы мы используем средства сканирования текстов системы Оберон. Здесь текст рассматривается как последовательность не литер, a лексем, которые могут быть идентификаторами, числами, цепочками литер, а также специальными литерами (такими как +, *, < и т. д.). Процедура Texts.Scan(S) просматривает текст, читая очередную лексему. Сканер S является разновидностью бегунка для текстов. (*! *) NEW(head); tail := head; Texts.Scan(S); WHILE S.class = Texts.Int DO x := S.i; Texts.Scan(S); y := S.i; p := find(x); q := find(y); NEW(t); t.id := q; t.next := p.trail; p.trail := t; INC(q.count); Texts.Scan(S) END После того как в фазе ввода построена структура данных, показанная на рис. 4.15, можно начинать выполнение собственно топологической сортировки, описанной ранее. Но так как она состоит из повторяющегося выбора элемента с нулевым числом предшественников, разумно сначала собрать все такие элемен% Линейные списки Динамические структуры данных 188 ты в связный список. Заметив, что исходный список ведущих впоследствии не понадобится, можно повторно использовать то же самое поле next для связыва% ния ведущих с нулевым числом предшественников. Такая операция замены одно% го списка другим часто встречается в обработке списков. Ниже она выписана в деталях. Для простоты новый список создается в обратном порядке: (* v *) p := head; head := NIL; WHILE p # tail DO q := p; p := q.next; IF q.count = 0 THEN (* q^ *) q.next := head; head := q END END Обращаясь к рис. 4.15, видим, что список ведущих, образованный цепочкой ссылок next , заменяется показанным на рис. 4.16, где неизображенные указатели остаются без изменений. Рис. 4.15. Списковая структура, порожденная программой TopSort Рис. 4.16. Список ведущих с нулевым числом предшественников 189 После всей этой подготовки, имея удобное представление частично упорядо% ченного множества S , мы можем наконец приступить собственно к задаче тополо% гической сортировки, то есть порождения выходной последовательности. Первая черновая версия может быть такой: q := head; WHILE q # NIL DO (* , #*) Texts.WriteInt(W, q.key, 8); DEC(n); t := q.trail; q := q.next; v v # t; , q END Операция, которую здесь нужно уточнить, представляет собой еще один про% смотр списка. На каждом шаге вспомогательная переменная p обозначает ведуще% го, чей счетчик нужно уменьшить и проверить. WHILE t # NIL DO p := t.id; DEC(p.count); IF p.count = 0 THEN (* p^ *) p.next := q; q := p END; t := t.next END Этим завершается построение программы топологической сортировки. Заме% тим, что в программе введен счетчик n для подсчета ведущих, порожденных в фазе ввода. Этот счетчик уменьшается каждый раз, когда ведущий выводится в фазе вывода. Поэтому его значение должно снова стать нулем после завершения программы. Если этого не происходит, значит, каждый из оставшихся элементов имеет предшественников. Очевидно, множество S в этом случае не является час% тично упорядоченным. Фаза вывода в представленном виде – пример процесса с «пульсирующим» списком, где элементы вставляются и удаляются в непредска% зуемом порядке. Другими словами, этот пример в полной мере демонстрирует гибкость списочной структуры с явными связями. VAR head, tail: Leader; n: INTEGER; (* ADruS433_TopSort *) PROCEDURE find (w: INTEGER): Leader; VAR h: Leader; BEGIN h := head; tail.key := w; (* *) WHILE h.key # w DO h := h.next END; IF h = tail THEN NEW(tail); INC(n); h.count := 0; h.trail := NIL; h.next := tail END; Линейные списки Динамические структуры данных 190 RETURN h END find; PROCEDURE TopSort (VAR R: Texts.Reader); VAR p, q: Leader; t: Trailer; (* # W*) x, y: INTEGER; BEGIN (* ! – *) NEW(head); tail := head; n := 0; (*! *) Texts.Scan(S); WHILE S.class = Texts.Int DO x := S.i; Texts.Scan(S); y := S.i; p := find(x); q := find(y); NEW(t); t.id := q; t.next := p.trail; p.trail := t; INC(q.count); Texts.Scan(S) END; (* v *) p := head; head := NIL; WHILE p # tail DO q := p; p := q.next; IF q.count = 0 THEN (* q *) q.next := head; head := q END END; (*! *) q := head; WHILE q # NIL DO Texts.WriteLn(W); Texts.WriteInt(W, q.key, 8); DEC(n); t := q.trail; q := q.next; WHILE t # NIL DO p := t.id; DEC(p.count); IF p.count = 0 THEN (* p *) p.next := q; q := p END; t := t.next END END; IF n # 0 THEN Texts.WriteString(W, " ") END; Texts.WriteLn(W) END TopSort. |