Примеры, показанные для круглых связанных списков и пропущенных списков

Question

Я хотел бы спросить ваши идеи о том, какие программы или даже методы, в которых я могу лучше объяснить полезность теории Круговых связанных списков и Пропустить списки длямои сверстники.

Мое убеждение в программировании состоит в том, что можно лучше понять концепцию, если вы дадите им примеры и метафоры.

Просто ваше представление о примерах программ для создания или решения (техника или алгоритм программирования),

Ура!

Answer 1

Хорошее использование для циклически связанных списков - это система планирования заданий, в которой каждое задание получает определенное количество времени с данным ресурсом (например, процессы в простой операционной системе).

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

current = current->next

Возможный пропуск списка - словарь в форме списка. Вы поддерживаете указатель на первое слово a, и он содержит нормальный указатель на aardvark и пропускающий указатель на baa ^{* a} .

---

^{* a} : На самом деле я не знаю, правильные ли это слова, но они должны быть близки, и, надеюсь, вы поймете идею.

Answer 2

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

Пропуск списков создает своего рода двоичное дерево поиска поверх обычного связанного списка, так что операции поиска занимают время O (log N) вместо O (N), делая их быстрее.Вы можете использовать их везде, где хотите использовать обычный связанный список, но вам нужен более быстрый доступ.

На следующей странице есть очень хорошее и простое обсуждение пропущенных списков: http://igoro.com/archive/skip-lists-are-fascinating/

Answer 3

Из Википедия :

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

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

Пропуск списков поддерживает быстрые (O (log (n))) операции и может использоваться какотсортированная структура данных - очень похоже на сбалансированное двоичное дерево поиска.Это делает их полезными везде, где нам нужно быстрое время вставки / удаления данных (например, связанный список, но в отличие от массива), а также быстрое время доступа (например, массив, но в отличие от связанного списка).Они также хороши для выполнения быстрых запросов (например, найти сумму (или max, min, product и т. Д.) Всех элементов в индексах [i, j] структуры).

Я не могу придуматьдостаточно простая метафора реального мира для списка пропусков, структура данных выглядит более сложной, чем все, что я могу ожидать увидеть с объектами в повседневной жизни.Но объяснение wikipedia довольно ясно, и проработка доказательства и алгоритма его построения должна стать хорошей отправной точкой.Вот ссылка на оригинальную статью , которая также является вполне читабельной IMO.