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

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

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

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

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

Север-> NorthEast-> Восток-> SouthEast-> Юг-> SouthWest-> Запад-> 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);
}

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

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

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

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

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

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

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

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

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

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

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}
    ]

Посмотрите, как о является циклическим:

>>> 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 полезна.

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 полезна.

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 полезна.

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

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

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

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

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

Затем у вас есть denver = [phoenix, philedelphia] и так далее.

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

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

чикаго -> чикаго

, так и из

чикаго -> денвер -> феникс -> чикаго

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

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