Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
nestudent.ru_46905.doc
Скачиваний:
22
Добавлен:
12.09.2019
Размер:
2.07 Mб
Скачать

Представление нумерацией связей

Представление нумерацией связей (forward star), впервые упомянутое в 4 главе, позволяет компактно представить деревья, графы и сети при помощи массива. Для представления дерева нумерацией связей, в массиве FirstLink записывается индекс для первых ветвей, выходящих из каждого узла. В другой массив, ToNode, заносятся узлы, к которым ведет ветвь.

Сигнальная метка в конце массива FirstLink указывает на точку сразу после последнего элемента массива ToNode. Это позволяет легко определить, какие ветви выходят из каждого узла. Ветви, выходящие из узла I, находятся под номерами от FirstLink(I) до FirstLink(I+1)-1. Для вывода связей, выходящих из узла I, можно использовать следующий код:

For link = FirstLink(I) To FirstLink(I + 1) - 1

Print Format$(I) & " -> " & Format$(ToNode(link))

Next link

@Рис. 6.6. Программа Nary

=======123

На рис. 6.7 показано дерево и его представление нумерацией связей. Связи, выходящие из 3 узла (обозначенного буквой D) это связи от FirstLink(3) до FirstLink(4)-1. Значение FirstLink(3) равно 9, а FirstLink(4) = 11, поэтому это связи с номерами 9 и 10. Записи ToNode для этих связей равны ToNode(9) = 10 и ToNode(10) = 11, поэтому узлы 10 и 11 будут дочерними для 3 узла. Это узлы, обозначенные буквами K и L. Это означает, что связи, покидающие узел D, ведут к узлам K и L.

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

По этим причинам большая часть литературы по сетевым алгоритмам использует представление нумерацией связей. Например, многие статьи, касающиеся вычисления кратчайшего пути, предполагают, что данные находятся в подобном формате. Если вам когда‑либо придется изучать эти алгоритмы в журналах, таких как “Management Science” или “Operations Research”, вам необходимо разобраться в этом представлении.

@Рис. 6.7. Дерево и его представление нумерацией связей

=======123

Используя представление нумерацией связей, можно быстро найти связи, выходящие из определенного узла. С другой стороны, очень сложно изменять структуру данных, представленных в таком виде. Чтобы добавить к узлу A на рис. 6.7 еще одного потомка, придется изменить почти все элементы в обоих массивах FirstLink и ToNode. Во‑первых, каждый элемент в массиве ToNode нужно сдвинуть на одну позицию вправо, чтобы освободить место под новый элемент. Затем, нужно вставить новую запись в массив ToNode, которая указывает на новый узел. И, наконец, нужно обойти массив ToNode, обновив каждый элемент, чтобы он указывал на новое положение соответствующей записи ToNode. Поскольку все записи в массиве ToNode сдвинулись на одну позицию вправо, чтобы освободить место для новой связи, потребуется добавить единицу ко всем затронутым записям FirstLink.

На рис. 6.8 показано дерево после добавления нового узла. Записи, которые изменились, закрашены серым цветом.

Удаление узла из начала представления нумерацией связей так же сложно, как и вставка узла. Если удаляемый узел имеет потомков, процесс занимает еще больше времени, поскольку придется удалять и все дочерние узлы.

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

@Рис. 6.8. Вставка узла в дерево, представленное нумерацией связей

=======124

Программа Fstar использует представление нумерацией связей для работы с деревом, имеющим узлы разного порядка. Она аналогична программе NAry, за исключением того, что она использует представление на основе массива, а не коллекций.

Если вы посмотрите на код программы Fstar, вы увидите, насколько сложно в ней добавлять и удалять узлы. Следующий код демонстрирует удаление узла из дерева.

Sub FreeNodeAndChildren(ByVal parent As Integer, _

ByVal link As Integer, ByVal node As Integer)

' Recursively remove the node's children.

Do While FirstLink(node) < FirstLink(node + 1)

FreeNodeAndChildren node, FirstLink(node), _

ToNode(FirstLink(node))

Loop

' Удалить связь.

RemoveLink parent, link

' Удалить сам узел.

RemoveNode node

End Sub

Sub RemoveLink(node As Integer, link As Integer)

Dim i As Integer

' Обновить записи массива FirstLink.

For i = node + 1 To NumNodes

FirstLink(i) = FirstLink(i) - 1

Next i

' Сдвинуть массив ToNode чтобы заполнить пустую ячейку.

For i = link + 1 To NumLinks - 1

ToNode(i - 1) = ToNode(i)

Next i

' Удалить лишний элемент из ToNode.

NumLinks = NumLinks - 1

If NumLinks > 0 Then ReDim Preserve ToNode(0 To NumLinks - 1)

End Sub

Sub RemoveNode(node As Integer)

Dim i As Integer

' Сдвинуть элементы массива FirstLink, чтобы заполнить

' пустую ячейку.

For i = node + 1 To NumNodes

FirstLink(i - 1) = FirstLink(i)

Next i

' Сдвинуть элементы массива NodeCaption.

For i = node + 1 To NumNodes - 1

NodeCaption(i - 1) = NodeCaption(i)

Next i

' Обновить записи массива ToNode.

For i = 0 To NumLinks - 1

If ToNode(i) >= node Then ToNode(i) = ToNode(i) - 1

Next i

' Удалить лишнюю запись массива FirstLink.

NumNodes = NumNodes - 1

ReDim Preserve FirstLink(0 To NumNodes)

ReDim Preserve NodeCaption(0 To NumNodes - 1)

Unload FStarForm.NodeLabel(NumNodes)

End Sub

Это намного сложнее, чем соответствующий код в программе NAry:

Public Function DeleteDescendant(target As NAryNode) As Boolean

Dim i As Integer

Dim child As NAryNode

' Является ли узел дочерним узлом.

For i = 1 To Children.Count

If Children.Item(i) Is target Then

Children.Remove i

DeleteDescendant = True

Exit Function

End If

Next i

' Если это не дочерний узел, рекурсивно

' проверить остальных потомков.

For Each child In Children

If child.DeleteDescendant(target) Then

DeleteDescendant = True

Exit Function

End If

Next child

End Function

=======125-126

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]