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

Ответ 1

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

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

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

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

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

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

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

Если вы создаете структуру данных, содержащую все города в V и все дороги в E, это структура данных графа. Этот график будет иметь циклы.

Ответ 2

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

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

Север → Северо-Восточный → Восток → Юго-Восточный → Юг → Юго-Запад → Запад → Северо-Запад → Север → ...

Заметьте, что мы вернулись на север.

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

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);
}

Это оказалось очень удобно и многое сделало намного сложнее.

Ответ 3

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

Ответ 4

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

Ответ 5

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

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

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

Тогда у вас есть denver = [phoenix, philedelphia] и т.д.

Феникс = [Чикаго, Нью-Йорк]

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

chicago → chicago

но также

chicago → denver → phoenix → chicago

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

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

Ответ 6

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', [...]]

Ответ 7

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

Ответ 8

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

Ответ 9

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

Ответ 10

Предположим, что у вас ограниченное хранилище, и данные постоянно накапливаются. Во многих случаях в реальной жизни вы не прочь избавиться от старых данных, но не хотите перемещать данные. Вы можете использовать циклический вектор; реализуется с использованием вектора v размера N с двумя специальными индексами: начало и конец, которые начинаются с 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
}

Ответ 11

Циклические структуры данных обычно используются для представления круговых отношений. Это звучит очевидно, но это происходит больше, чем вы думаете. Я не могу думать о том, что я использовал ужасно сложные циклические структуры данных, но двунаправленные отношения довольно распространены. Например, предположим, что я хотел сделать 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!")

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

Ответ 12

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

Ответ 13

Посмотрите на один практический пример.

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

• Имя записи
• В другом меню мы найдем его после нажатия.
• Действие, которое будет выполняться при нажатии меню.

При нажатии пункта меню мы активируем действие пункта меню и перейдем к следующему меню. Таким образом, наше меню будет простым списком словарей, например:

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 для циклических структур данных полезна.