390
правок
Изменения
м
→Псевдокод
====Псевдокод====
Каждый уровень списка с пропусками содержит отсортированный односвязный список, у которого есть начало <tex>\mathtt{head}\ </tex> и конец <tex>\mathtt{tail}</tex>. Для выполнения операций на списке с пропусками необходимо передавать в качестве аргумента ссылку на начало односвязного списка, расположенного на самом верхнем уровне.
Элементы односвязного списка — вершины <tex>\mathtt{node}</tex>, у которых есть <tex>3</tex> поля:
* <tex>\mathtt{next}</tex> — ссылка на следующий элемент спискана данном уровне
* <tex>\mathtt{key}</tex> — ключ, который хранится в данной вершине
* <tex>\mathtt{down}</tex> — ссылка на соответственный элемент, лежащий уровнем ниже
'''struct''' node: '''node''' next, down '''T''' key Также известно, что <tex>\mathtt{head{.}key} = -\infty \ </tex> и <tex>\mathtt{tail{.}key} = \infty</tex>.,
Функция <tex>\ \mathtt{build\_lvl} \ </tex> возвращает новый уровень списка с пропусками на основе предыдущего построенного уровня.
