什么是循环数据结构有用？

Question

我刚刚阅读”学习Python“作者Mark Lutz发现了这个代码示例：

>>> L = ['grail']
>>> L.append(L)
>>> L
['grail', [...]]

它被确定为循环数据结构。

所以我很想知道，这是我的问题：

在现实生活中使用什么“循环数据结构”？

似乎有点混乱，我认为这源于非常简短的代码示例......这里有几行使用相同的对象L

>>> L[0]
'grail'
>>> L[1][0]
'grail'
>>> L[1][1][0]
'grail'

Answer 1

很多事情。循环缓冲区，例如：你有一些前面和后面的数据集合，但有任意数量的节点，以及“下一个”节点。最后一项应该带你回到第一项。

图形结构通常是循环的; acyclicity是一个特例。例如，考虑一个包含旅行商问题中所有城市和道路的图表。

---

好的，这是一个特别的例子。我在科罗拉多州建立了一系列城镇：

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

然后，我建立了一对连接它们的道路的城市。

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

这有一堆循环。例如，您可以从科罗拉多斯普林斯，利蒙到丹佛，然后返回科罗拉多斯普林斯。

如果您创建的数据结构包含V中的所有城市和E中的所有道路，那么这就是图形数据结构。这个图表有周期。

Answer 2

我最近创建了一个循环数据结构来表示八个基本和有序方向。它对每个方向都有用，可以了解它的邻居。例如，Direction.North知道Direction.NorthEast和Direction.NorthWest是它的邻居。

这是循环的，因为每个neighor都知道它的邻居，直到它全速摆动（“ - ＆gt;”表示顺时针方向）：

北 - ＆gt; NorthEast - ＆gt;东 - ＆gt; SouthEast - ＆gt;南 - ＆gt; SouthWest - ＆gt;西 - ＆gt; NorthWest - ＆gt;北 - ＆gt; ...

请注意我们回到了北方。

这允许我做这样的事情（在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);
}

事实证明这非常方便，并且使很多事情变得复杂得多。

Answer 3

嵌套结构可用于垃圾收集器的测试用例。

Answer 4

它有点令人困惑，因为它是一个包含自身的列表，但我理解它的方式是不将L视为列表，而是一个节点，而不是列表中的东西，你想到的它可以作为此节点可以访问的其他节点。

举一个更真实的例子，把它们想象成一个城市的飞行路径。

所以chicago = [丹佛，洛杉矶，纽约市，芝加哥]（实际上你不会列出芝加哥本身，但为了举例，你可以从芝加哥到达芝加哥）

然后你有丹佛= [凤凰，菲利普]等等。

phoenix = [芝加哥，纽约]

现在你有来自

的循环数据

  

芝加哥 - ＆gt;芝加哥

但也

  

芝加哥 - ＆gt;丹佛 - ＆gt;凤凰 - ＆gt;芝加哥

现在你有：

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

Answer 5

确定性有限自动机迭代的数据结构通常是周期性的。

Answer 6

L 只包含对自身的引用作为其中一个元素。没什么特别的。

循环结构有一些明显的用途，其中最后一个元素知道第一个元素。但是常规python列表已经涵盖了这个功能。

您可以使用 [ - 1] 获取 L 的最后一个元素。您可以将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', [...]]

Answer 7

一个例子是一个链表，其中最后一个项指向第一个。这将允许您创建固定数量的项目，但始终能够获得下一个项目。

Answer 8

在进行晶格模拟时，经常使用循环/环形边界条件。通常一个简单的 lattice [i％L] 就足够了，但我想人们可以创建一个循环的格子。

Answer 9

假设您的存储空间有限，并且数据会不断累积。在许多现实生活中，您不介意删除旧数据，但您不想移动数据。你可以使用循环向量;使用大小为N的向量v和两个特殊索引实现：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
}

Answer 10

任何类型的对象层次结构，父母知道他们的孩子和孩子都知道他们的父母。我总是不得不在ORM中处理这个问题，因为我希望数据库知道他们的表和表，以了解他们所属的数据库，等等。

Answer 11

让我们看一个实际的例子。

让我们说我们正在为游戏编写菜单导航。我们想为每个菜单项存储

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对循环数据结构的支持很有用。

Answer 12

循环数据结构通常用于表示循环关系。这听起来很明显，但它的发生比你想象的要多。我无法想到任何时候我都使用了非常复杂的循环数据结构，但双向关系相当普遍。例如，假设我想创建一个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想要向Jill发送消息，你可以这样做：

Bob.send("Hi, Jill!")

当然，吉尔可能想要回复一条消息，所以她可以这样做：

Jill.send("Hi, Bob!")

不可否认，这是一个人为的例子，但它应该为您提供一个何时可能需要使用循环数据结构的示例。