Для чего нужна циклическая структура данных?

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

Множество вещей. Круговой буфер, например: у вас есть некоторый набор данных с лицевой и оборотной стороны, но произвольное количество узлов, и «следующий» элемент из последнего должен вернуть вас к первому.

Графические структуры часто бывают циклическими; ацикличность - особый случай. Рассмотрим, например, граф, содержащий все города и дороги в задаче коммивояжера.

Хорошо, вот вам конкретный пример. Я создал коллекцию городов здесь, в Колорадо:

V=["Boulder", "Denver", "Colorado Springs", "Pueblo", "Limon"]

Затем я создаю пары городов, где есть дорога, соединяющая их.

E=[["Boulder", "Denver"],
   ["Denver", "Colorado Springs"],
   ["Colorado Springs", "Pueblo"],
   ["Denver", "Limon"],
   ["Colorado Springs", "Limon"]]

У этого есть куча циклов. Например, вы можете поехать из Колорадо-Спрингс в Лимон, в Денвер и обратно в Колорадо-Спрингс.

Если вы создаете структуру данных, которая содержит все города в V и все дороги в E, это структура данных график. У этого графика были бы циклы.

при моделировании решетки часто используются циклические / тороидальные граничные условия. обычно достаточно простого lattice[i%L], но я полагаю, что можно создать циклическую решетку.

Вложенную структуру можно использовать в тестовом примере для сборщика мусора.

Недавно я создал циклическую структуру данных для представления восьми основных и порядковых направлений. Каждому направлению полезно знать своих соседей. Например, Direction.North знает, что Direction.NorthEast и Direction.NorthWest являются его соседями.

Это циклично, потому что каждый сосед знает своих соседей до тех пор, пока не пойдет полным ходом ("->" означает по часовой стрелке):

Север -> Северо-Восток -> Восток -> Юго-Восток -> Юг -> Юго-Запад -> Запад -> Северо-Запад -> Север -> ...

Обратите внимание, мы вернулись на Север.

Это позволяет мне делать такие вещи (на C#):

public class Direction
{
    ...
    public IEnumerable<Direction> WithTwoNeighbors
    {
        get {
           yield return this;
           yield return this.CounterClockwise;
           yield return this.Clockwise;
        }
    }
}
...
public void TryToMove (Direction dir)
{
    dir = dir.WithTwoNeighbors.Where (d => CanMove (d)).First ()
    Move (dir);
}

Это оказалось довольно удобным и значительно упростило многие вещи.

Предположим, у вас ограниченное хранилище, и данные постоянно накапливаются. Во многих реальных случаях вы не против избавиться от старых данных, но не хотите их перемещать. Вы можете использовать циклический вектор; реализовано с использованием вектора v размера N с двумя специальными индексами: begin и end, которые начинаются с 0.

Вставка «новых» данных теперь происходит следующим образом:

v[end] = a;
end = (end+1) % N;
if (begin == end)
  begin = (begin+1) % N;

Аналогичным образом вы можете вставить «старые» данные и стереть «старые» или «новые» данные. Сканирование вектора происходит так

for (i=begin; i != end; i = (i+1) % N) {
 // do stuff
}

Циклические структуры данных обычно используются для представления круговых отношений. Звучит очевидно, но случается чаще, чем вы думаете. Я не могу вспомнить ни одного случая, когда я использовал ужасно сложные циклические структуры данных, но двунаправленные отношения довольно распространены. Например, предположим, что я хочу создать IM-клиент. Я мог бы сделать что-то вроде этого:

class Client(object):
    def set_remote(self, remote_client):
        self.remote_client = remote_client

    def send(self, msg):
        self.remote_client.receive(msg)

    def receive(self, msg):
        print msg

Jill = Client()
Bob = Client()
Bob.set_remote(Jill)    
Jill.set_remote(Bob)

Затем, если Боб хотел отправить сообщение Джилл, вы могли просто сделать это:

Bob.send("Hi, Jill!")

Конечно, Джилл может захотеть отправить сообщение, чтобы она могла сделать это:

Jill.send("Hi, Bob!")

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

Любая иерархия объектов, при которой родители знают о своих детях, а дети знают о своих родителях. Мне всегда приходится иметь дело с этим в ORM, потому что я хочу, чтобы базы данных знали свои таблицы и таблицы, чтобы знать, частью какой базы данных они являются, и так далее.

Это немного сбивает с толку, поскольку это список, который содержит сам себя, но я понял, что это не L как список, а узел, и вместо вещей в списке вы думаете об этом как о другом узлы, достижимые этим узлом.

Чтобы привести более реальный пример, подумайте о них как о маршрутах полета из города.

Итак, чикаго = [денвер, лос-анджелес, нью-йорк, чикаго] (на самом деле вы не стали бы перечислять сам по себе Чикаго, но для примера вы можете добраться до Чикаго из Чикаго)

Тогда у вас есть денвер = [феникс, филедельфия] и так далее.

феникс = [чикаго, нью-йорк]

Теперь у вас есть циклические данные как из

chicago -> chicago

но также

chicago -> denver -> phoenix -> chicago

Теперь у вас есть:

chicago[0] == denver
chicago[0][0] == phoenix
chicago[0][0][0] == chicago

L просто содержит ссылку на себя как на один из своих элементов. Ничего особенного в этом нет.

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

Вы можете получить последний элемент L, используя [-1]. Вы можете использовать списки Python в качестве очередей с append() и pop(). Вы можете разделить списки Python. Каковы обычные виды использования циклической структуры данных.

>>> L = ['foo', 'bar']
>>> L.append(L)
>>> L
['foo', 'bar', [...]]
>>> L[0]
'foo'
>>> L[1]
'bar'
>>> L[2]
['foo', 'bar', [...]]
>>> L[2].append('baz')
>>> L
['foo', 'bar', [...], 'baz']
>>> L[2]
['foo', 'bar', [...], 'baz']
>>> L[2].pop()
'baz'
>>> L
['foo', 'bar', [...]]
>>> L[2]
['foo', 'bar', [...]]

Структуры данных, повторяемые детерминированные конечные автоматы, часто бывают циклическими.

Давайте посмотрим на единичный практический пример.

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

1. Название записи
2. Другое меню мы перейдем после нажатия на него.
3. Действие, которое будет выполнено при нажатии на меню.

Когда нажимается элемент меню, мы активируем действие элемента меню, а затем переходим к следующему меню. Итак, наше меню будет представлять собой простой список словарей, например:

options,start_menu,about = [],[],[]

def do_nothing(): pass

about += [
    {'name':"copyright by...",'action':None,'menu':about},
    {'name':"back",'action':do_nothing,'menu':start_menu}
    ]
options += [
    {'name':"volume up",'action':volumeUp,'menu':options},
    {'name':"save",'action':save,'menu':start_menu},
    {'name':"back without save",'action':do_nothing,'menu':start_menu}
    ]
start_menu += [
    {'name':"Exit",'action':f,'menu':None}, # no next menu since we quite
    {'name':"Options",'action':do_nothing,'menu':options},
    {'name':"About",'action':do_nothing,'menu':about}
    ]

Посмотрите, как about цикличен:

>>> print about
[{'action': None, 'menu': [...], 'name': 'copyright by...'},#etc.
# see the ellipsis (...)

Когда нажимается пункт меню, мы запускаем следующую функцию при щелчке:

def menu_item_pressed(item):
    log("menu item '%s' pressed" % item['name'])
    item['action']()
    set_next_menu(item['menu'])

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

Если циклические структуры данных были бы невозможны, нам придется реализовать это самостоятельно, например, пункт меню будет таким:

class SelfReferenceMarkerClass: pass
#singleton global marker for self reference
SelfReferenceMarker = SelfReferenceMarkerClass()
about += [
    {'name':"copyright by...",'action':None,'menu':srm},
    {'name':"back",'action':do_nothing,'menu':start_menu}
    ]

функция menu_item_pressed будет:

def menu_item_pressed(item):
    item['action']()
    if (item['menu'] == SelfReferenceMarker):
        set_next_menu(get_previous_menu())
    else:
        set_next_menu(item['menu'])

Первый пример немного приятнее, но да, отсутствие поддержки ссылок на себя - это не такая уж большая проблема, ИМХО, так как это ограничение легко преодолеть.

Пример меню похож на граф со ссылками на себя, где мы сохраняем граф списками указателей вершин (каждая вершина - это список указателей на другие вершины). В этом примере нам нужны собственные ребра (вершина, указывающая на себя), поэтому поддержка циклических структур данных в Python полезна.