Нужна информация о пропусках

В списке пропусков, таком как этот:

пропустить список

Имеет ли элемент 4 доступ к себе во втором и третьем списках? Причина, по которой я спрашиваю, заключается в том, что я пытаюсь понять, как реализовать операцию удаления для списка пропуска. Спасибо


c++ data-structures skip-lists
person Richard    schedule 02.04.2012    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Да, в списке пропуска каждый из указателей каким-то образом приведет вас к фактическим записям. Как правило, вы бы реализовали это, заставив каждый из указателей указывать не на ячейку связанного списка в какой-либо записи, а на саму запись. Пока вы помните текущую глубину, на которой находитесь, вы можете продолжить движение по связанному списку, индексируя массив указателей, хранящихся в следующей ячейке.

Например:

struct Cell {
    Cell* pointers[]; // Each points to the root of a new Cell
    Type data;
};

Надеюсь это поможет!

person templatetypedef    schedule 02.04.2012