Модели и структуры данных



         

Сортировки включением - часть 8


Самый первый слот выделенной памяти занимает вершина. Следующие 2 слота - элементы второго уровня, следующие 4 слота - третьего и т.д. Дерево с рис.3.17.б, например, будет линеаризовано таким образом:

12 16 28 20 35 30 32 58

В таком представлении отпадает необходимость хранить в составе узла дерева указатели, так как адреса потомков могут быть вычислены. Для узла, представленного элементом массива с индексом i индексы его левого и правого потомков будут 2*i и 2*i+1 соответственно. Для узла с индексом i индекс его предка будет i div 2.

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

  • процедура InitST - инициализация модуля, установка начального значения nt;
  • функция InsertST - вставка в дерево нового элемента; функция возвращает false, если в дереве нет свободного места, иначе - true;
  • функция DeleteST - выборка из дерева минимального элемента; функция возвращает false, если дерево пустое, иначе - true;
  • функция CheckST - проверка состояния дерева: ключ минимального элемента возвращается в выходном параметре, но элемент не исключается из дерева; а возвращаемое значение функции - 0 - если дерево пустое, 1 - если дерево заполнено не до конца, 2 - если дерево заполнено до конца.

Кроме того в модуле определены внутренние программные единицы:

  • функция Down - обеспечивает спуск свободного места из вершины пирамиды в ее основание, функция возвращает индекс свободного места после спуска;
  • процедура Up - обеспечивающая всплытие элемента с заданного места.

{===== Программный пример 3.13 =====} { Сортировка частично упорядоченным деревом } Unit SortTree; Interface Procedure InitSt; Function CheckST(var a : integer) : integer; Function DeleteST(var a : integer) : boolean; Function InsertST(a : integer) : boolean; Implementation Const NN=16; var tr : array[1..NN] of integer; { дерево } nt : integer; { индекс последнего эл-та в дереве } {** Всплытие эл-та с места с индексом l **} Procedure Up(l : integer); var h : integer; { l - индекс узла, h - индекс его предка } x : integer; begin h:=l div 2; { индекс предка } while h > 0 do { до начала дерева } if tr[l] < tr[h] then begin { ключ узла меньше, чем у предка } x:=tr[l]; tr[l]:=tr[h]; tr[h]:=x; { перестановка } l:=h; h:=l div 2; { предок становится текущим узлом } end else h:=0; { конец всплытия } end; { Procedure Up } {** Спуск свободного места из начала дерева **} Function Down : integer; var h, l : integer; { h - индекс узла, l - индекс его потомка } begin h:=1; { начальный узел - начало дерева } while true do begin l:=h*2; { вычисление индекса 1-го потомка } if l+1




Содержание  Назад  Вперед