Ich habe Probleme bei der Implementierung einer tiefen Kopiermethode für eine DoublyLinkedList Klasse. Eine tiefe Kopie soll eine neue, ursprüngliche Doppelliste zurückgeben, die nicht auf die ursprüngliche DLL verweist (im Gegensatz zu einer flachen Kopie).Tiefe Kopie einer doppelt verknüpften Liste in Python
Hier ist, was ich bisher:
class EmptyCollection(Exception):
pass
class DoublyLinkedList:
class Node:
def __init__(self, data=None, next=None, prev=None):
self.data = data
self.next = next
self.prev = prev
def disconnect(self):
self.data = None
self.next = None
self.prev = None
def __init__(self):
self.header = DoublyLinkedList.Node()
self.trailer = DoublyLinkedList.Node()
self.header.next = self.trailer
self.trailer.prev = self.header
self.size = 0
def __len__(self):
return self.size
def is_empty(self):
return (len(self) == 0)
def first_node(self):
if (self.is_empty()):
raise EmptyCollection("List is empty")
return self.header.next
def last_node(self):
if (self.is_empty()):
raise EmptyCollection("List is empty")
return self.trailer.prev
def add_first(self, elem):
return self.add_after(self.header, elem)
def add_last(self, elem):
return self.add_after(self.trailer.prev, elem)
def add_after(self, node, elem):
prev = node
succ = node.next
new_node = DoublyLinkedList.Node()
new_node.data = elem
new_node.prev = prev
new_node.next = succ
prev.next = new_node
succ.prev = new_node
self.size += 1
return new_node
def add_before(self, node, elem):
return self.add_after(node.prev, elem)
def delete(self, node):
prev = node.prev
succ = node.next
prev.next = succ
succ.prev = prev
self.size -= 1
data = node.data
node.disconnect()
return data
def __iter__(self):
if(self.is_empty()):
return
cursor = self.first_node()
while(cursor is not self.trailer):
yield cursor.data
cursor = cursor.next
def __str__(self):
return '[' + '<-->'.join([str(elem) for elem in self]) + ']'
def __repr__(self):
return str(self)
def deepCopy(lnk_lst):
currenthead = lnk_lst.first_node()
temp = DoublyLinkedList()
while currenthead is not lnk_lst.trailer:
temp.add_last(currenthead.data)
currenthead = currenthead.next
return temp
lnk_lst1 = DoublyLinkedList()
elem1 = DoublyLinkedList()
elem1.add_last(1)
elem1.add_last(2)
lnk_lst1.add_last(elem1)
elem2 = 3
lnk_lst1.add_last(elem2)
lnk_lst2 = deepCopy(lnk_lst1)
e1 = lnk_lst1.first_node()
e1_1 = e1.data.first_node()
e1_1.data = 10
e2 = lnk_lst2.first_node()
e2_1 = e2.data.first_node()
print(e2_1.data) #should print 1
Meine tiefe Kopie Methode scheint eine flache Kopie zurückzukehren. Die Ausgabe des Programms sollte 1 sein (da lnk_lst2 keine Elemente in lnk_lst1 referenzieren sollte.)
Kann jemand erklären, wie ich meine tiefe Kopiermethode ändern kann, um eine tiefe Kopie der verknüpften Liste und nicht eine flache Kopie zu erzeugen?
Ich kann Python eingebaute tiefe oder flache Kopie dafür nicht verwenden. Jede Hilfe wäre willkommen.
Ihr Beispiel ist ein wenig verwirrend. Warum ist Element1 eine Liste und kein Knoten? – RobertB
Da Sie nur eine flache Kopie geschrieben haben: 'temp.add_last (currenthead.data)' fügt das gleiche Objekt aus der Liste hinzu, die Sie in die Kopie kopieren. Das ist * eine flache Kopie. Normalerweise muss eine 'deepcopy'-Funktion rekursiv auf den Objekten arbeiten, also etwas wie 'temp.add_last (deepCopy (currenthead.data))', und Ihre' deepCopy' muss wissen, wie sie mit den erwarteten Objekten umgeht . –
Beachten Sie, dass dies ziemlich schnell ziemlich kompliziert werden kann, wenn Ihre 'deepCopy'-Funktion * irgendein beliebiges Objekt * erwartet. –