14

我刚刚阅读了 Mark Lutz 的“Learning Python”并遇到了这个代码示例：


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

它被识别为循环数据结构。

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

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

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


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

12 回答 12

17

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

图结构通常是循环的；非周期性是一种特殊情况。例如，考虑一个包含旅行商问题中所有城市和道路的图。

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

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

然后，我建立了成对的城市，其中有一条连接它们的道路。

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

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

如果创建一个数据结构，其中包含 V 中的所有城市和 E 中的所有道路，那就是图数据结构。该图将具有循环。

于 2009-01-01T22:17:30.567 回答
6

我最近创建了一个循环数据结构来表示八个基数和序数方向。它对每个方向了解其邻居很有用。例如，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);
}

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

于 2009-01-01T22:21:42.600 回答
1

可以在垃圾收集器的测试用例中使用嵌套结构。

于 2009-01-01T22:18:04.310 回答
1

这有点令人困惑，因为它是一个包含自身的列表，但我理解它的方式是不要将 L 视为一个列表，而是一个节点，而不是列表中的事物，您将其视为其他此节点可访问的节点。

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

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

然后你有 denver = [phoenix, philedelphia] 等等。

凤凰 = [芝加哥，纽约市]

现在你有来自的循环数据

芝加哥 -> 芝加哥

但是也

芝加哥 -> 丹佛 -> 凤凰城 -> 芝加哥

现在你有：

chicago[0] == denver
chicago[0][0] == phoenix
chicago[0][0][0] == chicago
于 2009-05-27T21:58:11.030 回答
1

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', [...]]
于 2009-05-27T22:38:53.210 回答
1

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

于 2009-05-27T23:35:20.757 回答
0

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

于 2009-01-01T22:17:08.897 回答
0

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

于 2009-01-01T22:17:42.157 回答
0

假设您的存储空间有限，并且数据不断累积。在许多现实生活中，您不介意删除旧数据，但您不想移动数据。您可以使用循环向量；使用具有两个特殊索引的大小为 N 的向量 v 实现：开始和结束，它们从 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
}
于 2009-01-01T22:37:49.637 回答
0

循环数据结构通常用于表示循环关系。这听起来很明显，但它发生的次数比你想象的要多。我想不出任何时候我使用过非常复杂的循环数据结构，但双向关系相当普遍。例如，假设我想做一个 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 可能想发回一条消息，所以她可以这样做：

Jill.send("Hi, Bob!")

诚然，这是一个人为的例子，但它应该为您提供一个示例，说明您何时可能想要使用循环数据结构。

于 2009-05-27T21:27:11.453 回答
0

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

于 2009-05-27T21:32:23.500 回答
0

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

假设我们正在为游戏编写菜单导航。我们要为每个菜单项存储

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

于 2009-05-28T07:00:04.310 回答