[C] Tri par insertion

Tri par insertion [C] - C - Programmation

Marsh Posté le 02-02-2005 à 14:12:36    

Bonjour, et merci d'avance pour votre aide  :hello:  
 
Je bloque sur un TP, il s'agit de trier une liste d'entiers, en insérant successivement ses éléments dans une liste initialement vide.
Exemples:
Les étapes pour trier la liste (4 2 3 1) sont:
()
(4)
(2 4)
(2 3 4)
(1 2 3 4)
 
 
J'ai évidemment commencé, mais ça fait plusieurs jours que je n'avance pas, si quelqu'un pouvait regarder où est l'erreur, je vous en serais reconnaissante.
 
Merci,
 
Sophie ;)
 
 

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include "list.h"
  6. list cons(CONTENT v, const list l) {
  7.   list newlist;
  8.   newlist=(list)malloc(sizeof(list_c*));
  9.   if(newlist==NULL)
  10.     {
  11.       fprintf(stderr,"Liste vide" );
  12.       exit(1);
  13.     }
  14.   else
  15.     {
  16.       newlist->car=v;
  17.       newlist->cdr=l;
  18.       return(newlist);
  19.     }
  20. }
  21.  
  22. unsigned length(const list l) {
  23.   unsigned somme=0;
  24.   list temp=l;
  25.   if(temp==NULL)
  26.     return(somme);
  27.   else
  28.     {
  29.       somme=1;
  30.       while (temp->cdr!=NULL)
  31. {
  32.   somme+=1;
  33.   temp=temp->cdr;
  34. }
  35.       return(somme);
  36.     }
  37. }
  39. void free_list(list l) {
  40.   list maliste=l->cdr;
  41.   if(l!=NULL)
  42.     {
  43.       free(l);
  44.       free_list(maliste);
  45.     }
  46. }
  50. void affiche_list(const list l) {
  51. list tmp = l;
  52. printf("Liste (" );
  53. if (tmp != NULL) {
  54.  for (tmp=l;tmp->cdr!=NULL;tmp=tmp->cdr) {
  55.   printf("%d, ",tmp->car);
  56.  }
  57.  printf("%d",tmp->car);
  58. }
  59. printf(" )\n" );
  60. }
  63. list insert_sort(bool compare(CONTENT, CONTENT), const list l) {
  64. if (l == NULL) {
  65.  /* Pas de liste */
  66.  return (NULL);
  67. }
  69. affiche_list(l);
  70. list newlist=NULL; /* liste () */
  71. list current = NULL; /* curseur */
  72. newlist=cons(l->car,newlist); /* liste contenant le 1er element de l */
  74. /* Prochain element de la liste */
  75. current = l->cdr;
  76. while (current != NULL) {
  77.  if (compare(newlist->car, current->car) == true) {
  78.   /* Si compare vaut true, on insere apres */
  79.   printf("Insere %d en queue de liste, element precedent %d\n",
  80.    current->car, newlist->car);
  81.   newlist = inser_fin(current->car, newlist);
  82.   /* for (tmp=newlist;tmp->cdr!=NULL;tmp=tmp->cdr) {}
  83.   tmp->cdr = cons(current->car, NULL);*/
  84.  } else {
  85.   int i=0;
  86.   /* On insere "au milieu" */
  87.   printf("Insere %d au milieu de liste\n",
  88.    current->car);
  89.   list curseur = NULL;
  90.   list tmp = NULL;
  91.   for (curseur = newlist; compare(curseur->car, current->car) ; curseur = curseur->cdr) {
  92.    tmp = curseur;
  93.   }
  94.   printf("curseur trouve\n" );
  95.   printf("Insere %d en tete de liste, element suivant %d\n",
  96.    current->car, curseur->car);
  97.   curseur = cons(current->car, curseur);
  98.   tmp->cdr = curseur;
  99.  }
  100.  current = current->cdr;
  101. }   
  102. affiche_list(newlist);
  103. return(newlist);
  104. }


 
 

Reply

Marsh Posté le 02-02-2005 à 14:12:36   

Reply

Marsh Posté le 02-02-2005 à 14:14:47    

J'ai pas encore lu le code, mais tu ne dis même pas quel est le problème que tu rencontres, là... :??:


---------------
Can't buy what I want because it's free -
Reply

Marsh Posté le 02-02-2005 à 14:16:37    

skeye a écrit :

J'ai pas encore lu le code, mais tu ne  dis même pas quel est le problème que tu rencontres, là... :??:


 
Et bien, il ne trie pas correctement les listes ;)
Excuse moi, j'ai oublié de préciser que j'étais vraiment pas douée en programmation :pfff:

Reply

Marsh Posté le 02-02-2005 à 14:27:51    

ca devient assez hard de ne pas utiliser le récursif avec des liste chaînées
je propose une autre solution (que je n'ai pas testé !!!) :

Code :
  1. list tri_insertion (list l)
  2. {
  3.         return insert (l->car, tri_insertion(l->cdr));
  4. }
  6. list insert (CONTENT t, list l)
  7. {
  8.         if ( (l==NULL) || (compare(t, l->car)==true))
  9.         {
  10.                 return cons (t, l);
  11.         }
  12.         else
  13.         {
  14.                 return cons (l->car, insert(t, l->cdr))
  15.         }
  16. }


Message édité par couak le 02-02-2005 à 14:28:28
Reply

Marsh Posté le 02-02-2005 à 14:28:25    

normal tu est une nana :whistle:
[:dehors]

Reply

Marsh Posté le 02-02-2005 à 14:34:16    

pains-aux-raisins a écrit :

normal tu est une nana :whistle:
[:dehors]


T'as pas tort :p
 
Merci couak, je teste ça de suite ;)

Reply

Marsh Posté le 02-02-2005 à 14:38:06    

couak a écrit :

ca devient assez hard de ne pas utiliser le récursif avec des liste chaînées
je propose une autre solution (que je n'ai pas testé !!!) :

Code :
  1. list tri_insertion (list l)
  2. {
  3.         return insert (l->car, tri_insertion(l->cdr));
  4. }
  6. list insert (CONTENT t, list l)
  7. {
  8.         if ( (l==NULL) || (compare(t, l->car)==true))
  9.         {
  10.                 return cons (t, l);
  11.         }
  12.         else
  13.         {
  14.                 return cons (l->car, insert(t, l->cdr))
  15.         }
  16. }



 
 
En fait j'ai oublié de préciser que le prototype des fonctions ne doit pas être changé ;)
Donc je dois faire avec une fonction:
 
list insert_sort(bool compare(CONTENT,CONTENT) , const list l)

Reply

Marsh Posté le 02-02-2005 à 18:21:01    

pains-aux-raisins a écrit :

normal tu est une nana :whistle:
[:dehors]


 
 :lol: , elle est bien bonne celle là  [:acherpy] .
Ca y est, on arrive à convaincre les nanas que la prog c cool  :sol:  
 
PS : c'est la premiere fois que je vois une nana poster sur cette section...enfin d'après le pseudo, pis là la signature est clair  [:amandine75011]  

Reply

Marsh Posté le 02-02-2005 à 18:28:27    

sophie74 a écrit :

Bonjour, et merci d'avance pour votre aide  :hello:  
 
Je bloque sur un TP, il s'agit de trier une liste d'entiers, en insérant successivement ses éléments dans une liste initialement vide.
Exemples:
Les étapes pour trier la liste (4 2 3 1) sont:
()
(4)
(2 4)
(2 3 4)
(1 2 3 4)
 
 
J'ai évidemment commencé, mais ça fait plusieurs jours que je n'avance pas, si quelqu'un pouvait regarder où est l'erreur, je vous en serais reconnaissante.
 
Merci,
 
Sophie ;)
 
 

Code :
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <time.h>
  4. #include "list.h"
  6. list cons(CONTENT v, const list l) {
  7.   list newlist;
  8.   //ci dessous, n'y a-t-il pas kkchose qui chie dans la colle la ?
  9.   newlist=(list)malloc(sizeof(list_c*));
  10.   if(newlist==NULL)
  11.     {
  12.       fprintf(stderr,"Liste vide" );
  13.       exit(1);
  14.     }
  15.   else
  16.     {
  17.       newlist->car=v;
  18.       newlist->cdr=l;
  19.       return(newlist);
  20.     }
  21. }



 
Sans lire tout le code, tu es sûr que ton malloc est correct ? :heink:

Reply

Marsh Posté le 02-02-2005 à 18:36:23    

malloc renvoie un pointeur non?
 
d'ailleurs comment ça se fait qu'il y ait si peu de pointeurs? [:gratgrat]


---------------
I mean, true, a cancer will probably destroy its host organism. But what about the cells whose mutations allow them to think outside the box by throwing away the limits imposed by overbearing genetic regulations? Isn't that a good thing?
Reply

Marsh Posté le 02-02-2005 à 18:36:23   

Reply

Marsh Posté le 02-02-2005 à 18:41:17    

Masklinn a écrit :

malloc renvoie un pointeur non?
 
d'ailleurs comment ça se fait qu'il y ait si peu de pointeurs? [:gratgrat]


 
...je dirais même un double pointeur dans ce cas. Je ne suis pas sûr que c'est ce qu'elle veut  :heink: et l'affectation me paraît douteuse.

Reply

Marsh Posté le 02-02-2005 à 18:46:15    

là ça renvoie effectivement un pointeur sur un pointeur de list_c qu'elle cast en list...
 
Enfin je vais arrêter là, étant une quiche en C je vais me mettre à raconter des conneries :sol:
 
Par contre le .h serait appréciable je pense


Message édité par masklinn le 02-02-2005 à 19:12:29

---------------
I mean, true, a cancer will probably destroy its host organism. But what about the cells whose mutations allow them to think outside the box by throwing away the limits imposed by overbearing genetic regulations? Isn't that a good thing?
Reply

Marsh Posté le 02-02-2005 à 20:12:32    

Qui vous dit que le type list n'est pas un pointeur ? Certains profs (qui n'ont probablement pas fait beaucoup de C) aiment bien cacher les pointeurs a coups de typedef.

Reply

Marsh Posté le 02-02-2005 à 20:16:42    

pas forcément, les élèves peuvent comprendre plus facilement l'algorithmie, notamment le type abstrait avec les listes chaînées, avant de se pencher et de coucher avec la machine en manipulant des pointeurs
perso c'est comme ca que j'ai le mieux compris (mais j'ai pas couché avec la machine)

Reply

Marsh Posté le 02-02-2005 à 21:18:15    

clair que les typedef sur les pointeurs, c'est l'horreur.
on ne voit plus qui est un pointeur, qui n'en est pas un, etc ... En plus, laisser le struct list_c* permet à l'éditeur de texte de colorer tout ça.
un truc tout bete, mais qui gène beaucoup dans la lecture d'un programme : la variable l que l'on confond avec 1.
 
Sinon, le malloc n'est pas correct. C'est contre-indiqué de caster. De plus, tu n'alloue pas la bonne taille puisque tu n'alloue que la taille d'un list_c*, et non d'un list_c.
 

Code :
  1. struct list_c* newlist;
  2. if ((newlist = malloc(sizeof *newlist)) == NULL)
  3. {
  4.     fputs("echec de l'allocation memoire\n",stderr); /* ou perror ... */
  5.     exit(EXIT_FAILURE); /* pas forcément si brutale */
  6. }


     
voila pour le début du code, j'ai pas tout lu ...


Message édité par ++fab le 02-02-2005 à 21:24:49
Reply

Sujets relatifs:

Leave a Replay

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