循环链表代码进入死循环
Circular linked list code is getting into infinite loop
我是这样定义循环链表的
class Link(object):
def __init__ (self, data, next = None):
self.data = data
self.next = next
class CircularList(object):
def __init__ ( self ):
self.first = Link(None, None)
self.first.next = self.first
def insert_first ( self, item ):
new_link = Link(item)
new_link.next = self.first
self.first = new_link
def __iter__(self):
current = self.first
first = current
while current.next != first:
yield current
current = current.next
def __str__(self):
return str([Link.data for Link in self])
def __repr__(self):
return self.__str__()
然后我将项目添加到我的列表中
a = CircularList()
a.insert_first(4)
a.insert_first(5)
我想用字符串表示我的循环列表,但看起来 __iter__()
正在无限循环。我可以正确定义我的迭代器,并获得正确的字符串表示吗?
我会分解步骤。
首先,我将 Link
重命名为 Node
。
class Node(object):
def __init__(self, data, next=None):
self.data = data
self.next = next
链接与节点不同 - 节点保存您的数据,而链接将两个节点连接在一起。
接下来,CircularList
class,需要一些修改。
__init__
将需要初始化一个 空 列表。这意味着根本没有节点 。为了方便起见,我把self.last
定义为大大简化了代码(注意,大大,你会比较辛苦的其他事情)。
class CircularList(object):
def __init__(self):
self.first = self.last = None
对于insert_first
,您需要处理列表为空时的极端情况和一般情况。相应地更新 self.first
和 self.last
。
def insert_first(self, item):
if self.first is None:
self.first = self.last = Node(item)
self.first.next = self.first
else:
self.first = Node(item, self.first)
self.last.next = self.first
您的__iter__
方法也应该以实物回应。内联评论。
def __iter__(self):
# corner case - yield empty list
if not self.first:
yield []
else:
# start by yielding the head node
yield self.first
cur = self.first.next
# iterate as long as you do not see the head node again
while cur is not self.first:
yield cur
cur = cur.next
其他方法不变。测试代码:
a = CircularList()
for i in [5, 4, 3, 2, 1]:
a.insert_first(i)
print(a)
[1, 2, 3, 4, 5]
完整代码清单
class Node(object):
def __init__(self, data, next=None):
self.data = data
self.next = next
class CircularList(object):
def __init__(self):
self.first = self.last = None
def insert_first(self, item):
if self.first is None:
self.first = self.last = Node(item)
self.first.next = self.first
else:
self.first = Node(item, self.first)
self.last.next = self.first
def __iter__(self):
if not self.first:
yield []
else:
yield self.first
cur = self.first.next
while cur is not self.first:
yield cur
cur = cur.next
def __str__(self):
return str([Link.data for Link in self])
def __repr__(self):
return self.__str__()
我是这样定义循环链表的
class Link(object):
def __init__ (self, data, next = None):
self.data = data
self.next = next
class CircularList(object):
def __init__ ( self ):
self.first = Link(None, None)
self.first.next = self.first
def insert_first ( self, item ):
new_link = Link(item)
new_link.next = self.first
self.first = new_link
def __iter__(self):
current = self.first
first = current
while current.next != first:
yield current
current = current.next
def __str__(self):
return str([Link.data for Link in self])
def __repr__(self):
return self.__str__()
然后我将项目添加到我的列表中
a = CircularList()
a.insert_first(4)
a.insert_first(5)
我想用字符串表示我的循环列表,但看起来 __iter__()
正在无限循环。我可以正确定义我的迭代器,并获得正确的字符串表示吗?
我会分解步骤。
首先,我将 Link
重命名为 Node
。
class Node(object):
def __init__(self, data, next=None):
self.data = data
self.next = next
链接与节点不同 - 节点保存您的数据,而链接将两个节点连接在一起。
接下来,CircularList
class,需要一些修改。
__init__
将需要初始化一个 空 列表。这意味着根本没有节点 。为了方便起见,我把self.last
定义为大大简化了代码(注意,大大,你会比较辛苦的其他事情)。
class CircularList(object):
def __init__(self):
self.first = self.last = None
对于insert_first
,您需要处理列表为空时的极端情况和一般情况。相应地更新 self.first
和 self.last
。
def insert_first(self, item):
if self.first is None:
self.first = self.last = Node(item)
self.first.next = self.first
else:
self.first = Node(item, self.first)
self.last.next = self.first
您的__iter__
方法也应该以实物回应。内联评论。
def __iter__(self):
# corner case - yield empty list
if not self.first:
yield []
else:
# start by yielding the head node
yield self.first
cur = self.first.next
# iterate as long as you do not see the head node again
while cur is not self.first:
yield cur
cur = cur.next
其他方法不变。测试代码:
a = CircularList()
for i in [5, 4, 3, 2, 1]:
a.insert_first(i)
print(a)
[1, 2, 3, 4, 5]
完整代码清单
class Node(object):
def __init__(self, data, next=None):
self.data = data
self.next = next
class CircularList(object):
def __init__(self):
self.first = self.last = None
def insert_first(self, item):
if self.first is None:
self.first = self.last = Node(item)
self.first.next = self.first
else:
self.first = Node(item, self.first)
self.last.next = self.first
def __iter__(self):
if not self.first:
yield []
else:
yield self.first
cur = self.first.next
while cur is not self.first:
yield cur
cur = cur.next
def __str__(self):
return str([Link.data for Link in self])
def __repr__(self):
return self.__str__()