[C]renverser une liste chainée

renverser une liste chainée [C] - C - Programmation

Marsh Posté le 26-05-2009 à 20:09:04    

Salut à tous,
 
J'ai besoin de renverser une liste chainée classique en C. J'ai trouvé un truc classique qui marchait bien:
 

Code :
  1. void Reverse(struct node** headRef) {
  2.     if (*headRef != NULL) {
  3.         struct node* middle = *headRef;
  4.         struct node* front = middle->next;
  5.         struct node* back = NULL;
  6.         while (1) {
  7.             middle->next = back;
  8.             if (front == NULL) break;
  9.             back = middle;
  10.             middle = front;
  11.             front = front->next;
  12.         }
  13.         *headRef = middle;
  14.     }
  15. }


 
Maintenant, je cherche à faire la même fonction Reverse mais avec pour prototype void Reverse(struct node* headRef) (et pas void Reverse(struct node** headRef)). Des idées ?

Message cité 1 fois
Reply

Marsh Posté le 26-05-2009 à 20:09:04   

Reply

Marsh Posté le 27-05-2009 à 08:20:21    

Oui, à mon avis c'est impossible car en C on passe des valeurs donc au sortir des fonctions elles sont inchangées et alors headref conserve sa valeur d'origine.
Tu peux par contre avoir un prototype du genre  
struct node* headRef Reverse(struct node* headRef)

Message cité 1 fois
Reply

Marsh Posté le 27-05-2009 à 08:21:31    

lejeremy a écrit :

Salut à tous,
 
J'ai besoin de renverser une liste chainée classique en C. J'ai trouvé un truc classique qui marchait bien:
 

Code :
  1. void Reverse(struct node** headRef) {
  2.     if (*headRef != NULL) {
  3.         struct node* middle = *headRef;
  4.         struct node* front = middle->next;
  5.         struct node* back = NULL;
  6.         while (1) {
  7.             middle->next = back;
  8.             if (front == NULL) break;
  9.             back = middle;
  10.             middle = front;
  11.             front = front->next;
  12.         }
  13.         *headRef = middle;
  14.     }
  15. }


 
Maintenant, je cherche à faire la même fonction Reverse mais avec pour prototype void Reverse(struct node* headRef) (et pas void Reverse(struct node** headRef)). Des idées ?


C'est pas possible. Il faut soit

Code :
  1. void Reverse(struct node** headRef);


soit

Code :
  1. struct node* Reverse(struct node* headRef);


 
(ou une globale, mais ce n'est plus de la programmation, mais du bricolage).
 
NOTA : si il s'agit de parcourir une liste chainée à l'envers, je conseille d'étudier ces quelques lignes...

Code :
  1. #include <stdio.h>
  3. struct node
  4. {
  5.    struct node *next;
  6.    int data;
  7. };
  9. static void display_r (struct node *p)
  10. {
  11.    if (p != NULL)
  12.    {
  13.       printf ("%d ", p->data);
  14.       display_r (p->next);
  15.    }
  16. }
  18. static void display (struct node *p)
  19. {
  20.    display_r (p);
  21.    printf ("\n" );
  22. }
  24. static void display_rev_r (struct node *p)
  25. {
  26.    if (p != NULL)
  27.    {
  28.       display_rev_r (p->next);
  29.       printf ("%d ", p->data);
  30.    }
  31. }
  33. static void display_rev (struct node *p)
  34. {
  35.    display_rev_r (p);
  36.    printf ("\n" );
  37. }
  39. int main (void)
  40. {
  42.    struct node a[] = {
  43.       {a + 1, 1},
  44.       {a + 2, 2},
  45.       {a + 3, 3},
  46.       {NULL, 4},
  47.    };
  49.    struct node *head = a;
  51.    display (head);
  52.    display_rev (head);
  54.    return 0;
  55. }



1 2 3 4
4 3 2 1
 
Process returned 0 (0x0)   execution time : 0.026 s
Press any key to continue.

Message cité 1 fois
Message édité par Emmanuel Delahaye le 27-05-2009 à 08:43:02

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 27-05-2009 à 14:19:35    

Emmanuel Delahaye a écrit :


C'est pas possible. Il faut soit

Code :
  1. void Reverse(struct node** headRef);


soit

Code :
  1. struct node* Reverse(struct node* headRef);
 

(ou une globale, mais ce n'est plus de la programmation, mais du bricolage).

 


 
Trap D a écrit :

Oui, à mon avis c'est impossible car en C on passe des valeurs donc au sortir des fonctions elles sont inchangées et alors headref conserve sa valeur d'origine.
Tu peux par contre avoir un prototype du genre
struct node* headRef Reverse(struct node* headRef)

 

Humm, en fait j'ai eu cette question récemment, il doit donc bien y avoir un moyen...  :??: (sur l'énoncé il est bien précisé qu'ils veulent struct node*headRef et pas struct node** headRef)

 


NB: Il est pas demandé de l'afficher mais bien de l'inverser.

 

en tout cas, merci pour votre aide  :jap:

 

[edit] Maintenant que j'y pense, la bonne réponse est peut être, "c'est pas possible"... mais ça serait une question super vache ....

Message cité 1 fois
Message édité par lejeremy le 27-05-2009 à 14:24:20
Reply

Marsh Posté le 27-05-2009 à 15:02:28    

lejeremy a écrit :


 
Humm, en fait j'ai eu cette question récemment, il doit donc bien y avoir un moyen...  :??: (sur l'énoncé il est bien précisé qu'ils veulent struct node*headRef et pas struct node** headRef)


Ah ? C'est un devoir ???
 
 

lejeremy a écrit :

NB: Il est pas demandé de l'afficher mais bien de l'inverser.
 
en tout cas, merci pour votre aide  :jap:
 
[edit] Maintenant que j'y pense, la bonne réponse est peut être, "c'est pas possible"... mais ça serait une question super vache ....


 
Il faut d'abord savoir comment est identifiée ta liste. Car il y a 2 façons d'identifier une liste chaînée et ça donne des possibilités différentes pour l'inversion. Et toujours en considérant que "struct node" est un noeud de la liste
1) soit tu possèdes en main l'adresse du premier noeud. Donc tu as un "struct node* first". Or, comme ta fonction d'inversion doit modifier cette adresse (puisque le premier noeud change), il te faut passer l'adresse de l'adresse à la fonction qui recevra donc un "struct node** pt". Une fonction qui modifie une variable doit recevoir l'adresse de la variable et ça c'est incontournable.  
 
2) soit tu possèdes en main une structure qui contient l'adresse du premier noeud. Par exemple un truc de ce style

Code :
  1. struct liste {
  2.      struct noeud* first;
  3. };


Ca peut paraître inutile voire idiot de créer une structure qui ne contient qu'un élément que tu pourrais donc tenir directement... sauf que ça permet ensuite de faire évoluer l'objet. Tu peux par exemple ensuite y rajouter une variable qui contiendra le nombre d'éléments, une autre qui contiendra l'élément en cours, une auitre qui contiendra le dernier, bref tout un panel d'outils pour t'aider à gérer ta liste. Ainsi ta structure peut devenir

Code :
  1. struct liste {
  2.      struct noeud* first;
  3.      struct noeud* last;
  4.      struct noeud* current;
  5.      unsigned long len;
  6. };


 
Et donc toute fonction qui doit manipuler ta liste n'aura qu'à recevoir un "struct liste *pt". Avec ce pt en main, la fonction pourra taper à loisir dans pt->first, pt->last, pt->len et modifier ces variables. Et tu n'as qu'un simple pointeur à gérer et non un double.
 
Voili voilà.

Message cité 1 fois
Message édité par Sve@r le 27-05-2009 à 15:04:16

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 27-05-2009 à 15:21:33    

Sve@r a écrit :


Ah ? C'est un devoir ???

 

Humm pour être honnête c'est une question que j'ai eu lors d'un entretien technique dans une boite (dont je préférerai rester discret sur le nom).

 
Sve@r a écrit :

 

Il faut d'abord savoir comment est identifiée ta liste. Car il y a 2 façons d'identifier une liste chaînée et ça donne des possibilités différentes pour l'inversion. Et toujours en considérant que "struct node" est un noeud de la liste

 

1) soit tu possèdes en main une structure qui contient l'adresse du premier noeud. Par exemple un truc de ce style

Code :
  1. struct liste {
  2.      struct noeud* first;
  3. };


Ca peut paraître inutile voire idiot de créer une structure qui ne contient qu'un élément que tu pourrais donc tenir directement... sauf que ça permet ensuite de faire évoluer l'objet. Tu peux par exemple ensuite y rajouter une variable qui contiendra le nombre d'éléments, une autre qui contiendra l'élément en cours, une auitre qui contiendra le dernier, bref tout un panel d'outils pour t'aider à gérer ta liste. Ainsi ta structure peut devenir

Code :
  1. struct liste {
  2.      struct noeud* first;
  3.      struct noeud* last;
  4.      struct noeud* current;
  5.      unsigned long len;
  6. };
 

Et donc toute fonction qui doit manipuler ta liste n'aura qu'à recevoir un "struct liste *pt". Avec ce pt en main, la fonction pourra taper à loisir dans pt->first, pt->last, pt->len et modifier ces variables. Et tu n'as qu'un simple pointeur à gérer et non un double.

 

Voili voilà.


Pas bête, j'avais pas pensé à changer la structure... Cependant, de mémoire il me semble bien qu'ils demandaient d'utiliser un struct node* et non pas un struct liste ou un truc du genre. Il faut que je leur redemande quand je les vois car vu vos réponses, ça me laisse perplexe...

 

[edit]j'avais la crêve pendant l'entretien, il se peut que j'ai aussi lu l'énoncé de travers.

Message cité 1 fois
Message édité par lejeremy le 27-05-2009 à 15:22:33
Reply

Marsh Posté le 27-05-2009 à 19:58:09    

lejeremy a écrit :

Pas bête, j'avais pas pensé à changer la structure... Cependant, de mémoire il me semble bien qu'ils demandaient d'utiliser un struct node* et non pas un struct liste ou un truc du genre. Il faut que je leur redemande quand je les vois car vu vos réponses, ça me laisse perplexe...


 
Autre solution à laquelle je n'ai pas pensé => tu ne modifies pas les adresses de tes noeuds... mais leur contenu.
Ainsi le contenu du premier noeud permute avec celui du dernier, celui du second avec celui de l'avant dernier etc.
 
Ca se fait à coup de memcpy en passant par un noeud intermédiaire et donc la fonction qui fait ça recevra un "struct node *" correspondant au premier noeud de la liste...
 
Je n'y ai pas pensé de suite tellement ça me parait con (vaut mieux permuter 2 adresses de 4 octets que 2 structures de taille inconnue (8Gb ???)) mais bon, si c'est imposé...


Message édité par Sve@r le 27-05-2009 à 19:59:46

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Marsh Posté le 28-05-2009 à 21:33:01    

Bon j'ai enfin la solution... Moi aussi j'étais passé totalement à côté qu'on pouvait copier manuellement le contenu des nodes.
 
Alors premièrement, on inverse la liste à partir du deuxième node comme dans le premier cas.
Ensuite, on switch manuellement le dernier caractère (copie manuelle) dans headRef et on le fait pointer bien où il faut. On fait aussi pareil en faisant pointer le dernier de la chaîne vers NULL (fin de liste chainée).
 
Je posterai ma solution en code demain si il y en a qui sont intéressés.
 
 
merci à tous ceux qui ont essayer de me répondre  :hello:
a+

Message cité 1 fois
Reply

Marsh Posté le 29-05-2009 à 10:52:21    

lejeremy a écrit :

Bon j'ai enfin la solution...


Je ne vois pas comment tu vas modifier le "head" original ...


---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 29-05-2009 à 15:59:50    

Comme promis, voici le code source:

 

(avec un schéma, c'est beaucoup plus facile à comprendre).

 
Code :
  1. struct node{
  2.     char c;
  3.     struct node* next;
  4. };
 
Code :
  1. void Reverse2(struct node* headRef) {
  2. //inversion de la sous listeen partant du 2ème maillon
  3. /*
  4. if cas limite ... liste avec que deux éléments ....
  5. ...
  6. */
  7. struct node* deb=headRef;
  8. struct node* middle=headRef->next;
  9. struct node* head=headRef->next->next;
  10. struct node* node2=headRef->next; //utile a la fin
  11. while(1){
  12.     middle->next=deb;
  13.     if(head->next==NULL){
  14.         break;
  15.     }
  16.     deb=middle;
  17.     middle=head;
  18.     head=head->next;
  19. }
  20.  
  21. //echange valeur du first et last node
  22. char tmp=headRef->c;
  23. headRef->c=head->c;
  24. head->c=tmp;
  25.  
  26. // on refait bien pointer le 1er node, le 2ème node et le dernier node
  27. headRef->next=middle;
  28. node2->next=head;
  29. head->next=NULL;
  30. }
 

voilà voila

Message cité 1 fois
Message édité par lejeremy le 29-05-2009 à 16:07:50
Reply

Marsh Posté le 29-05-2009 à 15:59:50   

Reply

Marsh Posté le 29-05-2009 à 16:13:30    

lejeremy a écrit :

Comme promis, voici le code source:

 

(avec un schéma, c'est beaucoup plus facile à comprendre).

 
Code :
  1. struct node{
  2.     char c;
  3.     struct node* next;
  4. };
 
Code :
  1. void Reverse2(struct node* headRef) {
  2. <...>




Je n'ai toujours pas compris comment tu modifiais headRef...

 

http://www.bien-programmer.fr/note [...] e_variable

 

Montre ton code de test.
 


Message édité par Emmanuel Delahaye le 29-05-2009 à 16:15:48

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 29-05-2009 à 16:15:06    

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <strings.h>
  4.  
  5. typedef struct node{
  6.     char c;
  7.     struct node* next;
  8. } node;
  9.  
  10. typedef node* llist;
  11.  
  12.  
  13. llist CreateList(char * str){
  14.     int i;int size=strlen(str);
  15.     llist liste=NULL; struct node* cur=liste;struct node*prev=NULL;
  16.     for(i=0;i<size;i++){
  17.         if (i==0){
  18.             liste=malloc(sizeof(struct node));
  19.             cur=liste;
  20.             cur->c=*(str+i);
  21.         }
  22.         else{
  23.             struct node* tmp=malloc(sizeof(struct node));
  24.             cur=tmp;
  25.             cur->c=*(str+i);
  26.             prev->next=cur;
  27.         }
  28.         prev=cur;
  29.  
  30.         if(i==size-1){
  31.             cur->next=NULL;
  32.         }
  33.  
  34.     }
  35.     return liste;
  36. }
  37.  
  38.  
  39. void DisplayList(llist liste){
  40.     struct node* cur=liste;
  41.     if (cur==NULL){
  42.         printf("ERREUR: liste vide\n\r" );
  43.         return;
  44.     }
  45.     while(cur->next!=NULL){
  46.         printf("%c ",cur->c);
  47.         cur=cur->next;
  48.     }
  49.     printf("%c\n\r",cur->c);
  50. }
  51.  
  52. void Reverse(struct node** headRef) {
  53.     if (*headRef != NULL) {
  54.         struct node* middle = *headRef;
  55.         struct node* front = middle->next;
  56.         struct node* back = NULL;
  57.         while (1) {
  58.             middle->next = back;
  59.             if (front == NULL) break;
  60.             back = middle;
  61.             middle = front;
  62.             front = front->next;
  63.         }
  64.         *headRef = middle;
  65.     }
  66. }
  67.  
  68.  
  69. void Reverse2(struct node* headRef) {
  70. //inversion de la sous listeen partant du 2ème maillon
  71. /*
  72. if cas limite ...
  73. ...
  74. */
  75. struct node* deb=headRef;
  76. struct node* middle=headRef->next;
  77. struct node* head=headRef->next->next;
  78. struct node* node2=headRef->next; //utile a la fin
  79. while(1){
  80.     middle->next=deb;
  81.     if(head->next==NULL){
  82.         break;
  83.     }
  84.     deb=middle;
  85.     middle=head;
  86.     head=head->next;
  87. }
  88.  
  89. //echange valeur du first et last
  90. char tmp=headRef->c;
  91. headRef->c=head->c;
  92. head->c=tmp;
  93.  
  94. // on remet headref au debut
  95. headRef->next=middle;
  96. node2->next=head;
  97. head->next=NULL;
  98. }
  99.  
  100.  
  101.  
  102.  
  103. int main (int argc,char** argv){
  104.     llist liste=CreateList("abcdefg" );
  105.     DisplayList(liste);
  106.     Reverse2(liste);
  107.     DisplayList(liste);
  108. }

Message cité 1 fois
Reply

Marsh Posté le 29-05-2009 à 16:24:36    

lejeremy a écrit :

<code>


Oui, je vois. La liste est inchangé, mais le contenu est modifié. C'est la pire des solutions sur le plan de l'efficacité. elle va à l'encontre d'un principe sage qui veut qu'on ne touche jamais aux données, mais au chainage... Qui dit que les données ont la même taille (on peut chainer n'importe quoi...)
 
Bref, cette contrainte absurde sur le prototype fait générer un code absurde et inutilisable. J'espère que le prof fera la remarque...


---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 29-05-2009 à 16:29:17    

En fait, je sais pas si tu as regardé, mais au final on change le contenu seulement pour 2 maillons de la chaine. Pour les autres on inverse classiquement les pointeurs. Et encore une fois, c'est pas pour un prof mais c'était pour un entretien technique dans une boite.
 
Toujours est-il que moi aussi je suis passé carrément à côte de la solution au début.

Message cité 2 fois
Reply

Marsh Posté le 29-05-2009 à 16:34:17    

lejeremy a écrit :

En fait, je sais pas si tu as regardé, mais au final on change le contenu seulement pour 2 maillons de la chaine. Pour les autres on inverse classiquement les pointeurs. Et encore une fois, c'est pas pour un prof mais c'était pour un entretien technique dans une boite.

 

Toujours est-il que moi aussi je suis passé carrément à côte de la solution au début.


Eh bé. Si cette boite attend ce genre de solution technique, ça fait peur... Sans dec, si les données n'ont pas la même tallle, ça va être chaud... Il existe des structures de données comme ceci :

 
Code :
  1. struct data
  2. {
  3.    size_t taille;
  4.    type_t data[1];
  5. };
 

mappés sur une zone mémoire de taille adéquate (et oui, c'est portable. Cette 'astuce' a même été entérinée en C99 sous la forme :

Code :
  1. /* C99 */
  2. struct data
  3. {
  4.    size_t taille;
  5.    type_t data[];
  6. };


).

Message cité 1 fois
Message édité par Emmanuel Delahaye le 29-05-2009 à 16:35:31

---------------
Des infos sur la programmation et le langage C: http://www.bien-programmer.fr Pas de Wi-Fi à la maison : http://www.cpl-france.org/
Reply

Marsh Posté le 30-05-2009 à 12:32:50    

lejeremy a écrit :

Toujours est-il que moi aussi je suis passé carrément à côte de la solution au début.


C'est naturel. Seul un gros débile ou un très débutant y aurait pensé d'instinct. Et en plus Emmanuel a fait une bonne remarque en disant qu'on peut chaîner n'importe quoi car la solution de permut des data suppose que les data sont de même nature (ou au pire de même taille).
 

Emmanuel Delahaye a écrit :

Eh bé. Si cette boite attend ce genre de solution technique, ça fait peur...


Ouaip. Ou alors ils cherchent le cas le plus tordu pour voir jusqu'où peut aller le candidat pour répondre au problème imposé.  
 

Emmanuel Delahaye a écrit :

Il existe des structures de données comme ceci :  
 

Code :
  1. struct data
  2. {
  3.    size_t taille;
  4.    type_t data[1];
  5. };


 
mappés sur une zone mémoire de taille adéquate


Euh... je ne comprends pas le rôle de ce genre de structure, ni pourquoi data n'est pas un simple pointeur ???


Message édité par Sve@r le 30-05-2009 à 12:44:34

---------------
Vous ne pouvez pas apporter la prospérité au pauvre en la retirant au riche.
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed