Оператор в (4.32), который осталось уточнить, осуществляет еще один проход по списку [см. схему (4.17)]. На каждом шаге вспомогательная переменная р указывает на ведущий дискриптор, счетчик которого нужно уменьшить и проверить на равенство нулю.

vchile t Ф- nil do

begin p := t\.id;p\.count :== pixount-l; if p\.count = 0 then

begin {включениеp\ в список ведущих} /4334 p\.next : q;q:=p

end;

t := tl-next

Ha этом завершается разработка- программы топологической сортировки. Обратите внимание, что был введен счетчик для подсчета ведущих дескрипторов, сформированных на фазе ввода. Этот счетчик уменьшается каждый раз, когда ве-ДУЩий дескриптор выводится на фазе вывода. Поэтому он Должен вновь стать равным О в конце работы программы. Ьсли он не смог вернуться к О, это указывает, что в структуре отались элементы и среди них нет таких, у которых отсут-вуют предшественники. Очевидно, что в этом случае множество S не является частично упорядоченным.

Приведенная выше программа фазы вывода служит при-Ром работы со списком, который пульсирует , т. е. эле-leBTbi которого добавляются и удаляются в непредсказуемом рядке. Следовательно, это пример процесса, полностью

После всех этих подготовительных действий, направленна то, чтобы выработать подходящее представление час- flo упорядоченного множества S, мы можем, наконец, пе- йти к собственно топологической сортировке, т. е. формн-

дйЮ выходной последовательности. В первом, грубом рйблйзкении это можно описать следующим образом:

-sJieai;- -------------- .

in {вывести этот элемент, затем исключить его} \rileln(qlkey); z:=z -1; (4.32)

f :== \.trail; q := q\.next;

уменьшить счетчик предшественников у всех его последователей в списке ведомых если какой-либо счетчик стал равен О, добавить этот элемент к списку ведущих q

program topsort(tnpui,outputy, type Iref = ] leader; tref = \ frailer; leader - record key: integer;

count: integer; trail: tref; next: Iref; end ;

trailer ~ record id: Iref;

next: tref end ;

vat head, tail, p,q: Iref; t: tref; z: integer; x,y: integer;

function LCwr-fntsger): Iref г ;

[ссылка на ведущего с ключом w] var h: Iref; begin h :=: head; tail\.key :~ w; vcliile h\.key Ф w do Л := h\.next, \\h tailtlim

begin {0 списке нет элемента с ключом w\ newitail); z := i+l;

h\.count := 0; h\.trail := nil; h\jiext := tail end ; i := Й end {L} ;

begin [инициация списка ведущих фиктивным элементов]

newQiead); tail := head; z := 0; [фаза ввода] readix); while x 0 do begin/ eflfJC); writeln{x,y);

P Цх); q := L(y);

new(t); t].id :=j q; t\Mext : р\.ШИ; .

p\.trail:- t; q\.count := q\.count + Ij

read{x) end ;

[поиск ведущих со счетчиком-0] р :- head; head nil;

while p Ф tail do : :

begm q :- p; p :=s p\Mxt; if q\.count =s 0 then

begin q\mext head; Неа41==г q

.. begin p tf\.id; p].count := p].count - 1; if p\.count = 0 then begin [включение pfe q-список]

p].next := q;, q \== p end ;

t := t\.next

ii z Ф Q Xheawiteln (THIS SET IS Nor PARTIALLY ORDERED) end .

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

использующего гибкость, которую обеспечивает явно связанный список.

4.4. древовидные структуры

4.4.1. Основные понятия и определения

Мы видели, что последовательности и списки можно определить следующим образом: любая последовательность (список) с базовым типом Т - это либо:

1 пустая последовательность (список); либо

2 конкатенация (цепочка) из элемента типа Т и последовательности с базовым типом Т.

Здесь для определения принципов структурирования (следования или итерации) используется рекурсия. Следование и итерация встречается настолько часто, что их обычно счн-laiOT фундаментальными образами как структур данных, ак и управления в программах. Однако всегда следует

омнить, что с помощью рекурсий их только можно опреде-ть, но рекурсии можно эффективно и элегантно использо-

для определения более сложных структур.

Хорощо известным примером служат деревья. Пусть дре-идная структура определяется следующим образом: дре-чдная структура с базовым типом Г -это либо:

Пустая структура; либо

-

end . ; .

;,:.-end;- -

фаза вывода] q :== headi while q Ф nil do \ieg\rs.mitdn{q\.key); z \~ z~\, t := q\.tmil; q := q\.next; while ; ? nil do