einen Knoten an das Ende einer Kette von Knoten bewegen

Question

I eine Funktion haben, wo ich einen vorhandenen Code beispielsweise bewegen

def print_chain_and_ids(chain): 
    current = chain 
    while current != None: 
     print(id(current), current.get_data()) 
     current = current.get_next() 

a = Node('first') 
b = Node('middle') 
c = Node('last') 
a.set_next(b) 
b.set_next(c) 

print_chain_and_ids(a) 
move_node_to_end(a, 'middle')  

print_chain_and_ids(a) 

so dass nun die Kette geht:

a ----> b ----> c

mit dem Knoten c am Ende der Kette.

Wenn ich wollte den Knoten b bis zum Ende der Kette bewegen, so geht es:

a ----> c ----> b

so, dass es nicht den Wert des letzten Knotens ändert sich aber gerade bewegt er sich um. Ich habe eine Knoten-Klasse bereit:

class Node: 
    def __init__(self, init_data): 
     self.data = init_data 
     self.next = None 

    def get_data(self): 
     return self.data 

    def get_next(self): 
     return self.next 

    def set_data(self, new_data): 
     self.data = new_data 

    def set_next(self, new_next): 
     self.next = new_next 

    def __str__(self): 
     return str(self.data) 

Ich wollte wissen, wie ich das tun würde.

Ich möchte machen, um eine Funktion zu machen, die zwei Eingänge, der erste Knoten der Kette, und auch der Wert, der auf die letzte Position der Kette bewegt. Also:

def node_to_end(first_node, value_to_move): 
    ..... 

Hier muss ich die Position der Knoten ändern. Dieser zu bewegende Wert geht also zur letzten Position.

a = Node('blue') 
b = Node('red') 
c = Node('green') 

a.set_next(b) 
b.set_next(c) 

, die in blue red green

node_to_end(a, 'red') 

führen würde würde eine Kette von

blue green red

Danke für jede Hilfe erstellen.

Answer 1

Ihre Knotenkette ist der sogenannten Einfachverknüpfungsliste sehr ähnlich.Mit diesen werden Knoten typischerweise entfernt, indem der vorherige Knoten während des Durchquerens der Liste verfolgt wird, so dass, wenn der Zielknoten gefunden wird, du weißt, welcher (wenn überhaupt) davor kam. Mit dieser Information kann die Liste leicht geändert werden.

So wenden Sie das auf Ihren Code an. Ich habe auch ein kleines Dienstprogramm hinzugefügt, um den Inhalt von Ketten zu drucken, um klarzustellen, was in ihnen steckt.

class Node: 
    def __init__(self, init_data): 
     self.data = init_data 
     self.next = None 

    def get_data(self): 
     return self.data 

    def get_next(self): 
     return self.next 

    def set_data(self, new_data): 
     self.data = new_data 

    def set_next(self, new_next): 
     self.next = new_next 

    def __str__(self): 
     return str(self.data) 

def move_to_end(start, target): 
    """Move target node from the chain beginning with start to end.""" 
    previous = None 
    current = start 
    while current: 
     if current.get_next() is target: 
      previous = current 
      break 
     current = current.get_next() 

    if previous: # target found in chain? 
     previous.set_next(target.get_next()) # remove it 
     # and move it to the end 
     current = target 
     while current: 
      if not current.get_next(): # last node in chain? 
       target.set_next(None) 
       current.set_next(target) 
       break 
      current = current.get_next() 

def print_node_chain(start): 
    """Utility to print out a node chain starting from given node.""" 
    values = [] 
    current = start 
    while current: 
     values.append(str(current)) 
     current = current.get_next() 

    print(' ----> '.join(values) + ' ----> None') 

a = Node('blue') 
b = Node('red') 
c = Node('green') 

a.set_next(b) 
b.set_next(c) 

print_node_chain(a) 
move_to_end(a, b) 
print_node_chain(a) 

Ausgang:

blue ----> red ----> green ----> None 
blue ----> green ----> red ----> None 

Answer 2

Nun, dies wird einige Berechnungen erfordern. Lassen Sie sich den allgemeinen Fall annehmen:

e _i-1-> e _i-> e _{i + 1}-> ... - > e _n

Jetzt wollen wir e _i auf die letzte Position zu bewegen:

e _i-1-> e _{i + 1}-> ... - > e _n-> e _i

Die Frage ist also: Was sollte sich ändern?Basierend auf dem allgemeinen Fall gibt es drei Zeiger, die sich ändern müssen:

• e _i-1 jetzt _{verweist auf e i + 1};
• e _i zeigt jetzt auf nichts (None); und
• e _n zeigt nun auf e _i.

Da nun die verknüpfte Liste nicht doppelt verknüpft ist: ein Knoten hat keinen Hinweis auf den vorherigen Knoten, das einzige, was wir das vorherige Element tun zu bekommen, ist Iterierte von der Wurzel, bis wir finden das Element:

def get_prev_element(root,node): 
    while root.get_next() is not node: 
     root = root.get_next() 

Sobald wir das vorherige Element haben, können wir es auf das nächste Element lassen verlinken:

previous.set_next(node.get_next()) 

Aber Jetzt müssen wir noch herausfinden, was das letzte Element ist. Und raten Sie mal, was wir dies wieder tun, von iterieren, können wir jedoch von unseren eigenen Knoten starten:

def get_last(node): 
    while node.get_next() is not None: 
     node = node.get_next() 
    return node 

Jetzt setzen wir die next des letzten Knotens, zu unserem eigenen Knoten:

last.set_next(node) 

und schließlich setzen wir unsere eigenen neben None:

node.set_next(None) 

Nun ist diese Gruppierung alle zusammen können wir eine Methode definieren auf dem Knoten:

class Node: 

    # ... 

    def get_previous(self,root): 
     previous = root 
     while previous.get_next() is not self: 
      previous = previous.get_next() 
     return previous 

    def get_last(self): 
     last = self 
     while last.get_next() is not None: 
      last = last.get_next() 
     return last 

    def move_last(self,root): 
     previous = self.get_previous(root) 
     previous.set_next(self.get_next()) 
     last = self.get_last() 
     last.set_next(self) 
     self.set_next(None) 

Beachten Sie, dass, da die verknüpfte Liste nicht doppelt gebunden ist, werden Sie es das Wurzelelement geben.

---

Intermezzo: Da haben Sie Verweise auf a, b und c. Natürlich gibt es keinen Grund, das Vorhergehende und das Letzte zu berechnen: Sie wissen, dass a das vorherige ist und dass c das letzte ist. Also in diesem Fall, ist der Code einfach:

a.set_next(c) 
c.set_next(b) 
b.set_next(None) 

---

Dieser Code nicht funktioniert, wenn das Wurzelelement der Knoten selbst ist. Ich überlasse es als Übung, den Code so zu modifizieren, dass er richtig funktioniert. Es ist nicht sehr schwer.