Fonction récursive qui inverse une liste chaînée

Salut les amis ..
voici une fonction qui inverse une liste sans copier ses elements :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

//ma structure : typedef struct node{ int data; struct node* next; }node; typedef node* pt ;   void reverserecv2(pt* listhead){ pt curr=*listhead,suiv; //printf("before call : \nargument = %p \tcurr= %p \tcurr->next =%p \n",*listhead,curr,curr->next); if(curr && curr->next){ suiv=curr->next; reverserecv2(&((*listhead)->next)); //printf("after call before changing listhead : \n argument = %p \tcurr= %p \tcurr->next =%p \t suiv =%p\n",*listhead,curr,curr->next,suiv); suiv->next=curr; *listhead=curr->next; //printf("after changing listhead :\nargument = %p \t curr= %p \t curr->next =%p \tsuiv =%p\n",*listhead,curr,curr->next,suiv); suiv->next->next=NULL; } }

---

le probleme que j'ai c'est le changement du listhead qui saute vers le dernier noeud , comment curr->next reste stable ? suiv et curr changent apres l'appel mais curr->next pointe toujours vers le dernier noeud .. pourquoi ? et merci beaucoup

Bonjour

Citation:

---

Envoyé par MouadCR7

le probleme que j'ai c'est le changement du listhead qui saute vers le dernier noeud

---

Non. Le problème c'est que ce code est imbittable. Son principal souci est qu'il a trop de commentaires.

Citation:

---

Envoyé par MouadCR7

comment curr->next reste stable ? suiv et curr changent apres l'appel mais curr->next pointe toujours vers le dernier noeud .. pourquoi ?

---

Ben peut-être parce que tu ne modifies pas vraiment le maillon mais juste sa copie. Si j'écris par exemple a=b puis b=5, est-ce que ça va modifier "a" ? C'est un peu la même chose avec ton code.
Déjà on ne cache jamais un pointeur derrière un type. Ca ne sert à rien et ça nuit à la bonne compréhension. Parce que lire ce reverserecv2(&((*listhead)->next)); ça me fait un peu saigner les yeux et je crains pour la partie de code que tu ne montres pas (celle où tu remplis et affiche la liste). Je sais bien que tu te bats avec des node **x vu que tu veux modifier des adresses de noeuds. Mais justement, ton principal souci c'est que tu n'as pas pensé à créer un type pour la liste.

Parce que tu l'aurais fait, tu n'aurais plus de souci de "**". Regarde cet exemple assez simplifié...

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60

#include <stdio.h> #include <stdlib.h>   typedef struct s_noeud { int v; struct s_noeud *next; } t_noeud;   typedef struct { t_noeud *first; } t_liste;   void liste_init(t_liste*); void liste_insert(t_liste*, t_noeud*); void liste_affich(t_liste*);   t_noeud *noeud_create(int); void noeud_affich(t_noeud*);   void liste_init(t_liste *l) { l->first=NULL; }   void liste_insert(t_liste *l, t_noeud *n) { n->next=l->first; l->first=n; }   void liste_affich(t_liste *l) { if (l->first == NULL) { printf("liste vide !!!\n"); return; } t_noeud *p; for (p=l->first; p != NULL; p=p->next) noeud_affich(p); }   t_noeud *noeud_create(int v) { t_noeud *n; n=malloc(sizeof(*n)); if (n == NULL) return NULL; n->v=v; n->next=NULL; return n; }   void noeud_affich(t_noeud *n) { printf("n=%p, v=%d, next=%p\n", n, n->v, n->next); }   int main() { t_liste l; liste_init(&l); liste_affich(&l); int i; for (i=1; i <= 10; i++) liste_insert(&l, noeud_create(i)); liste_affich(&l); }

---

Des fonctions simples, dédiées à leur travail et à rien d'autre. Et donc que tu peux appeler quand tu en as besoin. Je pense qu'en repartant de là, tu auras moins de soucis à coder ton "reverse"...

merci pour votre reponse , je suis tout d'accord avec vous .. cette fonction est de mon prof lors d'un exercice , elle est un peu difficile a lire mais elle est correct . le probleme que j'ai est dans la comprehension de cette fonction c'est ca pourquoi j'ai ajoute des printf() pour voir comment les addresses changent .. curr->next comme curr et suiv changent mais lors d'un premier return elle seul reste stable dans le dernier noeud , c'est ca pourquoi mon vrai *listhead ( mon premier argument) change et devient le dernier , ma question est pourquoi curr->next ne change pas, j'ai dessine plus qu'un exemple et vraiment je me suis coince ici

Alors il nous faudrait tout le code pour qu'on puisse le tester...

d'accord voici tout mon code source :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

#include<stdio.h> #include<stdlib.h> typedef struct node{ int data; struct node* next; }node; typedef node* pt ;   pt getNode(){ pt noeud=malloc(sizeof(node)); if(noeud==NULL) {printf("no memorry ! sorry .. \n"); return noeud;} printf("give me the data : \t "); scanf("%d",&(noeud->data)); noeud->next=NULL; return noeud; } pt creatList(int n){ pt listhead=getNode(),temp; if(listhead==NULL) exit(0); int i; temp=listhead; for(i=1;i<n;i++){ temp->next=getNode(); if(temp->next==NULL) exit(0); temp=temp->next; } return listhead; }   void reverse(pt* listhead){ pt curr=(*listhead)->next ,prec=*listhead,suiv=curr->next; if(curr && prec && suiv){ while (suiv) { curr->next=prec; prec=curr; curr=suiv; suiv=suiv->next; } } curr->next=prec; (*listhead)->next=NULL; (*listhead)=curr; } // cell ci void reverserecv2(pt* listhead){ pt curr=*listhead,suiv; //printf("before call : \nargument = %p \tcurr= %p \tcurr->next =%p \n",*listhead,curr,curr->next); if(curr && curr->next){ suiv=curr->next; reverserecv2(&((*listhead)->next)); //printf("after call before changing listhead : \nargument = %p \tcurr= %p \tcurr->next =%p \tsuiv =%p\n",*listhead,curr,curr->next,suiv); suiv->next=curr; *listhead=curr->next; //printf("after changing listhead :\nargument = %p \tcurr= %p \tcurr->next =%p \tsuiv =%p\n",*listhead,curr,curr->next,suiv); suiv->next->next=NULL; } } void screen(pt listhead){ while(listhead){ printf("%d\t",listhead->data); listhead=listhead->next; } printf("\n"); }       int main(int argc, char const *argv[]) { int n; pt temp=creatList(4); screen(temp); reverserecv2(&temp); screen(temp);   return 0; }

---

Citation:

---

Envoyé par MouadCR7

le probleme que j'ai c'est le changement du listhead qui saute vers le dernier noeud , comment curr->next reste stable ? suiv et curr changent apres l'appel mais curr->next pointe toujours vers le dernier noeud .. pourquoi ? et merci beaucoup

---

Tu sembles louper le concept de pointeur. Un pointeur c'est une variable qui pointe quelque part.

Relis bien ton dessin en même temps que mes notes.

Ici curr, suiv et listhead sont 2 variables et 1 paramètres locaux. Donc pendant l'appel récursif, il ne changeront pas de valeur (la sous fonction n'a aucun accès aux variables de l'appelant) et comme ce sont des pointeurs ils pointerons toujours vers la même mémoire.
Avant et après l'appel :
- listhead pointe sur la mémoire où il faudra écrire le début de la liste.
- curr pointe sur ce qui était le premier node de la liste.
- suiv pointe sur ce qui était le second node de la liste.
L'appel reçoit l'adresse de curr->suiv, il va mettre dans cette mémoire (qui n'a rien à voir avec les 3 mémoires locales ci-avant.) la nouvelle adresse du début la sous liste qu'il a fabriqué (les nodes qui étaient second et dernier de la liste initiale, sont devenus respectivement dernier et premier de la sous liste.)
Il ne reste plus qu'à tout mettre à la bonne position
suiv->next=curr; suiv pointe sur l'ancien second devenu dernier, curr pointe sur le premier. Donc le premier passe après le dernier.
*listhead=curr->next; on doit noter la nouvelle tête de liste, c'est celle que l'appel a trouvé, il a mis sa valeur dans l'adresse qu'on lui a passé. curr n'a pas bougé, &curr->next est justement l'adresse passée, donc curr->next contient bien le début de la sous-liste.
suiv->next->next=NULL; La ligne la plus complexe, on aurait pu écrire également curr->next=NULL;, qui dit que le dernier (désigné par curr) n'a pas de suivant.