Главная Промышленная автоматика.

2.22. Можно хранить к стеков в одном массиве, если используется структура данных, показанная на рис. 2.12 для случая /с = 3. В этом случае можно организовать вставку и удаление элементов для каждого стека так же, как описано в разделе 2.3. Но если случится, что при вставке элемента в стек 1 вершина Т0Р(1) совпадет с "дном" предыдущего стека BOTTOM(i-l), то возникает необходимость переместить все стеки так, чтобы между каждой парой смежных стеков бьш зазор из пустых ячеек массива. В этом случае мы можем сделать все зазоры одинаковыми или пропорциональными длине соседнего с зазором стека (из теории следует: чем больше стек, тем вероятнее в ближайшем будущем его рост, а мы, естественно, хотим отсрочить следующую реорганизацию массива).

а) в предположении, что есть процедура reorganize (реорганизация), вызываемая при возникновении "конфликтов" между стеками, напишите код для пяти операторов стека;

б) напишите процедуру reorganize в предположении, что уже сзтцествует процедура ntakenewtops (сделать новые вершины), которая вычисляет newtop[i], - новую позицию вершины стека i для всех 1, I < i < к. Совет: отметим, что стек 1 может перемещаться как вверх, так и вниз по массиву. Если новая позиция стека / захватывает старую позицию стека i, то стек i надо переместить раньше стека j. Рассматривая стеки в порядке 1, 2, к, создадим еще стек "целей", кавдая "цель" будет перемещать отдельный конкретный стек. Если стек i можно безопасно переместить, то перемещение выполняется и повторно рассматривается стек, чей номер находится в вершине стека целей. Если стек i нельзя переместить, не затрагивая других стеков, то его номер помещается в стек целей;

в) какая подходящая реализация для стека целей? Необходимо ли для этого использовать список из целых чисел или можно воспользоваться более простой реализацией?

г) реализзщте процедуру makenewtops так, чтобы пространство перед каясдым стеком было пропорционально его текущей длине;

д) какие изменения надо сделать в схеме рис. 2.12, чтобы ее можно было применить для очередей? А для произвольных списков?


вершины

массив

Рис. 2.12. Расположение нескольких стеков в одном массиве

2.23. Измените реализации операторов POP и ENQUEUE из разделов 2.3 и 2.4 так, чтобы они возвращали элементы, удаленные соответственно из стека и очере-

УПРАЖНЕНИЯ



ди. Что необходимо сделать, если элемент имеет тип данных, который функция не может вернуть? 2.24. Используйте стек для исключения рекурсивных вызовов из следующих процедур:

fimction comb ( п, т: integer ) : integer;

{вычисление биномиальных коэффициентов С™ при 0<m<n и п>1} begin

if (n= 1) or (т = 0) or (т = л) then return(1)

else

return(comb(n - 1, m) + cowb{n - 1, т - 1))

end; { comb }

procedure reverse { var L: LIST ); { обращение сгшска L } var

x: elementtype; begin

if not EMPTY(L) then begin

x: = RETRIEVE (FIRST (L) , L) ; DELETE (FIRST ( L), b) ; reverse(L); INSERT {;<, END{L) , L)

end; { reverse }

*2.25. Можно ли исключить последние рекурсивные вызовы из программ примера 2.24? Если можно, то как?

Библиографические примечания

Книга [63] содержит дополнительный материал по реализациям списков, стеков и очередей. Многие языки программирования, например LISP и SNOBOL, поддерживают списки в удобной форме. См. работы [80], [86], [94] и [117], содержащие исторические справки и описания таких языков.



ГЛАВА 3

Деревья

Деревья представляют собой иерархическую структуру некой совокупности элементов. Знакомыми вам примерами деревьев могут служить генеалогические и организационные диаграммы. Деревья используются при анализе электрических цепей, при представлении структур математических формул. Они также естественным путем возникают во многих областях компьютерных наук. Например, деревья используются для организации информации в системах управления базами данных и для представления синтаксических структур в компиляторах программ. В главе 5 описано применение деревьев для представления данных. В этой книге вы встретитесь со многими примерами деревьев. В этой главе мы введем основные определения (терминологию) и представим основные операторы, выполняемые над деревьями. Затем опишем некоторые наиболее часто используемые структуры данных, представляющих деревья, и покажем, как наиболее эффективно реализовать операторы деревьев.

3.1. Основная терминология

Дерево - это совокупность элементов, называемых узлами (один из которых определен как корень), и отношений ("родительских"), образующих иерархическую структуру узлов. Узлы, так же, как и элементы списков, могут быть элементами любого типа. Мы часто будем изображать узлы буквами, строками или числами. Формально дерево можно рекуррентно определить следующим образом.

1. Один узел является деревом. Этот же узел также является корнем этого дерева.

2. Пусть п - это узел, а Т, . . . - деревья с корнями n-i, п, л* соответственно. Можно построить новое дерево, сделав га родителем узлов nj, га,,, щ. В этом дереве п будет корнем, а Т, Tj, - поддеревьями этого корня. Узлы П\,П2, • • • >л4называются сыковьял«1злага.

Часто в это определение включают понятие нулевого дерева, т.е. "дерева" без узлов, такое дерево мы будем обозначать символом Л.

Пример 3.1. Рассмотрим оглавление книги, схематически представленное на рис. 3.1, а. Это оглавление является деревом, которое в другой форме показано на рис. 3.1, б. Отношение родитель-сын отображается в виде линии. Деревья обычно рисуются сверху вниз, как на рис. 3.1, б, так, что родители располагаются выше "детей".

Книга Книга

Гл.1 Р1.1

Р. 1.2 Гл.1 Гл.2 Гл.З

Гл.2 Р.2.1

Р.2.1.1

R2.1.2 Р.2.2

Р-2 3 p.2.i.i р.2,1.2

Гл.З

Рис. 3.1. Оглавление книги и его представление в виде дерева


Р.1 1 R1.2 R2.1 Р2.2 Р.2,3





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 [21] 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123

0.004