page{outpiit); printtree(root); end

Программа 4.5. Построение таб.пицы перекреигных ссылок.

2 В качестве ключа хранятся только первые с1 символов. Таким образом, два слова, у которых первые с1 символов

не различаются, считаются одинаковыми.

3 Эти с1 символов упаковываются в массив id (типа alfa). Если с1 достаточно мало, во многих вычислительных машинах такие упакованные массивы могут сравниваться с помощью одной команды.

4. Переменная kl-это индекс, который, используется в следующем инвариантном условии, касающемся буфера символов а:

a[i] = для ikl + l ... cl.

Это означает, что слова, состоящие из менее чем с1 символов, дополняются соответствующим количеством пробелов.

5. Желательно, чтобы номера строк в таблице перекрестных ссылок печатались в возрастающем порядке. Поэтому список отметок должен формироваться в том же порядке, в каком они печатаются. Это требование предполагает использование в каждом слове-узле двух ссылок, из которых

одна указывает на первый, а вторая - на последний элемент списка отметок.

Сканер строится таким образом, что слова в кавычках и внутри комментариев не включаются в таблицу пере-рестных ссылок; при этом предполагается, что кавычки и комментарии не переходят через концы строк.

В табл. 4.4 показан результат обработки некоторого тек- программы.

Удаление из дерева

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

1 я узла с ключом к из дерева с упорядоченными ключами.

Жалению, удаление элемента обычно не так просто, как

repeat writeif]); get(f)

until /t = };

write Щ); get (J)

end end ;

writeln; get{f)

Таблица 4.4. Пример распечатки, полученной в результате работ программы 4.5.

1 PROGRAM PERMUTE (OUTPUT);

2 3 4 Б 6 7 S 9 10 11 -1-2

CONST N = 4; VAR I: INTEGER;

A: ARRAY [1 .. JN] OF INTEGER;

PROCEDURE PRINT;

VAR I; INTEGER; BEGIN FOR I := 1 TO N DO WRITE {A[l] :3);

WRITELN END {PRINT} ;

PROCEDURE PERM (K: INIbUR);

VAR I,X: INTEGER; BEGIN

IF К = 1 THEN PRINT ELSE BEGIN PERM (K-1);

FOR I := 1 TO K-1 DO BEGIN X := A[I]; A[I] := A[K]; A[K] := X; PERM (K-1);

X := A[l]; A[l] := A[K]; A[K] := Xi

END END END {PERM] ;

13 14 15 16 17 18 19 20 21 22 23 24

25 BEGIN

26 FOR I := 1 TO N DO A[l] := I;

27 PERM (N)

28 END .

20 2 4 1 1

12 6 6 1

15 8 3 5 8

16 15 12

18 27

Продолжение 18 13 20

fHOCEDURE fROGRAM THEN TO VAR

WRITELN fWRlTE

I 13 18 18 20 20

включение. Оно просто в случае, когда удаляемый элемент является терминальным узлом или им(ет одного потомка.

17 7

Рис. 4.28. Удаление из дерева.

т

РУДность заключается в удалении элементов с двумя потом-. поскольку мы не можем указывать одной ссылкой на Направления. В этом случае удаляемый элемент нужно gHHTb либо на самый правый элемент его левого поддс'