Ich versuche, zwei Knoten zu tauschen. Wenn zum Beispiel die Knoten a und b sind, übergebe ich die Zeiger
(a-1)->next und (b-1)->next , die im Grunde die Knoten a und b sind.
Was mache ich falsch? Wenn ich versuche, die Knoten nach dem Aufruf der Funktion zu drucken, ist es eine Endlosschleife. Bitte helfen.
Unendliche Schleife ist wegen Selbstschleife in Ihrer Liste nachdem swap() Funktion aufgerufen hat. In swap() code following-Anweisung ist fehlerhaft.
Warum? : Nachdem die Zuweisungsanweisung in swap() function temp1 als nächstes auf b node zeigt. Und node[b] zeigt als nächstes auf sich selbst in einer Schleife. Und die Selbstschleife ist der Grund für Endlosschleife , irgendwo in Ihrem Code, wo Sie die verknüpfte Liste durchlaufen.
Unten wurde gezeichnet, um zu zeigen, wie swap() Schritt für Schritt funktioniert. Vielleicht hilft Ihnen das, Ihren Fehler zu verstehen:
Sie haben das nicht erwähnt, aber ich nehme an, dass die verknüpfte Liste folgende Beziehung zwischen a und b hat: ( rote Kommentare lesen )
(Schritt-1):
%Vor%(Schritt-3): Die fehlerhafte Anweisung
%Vor% Siehe (temp1)->next; ist tatsächlich b und Sie weisen (*b)->next = (*b) zu, indem Sie (*b)->next = (temp1)->next; ausführen und somit eine Selbstschleife hinzufügen.
(Schritt-4):
Ich denke, mit dem Diagramm können Sie leicht verstehen, was die letzten beiden Zeilen Ihres swap() Codes tun:
Nachfolgend ist mein Diagramm für diese zwei Zeilen:
%Vor% (Schritt-5): Auch letzte Zeile Ihrer Funktion swap() linke Schleife wie folgt:
So Schleife immer noch bei two Knoten so Endlosschleife.
Eine Möglichkeit besteht darin, die Daten des Knotens zu tauschen, anstatt die Position des Knotens in der verknüpften Liste zu vertauschen (, wie ich Ihre Frage zu kommentiert habe). Aber möchten Sie die Position des Knotens in der Liste tauschen.
Gut so gut! Wenn die Knotendatengröße größer ist, ist es besser, die Position des Knotens zu tauschen, als die Daten des Knotens zu tauschen ( Tauschen von Daten ist eine schlechte Wahl )
Da Sie einzelne verkettete Liste haben, um zwei beliebige Knoten in der Liste zu tauschen, brauchen Sie auch vorherige Knotenadressen . ( Dies ist der Punkt, den Sie in Ihrer Austauschlogik nicht berücksichtigen )
WARUM brauchen vorherige Zeiger? :
Angenommen, nach einigen erfolgreichen Operationen zum Einfügen (Drücken) wird Ihre Liste wie folgt:
Ein horizontales Diagramm - Angenommen, Sie möchten tauschen sagen Sie zwei Knoten (q) und (p) :
Wie gesagt, zum Tauschen brauchen wir vorherige Zeiger. Sie müssen darüber nachdenken, zu folgen
( Theoretisch schreibe ich für die spezifischen Knoten (p) und (q) nur um die Erklärung einfach zu halten. aber meine Implementierung ist generell beendet ):
In der Liste der vorherigen Zeiger:
%Vor%Und
%Vor% HINWEIS: Wenn Sie zwei Knoten tauschen wollen, sagen Sie node[ 9 ] und node[ 6 ] , dann sollten Sie die Zeiger der Knoten vor diesen beiden Knoten verwenden.
Zum Beispiel: zwei swap node[ 9 ] und [ 6 ] , Sie müssen auch den nächsten Zeiger von node[ 0 ] und den nächsten Zeiger von node[ 2 ] im obigen Diagramm ändern.
Wie wäre die Liste nach dem Austausch dieser beiden Knoten?
%Vor% Was ist jetzt in den vorherigen Knoten [o] und [2] ?
Nach dem Tauschen, In Liste vorherige Zeiger
Und
%Vor%Wenn Sie also zwei Knoten tauschen wollen; da wirkt sich der unmittelbar vorhergehende Knoten auch aus und da die Liste nur eine Link-Liste ist, braucht man auch vorherige Zeiger.
So finden Sie frühere Knotenzeiger?
Angenommen, Sie möchten zwei beliebige Knoten node[p] und node[q] tauschen, dann können Sie mit head pointer den vorherigen Knoten finden.
Also swap function Syntax ( In meiner Implementierung ) ist wie:
%Vor%Und Sie werden folgende Funktion aufrufen:
%Vor%Definition: ( Um den Code zu verstehen, lies bitte Kommentare, die ich fast an jeder Zeile hinzugefügt habe )
%Vor% In swap() function können Sie feststellen, dass ich eine Hilfsfunktion get_prevnd(, ); aufruft. Diese Funktion gibt die Adresse des vorherigen Knotens in der Liste zurück. In der Funktion get_prevnd(, ); ist das erste Argument Listenkopf und das zweite Argument ist der Knoten, nach dem Sie suchen.
Und glücklicherweise funktioniert der Code :). Unten finden Sie einen Link für den Online-Test dieses Codes. Ich habe für verschiedene Arten von Eingaben getestet.
CodePad: Knoten in der einzelnen verknüpften Liste tauschen. Überprüfen Sie die Ausgabe.
Und Entschuldigung für schlecht Englisch
Ich hatte auf Code zum Ausschneiden und Einfügen gehofft, aber ich habe ihn nicht gefunden. Wenn noch jemand interessiert ist, ist dies die Antwort. Ich habe die Brute-Force-Analyse aller 3 Fälle durchgeführt.
%Vor%Hinweis: Dieser Code funktioniert, wenn sp == tp, nimmt aber an, dass Sie nicht den pathologischen Fall haben, bei dem BOTH & amp; & amp; & amp;; & ndash; next == tp & amp; & amp ;; & amp; t- & gt; next == sp (beginnend mit dem Zyklus).
SwapanyTwoNodeData(int, int); Diese Funktion nimmt zwei Integer als Parameter und tauscht diese aus
Knotendaten.
%Vor% SwapanyTwoNodeData (2,4);
100% Arbeitsfunktion. . . . Genießen.
%Vor%Tags und Links c pointers swap singly-linked-list