Приведенный ниже итеративный алгоритм вставки для связанных списков
4. Приведенный ниже итеративный алгоритм вставки для связанных списков оказывается длиннее соответствующего рекурсивного алгоритма, потому что в нем отдельно рассматриваются ситуации вставки элемента сразу после первого в списке и во все прочие позиции.
void 1nsert(t) i f head ->va1 == t return if head - >va1 > t
head = new node(t. head) n++
return
for (p = head: p->next->val < t. p = p-> next)
if p->next->val == t retu rn
p->next = new node(tr p->next) n + +
Более простая версия этого алгоритма использует указатель па указатель: void insert(t)
for (p = & h e a d: (*p)->val < t. p = &( (*p)->next))
Память под все узлы, которые мы собираемся выделить в будущем, выделяется при вызове конструктора класса:
freenode = new node[maxelms]
Затем по мере необходимости мы выделяем намять иод вставляемые элементы:
if (р == 0) р - freenode++ р - > v а 1 = t
p->left = p->right = О n + + else if
Аналогичный метод можно применить и к корзинам. В решении задачи 7 он применен к двоичным деревьям поиска.
6. Вставка узлов в порядке возрастания позволяет измерить скорость поиска в массивах и списках с небольшими затратами на собственно вставку. Такая последовательность элементов создает наихудшую ситуацию для корзин и двоичных деревьев поиска.
7. Указатели, которые в предыдущей версии были нулевыми (null), будут теперь указывать па маркерный узел. Он инициализируется тем же конструктором:
root = sentinel = new node
Функция вставки сначала помещает вставляемое значение в маркерный узел, а затем использует указатель па указатели (как в решении задачи 4), спускаясь по дереву до тех пор, пока пе будет найден элемент t. После этого для вставки нового узла используется метод из решеппя задачи 5.
void 1nsert(t) sen11ne1 - >v а 1 = t p - &root
while (*p b>va 1 = t if t < (*p)->val p = &((*p)->1eft) else
p = &((*p)->right) if *p == sentinel *p - freenode++
(*p) - >va1 = t
(*p)->left = (*p)->right = sentinel n + +
Переменная node объявляется п инициализируется следующим оператором:
node **p = &root.
Главная
Каталог файлов
