aide au débogage – permutation de 2 nœuds de la liste de liens doubles

Pourriez-vous s’il vous plaît m’aider à déboguer ce code pour échanger deux nœuds de la liste de liens doubles? Je ne suis pas capable de comprendre ce que je fais mal 🙁

voici le code:

dll* swap_node(dll *head , dll *node1 , dll *node2) { dll *tmp; int flag=0; if(node1->prev!=NULL) { node1->prev->next=node2; } else { flag=1; } if(node1->next!=NULL) { node1->next->prev=node2; } if(node2->prev!=NULL) { node2->prev->next=node1; } if(node2->next!=NULL) { node2->next->prev=node1; } tmp=node1->next; node1->next=node2->next; node2->next=tmp; tmp=node1->prev; node1->prev=node2->prev; node2->prev=tmp; if(flag==1) { head=node2; } return head; } 

Merci d’avance

Supposons que node1->next == node2 && node2->prev == node1 . Retrouvons maintenant:

 if(node1->next!=NULL) { node1->next->prev=node2; } 

Maintenant, node2->prev pointe vers node2 lui-même!

 if(node2->prev!=NULL) { node2->prev->next=node1; } 

Maintenant, node2->next pointe vers node1 , ce qui est ok pour le moment.

Rappelez-vous que node1->next pointe toujours sur node2 et que node2->next pointe sur node1 .

 tmp=node1->next; // == node2 node1->next=node2->next; // == node1 (!) node2->next=tmp; // == node2 

Nous avons donc node1->next pointant vers node1 , et node2->next de node2 . Clairement faux.

Rappelez-vous que node2-> prev pointe vers node2 , bien que node1->prev soit correct.

 tmp=node1->prev; // correct node1->prev=node2->prev; // == node2 node2->prev=tmp; // correct 

Donc, node1->prev pointe vers node2 , ce qui est correct.

Mais node1->next et node2->next ont encore tort!


Comment résoudre ceci? Ce n’est pas un problème à résoudre, car il y a quelques cas particuliers.

Peut-être détecter le cas spécial que j’ai décrit et avoir un code distinct pour celui-ci (et ne pas oublier cet autre cas spécial).

L’écriture de ce code est laissée comme un exercice au lecteur;)

Votre logique ne fonctionnera pas,

  1. Si node2 est le premier élément de la liste doublement liée
  2. Si node1 et node2 sont adjacents.

Veuillez affiner la logique mise à jour donnée ci-dessous.


 dll * swap_node (dll * head, dll * node1, dll * node2) 
 { 
     dll * previous_to_node1 = NULL;
     dll * next_to_node1 = NULL;
     dll * previous_to_node2 = NULL;
     dll * next_to_node2 = NULL;

     if ((node1 == NULL) || (node2 == NULL))
          retourne 0;

     previous_to_node1 = node1-> previous;
     next_to_node1 = node1-> next;
     previous_to_node2 = node2-> previous;
     next_to_node2 = node2-> next;

     if (previous_to_node1! = NULL) previous_to_node1-> next = node2;
     if (next_to_node1! = NULL) next_to_node1-> previous = node2;
     if (pevious_to_node2! = NULL) previous_to_node2-> next = node1;
     if (next_to_node2! = NULL) next_to_node2-> previous = node1;

     node1-> next = next_to_node2;    
     node1-> previous = previous_to_node2;
     node2-> next = next_to_node1;
     node2-> previous = previous_to_node1;

     if (previous_to_node1 == NULL) 
     {
         return node2;
     }
     else if (previous_to_node2 == NULL)
     {
         return node1;
     }

     retourne la tête;
 }