Структуры данных и модели вычислений



         

Вспомогательные структуры - часть 2


которые интерпретируем следующим образом:

  • — -й разряд, равный количеству деревьев ранга ;
  • — прямой указатель -го разряда;
  • — указатель на список деревьев ранга , присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя

    корневых узлов связываемых деревьев. Если в куче нет деревьев ранга , то указатель заземлен. Заметим, что если значение равно нулю, то нам неважно, каково значение указателя .

Инициализация корневого счетчика (InitRootCount). Поскольку корневой счетчик реализован как массив записей, возникает вопрос о величине данного массива и о том, что делать, когда весь этот массив заполнен. Чтобы была возможность оценить время инициализации счетчиков величиной , используем поразрядную их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную , которая показывает нам, какая часть массивов счетчиков используется в данный момент.

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

Обновление прямого указателя i-го разряда корневого счетчика заключается в выполнении операторов

Корректировка списочной части i-го разряда корневого счетчика при вставке в кучу нового дерева ранга i. Эта процедура вставляет новое дерево ранга

(на него указывает указатель ) в списочную часть -го разряда корневого счетчика и заключается в выполнении операторов

Корректировка списочной части i>-го разряда корневого счетчика при удалении из кучи дерева ранга i. Эта процедура удаляет дерево ранга (на него указывает указатель ) из списочной части -го разряда корневого счетчика . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении операторов

Связывание (Fastening (p1, p2, p3)) трех толстых деревьев ранга i в одно толстое дерево ранга i +1.Эта функция принимает три указателя на три разных толстых дерева одного и того же ранга и возвращает указатель на вновь сформированное дерево ранга .




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