Einfügen in geordnete Verknüpfte Liste (Python)

Ich habe Schwierigkeiten, eine Insert-Funktion für eine geordnete Linked List zu erstellen. Hier ist was ich bisher habe

class Node: def __init__(self, initial_data): self.data = initial_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 class LinkedList: def __init__(self): self.head = None def __str__(self): output_string = '' current = self.head while current is not None: output_string += str(current.get_data()) next_node = current.get_next() if next_node is not None: output_string += "->" current = next_node return output_string def insert(self, data): other = self.head previous = None if other is None: new_node = Node(data) new_node.set_next(self.head) self.head = new_node else: while data > other.get_data(): previous = other other = other.get_next previous.set_next(Node(data)) 

  • Wie installiere ich ipython qtconsole mit pyenv (Python Version 3.4.2)
  • Wie bekomme ich Python isidentifer () Funktionalität in Python 2.6?
  • Urllib kombiniert mit elementtree
  • Speichern Sie das Ergebnis in die Variable
  • Flurry Login Requests.Session () Python 3
  • Wie werden Funktionen innerhalb der Funktionen genannt? Und kann ich auf diese Funktionen zugreifen oder sie funktionieren wie "Helfer Methoden"?
  • Wie bekomme ich den "alten" Zip () in Python3?
  • Verweis auf eine Funktion von einer anderen Klasse in Kivy
  • 2 Solutions collect form web for “Einfügen in geordnete Verknüpfte Liste (Python)”

    Sie müssen Ihren Artikel in die Liste einfügen . Das heißt, Sie müssen:

    • Brechen Sie die Kette an der Stelle, die Sie einfügen werden
    • Erstellen Sie einen neuen Knoten
    • Verbinde die Kette wieder mit deinem neuen Knoten in der Mitte.

    Sie müssen nicht technisch die Kette brechen, da die Einstellung des nächsten Links auf den previous Artikel wird die alte Link zu löschen, so dass alles, was Sie tun müssen, noch ist die Kette wieder zusammen:

     while data > other.get_data(): previous = other other = other.get_next() new = Node(data) previous.set_next(new) new.set_next(other) 

    Ich habe auch einen anderen Fehler korrigiert, du hast Node.get_next() nicht aufgerufen .

    Als nächstes musst du mehr über Randfälle denken. Was passiert, wenn du am Ende deiner Kette kommst, aber keinen Knoten gefunden node.get_data() wo node.get_data() größer ist als deine eingefügten Daten?

    Sie müssen Ihre while Schleife anpassen, um sicherzustellen, dass Sie für diesen Fall testen; other wird für das letzte Element der Kette nicht sein:

     while other is not None and data > other.get_data(): previous = other other = other.get_next() new = Node(data) previous.set_next(new) new.set_next(other) 

    Es gibt andere Dinge, die du tun kannst, um deinen Code zu verbessern. Es gibt keine Notwendigkeit, Setter und Getter in Python zu verwenden; Es gibt keine Kosten für das @property Attributen zu @property s in der Zukunft, also verwenden Sie einfach Attribute hier.

    Du könntest auch deinen Node() ein nächstes Element im Konstruktor annehmen, das würde das Einfügen eines Elements erleichtern.

    Sie können str.join() , um einen festen String zwischen Elementen einer Sequenz einzufügen. Setzen Sie alle Ihre Datenattribute in eine Python- list und verbinden Sie diese Liste.

    Sie müssen nicht selbst den self.head als den nächsten Knoten setzen, wenn Sie ein Anfangselement erstellen (wenn self.head ist); Das ist schon standardmäßig:

     class Node: def __init__(self, initial_data, next=None): self.data = initial_data self.next = next class LinkedList: def __init__(self): self.head = None def __str__(self): data_list = [] current = self.head while current is not None: data_list.append(str(current.data)) current = current.next return '->'.join(data_list) def insert(self, data): other = self.head previous = None if other is None: self.head = Node(data) else: while other is not None and data > other.data: previous = other other = other.next previous.next = Node(data, other) 

    Demo:

     >>> ll = LinkedList() >>> str(ll) '' >>> ll.insert(10) >>> str(ll) '10' >>> ll.insert(20) >>> str(ll) '10->20' >>> ll.insert(15) >>> str(ll) '10->15->20' 

    Ich denke, das zu ändern:

      else: while data > other.get_data(): previous = other other = other.get_next previous.set_next(Node(data)) 

    Dazu sollte es funktionieren

      else: # First condition will short circuit so there won't be exception on calling other.get_data() if other is None while other is not None and data > other.get_data(): previous = other other = other.get_next() node = Node(data) node.set_next = previous.get_next() previous.set_next(node) 

    Auch Getter und Setter Methoden sind nicht wirklich notwendig in Python. Die Konvention ist, @property Annotation zu verwenden, wenn Sie diese Art von Verhalten benötigen und private Mitglieder sind in der Regel mit einem _ vorangestellt.

    Python ist die beste Programmiersprache der Welt.