Austauschen von Knoten in einer einzelnen verketteten Liste

Question

Ich versuche, eine swapNode Funktion zu machen, die beliebige zwei Knoten nehmen und sie tauschen kann. Ich habe einen Algorithmus entwickelt, der funktioniert, wenn er mindestens 2 Knoten entfernt ist, aber ich kann keinen Algorithmus finden, der funktioniert, wenn sie näher beieinander liegen.

Hier ist, was ich bisher geschrieben:

void swapNode(call * &head, call * &first, call * &second){ 
    call * firstPrev = NULL; 
    call * secPrev = NULL; 
    call * current = head; 

    //set previous for first 
    while((current->next != first)){ 
     current = current->next; 
    } 

    firstPrev = current; 
    current = head; 

    //set previous for second 
    while((current->next != second)){ 
     current = current->next; 
    } 

    secPrev = current; 
    current = second->next; 

    //set firstPrev-> next to second 
    firstPrev->next = second; 
    //set secPrev->next to first 
    secPrev->next = first; 
    //set second->next = first->next 
    second->next = first->next; 
    //set first->next to current 
    first->next = current; 

    current = head; 
    while(current->next != NULL){ 
     cout << current->number << endl; 
     current = current->next; 
    } 

    cout << current->number << endl; 
} 

EDIT: Ich habe jetzt das als meine Swap-Teil, aber es scheint immer noch nicht richtig

//swap firstPrev-> next with second->next 
tmp = firstPrev->next; 
second->next = firstPrev->next; 
second->next = tmp; 
//swap swap first->next with second->next 
tmp = first->next; 
second->next = first->next; 
second->next = tmp; 

EDIT2 zu arbeiten: Dieser scheint auch nicht zu funktionieren, ich bekomme einen seg Fehler.

//swap previous's->next 
    tmp =firstPrev->next; 
    secPrev->next = firstPrev->next; 
    secPrev->next = tmp; 
    //swap swap first->next with second->next 
    tmp = first->next; 
    second->next = first->next; 
second->next = tmp; 

Answer 1

Sagen wir:

Node1 -> Node2 -> Node3 -> Node4 -> Node5 

zwei Knoten zu tauschen, können Sie die next Werte von denen vor jedem von ihnen, und auch die next Werte der Knoten tauschen müssen Sie tauschen .

So tauschen, sagen wir, Node2 und Node3, Sie effektiv Node1->next mit Node2->next tauschen müssen, und Node2->next mit Node3->next. Das funktioniert, auch wenn sie direkt nebeneinander liegen (oder auch wenn es sich um denselben Knoten handelt). Zum Beispiel:

Swap Node1->next und Node2->next

Node1->next = Node3 
Node2->next = Node2 

Swap Node2->next mit Node3->next

Node2->next = Node4 
Node3->next = Node2 

Dies kommt als:

Node1 -> Node3 -> Node2 -> Node4 -> Node5 

Swapped!

Wie in der Abwicklungsbemerkung vermerkt, wenn Sie Node1 mit irgendetwas vertauschen, müssen Sie einen neuen Kopf für die verknüpfte Liste festlegen.

---

Als Reaktion auf die Bearbeitung der Frage:

Ihr Code für fast rechts austauschen. Allerdings müssen Sie die erste Vorbesprechung mit secPrev tauschen. In meinem Beispiel ist es so passiert, dass wir einen der Werte next des Knotens zweimal ausgetauscht haben, weil sie nebeneinander lagen. Aber logisch, wir wollen die next s der beiden vorherigen austauschen und dann die next s der tatsächlichen Knoten tauschen. Versuchen Sie folgendes:

//swap firstPrev-> next with secPrev->next 
tmp = firstPrev->next; 
secPrev->next = firstPrev->next; 
secPrev->next = tmp; 
//swap swap first->next with second->next 
tmp = first->next; 
second->next = first->next; 
second->next = tmp; 

Wenn Sie eine segfault bekommen, überprüfen Sie die Variable tmp - es könnte ein Fehler der Zuteilung oder Löschung irgendwo sein. Wo bekommst du den Segfault?

Answer 2

In den meisten realen Szenarien, die Werte tauschen die beste Lösung sein:

void swapNode(call * &head, call * &first, call * &second) { 
    // swap values, assuming the payload is an int: 
    int tempValue = first->value; 
    first->value = second->value; 
    second->value = tempValue; 
} 

Wenn das ist nicht erlaubt, dann wollen Sie auf der einen ähnlichen Stil Swap tun -> weiter statt der -> Wertkomponente. Und tu dann einen weiteren Tausch auf den ersten Prev-> Next und SecondPrev-> Next-Komponenten. Achten Sie auf den Spezialfall, wo erster oder zweiter == Kopf ist.

Answer 3

Während ich nicht 100% sicher bin, sollte die Antwort Verweise auf Knotenzeiger (oder Zeiger auf Zeiger) beinhalten und dies sollte dann einen Fall behandeln, wenn einer der Knoten auch der Kopf der Liste ist.

void swapNodes(node *&first, node *&second) 
{ 
    node *t = second->next; 
    second->next = first->next; 
    first->next = t; 
    t = second; 
    second = first; 
    first = t; 
} 

Dann können Sie es zum Beispiel nennen:

swapNodes(head, secPrev->next); 

oder

swapNodes(firstPrev->next, head); 

oder

swapNodes(firstPrev->next, secPrev->next) 

und es sollte automatisch funktionieren.

EDIT:

swapNodes könnte noch besser lesbar:

void swapNodes(node *&first, node *&second) 
{ 
    std::swap(first->next, second->next); 
    std::swap(first, second); 
} 

Answer 4

Daumenregel: "Immer getrennte Daten von Zeigern und nie Zeiger tauschen, werden nur die Daten". Machen Sie Swap explizit, ohne memcpy() zu verwenden, damit Sie Ausrichtungsprobleme vermeiden können. Es verursacht keine Leistungseinbußen hinsichtlich der algorithmischen Komplexität, macht aber Ihren Code lesbarer und sicherer.

Answer 5

Wenn Sie von Vertauschen zweier Knoten in verkettete Listen in einfachen C alle Methoden wissen nur dann auf diesen Link besuchen:

http://sahilalipuria.wordpress.com/2013/01/21/swapping-two-nodes-of-a-singly-linked-lists-set-2/

Answer 6

void swap() 
{ 
struct node *temp=0,*nxt,*ptr; 
ptr=head; 
int count=0; 
while(ptr) 
{ 
    nxt=ptr->link; 
    if(nxt) 
{ 
    if(count==0) 
    head=nxt; 
    count++; 
    ptr->link=nxt->link; 
    nxt->link=ptr; 
    if(temp!=NULL) 
    temp->link=nxt; 
    temp=ptr; 
    if(ptr->link==NULL) 
    break; 
    ptr=nxt->link->link; 
} 

} }

Answer 7

Hier P1 der erste zu swapende Knoten ist p2 der zweite zu swapende Knoten. Und prevnode ist der Knoten, p2 vorherigen von

ist

 temp=head; 
     while(temp!=NULL){ 
     if(temp->link==p1){ 
      temp->link=p2; 

      prevnode->link=p2->link; 
      p2->link=p1->link; 
      t=p1->link; 
      while(t!=prevnode) 
       t=t->link; 
       cout<<" YES"; 
      cout<<"["<<t->num<<"] "; 
      p1->link=prevnode->link; 
      prevnode->link=p1; 

      temp=p1; 
     }//if_ 

     cout<<" "<<temp->num;    
     temp=temp->link; 
    } 

Answer 8

Sie müssen auch die next Komponente des vorherigen Knoten tauschen, sonst wird die verknüpfte Liste nicht miteinander verbunden bleiben. Beachten Sie, dass meine Struktur node heißt.

int swapNode(node *&head * &first, node * &second) 
{ 
    //first we will declare the 
    //previous of the swapping nodes 
    node *firstprev=NULL; 
    node*secprev=NULL; 
    node*current=head; 
    //set previous first 
    while(current->next!=first) 
    { 
     current=current->next; 
    } 
    firstprev=current; 
    //seting 2nd previous 
    while(current->next!=second) 
    { 
     current=current->next; 
    } 

    // swap values, assuming the payload is an int: 
    int tempValue = first->value; 
    first->value = second->value; 
    second->value = tempValue; 
    //swaping next of the nodes 
    firstprev->next=second; 
    secprev->next=first; 
    return; 
} 

Answer 9

Vielen Dank für Ihre Antworten! Ich bin mir bewusst, dass diese Frage vor fast zwei Jahren gestellt wurde und eine Antwort schon lange akzeptiert wurde, aber ich war ein wenig verwirrt von den Antworten. Obwohl der Fragesteller sich wahrscheinlich nicht um neue Antworten kümmert, würde ich gerne meine Version hinzufügen, falls andere Leser ebenfalls verwirrt wären und meinen eigenen Ansatz dokumentieren würden. Einige davon mögen passender als Kommentare gewesen sein, aber ich habe noch nicht den Ruf, sie zu kommentieren.

Erstens, egal wie oft ich es ansehe - auf dem Whiteboard oder im Debugger - ich kann nicht vermeiden, mit einer Schleife im ersten Knoten zu enden, d.auf sich selbst zeigen, wenn ich keine Bedingung verwende, um zwischen Fällen von benachbarten Knoten zu unterscheiden, auch nicht mit den abstrakten Schritten oder dem konkreten Code aus der aktuell akzeptierten Antwort von Smashery. Ich habe mich ein bisschen im Internet umgeschaut, um Code im Stil der aktuell akzeptierten Antwort zu finden, um eine solche Bedingung zu vermeiden, aber für mich ist es überraschend schwierig zu vermeiden und meine Recherchen haben keine solche Lösung ergeben (außer ich liege falsch über die vorgeschlagene möglicherweise falsch). Wenn es einen cleveren Ausdruck gäbe, der die Adresse des ersten Knotens ergibt, wenn sie benachbart sind, und die Adresse des nächsten Knotens, wenn nicht, dann wäre diese Bedingung nicht erforderlich, weil das Herausfinden des neuen Knotens (was offensichtlich ist) notwendig ist das bedingt.

Zweitens habe ich die gleiche Frage über die aufeinanderfolgenden Zuweisungen an die gleichen Variablen in der angenommenen Antwort als andere Kommentatoren. Ich hoffe, dass ich hier nicht extrem dicht bin, aber der gleichen Variablen nacheinander verschiedene Werte zuzuordnen, außer vielleicht im Falle von Nebenwirkungen, scheint mir die Variable niemals einen anderen Wert als die letzte Zuweisung zu haben, egal welche Konfiguration der Knoten ich betrachte und damit die vorherigen Zuweisungen scheinbar überflüssig mache. Wenn ich falsch liege und dieser Ansatz dieses Problem tatsächlich lösen würde, wäre ich in der Lage gewesen, die letzte Bedingung in dem Code unten zu eliminieren, den ich versuchte loszuwerden, als ich zum ersten Mal im Internet nach einer Lösung suchte Tauschen von Knoten ohne spezielle benachbarte Knoten. Ich bin mir nicht ganz sicher, aber es hörte sich an, als ob Smashery diese wiederholten Aufgaben absichtlich aus der logischen Strenge ließ und die Prozedur besser illustrierte - ich habe das vielleicht missverstanden.

Drittens, auf dieser und anderen Seiten habe ich oft die Aussage aus anderen Antworten wiederholt, dass es besser ist, den Inhalt der Knoten zu tauschen, als die Zeiger. Im Fall von einfachen ganzen Zahlen, wie in den Beispielen bisher, ergibt dies natürlich einen kürzeren, einfacheren Code. Wenn wir jedoch verknüpfte Listen mit Knoten diskutieren, die ganze Zahlen enthalten, ist dies normalerweise ein Ersatz für die Hintergrunddatenstruktur eines komplexeren und allgemeineren Containers. Daher glaube ich nicht, dass das Austauschen der Inhalte der Knoten wirklich so einfach ist, zumindest wenn die Implementierung der Datenstruktur keine Annahmen über die Kopiesemantik der Container-Elemente machen kann. Außerdem kann ich durch die Möglichkeit, den Inhalt von Knoten auszutauschen, erkennen, dass die verknüpfte Liste Eigentümer des Inhalts dieser Knoten ist, da Code außerhalb der Methode der verknüpften Liste sonst Verweise auf die Objekte in diesen Knoten enthält, deren Werte plötzlich unter ihnen wechseln.

Ich gebe jedoch zu, dass dies von der Semantik des Containers abhängen könnte. Für ein Array wird erwartet, dass eine Swap-Methode den Wert unterhalb von Referenzen auf einen bestimmten Index dieses Arrays ändert. Das würde bedeuten, dass die Referenzen sich nicht auf ein bestimmtes Objekt beziehen, sondern auf eine Position in einem Container, die man indexieren kann. Wenn wir eine verkettete Liste als ein Mittel ansehen, um nur eine Menge von Objekten anzuordnen, die außerhalb der verknüpften Liste verwendet werden, würde ein Benutzer wahrscheinlich erwarten, dass eine Austauschoperation nur die Position und nicht den Inhalt tauscht.

Stellen Sie sich zum Beispiel vor, dass die verkettete Liste Objekte vom Typ "Auto" darstellt. Jedes Auto hat einen Besitzer und dieser Besitzer referenziert sein Auto durch einen Zeiger darauf. Angenommen, die verkettete Liste stellt die Reihenfolge dar, in der ein Satz von Fahrzeugen zur Inspektion bei einem Autohändler gewartet werden soll. Wenn wir den Inhalt von zwei Knoten tauschten, um die Zeitpläne für zwei Autos zu tauschen, und indem wir ihren Inhalt austauschten, würde die Wartung tatsächlich in der neuen, richtigen Reihenfolge geschehen - aber die Leute würden auch plötzlich Eigentümer sein verschiedene Autos! (Ich hätte aber nichts dagegen, mit einem Tesla zu tauschen, weil ich nur einen Corolla fahre.)

Wenn die verkettete Liste, wie im Beispiel des Arrays, basierend auf Indizierung Semantik dann die Position im Knoten könnte einfach die Reihenfolge darstellen, in der die Autos auf ein Schiff zum Transport geladen werden. Zu diesem Zeitpunkt haben die Autos keine Besitzer und wir kümmern uns wirklich nur darum, in welchem ​​Slot sie sich befinden. Dann schadet es wirklich nicht, Autos auszutauschen, d. H. Den Inhalt der Objekte, auf die die Knoten verweisen.

Schließlich zum Code. Wie ich oben sagte, konnte ich das Spezialgehäuse für benachbarte Knoten nicht vermeiden.

Zuerst wird die Definition eines Hilfs Methode:

int find_node(int v, node* root, node** n, node** pn) { 
    int i = 0; 
    for (*n = root; *n != NULL && (*n)->v != v; ++i) { 
     *pn = *n; 
     *n = (*n)->next; 
    } 
    return i; 
} 

Diese Methode findet einen Knoten durch seinen Wert. Die zurückgegebene Ganzzahl ist die auf Null basierende Position des Node in der verknüpften Liste (nennen Sie es ihren Index, wenn Sie möchten). Ich fand, dass die Adjazenz durch Position statt durch Zeigervergleiche besser lesbar ist. Der Anfang der Liste ist root. Die Methode setzt n auf den Knoten, der den übergebenen Wert enthält. In pn speichert die Methode den Vorgänger von n.

Im Folgenden ist der eigentliche swap:

void swap_nodes(node **root, int v1, int v2) { 
    if (v1 == v2) return; 

    node *n1, *n2, *pn1, *pn2; 

    int p1 = find_node(v1, *root, &n1, &pn1); 
    int p2 = find_node(v2, *root, &n2, &pn2); 

    if (p1 > p2) { 
     std::swap(n1, n2); 
     std::swap(pn1, pn2); 
     std::swap(p1, p2); 
    } 

    if (p1 == 0) *root = n2; 
    else pn1->next = n2; 

    node* nn1 = n1->next; 
    n1->next = n2->next; 

    if (p2 - p1 > 1) { 
     n2->next = nn1; 
     pn2->next = n1; 
    } else { 
     n2->next = n1; 
    } 
} 

Es tut mir leid, dass ich die Unterschrift des Verfahrens der OP ein wenig geändert haben. Ich fand es bequemer, die Werte der Knoten zu tauschen, im Gegensatz zu Knotenzeigern. Wenn Sie nur Knotenzeiger an die jeweiligen Knoten übergeben, müssen Sie eine weitere Traversierung durchführen, um die Vorgänger mit dieser Lösung zu finden, was mir etwas peinlich war. Wenn wir Knoten nicht anhand dieser Werte unterscheiden können, z. Werte sind nicht eindeutig, wir benötigen jedoch Zeiger auf die Knoten.

Wie bei der obigen Erläuterung zu find_node finden wir zuerst die Positionen, Knoten und Vorgänger für die Knotenwerte, die über v1 und v2 an swap_nodes übergeben werden. Die Werte für den ersten und zweiten Knoten werden alle vertauscht, wenn der zweite zu tauschende Knoten vor dem ersten angezeigt wird. Es ist nicht viel Code zu tun, reduziert spezielle Gehäuse und macht es ein wenig einfacher zu visualisieren.

Jetzt sind nur noch zwei weitere Bedingungen übrig, von denen keine zu trivial zu vermeiden war. Wenn sich der erste Knoten an der Spitze der verknüpften Liste befindet, d. H. An der Position Null, muss die Wurzel auf den zweiten Knoten zeigen. Andernfalls zeigt der Vorgänger des ersten Knotens auf den zweiten Knoten.

Der vorherige Wert des Nachfolgers des ersten Knotens muss gespeichert werden, falls die Knoten nicht benachbart sind. Dann wird der Nachfolger des ersten Knotens auf den aktuellen Nachfolger des zweiten Knotens gesetzt. Dies ist die einzige Änderung, die für alle Fälle gilt: Der neue Nachfolger des ersten Knotens, der der alte Nachfolger des zweiten Knotens ist, ist die einzige Gewissheit und hilfreich, um mit den Zeigeroperationen und ihrer Reihenfolge bei der Implementierung dieses Austauschs zu beginnen .

Wenn die Positionen der Knoten sich um mehr als eins unterscheiden, sind sie nicht benachbart. Dann wird der neue Nachfolger des zweiten Knotens der alte Nachfolger des ersten Knotens - oben gespeichert - und der Vorgänger des zweiten Knotens zeigt nun auf den ersten Knoten. Wenn sie benachbart sind, gibt es keine Knoten zwischen den Knoten, die ausgetauscht werden müssen, die aktualisiert werden müssen, so dass nur noch der zweite Knoten mit dem ersten verbunden werden muss.