Методы программирования. Громов Ю.Ю - 48 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

48
Обратным порядком прохождения узлов этого же леса является по-
следовательность BKCAHEJFGD. Она получается таким же способом,
как и для прямого порядка, но только в соответствующем представлении
леса с помощью вложенных скобок каждый узел записывается после сво-
их потомков, а не перед ними:
((B, (K) C) A, ((H) E, (J) F, G) D) (32)
Узлы нашего леса в концевом порядке образуют последовательность
KCBHJGFEDA. Это на первый взгляд несколько странное расположение
узлов довольно просто объясняется. В строке символов (31) или (32) не-
обходимо двигаться слева направо до тех пор, пока не будет достигнута
первая правая скобка. Затем начать проходить узлы, двигаясь справа на-
лево до тех пор, пока не будет достигнута левая скобка. Потом из всей
строки вычеркнуть полностью группу символов, включая эти скобки.
В полученной строке опять двигаться слева направо до первой правой
скобки и проходить узлы справа налево до тех пор, пока не будет достиг-
нута левая скобка и так далее, пока строка не станет пустой.
Помимо рассмотренного выше представления лесов, которое услов-
но можно назвать «левый сын – правый брат», существует ещё много
способов представления древовидных структур в компьютере. Из них,
прежде всего, используют методы последовательного распределения па-
мяти.
Один из способов представления лесов методом последовательного
распределения памяти заключается, по существу, в том, что опускаются
связи LLINK.
В случае представления нашего леса в прямом порядке при последо-
вательном распределении узлы располагаются в прямом порядке с поля-
ми INFO, RLINK, LTAG в каждом узле:
RLINK
INFO A B C K D E H F J G (33)
LTAG +
+
+ +
+
Здесь непустые связи RLINK отмечены стрелками, а связи LLINK не
нужны, поскольку такая связь была бы нулевой или указывала бы на сле-
дующий элемент последовательности.
Реверсивный к концевому порядок представления леса при последо-
вательном распределении памяти отличается от прямого порядка тем, что
опускаются связи RLINK, а связи LLINK сохраняются:

Страницы