Tri d'une liste doublement chainée

Tri d'une liste doublement chainée - C++ - Programmation

Marsh Posté le 29-12-2012 à 14:39:29    

J'ai programmé une fonction de tri pour ma liste, mais il n'affiche pas la dernière valeur.
Par exemple j'ai 4 valeurs a trier:
2
7
4
3
 
et la fonction tri comme ça:
2
3
4
 
Voila le code si quelqu'un peut me dire ce ça marche pas:
 


Message édité par assil le 30-12-2012 à 23:50:48
Reply

Marsh Posté le 29-12-2012 à 14:39:29   

Reply

Marsh Posté le 29-12-2012 à 15:18:28    

Moi j'aime bien l'indentation.

Code :
  1. void Tri_liste(Element** Entete)
  2. {
  3.   Element *courant;
  4.   courant=*Entete;
  5.  
  6.   if (courant->suivant==NULL)
  7.     return;
  8.  
  9.   Element *ptr,*tmp;
  10.  
  11.   courant=courant->suivant;
  12.   while(courant!=NULL)
  13.     {
  14.       ptr=courant;
  15.       tmp=courant->precedent;
  16.       courant=courant->suivant;
  17.       while (tmp!=NULL && tmp->prix>ptr->prix)
  18.         {
  19.           tmp=tmp->precedent;
  20.         }
  21.       ptr->precedent->suivant=ptr->suivant;
  22.       if (ptr->suivant!=NULL)
  23.         {
  24.           ptr->suivant->precedent=ptr->precedent;
  25.           if (tmp==NULL)
  26.             {
  27.               tmp=*Entete;
  28.               ptr->precedent=NULL;
  29.               ptr->suivant=tmp;
  30.               ptr->suivant->precedent=ptr;
  31.               *Entete=ptr->precedent;
  32.             }
  33.           else
  34.             {
  35.               tmp=tmp->suivant;
  36.               tmp->precedent->suivant=ptr;
  37.               ptr->precedent=tmp->precedent;
  38.               tmp->precedent=ptr;
  39.               ptr->suivant=tmp;
  40.             }
  41.         }
  42.     }
  43. }


 
Ceci dit, le code est un poil tordu pour moi, je ne peux que te conseiller d'ajouter quelque print pour bien saisir le déroulement de ton programme.

Reply

Marsh Posté le 29-12-2012 à 15:36:22    

Merci pour ta réponse, mais j'ai essayé tout ce que je peux sans rien trouver.

Reply

Marsh Posté le 29-12-2012 à 22:40:09    

J'ai corrigé le code  

Code :
  1. void Tri_liste(Element** Entete)
  2. {
  3.      Element *courant;
  4.      Element *ptr,*tmp, *tmp1;
  6.      courant=*Entete;
  7.    
  8.      if (courant->suivant==NULL)
  9.        return;
  10.    
  11.    
  12.      courant=courant->suivant;
  13.      while(courant!=NULL)
  14.      {
  15.          ptr=courant;
  16.          tmp=courant->precedent;
  17.          courant=courant->suivant;
  18.          while (tmp !=NULL && tmp->prix>ptr->prix)
  19.          {
  20.              tmp=tmp->precedent;
  21.          }
  22.   // on raccorde les elemnts qui entourent ptr
  23.   ptr->precedent->suivant=ptr->suivant;
  24.   if (ptr->suivant != NULL)
  25.   ptr->suivant->precedent = ptr->precedent;
  27.   if (tmp == NULL)
  28.   { // on ajoute en tete
  29.    ptr->precedent = NULL ;
  30.    (*Entete)->precedent = ptr;
  31.    ptr->suivant = *Entete;
  32.    *Entete = ptr;
  33.   }
  34.   else
  35.   {
  36.   ptr->suivant = tmp->suivant;
  37.   if (tmp->suivant != NULL)
  38.    tmp->suivant->precedent = ptr;
  39.   tmp->suivant = ptr;
  40.   ptr->precedent = tmp;
  41.   }
  43. }
  44. }


Reply

Marsh Posté le 29-12-2012 à 23:09:53    

Merci pour votre aide mais même avec ça, le tri marche pas et pour les valeurs 7,2,4 et 3 j'ai eu comme résultat 0,2,3 et 4.

Message cité 1 fois
Reply

Marsh Posté le 30-12-2012 à 10:05:02    

assil a écrit :

Merci pour votre aide mais même avec ça, le tri marche pas et pour les valeurs 7,2,4 et 3 j'ai eu comme résultat 0,2,3 et 4.

Mon code fonctionne très bien chez moi, le voici en intégralite :

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <conio.h>
  5. typedef struct _elem
  6. {
  7. int prix;
  8. struct _elem *precedent;
  9. struct _elem *suivant;
  10. } Element ;
  13. void Tri_liste(Element** Entete)
  14. {
  15.      Element *courant;
  16.      Element *ptr,*tmp;
  18.  puts("Tri de la liste" );
  20.      courant=*Entete;
  21.    
  22.      if (courant == NULL || courant->suivant==NULL)
  23.        return;
  24.    
  25.    
  26.      courant=courant->suivant;
  27.      while(courant!=NULL)
  28.      {
  29.          ptr=courant;
  30.          tmp=courant->precedent;
  31.          courant=courant->suivant;
  32.          while (tmp !=NULL && tmp->prix>ptr->prix)
  33.          {
  34.              tmp=tmp->precedent;
  35.          }
  36.   // on raccorde les elemnts qui entourent ptr
  37.   ptr->precedent->suivant=ptr->suivant;
  38.   if (ptr->suivant != NULL)
  39.   ptr->suivant->precedent = ptr->precedent;
  41.   if (tmp == NULL)
  42.   { // on ajoute en tete
  43.    ptr->precedent = NULL ;
  44.    (*Entete)->precedent = ptr;
  45.    ptr->suivant = *Entete;
  46.    *Entete = ptr;
  47.   }
  48.   else
  49.   {
  50.   ptr->suivant = tmp->suivant;
  51.   if (tmp->suivant != NULL)
  52.    tmp->suivant->precedent = ptr;
  53.   tmp->suivant = ptr;
  54.   ptr->precedent = tmp;
  55.   }
  57. }
  58. }
  63. Element *add(Element *Liste, int Val)
  64. {
  65. Element *elem = malloc(sizeof(*elem));
  66. Element *tmp ;
  67. if (elem == NULL)
  68.         {
  69.                 printf("Pb ajout de %d\n", Val);
  70.  return Liste;
  71.         }
  72. elem->prix = Val;
  73. elem->precedent = NULL;
  74. elem->suivant = NULL;
  76. if (Liste == NULL)
  77.  Liste = elem;
  78. else
  79. {
  80.  tmp = Liste;
  82.  while(tmp->suivant != NULL)
  83.   tmp = tmp -> suivant;
  85.  tmp->suivant = elem;
  86.  elem->precedent = tmp;
  87. }
  88. return Liste ;
  89. }
  92. void my_free(Element *Liste)
  93. {
  94. Element *tmp = Liste;
  95. Element *tmp2 ;
  97. while(tmp != NULL)
  98. {
  99.  tmp2 = tmp->suivant;
  100.  free(tmp);
  101.  tmp = tmp2;
  102. }
  103. }
  106. void printf_liste(Element *Liste)
  107. {
  108. Element *tmp = Liste;
  109. Element *tmp1 = Liste;
  111. puts("Affichage de la liste en sens direct" );
  112. while(tmp != NULL)
  113. {
  114.  printf("%d\n", tmp->prix);
  115.  tmp = tmp->suivant;
  116. }
  118. puts("Affichage de la liste en sens indirect" );
  120. tmp = Liste;
  121. while (tmp != NULL)
  122. {
  123.  tmp1 = tmp;
  124.  tmp = tmp->suivant;
  125. }
  126. while(tmp1 != NULL)
  127. {
  128.  printf("%d\n", tmp1->prix);
  129.  tmp1 = tmp1->precedent;
  130. }
  132. puts("\n" );
  134. }
  137. // Liste a sans element
  138. void t1(void)
  139. {
  140. Element *Liste = NULL;
  142. puts("Liste sans element" );
  144. printf_liste(Liste);
  146. Tri_liste(&Liste);
  148. printf_liste(Liste);
  150. my_free(Liste);
  151. }
  154. // liste avec un seul element
  155. void t2(void)
  156. {
  157. Element *Liste = NULL;
  159. puts("Liste avec un seul element" );
  161. Liste = add(Liste, 2);
  163. printf_liste(Liste);
  165. Tri_liste(&Liste);
  167. printf_liste(Liste);
  169. my_free(Liste);
  170. }
  172. // liste avec un plusieurs elements tries
  173. void t3(void)
  174. {
  175. Element *Liste = NULL;
  177. puts("liste avec un plusieurs elements tries" );
  179. Liste = add(Liste, 2);
  180. Liste = add(Liste, 3);
  181. Liste = add(Liste, 4);
  182. Liste = add(Liste, 5);
  183. Liste = add(Liste, 7);
  186. printf_liste(Liste);
  188. Tri_liste(&Liste);
  190. printf_liste(Liste);
  192. my_free(Liste);
  193. }
  195. // liste avec un plusieurs elements tries en sens inverse
  196. void t4(void)
  197. {
  198. Element *Liste = NULL;
  200. puts("liste avec un plusieurs elements tries en sens inverse " );
  201. Liste = add(Liste, 7);
  202. Liste = add(Liste, 5);
  203. Liste = add(Liste, 4);
  204. Liste = add(Liste, 3);
  205. Liste = add(Liste, 2);
  208. printf_liste(Liste);
  210. Tri_liste(&Liste);
  212. printf_liste(Liste);
  214. my_free(Liste);
  215. }
  217. // liste avec un plusieurs elements
  218. void t5(void)
  219. {
  220. Element *Liste = NULL;
  222. puts("liste avec un plusieurs elements quelconques" );
  224. Liste = add(Liste, 7);
  225. Liste = add(Liste, 10);
  226. Liste = add(Liste, 4);
  227. Liste = add(Liste, 9);
  228. Liste = add(Liste, 4);
  231. printf_liste(Liste);
  233. Tri_liste(&Liste);
  235. printf_liste(Liste);
  237. my_free(Liste);
  238. }
  240. int main(void)
  241. {
  243. t1();
  244. t2();
  245. t3();
  246. t4();
  247. t5();
  249. _getch();
  250. return 0;
  251. }


EDIT C'est quoi ce problème d'indentation ? Les tab ne sont pas transformés en espaces ?


Message édité par Trap D le 30-12-2012 à 10:55:59
Reply

Marsh Posté le 30-12-2012 à 11:49:47    

J'ai testé ton code mais lorsque j'ai essayé de l'implanté sur mon code sa marche pas:
 
Voila mon code avec 3 fonctions (chargement de la liste, tri de la liste et affichage):
 


Message édité par assil le 30-12-2012 à 23:51:29
Reply

Marsh Posté le 30-12-2012 à 12:57:47    

Primo, ce sujet devrait se trouver en catégorie C++ (et je viens de le déplacer)
Secondo:

Code :
  1. class Element
  2. {
  3. public:
  4. string titre;
  5. string source;
  6. int numero;
  7. int prix;
  8. string niveaux_de_confidentialite;
  9. string adresse;
  10. int ID;
  11. int date;
  12. int age;
  13. string examen;
  14. Element* suivant;
  15. Element* precedent;
  16. ..........
  17. }


Surtout pas!
 

Code :
  1. class Donnees
  2. {
  3. public:
  4. string titre;
  5. string source;
  6. int numero;
  7. int prix;
  8. string niveaux_de_confidentialite;
  9. string adresse;
  10. int ID;
  11. int date;
  12. int age;
  13. string examen;
  14. ...........
  15. }
  17. class Element
  18. {
  19. Donnees* donnees;
  20. Element* suivant;
  21. Element* precedent;
  22. ..........
  23. }


Il n'y a aucune raison de mélanger les torchons avec les serviettes, ie ce qui fait partie du chaînage et ce qui fait partie des données.
De plus en procédant ainsi, ta fonction de tri n'a plus besoin de modifier la liste chaînée, elle a juste à échanger la valeur des pointeurs donnees.
 
A+,


Message édité par gilou le 30-12-2012 à 13:03:03

---------------
There's more than what can be linked! --    Iyashikei Anime Forever!    --  AngularJS c'est un framework d'engulé!  --
Reply

Sujets relatifs:

Leave a Replay

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