1. Vorwort
Bei der Überprüfung von Datenstrukturen und Algorithmen verwenden einige Algorithmusprobleme kürzlich die Idee von Stapeln, und wenn es um Stapel geht, müssen wir über verknüpfte Listen sprechen. Arrays und verknüpfte Listen sind die Grundlage für lineare Speicherstrukturen, und Stapel und Warteschlangen sind Anwendungen linearer Speicherstrukturen ~
Dieser Artikel erläutert hauptsächlich die Grundkenntnisse von einzelbrennenden Listen und macht eine einfache Einführung. Wenn es einen Fehler gibt, korrigieren Sie ihn bitte.
2. Überprüfung und Wissen
Apropos verknüpfte Listen, erwähnen wir zunächst das Array. Wenn Sie sie mit Arrays vergleichen, verstehen Sie die Speicherstruktur von verknüpften Listen sehr gut.
2.1 Überprüfen Sie das Array
Wir haben Arrays sowohl in C als auch in Java gelernt:
Vorteile von Arrays:
Nachteile von Arrays:
2.2 Linkliste Beschreibung
Gehen Sie nach dem Lesen des Arrays zurück zu unserer verknüpften Liste:
Die N -Knoten werden diskret zugewiesen und durch Zeiger miteinander verbunden. Jeder Knoten hat nur einen Vorgängerknoten, jeder Knoten hat nur einen nachfolgenden Knoten, der erste Knoten hat keinen Vorgängerknoten und der Heckknoten hat keinen nachfolgenden Knoten.
Vorteile der verknüpften Liste:
Nachteile von verknüpften Listen:
Ich werde die Begriffe im Zusammenhang mit der verlinkten Liste über das obige Bild erläutern:
Um eine verknüpfte Liste zu ermitteln, benötigen wir nur einen Kopfzeiger, und die gesamte verknüpfte Liste kann über den Kopfzeiger ~ abgeleitet werden
Es gibt verschiedene Kategorien verknüpfter Listen:
1. Einweg-Link-Tabelle
2. Bidirektionale Verbindungstabelle
3.. Recycling -Linkliste
Sie müssen sich beim Betrieb einer verknüpften Liste erinnern, ist:
Das Zeigerfeld im Knoten zeigt auf einen Knoten!
A. Java Implementierungslinkliste
Algorithmus:
Erstens definieren wir eine Klasse als Knoten
Für die Bequemlichkeit des Betriebs habe ich es direkt als öffentlich definiert.
Öffentliche Klasse Node {// Datendomäne öffentliche Int -Daten; // Zeigerdomäne, der als nächstes auf den nächsten Knoten hinweist; public node () {} public node (int data) {this.data = data; } public node (int data, node als nächstes) {this.data = data; this.Next = Weiter; }} 3.1 Erstellen einer verknüpften Liste (Knoten hinzufügen)
Fügen Sie Daten in die verknüpfte Liste ein:
/*** Daten zur verknüpften Liste hinzufügen** @param -Wertdaten, die hinzugefügt werden sollen // Temporärer Knotenknoten temp = Kopf; // den Tail -Knoten wobei (temp.Next! = Null) {temp = temp.Next; } // Der Fall, in dem der Kopfknoten.Next null ist, wurde ~ temp.Next = newnode; } 3.2 Durchqueren der verknüpften Liste
Wir haben die oben erwähnte Methode geschrieben, und jetzt werden wir sie durchgehen, um festzustellen, ob sie korrekt ist ~~~
Beginnen Sie vom ersten Knoten und suchen Sie weiter hinter sich, bis keine Daten auf dem nachfolgenden Knoten vorhanden sind:
/ *** Durchqueren der verknüpften Liste** @param Head Head Head Node*/ public static void Traverse (Knotenkopf) {// Temporärer Knoten, starten Sie vom ersten Knotenknoten temp = head.next; while (temp! // Weiter mit dem nächsten temp = temp.next; }}Ergebnis:
3.3 Knoten einfügen
/*** Node einfügen** @param Head Head Zeiger* @param Indexposition, der eingefügt werden soll* @param -Wert, der eingefügt werden soll zurückkehren; } // Temporärer Knoten, starten Sie vom Anfang Knoten Knoten temp = Kopf; // Klicken Sie auf die aktuelle Position des Traversal int currentPos = 0; // Initialisieren Sie den zu integrierten Knoten insertnode = neuer Knoten (Wert); while (temp.Next! // Zeigen Sie das Zeigerfeld des vorherigen Knotens auf den zugefügten Knoten temp.Next = InsertNode; zurückkehren; } currentPos ++; temp = temp.Next; }}
3.4 Erhalten Sie die Länge der verknüpften Liste
Es ist sehr einfach, die Länge der verknüpften Liste zu erhalten. Es kann durch Überqueren und +1 für jeden Knoten ~ durchgeführt werden ~
/ *** Erhalten Sie die Länge der verknüpften Liste* @param Head Head Zeiger*/ public static int linkListLength (Knotenkopf) {int Länge = 0; // Temporärer Knoten, starten Sie vom ersten Knotenknoten temp = head.Next; // den Heckknoten wobei (temp! = Null) {Länge ++; temp = temp.Next; } Rückkehrlänge; } 3.5 Knoten löschen
Das Löschen eines Knotens an einem bestimmten Ort ist dem Einfügungsknoten tatsächlich sehr ähnlich, und Sie müssen auch den vorherigen Knoten finden. Ändern Sie das Zeigerfeld des vorherigen Knotens und Sie können es löschen ~
/** * Knoten nach Ort löschen * * @param Head Head Zeiger * @param Index Der zu löschen gelöschte Ort */public static void DeleteNode (Knotenkopf, int index) {// Zunächst müssen Sie bestimmen, ob der angegebene Ort legal ist, if (Index <1 || Index> LinkListlänge (HeadLegth) + 1). zurückkehren; } // Temporärer Knoten, starten Sie vom Anfang Knoten Knoten temp = Kopf; // Der aktuelle Standort des Datensatzquellens ist int currentPos = 0; while (temp.Next! // Der nächste Knoten, den Sie löschen möchten, wird dem vorherigen Knoten übergeben, um temp.next = deleteNode.next zu steuern; // Java wird es recyceln, und es sollte nicht viel Sinn machen, es auf null zu setzen (ich persönlich denke, wenn es nicht korrekt ist, richten Sie bitte darauf hin ~) delEtenode = null; zurückkehren; } currentPos ++; temp = temp.Next; }} 3.6 Sortieren Sie die verknüpfte Liste
Ich habe bereits über 8 Sortieralgorithmen gesprochen [Zusammenfassung von acht Sortieralgorithmen]. Ich werde diesmal eine einfache Blasensortierung wählen (eigentlich möchte ich eine schnelle Art schreiben, aber es fühlt sich ein bisschen schwierig an, es zu versuchen ...)
/ ** * Sortieren Sie die verknüpfte Liste * * @param head * */ public static void sortLinkList (Knotenkopf) {Knoten currentNode; Knoten NextNode; für (currentNode = head.next; currentNode.next! NextNode.data = NextNode.Next.data; NextNode.Next.data = temp; }}}} 3.7 Suchen Sie den k-lastigen Knoten in der verknüpften Liste
Dieser Algorithmus ist sehr interessant: Setzen Sie zwei Zeiger P1 und P2, um P2 -K -Knoten schneller als P1 zu machen, und durchqueren gleichzeitig rückwärts. Wenn P2 leer ist, ist P1 der k-te letzte Knoten
/ *** Finden Sie den k-h bis zum letzten Knoten in der verknüpften Liste (setzen Sie zwei Zeiger P1 und P2, machen Sie P2 K schneller als p1 und treten Sie gleichzeitig nach hinten. Wenn p2 leer ist, ist p1 der k-d der letzten Knoten** @param head* @param k-tH bis zum letzten node*/ public node*/ public node |/ public node |/ public node LinkListLength (Kopf)) Null; p1;
3.8 Duplikatdaten auf verknüpfter Liste löschen
Es ähnelt der Blase -Sortierung, solange es gleich ist, kann es gelöscht werden ~
/ ** * löschen Sie doppelte Daten in der verknüpften Liste (ähnlich wie Bubbling, es entspricht dem Löschen) * * @param Head Head Head-Knoten */ public static void Deleteduplecate (Knotenkopf) {// temporärer Knoten (Beginn des ersten Knotens-> Knoten mit realem Daten). // Nächster Knoten des aktuellen Knotenknotenknotens NextNode = temp.Next; while (temp.Next! = null) {while (NextNode.Next! } else {// Weiter mit dem nächsten nächstenNode = nextNode.Next; }} // nächste Runde des Vergleichs temp = temp.Next; }} 3.9 Abfragen Sie die Zwischenknoten der verknüpften Liste ab
Dieser Algorithmus ist ebenfalls sehr interessant: ein Zeiger, der jedes Mal 1 Schritt macht, ein Zeiger, der jedes Mal 2 Schritte unternimmt und dann einen Schritt unternimmt, das ist der Zwischenknoten
/ *** Abfragen Sie den Zwischenknoten einer einzelnen verknüpften Liste*/ öffentlicher statischer Knoten SearchMid (Knotenkopf) {Knoten p1 = Kopf; Knoten P2 = Kopf; // Machen Sie einen Schritt und einen Schritt zwei Schritte, bis es null ist. Der mittlere Knoten, den Sie erreichen (p2! = Null && p2.Next! = Null && p2.Next.Next! p2 = p2.Next.Next; } return p1; }3.10 rekursiv einkräuselte Tabellen von Schwanz zu Kopf ausgeben
/ *** Ausgabe einer einzelnen verknüpften Liste von Schwanz zu Kopf durch rekursiv** @param Head Head Node*/ public static void printlistrevery (Knotenkopf) {if (head! = Null) {printlistRevery (head.next); System.out.println (head.data); }} 3.11 Reverse -Link -Liste
/ *** Implementieren Sie die Inversion der verknüpften Liste** @param -Knoten Der Kopfknoten der verknüpften Liste*/ public static Knode ReverSelinkList (Knotenknoten) {Knoten pre; if (node == null || node.next == null) {prev = node; } else {node tmp = ReverSelinkList (node.next); node.next.next = node; node.next = null; PREV = TMP; } return prev; } Verweise auf die umgekehrte Linkliste von: //www.vevb.com/article/136185.htm
4. Endlich
Es ist nicht schwierig, die verknüpfte Liste selbst zu verstehen, aber es kann bei verwandten Operationen Kopfschmerzen verursachen. Head.Next Nächstes nächstes am nächsten .... (Ich bin immer noch schwach im Algorithmus ... Ich habe nicht genug Gehirn ...) Ich habe dieses kleine Ding nach zwei Tagen geschrieben ...
Sie können alles tun, indem Sie einfach den Kopfzeiger kennen, wenn Sie eine verknüpfte Liste betreiben.
1. Fügen Sie Daten zur verlinkten Liste hinzu
2. durchqueren Sie die verknüpfte Liste
3. Einfügen Knoten in die verknüpfte Liste an einem bestimmten Ort
4. Erhalten Sie die Länge der verlinkten Liste
5. Löschen Sie den Knoten an der angegebenen Stelle
6. Sortieren Sie die verknüpfte Liste
7. Finden Sie den k-lastigen Knoten in der verknüpften Liste
8. Löschen Sie doppelte Daten auf der verknüpften Liste
9. Fragen Sie die Zwischenknoten der verknüpften Liste ab
10. rekursiv einkloster Tisch von Schwanz zu Kopf ausgeben
11. Reverse -Link -Liste
PS: Die Implementierung aller wird unterschiedlich sein, sodass sich einige kleine Details unweigerlich ändern, und es gibt keine feste Möglichkeit, sie zu schreiben, sodass Sie die entsprechenden Funktionen erkennen können ~
Zusammenfassen
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels einen gewissen Referenzwert für das Studium oder die Arbeit eines jeden hat. Wenn Sie Fragen haben, können Sie eine Nachricht zur Kommunikation überlassen. Vielen Dank für Ihre Unterstützung bei Wulin.com.
Referenzen: