yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Листинг 3.6. Функции, использующие представление деревьев посредством связанных списков 

Алгоритмы структуры данных

Листинг 3.6. Функции, использующие представление деревьев посредством связанных списков 

function LEFTMOST_CHILD   (   n:   node;   Т:   TREE   }:   node;

{   возвращает самого левого сына узла л дерева  Т }

var

L:   integer;   {  курсор на начало списка сыновей узла n  }

begin

L:=   T.header[n] ;

if L = 0 then  { n является листом }

return(0)

else

return(cellspace[L] . node)

end; { LEFTMOST_CHILD }

 

function PARENT ( n: node; T: TREE ): node;

{ возвращает родителя узла л дерева Т }

 var

р: node; { пробегает возможных родителей узла n }

i: position; { пробегает список сыновей р }

begin

for p:= 1 to maxnodes do begin

i:= T.header[p] ;

while і <> 0 do {проверка на наличие

сыновей узла р }

if cellspaсе[і].node = n then

return (p)

else

i:= cellspacefi].next

end;

return(O) { родитель не найден }

end; { PARENT }

Представление левых сыновей и правых братьев

Среди прочих недостатков описанная выше структура данных не позволяет также с помощью операторов CREATEi создавать большие деревья из малых. Это является следствием того, что все деревья совместно используют массив cellspace для представления связанных списков сыновей; по сути, каждое дерево имеет собственный массив заголовков для своих узлов. А при реализации, например, оператора CREATE2(v, Т1, Т2) надо скопировать деревья Т1 и Т2 в третье дерево и добавить новый узел с меткой v и двух его сыновей — корни деревьев Т1 и Т2.

Если мы хотим построить большое дерево на основе нескольких малых, то желательно, чтобы все узлы всех деревьев располагались в одной общей области. Логическим продолжением представления дерева, показанного на рис. 3.8, будет замена массива заголовков на отдельный массив nodespace (область узлов), содержащий записи с произвольным местоположением в этом массиве. Содержимое поля header этих записей соответствует "номеру" узла, т.е. номеру записи в массиве cellspace, всвою очередь поле node массива cellspace теперь является курсором для массива nodespace, указывающим позицию узла. Тип TREE в этой ситуации "просто курсор в массиве nodespace, указывающий позицию корня.

Пример 3.7. На рис. 3.9, а показано дерево, а на рис. 3.9, б — структура данных, где узлы этого дерева, помеченные как А, В, С и D, размещены в произвольных позициях массива nodespace. В массиве cellspace также в произвольном порядке размещены списки сыновей.

Структура данных, показанная на рис. 3.9, б, уже подходит для того, чтобы организовать слияние деревьев с помощью операторов CREATEi. Но и эту структуру можно значительно упростить. Для этого заметим, что цепочка указателей поля next массива cellspace перечисляет всех правых братьев.

Используя эти указатели, можно найти самого левого сына следующим образом. Предположим, что cellspace[i].node = п. (Повторим, что "имя" узла, в отличие от его метки, является индексом в массиве nodespace и этот индекс записан в поле cell-space[i].node.) Тогда указатель nodespace[n].header указывает на ячейку самого левого сына узла п в массиве cellspace, поскольку поле node этой ячейки является именем этого узла в массиве nodespace.

Можно упростить структуру, если идентифицировать узел не с помощью индекса в массиве nodespace, а с помощью индекса ячейки в массиве cellspace, который соответствует данному узлу как сыну. Тогда указатель next (переименуем это поле в right_sibling — правый брат) массива cellspace будет точно указывать на правого брата, а информацию, содержащуюся в массиве nodespace, можно перенести в новое поле leftmost_child (самый левый сын) массива cellspace. Здесь тип TREE является целочисленным типом и используется как курсор в массиве cellspace, указывающий на корень дерева. Массив cellspace можно описать как следующую структуру:

var

cellspace: array[1..maxnodes] of record

label: labeltype;

leftmost__child: integer;

right_sibling: integer

end;

Пример 3.8. Новое представление для дерева, показанного на рис. 3.9, а, схематически изображено на рис. ЗЛО. Узлы дерева расположены в тех же ячейках массива, что и на рис. 3.9, б.

Используя описанное представление, все операторы, за исключением PARENT, можно реализовать путем прямых вычислений. Оператор PARENT требует просмотра всего массива cellspace. Если необходимо эффективное выполнение оператора PARENT, то можно добавить четвертое поле в массив cellspace для непосредственного указания на родителей.

В качестве примера операторов, использующих структуры данных рис. З.10, напишем код функции CREATE2, показанный в листинге 3.7. Здесь мы предполагаем, что неиспользуемые ячейки массива cellspace связаны в один свободный список, который в листинге назван как avail, и ячейки этого списка связаны посредством поля right_sibling. На рис. 3.11 показаны старые (сплошные линии) и новые (пунктирные линии) указатели в процессе создания нового дерева.

 

 

38