ВУЗ:
Составители:
Рубрика:
52
Пример 59: преобразование строки в список символов с использованием
предиката frontchar.
domains
list=char*
predicates
convert (string, list)
clauses
convert («», []).
convert (Str, [H\T]):- frontchar(Str, H, Str1),
convert(Str1, T).
2.17 Представление бинарных деревьев
Одной из областей применения списков является представление
множества объектов. Недостатком представления множества в виде списка
является неэффективная процедура проверки принадлежности элемента
множеству. Используемый для этой цели предикат member неэффективен при
использовании больших списков.
Для представления
множеств могут использоваться различные
древовидные структуры, которые обеспечивают более эффективную
реализацию проверки принадлежности элемента множеству, в частности, в
данном разделе для этой цели рассматриваются бинарные деревья.
Представление бинарных деревьев основано на определении
рекурсивной структуры данных, использующей функцию типа tree (Top, Left,
Right) или tree (Left, Top, Right), где Top - вершина дерева, Left и Right -
соответственно левое и правое поддерево
. Пустое дерево обозначим термом
nil. Объявить бинарное дерево можно следующим образом:
Пример 60:
domains
treetype1=tree(symbol, treetype1, treetype1);nil
treetype2=tree(treetype2, symbol, treetype2);nil
Пример 61:
Пусть дано дерево следующего вида:
a
b c
d e
Такое дерево может быть задано следующим образом:
1. левое поддерево: tree (b, tree (d, nil, nil), tree (e, nil, nil)).
2. правое поддерево: tree (c, nil, nil).
3. все дерево: tree (a, tree (b, tree (d, nil, nil), tree (e, nil, nil)), tree (c, nil,
nil)).
Страницы
- « первая
- ‹ предыдущая
- …
- 50
- 51
- 52
- 53
- 54
- …
- следующая ›
- последняя »
