échange en liste doublement chaînée

J’essaie d’échanger deux nœuds dans une liste doublement chaînée. Ci-dessous se trouve la partie du programme ayant une fonction d’échange.

int swap (int x, int y) { struct node *temp = NULL ; struct node *ptr1, *ptr2; temp = (struct node *)malloc(sizeof(struct node)); if (head == NULL ) { printf("Null Nodes"); } else { ptr1 = ptr2 = head; int count = 1; while (count != x) { ptr1 = ptr1->next; count++; } int count2 = 1; while (count2 != y) { ptr2 = ptr2->next; count2++; } ptr1->next->prev = ptr2; ptr1->prev->next = ptr2; ptr2->next->prev = ptr1; ptr2->prev->next = ptr1; temp->prev = ptr1->prev; ptr1->prev = ptr2->prev; ptr2->prev = temp->prev; temp->next = ptr1->next; ptr1->next = ptr2->next; ptr2->next = temp->next; } return 0; } 

Lorsque j’exécute ce programme, en cas de premier et deuxième nœuds, il se bloque. tandis que dans le cas de tout autre nœud, il donne une sortie de boucle infinie (par exemple: – 2-> 4 2-> 4 2-> 4 …. etc.) `.

Je sais qu’il y a d’autres questions sur les échanges de nœuds, mais je n’en ai trouvé aucune semblable à mon problème. Sil te plait aide moi..!!

Merci d’avance.

Le code échouera si ptr1 == head (ptr1-> prev == NULL) ou ptr2 == head (ptr2-> prev == NULL), car il finit par essayer d’utiliser head-> next, ce qui n’existe pas . Il faut également vérifier la fin de la liste si ptr1-> next == NULL ou ptr2-> next == NULL, ce qui peut être traité à l’aide d’un pointeur de queue local. L’utilisation de pointeurs pour désigner un nœud peut simplifier le code. Par exemple, le pointeur sur le pointeur suivant sur ptr1 pourrait être & ptr1-> prev-> next ou & head. Le pointeur vers le pointeur précédent sur ptr2 pourrait être & ptr2-> next-> prev ou & tail (et définir tail = ptr2).

L’utilisation de pointeurs pour désigner un nœud corrige le problème de permutation des nœuds adjacents. Temp peut également être un pointeur sur un nœud.

Exemple de code utilisant des pointeurs vers des nœuds (au lieu de comptes) pour permuter:

 typedef struct node NODE; /* ... */ NODE * SwapNodes(NODE *head, NODE *ptr1, NODE *ptr2) { NODE **p1pn; /* & ptr1->prev->next */ NODE **p1np; /* & ptr1->next->prev */ NODE **p2pn; /* & b->prev->next */ NODE **p2np; /* & b->next->prev */ NODE *tail; /* only used when x->next == NULL */ NODE *temp; /* temp */ if(head == NULL || ptr1 == NULL || ptr2 == NULL || ptr1 == ptr2) return head; if(head == ptr1) p1pn = &head; else p1pn = &ptr1->prev->next; if(head == ptr2) p2pn = &head; else p2pn = &ptr2->prev->next; if(ptr1->next == NULL){ p1np = &tail; tail = ptr1; } else p1np = &ptr1->next->prev; if(ptr2->next == NULL){ p2np = &tail; tail = ptr2; }else p2np = &ptr2->next->prev; *p1pn = ptr2; *p1np = ptr2; *p2pn = ptr1; *p2np = ptr1; temp = ptr1->prev; ptr1->prev = ptr2->prev; ptr2->prev = temp; temp = ptr1->next; ptr1->next = ptr2->next; ptr2->next = temp; return head; } 

Cela peut être compacté, mais si vous rencontrez des problèmes, il peut être utile de le préciser en détail.

 typedef struct node Node; void link( Node* a, Node* b ) { a->next = b; b->prev = a; } void swap_nodes( Node* a, Node* b ) { if(a==b) return; // don't swap with yourself // handle adjacent nodes separately if( a->next == b ) { Node* bef = a->prev; Node* aft = b->next; link( bef, b); // link bef, b, a, aft link( b, a ); link( a, aft ); } else if( b->next == a ) { Node* bef = b->prev; Node* aft = a->next; link( bef, a); // link bef, a, b, aft link( a, b ); link( b, aft ); } else { Node* a_prv = a->prev; Node* a_nxt = a->next; Node* b_prv = b->prev; Node* b_nxt = b->next; link( a_prv, b ); link( b, a_nxt ); // links b in a's old position link( b_prv, a ); link( a, b_nxt ); // links a in b's old position } } 

Notez également que votre nœud principal ne doit jamais être null , il doit s’agir d’un nœud sentinelle qui renvoie à lui-même si votre liste est vide. Cela signifie qu’il n’y a jamais de premier nœud, ni de dernier, et la liste n’est jamais vide. Cela supprime une tonne de cas spéciaux. Voir ici