在 python 中的两个双向链表之间传递值
Passing values between two doubly linked lists in python
我想将我的双向链表的值传递到一个新的空双向链表中，这样我就可以在不更改核心链表的情况下对 DLL 中的节点进行排序和删除。
这是它的样子：
dllToBeSorted = DoublyLinkedList()
dllToBeSorted = newDoublyLinkedList #contents of newDoublyLinkedList here: 0 3 0 4 1 1 2 3
dllToBeSorted.sortList()
dllToBeSorted.removeDuplicates()
dllToBeSorted.display() #contents of dllToBeSorted here: 0 1 2 3 4
newDoublyLinkedList.display() #contents of newDoublyLinkedList here: 0 1 2 3 4
但是当我尝试显示值时，两个 DLL 是相同的。我不知道为什么会这样，因为这个方法适用于普通变量（字符串、整数等等），但由于某种原因，它改变了我的两个 DLL。
我将整个可执行代码放在下面：
class Node:
def __init__(self, data):
self.item = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.start_node = None
def insertToEmptyList(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
def insertToEnd(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
return
n = self.start_node
while n.next is not None:
n = n.next
new_node = Node(data)
n.next = new_node
new_node.prev = n
def display(self):
if self.start_node is None:
print(" ")
return
else:
n = self.start_node
while n is not None:
print(n.item, end=" ")
n = n.next
print("\n")
def searchNode(self, data):
if self.start_node is None:
print("0")
return
else:
n = self.start_node
counter = 0
while n is not None:
if n.item == data:
counter += 1
n = n.next
print(counter)
def sortList(self):
if self.start_node is not None:
n = self.start_node
while n.next is not None:
index = n.next
while index is not None:
if n.item > index.item:
temp = n.item
n.item = index.item
index.item = temp
index = index.next
n = n.next
def removeDuplicates(self):
if self.start_node is not None:
n = self.start_node
while n is not None:
index = n.next
while index is not None:
if n.item == index.item:
temp = index
index.prev.next = index.next
if index.next is not None:
index.next.prev = index.prev
temp = None
index = index.next
n = n.next
newDoublyLinkedList = DoublyLinkedList()
newDoublyLinkedList.insertToEnd(0)
newDoublyLinkedList.insertToEnd(3)
newDoublyLinkedList.insertToEnd(0)
newDoublyLinkedList.insertToEnd(4)
newDoublyLinkedList.insertToEnd(1)
newDoublyLinkedList.insertToEnd(1)
newDoublyLinkedList.insertToEnd(2)
newDoublyLinkedList.insertToEnd(3)
dllToBeSorted = DoublyLinkedList()
dllToBeSorted = newDoublyLinkedList #contents of newDoublyLinkedList here: 0 3 0 4 1 1 2 3
dllToBeSorted.sortList()
dllToBeSorted.removeDuplicates()
dllToBeSorted.display() #contents of dllToBeSorted here: 0 1 2 3 4
newDoublyLinkedList.display() #contents of newDoublyLinkedList here: 0 1 2 3 4
这是因为您正在处理指向同一数据结构 (https://www.geeksforgeeks.org/copy-python-deep-copy-shallow-copy/) 的 2 个不同变量。
在 DoublyLinkedList 中覆盖 copy 应该可以解决问题。
def __copy__(self):
newList = DoublyLinkedList()
# add all data from self to newList
return newList
因此您的代码将变为：
dllToBeSorted = DoublyLinkedList()
dllToBeSorted = newDoublyLinkedList.copy() #contents of newDoublyLinkedList here: 0 3 0 4 1 1 2 3
dllToBeSorted.sortList()
dllToBeSorted.removeDuplicates()
dllToBeSorted.display() #contents of dllToBeSorted here: 0 1 2 3 4
newDoublyLinkedList.display() #contents of newDoublyLinkedList here: 0 1 2 3 4
要理解您的问题，您必须理解这个小例子。
my_data = [1,2,3]
def my_func(data):
data.append(100)
return data
print("You sent: ", my_data)
# Calling my function to add an element to the list and returning the result
result_data = my_func(my_data)
print("I changed it to: ", result_data)
print("Your original input: ", my_data)
我们没想到作为参数传递的列表会被修改，但它被修改了。详细答案可以阅读this article
所以基本上您是在幕后对原始 lists/items 执行所有排序操作，并且您的显示功能会获得相同的输出。
您可以使用 python 列表复制功能（或为您的 class 创建一个实现）
为了使我的示例按预期工作，您可以使用
调用函数 my_func
# result_data = my_func(my_data) Old way
result_data = my_func( my_data.copy() )
我建议采用不同的方法。
制作双向链表：
- 循环，包括一个哨兵节点。这个哨兵节点可以通过从
Node. 继承 DoublyLinkedList 来实例化
- 可迭代，无需重复代码即可轻松迭代、打印、搜索
- 使用本机排序作为解决方案（这是值得商榷的，但至少它会比冒泡排序更快）。
排序时- 到return一个新列表，而不是就地排序
- 使用带有可选参数的构造函数来填充列表
让 Node 构造函数为其 prev/next 属性采用可选参数，并为其提供一个 isolate 方法，使其与邻居分离，缩小差距，因此这些邻居成为彼此的邻居。
看看这种方法给您的代码带来了什么：
class Node:
def __init__(self, data=None, prev=None, nxt=None): # optional arguments
self.item = data
# Avoid that any next/prev becomes None. Should always reference a Node
self.next = nxt or self # default to referring to itself
self.prev = prev or self
# Make consistent
self.next.prev = self
self.prev.next = self
# Method to detach the node from its neighbors
def isolate(self):
self.prev.next = self.next
self.next.prev = self.prev
self.next = self.prev = self
# Subclassing makes the list a sentinel node.
# It does not count as a data node, but its next attribute will
# reference the first node (if any, else itself), and its prev
# attribute will reference the last node (if any, else itself)
class DoublyLinkedList(Node):
def __init__(self, *values):
super().__init__()
for data in values:
self.insertToEnd(data)
def insertToFront(self, data):
Node(data, self, self.next)
def insertToEnd(self, data):
Node(data, self.prev, self)
def __iter__(self): # This is very useful to have!!
node = self.next
while node is not self:
yield node.item
node = node.next
def __repr__(self):
return " ".join(map(repr, self))
def display(self): # Not really needed, as
print(self) # ... the list is printable
def search(self, data):
# Return the index of first occurrence, -1 if not found:
return next((i for i, item in enumerate(self) if item == data), -1)
def sorted(self):
return DoublyLinkedList(*sorted(self))
def removeDuplicates(self):
node = self.next
while node.next is not self:
if node.item == node.next.item:
node.next.isolate()
else:
node = node.next
myList = DoublyLinkedList(0, 3, 0, 4, 1, 1, 2 ,3)
print(myList)
mySorted = myList.sorted()
mySorted.removeDuplicates()
print(mySorted) # 1 2 3 4
我想将我的双向链表的值传递到一个新的空双向链表中，这样我就可以在不更改核心链表的情况下对 DLL 中的节点进行排序和删除。
这是它的样子：
dllToBeSorted = DoublyLinkedList()
dllToBeSorted = newDoublyLinkedList #contents of newDoublyLinkedList here: 0 3 0 4 1 1 2 3
dllToBeSorted.sortList()
dllToBeSorted.removeDuplicates()
dllToBeSorted.display() #contents of dllToBeSorted here: 0 1 2 3 4
newDoublyLinkedList.display() #contents of newDoublyLinkedList here: 0 1 2 3 4
但是当我尝试显示值时，两个 DLL 是相同的。我不知道为什么会这样，因为这个方法适用于普通变量（字符串、整数等等），但由于某种原因，它改变了我的两个 DLL。
我将整个可执行代码放在下面：
class Node:
def __init__(self, data):
self.item = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.start_node = None
def insertToEmptyList(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
def insertToEnd(self, data):
if self.start_node is None:
new_node = Node(data)
self.start_node = new_node
return
n = self.start_node
while n.next is not None:
n = n.next
new_node = Node(data)
n.next = new_node
new_node.prev = n
def display(self):
if self.start_node is None:
print(" ")
return
else:
n = self.start_node
while n is not None:
print(n.item, end=" ")
n = n.next
print("\n")
def searchNode(self, data):
if self.start_node is None:
print("0")
return
else:
n = self.start_node
counter = 0
while n is not None:
if n.item == data:
counter += 1
n = n.next
print(counter)
def sortList(self):
if self.start_node is not None:
n = self.start_node
while n.next is not None:
index = n.next
while index is not None:
if n.item > index.item:
temp = n.item
n.item = index.item
index.item = temp
index = index.next
n = n.next
def removeDuplicates(self):
if self.start_node is not None:
n = self.start_node
while n is not None:
index = n.next
while index is not None:
if n.item == index.item:
temp = index
index.prev.next = index.next
if index.next is not None:
index.next.prev = index.prev
temp = None
index = index.next
n = n.next
newDoublyLinkedList = DoublyLinkedList()
newDoublyLinkedList.insertToEnd(0)
newDoublyLinkedList.insertToEnd(3)
newDoublyLinkedList.insertToEnd(0)
newDoublyLinkedList.insertToEnd(4)
newDoublyLinkedList.insertToEnd(1)
newDoublyLinkedList.insertToEnd(1)
newDoublyLinkedList.insertToEnd(2)
newDoublyLinkedList.insertToEnd(3)
dllToBeSorted = DoublyLinkedList()
dllToBeSorted = newDoublyLinkedList #contents of newDoublyLinkedList here: 0 3 0 4 1 1 2 3
dllToBeSorted.sortList()
dllToBeSorted.removeDuplicates()
dllToBeSorted.display() #contents of dllToBeSorted here: 0 1 2 3 4
newDoublyLinkedList.display() #contents of newDoublyLinkedList here: 0 1 2 3 4
这是因为您正在处理指向同一数据结构 (https://www.geeksforgeeks.org/copy-python-deep-copy-shallow-copy/) 的 2 个不同变量。 在 DoublyLinkedList 中覆盖 copy 应该可以解决问题。
def __copy__(self):
newList = DoublyLinkedList()
# add all data from self to newList
return newList
因此您的代码将变为：
dllToBeSorted = DoublyLinkedList()
dllToBeSorted = newDoublyLinkedList.copy() #contents of newDoublyLinkedList here: 0 3 0 4 1 1 2 3
dllToBeSorted.sortList()
dllToBeSorted.removeDuplicates()
dllToBeSorted.display() #contents of dllToBeSorted here: 0 1 2 3 4
newDoublyLinkedList.display() #contents of newDoublyLinkedList here: 0 1 2 3 4
要理解您的问题，您必须理解这个小例子。
my_data = [1,2,3]
def my_func(data):
data.append(100)
return data
print("You sent: ", my_data)
# Calling my function to add an element to the list and returning the result
result_data = my_func(my_data)
print("I changed it to: ", result_data)
print("Your original input: ", my_data)
我们没想到作为参数传递的列表会被修改，但它被修改了。详细答案可以阅读this article
所以基本上您是在幕后对原始 lists/items 执行所有排序操作，并且您的显示功能会获得相同的输出。
您可以使用 python 列表复制功能（或为您的 class 创建一个实现）
为了使我的示例按预期工作，您可以使用
调用函数 my_func# result_data = my_func(my_data) Old way
result_data = my_func( my_data.copy() )
我建议采用不同的方法。
制作双向链表：
- 循环，包括一个哨兵节点。这个哨兵节点可以通过从
Node. 继承 - 可迭代，无需重复代码即可轻松迭代、打印、搜索
- 使用本机排序作为解决方案（这是值得商榷的，但至少它会比冒泡排序更快）。 排序时
- 到return一个新列表，而不是就地排序
- 使用带有可选参数的构造函数来填充列表
DoublyLinkedList 来实例化
让 Node 构造函数为其 prev/next 属性采用可选参数，并为其提供一个 isolate 方法，使其与邻居分离，缩小差距，因此这些邻居成为彼此的邻居。
看看这种方法给您的代码带来了什么：
class Node:
def __init__(self, data=None, prev=None, nxt=None): # optional arguments
self.item = data
# Avoid that any next/prev becomes None. Should always reference a Node
self.next = nxt or self # default to referring to itself
self.prev = prev or self
# Make consistent
self.next.prev = self
self.prev.next = self
# Method to detach the node from its neighbors
def isolate(self):
self.prev.next = self.next
self.next.prev = self.prev
self.next = self.prev = self
# Subclassing makes the list a sentinel node.
# It does not count as a data node, but its next attribute will
# reference the first node (if any, else itself), and its prev
# attribute will reference the last node (if any, else itself)
class DoublyLinkedList(Node):
def __init__(self, *values):
super().__init__()
for data in values:
self.insertToEnd(data)
def insertToFront(self, data):
Node(data, self, self.next)
def insertToEnd(self, data):
Node(data, self.prev, self)
def __iter__(self): # This is very useful to have!!
node = self.next
while node is not self:
yield node.item
node = node.next
def __repr__(self):
return " ".join(map(repr, self))
def display(self): # Not really needed, as
print(self) # ... the list is printable
def search(self, data):
# Return the index of first occurrence, -1 if not found:
return next((i for i, item in enumerate(self) if item == data), -1)
def sorted(self):
return DoublyLinkedList(*sorted(self))
def removeDuplicates(self):
node = self.next
while node.next is not self:
if node.item == node.next.item:
node.next.isolate()
else:
node = node.next
myList = DoublyLinkedList(0, 3, 0, 4, 1, 1, 2 ,3)
print(myList)
mySorted = myList.sorted()
mySorted.removeDuplicates()
print(mySorted) # 1 2 3 4