Основы программирования. Динамические массивы. Списки. Ассоциативные массивы. Деревья. Хеш-таблицы - 43 стр.

UptoLike

ВУЗ: 

ЮФУ | Ростов-на-Дону

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

Рубрика: 

45
TNode=record
Key: KeyType;
Value: ValueType;
left,right: PNode;
end;
Интерфейс модуля PairsSIBST, реализующего дерево пар
(string,integer), будет выглядеть следующим образом:
function NewNode(Key: KeyType; Value: ValueType;
left,right: PNode): PNode;
procedure Add(Key: KeyType; Value: ValueType;
var r: PNode);
function Search(Key: KeyType; r: PNode): PNode;
procedure Delete(Key: KeyType; var r: PNode);
Поиск и сравнение при этом следует проводить только по ключевому полю
Key. Для реализации методов SetItems и GetItems не потребуется ни итера-
тора, ни вспомогательных методов. Приведем
реализацию SetItems, а реализа-
цию GetItems оставим в качестве упражнения:
procedure SetItems(Key: string; Value: integer);
var v: Pnode;
begin
v:=Search(Key,root);
if v=nil then
Add(Key,Value,root)
else v.Value:=Value;
end;
4.5 Реализация произвольного дерева
Произвольное дерево будем составлять из узлов вида:
PTreeNode = ^TreeNode;
TreeNode = record
data: DataType;
leftChild, rightSibling: PTreeNode;
end;
где тип DataType опрделен ранее. Каждый элемент хранит указатель на своего
самого левого сына leftChild и на своего правого брата rightSibling
(sibling – родной брат/сестра). У корневого элемента братья отсутствуют.
Дерево, изображенное на приведенном ниже рисунке,

Страницы