Swap-Position in einfach verknüpften Liste in C

Question

Mir wurde eine Aufgabe zugewiesen, verschiedene Methoden für eine verkettete Liste in C zu erstellen. Ich bin auf der Swap-Methode fest, die nur scheint die gesamte verkettete Liste zu versauen. Hat jemand einen Rat, wo ich falsch liege? Prost!

Hier ist mein Code.

int main(int argc, char* argv[]) 
{ 
    // A list of pointers to Reminders 
    const int MAX_ENTRIES = 10; 
    int numOfEntries = 0 ; 
    reminder_t* pFirst = (reminder_t*) malloc (sizeof(reminder_t)); 
    reminder_t* pSecond = (reminder_t*) malloc (sizeof(reminder_t)); 
    reminder_t* pThird = (reminder_t*) malloc (sizeof(reminder_t)); 
    reminder_t* pStart = NULL; 
    if (pFirst != NULL) 
    { 
     strcpy(pFirst->message, "Mikes Birthday"); 
     pFirst->dateOfEvent.day= 1; 
     pFirst->dateOfEvent.month= 1; 
     pFirst->dateOfEvent.year= 2013; 
     pFirst->pNext = NULL; 
    } 

    if (pSecond != NULL) 
    { 
     strcpy(pSecond->message, "Als Soccer Match"); 
     pSecond->dateOfEvent.day= 2; 
     pSecond->dateOfEvent.month= 2; 
     pSecond->dateOfEvent.year= 2013; 
     pSecond->pNext = NULL; 
    } 

    if (pThird != NULL) 
    { 
     strcpy(pThird->message, "School Concert"); 
     pThird->dateOfEvent.day= 3; 
    pThird->dateOfEvent.month= 3; 
    pThird->dateOfEvent.year= 2013; 
    pThird->pNext = NULL; 
} 

pFirst->pNext = pSecond; 
pSecond->pNext = pThird; 
pThird->pNext = NULL; 
pStart = pFirst; 

printf("\n------Before------\n"); 
listEntries(pStart); 
swapPositonOf(pFirst,pThird); 

printf("\n------After-aa-----\n"); 
listEntries(pStart); 

getchar(); 
return 0; 
} 

void listEntries(reminder_t * pList) 
{ 
    printf("\n"); 
    while (pList != NULL) 
    { 
      printf("%s\n", pList->message); 
     pList = pList->pNext; 
    } 
} 

void swapPositonOf(reminder_t* first , reminder_t* second) 
{ 
    reminder_t* pFirst = (reminder_t*) first; 
reminder_t* pSecond = (reminder_t*) second; 
reminder_t* temp = second->pNext; 

pSecond->pNext = pFirst->pNext; 
pFirst->pNext = temp; 
temp = pSecond; 
pSecond = pFirst; 
pFirst = temp; 
} 

Erwartete Ausgabe:

------Before------ 

Mikes Birthday 
Als Soccer Match 
School Concert 

------After-aa----- 
School Concert 
Als Soccer Match  
Mikes Birthday 

Ausgang:

------Before------ 

Mikes Birthday 
Als Soccer Match 
School Concert 

------After-aa----- 

Mikes Birthday 

Answer 1

Wenn Sie den Inhalt des tauschen wollen Listen Knoten, dann ist es nicht schwer: Sie können nur einen Austausch für message und dateOfEvent Felder in den beiden Knoten tun.

Aber wenn Sie die Positionen dieser Knoten tauschen möchten (wie der Name der Funktion suggeriert), dann müssen Sie auf die pNext Daten Mitglied achten.
In der Tat, nur die Knoten Zeiger Swapping ist nicht genug.
Sie müssen die Positionen der Knoten vorfirst und last und etwas tun, wie zu finden:

/* reminder_t* beforeFirst, reminder_t* beforeSecond */ 
beforeFirst->pNext = second; 
beforeSecond->pNext = first; 

und Swap first->pNext und second->pNext.

Darüber hinaus ist es in diesen Listenimplementierungen im Allgemeinen wichtig, auf Sonderfälle wie Kopfknoten und Endknoten zu achten.

Answer 2

Sie sind nicht die pNext Zeiger für die Knoten kurz vor first und second Knoten ändern.

Sie müssen die pNext des Knotens vor "first Knoten" auf "second Knoten" zeigen und umgekehrt.

die verknüpfte Liste Angenommen:

Node_A -> Node_B -> Node_C -> Node_D -> Node_E

Sie haben Node_B und Node_D tauschen:
Anzahl der Links zu brechen und Form:

1. Alter Link: Node_A -> Node_B .... Neu Link: Node_A -> Node_D
2. Alter Link: Node_B -> Node_C .... Neuer Link: Node_D -> Node_C
3. Alter Link: Node_C -> Node_D .... Neuer Link: Node_C -> Node_B
4. Alter Link: Node_D -> Node_E .... Neuer Link: Node_B -> Node_E

Auch die Ecke Fälle wie NULL-Zeiger und aufeinanderfolgende Knoten erinnern.

Answer 3

Sie vertauschen es nicht richtig, was ist mit dem Knoten vor dem ersten Knoten und dem Knoten vor dem zweiten Knoten?

Answer 4

Mit einer einfach verknüpften Liste können Sie das Listenelement nicht direkt vor dem Element finden, das Sie tauschen möchten. Sie haben zuerst, zweite, und Sie können sie direkt manipulieren, aber Sie haben nicht zuerst.prev und second.prev.

Sie müssen Ihre Liste durchlaufen und die Knoten finden, die vor den zwei Knoten liegen, die Sie tauschen möchten (first_previous, second_previous). Dann muss der Knotenaustausch den nächsten von jedem dieser vorherigen Knoten austauschen.

reminder_t* first_prev, *second_prev; 
first_prev = second_prev = pStart; 
reminder_t* iter; 
for(iter = pStart; iter; iter=iter->next) 
{ 
    if(iter->next == first) first_prev = iter; 
    if(iter->next == second) second_prev = iter; 
} 

Sie müssen die oben zu behandeln leere Liste zu beheben, eine Elementliste, und Leiten ersten oder zweiten am Kopf der Liste ...