如何从循环链表中删除重复项
How to remove duplicates from circular linked list
我的代码如下。它将一些数字附加到循环列表中。我的程序运行良好。它给出 [5,3,3] 或输入的任何数字的精确输出。但我想对输出进行一些更改。在不添加任何新函数的情况下,在 def append(....)
和 def add_before(...)
中进行什么样的更改,因此它提供了一个唯一的数字,这意味着它摆脱了重复项。例如,将给出 [5,3]
class CirList:
def __init__(self):
head_node = NodeDLL(None)
head_node.next = head_node
head_node.prev = head_node
self.__head = head_node
def append(self, item):
curr = self.__head
new_node = NodeDLL(item, curr, curr.get_prev())
curr.set_prev(new_node)
new_node.get_prev().set_next(new_node)
def add_before(self, item, old_item):
curr = self.__head.next
found = False
while curr.get_data() != None and not found:
if curr.get_data() == old_item:
found = True
else:
curr = curr.get_next()
if found:
new_node = NodeDLL(item, curr, curr.get_prev())
curr.set_prev(new_node)
new_node.get_prev().set_next(new_node)
return found
def remove(self, item):
curr = self.__head.next
found = False
while curr.get_data() != None and not found:
if curr.get_data() == item:
found = True
else:
curr = curr.get_next()
if found:
curr.get_prev().set_next(curr.get_next())
curr.get_next().set_prev(curr.get_prev())
def printall(self):
curr = self.__head.next
while curr.get_data() != None:
print(curr.get_data(), end=" ")
curr = curr.get_next()
print()
def __str__(self):
result = "["
curr = self.__head.next
while curr.get_data() != None:
result += str(curr.get_data()) + " "
curr = curr.get_next()
result = result.rstrip(" ")
result += "]"
return result
测试
listA = CirList()
listA.append(5)
listA.append(3)
listA.append(3)
print(listA)
两个选项(我能想到的):
不要重复添加:
class CirList:
def __init__(self):
head_node = NodeDLL(None)
head_node.next = head_node
head_node.prev = head_node
self.__head = head_node
self._knownNumbers = set() # optimized lookup if number known
def append(self, item):
if item not in self._knownNumbers: # only add if not known
self.__knownNumbers__.add(item)
curr = self.__head
new_node = NodeDLL(item, curr, curr.get_prev())
curr.set_prev(new_node)
new_node.get_prev().set_next(new_node)
def add_before(self, item, old_item):
if item not in self._knownNumbers: # only add if not known
self.__knownNumbers__.add(item)
curr = self.__head.next
found = False
while curr.get_data() != None and not found:
if curr.get_data() == old_item:
found = True
else:
curr = curr.get_next()
if found:
new_node = NodeDLL(item, curr, curr.get_prev())
curr.set_prev(new_node)
new_node.get_prev().set_next(new_node)
return found
def remove(self, item):
self._knownNumbers.remove(item) # forget this number again
curr = self.__head.next
found = False
while curr.get_data() != None and not found:
if curr.get_data() == item:
found = True
else:
curr = curr.get_next()
if found:
curr.get_prev().set_next(curr.get_next())
curr.get_next().set_prev(curr.get_prev())
或者干脆不要重复打印:
def __str__(self):
result = "["
curr = self.__head.next
known = set() # keep what we added already
while curr.get_data() != None:
if curr.get_data() not in known: # only add if not yet added
result += str(curr.get_data()) + " "
known.add(curr.get_data()) # remember this one
curr = curr.get_next()
result = result.rstrip(" ")
result += "]"
return result
如果你想让它模仿这种行为,你必须相应地修改你的 printall()
- 你仍然会存储所有重复项,所以对我来说没有多大意义,除非你创建一个单独的 def printNoDuplicates(self)
专门用于此目的。
我的代码如下。它将一些数字附加到循环列表中。我的程序运行良好。它给出 [5,3,3] 或输入的任何数字的精确输出。但我想对输出进行一些更改。在不添加任何新函数的情况下,在 def append(....)
和 def add_before(...)
中进行什么样的更改,因此它提供了一个唯一的数字,这意味着它摆脱了重复项。例如,将给出 [5,3]
class CirList:
def __init__(self):
head_node = NodeDLL(None)
head_node.next = head_node
head_node.prev = head_node
self.__head = head_node
def append(self, item):
curr = self.__head
new_node = NodeDLL(item, curr, curr.get_prev())
curr.set_prev(new_node)
new_node.get_prev().set_next(new_node)
def add_before(self, item, old_item):
curr = self.__head.next
found = False
while curr.get_data() != None and not found:
if curr.get_data() == old_item:
found = True
else:
curr = curr.get_next()
if found:
new_node = NodeDLL(item, curr, curr.get_prev())
curr.set_prev(new_node)
new_node.get_prev().set_next(new_node)
return found
def remove(self, item):
curr = self.__head.next
found = False
while curr.get_data() != None and not found:
if curr.get_data() == item:
found = True
else:
curr = curr.get_next()
if found:
curr.get_prev().set_next(curr.get_next())
curr.get_next().set_prev(curr.get_prev())
def printall(self):
curr = self.__head.next
while curr.get_data() != None:
print(curr.get_data(), end=" ")
curr = curr.get_next()
print()
def __str__(self):
result = "["
curr = self.__head.next
while curr.get_data() != None:
result += str(curr.get_data()) + " "
curr = curr.get_next()
result = result.rstrip(" ")
result += "]"
return result
测试
listA = CirList()
listA.append(5)
listA.append(3)
listA.append(3)
print(listA)
两个选项(我能想到的):
不要重复添加:
class CirList:
def __init__(self):
head_node = NodeDLL(None)
head_node.next = head_node
head_node.prev = head_node
self.__head = head_node
self._knownNumbers = set() # optimized lookup if number known
def append(self, item):
if item not in self._knownNumbers: # only add if not known
self.__knownNumbers__.add(item)
curr = self.__head
new_node = NodeDLL(item, curr, curr.get_prev())
curr.set_prev(new_node)
new_node.get_prev().set_next(new_node)
def add_before(self, item, old_item):
if item not in self._knownNumbers: # only add if not known
self.__knownNumbers__.add(item)
curr = self.__head.next
found = False
while curr.get_data() != None and not found:
if curr.get_data() == old_item:
found = True
else:
curr = curr.get_next()
if found:
new_node = NodeDLL(item, curr, curr.get_prev())
curr.set_prev(new_node)
new_node.get_prev().set_next(new_node)
return found
def remove(self, item):
self._knownNumbers.remove(item) # forget this number again
curr = self.__head.next
found = False
while curr.get_data() != None and not found:
if curr.get_data() == item:
found = True
else:
curr = curr.get_next()
if found:
curr.get_prev().set_next(curr.get_next())
curr.get_next().set_prev(curr.get_prev())
或者干脆不要重复打印:
def __str__(self):
result = "["
curr = self.__head.next
known = set() # keep what we added already
while curr.get_data() != None:
if curr.get_data() not in known: # only add if not yet added
result += str(curr.get_data()) + " "
known.add(curr.get_data()) # remember this one
curr = curr.get_next()
result = result.rstrip(" ")
result += "]"
return result
如果你想让它模仿这种行为,你必须相应地修改你的 printall()
- 你仍然会存储所有重复项,所以对我来说没有多大意义,除非你创建一个单独的 def printNoDuplicates(self)
专门用于此目的。