Wie tauscht man Knoten in einer verketteten Liste, ohne Daten in der C-Sprache auszutauschen?

Question

Ich benutze diese Sortierfunktion, aber ich weiß nicht wie Knotenadressen anstelle von Werten zu tauschen. Ich verwende eine doppelt verkettete Liste.

Danke

void sort(LISTnode **h) { 
    LISTnode * start, * min, * temp; 
    int num; 
    start = *h; 
    while (start->next != NULL) { 
     temp = start; 
     min = temp; 
     temp = temp->next; 

     while (temp != NULL) { 
      if (temp->number < min->number) 
       min = temp; 
       temp = temp->next; 
     } 

     // This part of the code 
     num = min->number; 
     min->number = start->number; 
     start->number = num; 

     start = start->next; 
    }  
} 

Answer 1

Swapping zwei Knoten (Edit: nicht-benachbarte - Sonderbehandlung wird als Code erforderlich unten wird ein Teil der beteiligten nächsten/vorherigen Zeiger zurück auf das eigene Objekt gesetzt! auf benachbarten Knoten !!!):

x->prev->next = y; 
x->next->prev = y; 

y->prev->next = x; 
y->next->prev = x; 

Nun sind die Knoten ihre Positionen in der Liste geändert haben, müssen Knoten selbst anzupassen:

tmp = x->prev; 
x->prev = y->prev; 
y->prev = tmp; 

tmp = x->next; 
x->next = y->next; 
y->next = tmp; 

Schließlich: Einstellen der Kopfzeiger:

if(list->head == x) 
{ 
    list->head = y; 
} 
else if(list->head == y) 
{ 
    list->head = x; 
} 

Erledigt ...

Nun, nur auf halbem Weg: Über gilt für einen doppelt und zirkular verkettete Liste (wo man den Schwanz bekommen via list->head->previous). Wenn Sie keine zirkulär verknüpfte Liste haben, fügen Sie dem ersten Codeabschnitt (der zweite, den Sie nicht benötigen, entsprechende xx und y sind beide nicht null ...) entsprechende Nullzeiger-Checks hinzu und führen Sie die Kopfanpassung für den Tail durch , auch.

Randbemerkung: Wegen Kopf anpassen zu müssen (und Schwanz, wenn es sein muss), können Sie nicht sicher tauschen, ohne die übergeordnete Liste der Knoten ...

, die notwendig ziemlich viele Zeiger Einstellung ist, obwohl . Ich würde lieber in Erwägung ziehen, Daten innerhalb der Knoten auszutauschen (obwohl Sie in Ihrer Frage explizit ausgeschlossen sind!). Wenn Sie dies nicht tun wollten, weil Daten zu groß sind, dann sollten Sie die Daten getrennt von den Knoten speichern und die Knoten einen Zeiger auf die Daten haben lassen. Swapping dann nur zwei Zeiger tauschen, und Sie sogar die Eltern Liste Objekt nicht brauchen ...

Answer 2

Alternative Methode ..
Statt mit den Zeigern der Manipulation ist es einfacher, die Zeiger mit Doppelzeiger zu tauschen ..

void swap(Node* &a,Node* &b){ 
    Node* c=a,a=b,b=c; 
} 

void swapNodes(Node** head_ref, int x, int y) 
{ 
    Node**a=NULL,**b=NULL; 
    Node* head=*head_ref; 
    while(head!=NULL){ 
     if(head->data==x) *a=head; 
     else if(head->data==y) *b=head; 
    } 
    if(a&&b){ 
     swap(*a,*b); 
     swap((*a)->next,(*b)->next); 
    } 
}