Forum |  HardWare.fr | News | Articles | PC | S'identifier | S'inscrire | Shop Recherche
1565 connectés 

  FORUM HardWare.fr
  Programmation
  C

  [C] Tri par insertion

 



 Mot :   Pseudo :  
 
Bas de page
Auteur Sujet :

[C] Tri par insertion

n°969383
sophie74
Posté le 02-02-2005 à 14:12:36  profilanswer
 

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


 
 

mood
Publicité
Posté le 02-02-2005 à 14:12:36  profilanswer
 

n°969393
skeye
Posté le 02-02-2005 à 14:14:47  profilanswer
 

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 -
n°969399
sophie74
Posté le 02-02-2005 à 14:16:37  profilanswer
 

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:

n°969409
couak
Posté le 02-02-2005 à 14:27:51  profilanswer
 

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. }
  5. list insert (CONTENT t, list l)
  6. {
  7.         if ( (l==NULL) || (compare(t, l->car)==true))
  8.         {
  9.                 return cons (t, l);
  10.         }
  11.         else
  12.         {
  13.                 return cons (l->car, insert(t, l->cdr))
  14.         }
  15. }


Message édité par couak le 02-02-2005 à 14:28:28
n°969410
pains-aux-​raisins
Fatal error
Posté le 02-02-2005 à 14:28:25  profilanswer
 

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

n°969423
sophie74
Posté le 02-02-2005 à 14:34:16  profilanswer
 

pains-aux-raisins a écrit :

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


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

n°969435
sophie74
Posté le 02-02-2005 à 14:38:06  profilanswer
 

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. }
  5. list insert (CONTENT t, list l)
  6. {
  7.         if ( (l==NULL) || (compare(t, l->car)==true))
  8.         {
  9.                 return cons (t, l);
  10.         }
  11.         else
  12.         {
  13.                 return cons (l->car, insert(t, l->cdr))
  14.         }
  15. }



 
 
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)

n°969796
Giz
Posté le 02-02-2005 à 18:21:01  profilanswer
 

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]  

n°969801
Giz
Posté le 02-02-2005 à 18:28:27  profilanswer
 

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"
  5. list cons(CONTENT v, const list l) {
  6.   list newlist;
  7.   //ci dessous, n'y a-t-il pas kkchose qui chie dans la colle la ?
  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. }



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

n°969806
masklinn
í dag viðrar vel til loftárása
Posté le 02-02-2005 à 18:36:23  profilanswer
 

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


---------------
I've never understood the compulsion to use Web technologies minus the Web's security and deployment models. It seems a bit like throwing the orange away and eating the peel. — @ justinschuh‬
mood
Publicité
Posté le 02-02-2005 à 18:36:23  profilanswer
 

n°969812
Giz
Posté le 02-02-2005 à 18:41:17  profilanswer
 

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.

n°969817
masklinn
í dag viðrar vel til loftárása
Posté le 02-02-2005 à 18:46:15  profilanswer
 

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've never understood the compulsion to use Web technologies minus the Web's security and deployment models. It seems a bit like throwing the orange away and eating the peel. — @ justinschuh‬
n°969865
matafan
Posté le 02-02-2005 à 20:12:32  profilanswer
 

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.

n°969868
couak
Posté le 02-02-2005 à 20:16:42  profilanswer
 

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)

n°969909
++fab
victime du syndrome IH
Posté le 02-02-2005 à 21:18:15  profilanswer
 

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

Aller à :
Ajouter une réponse
  FORUM HardWare.fr
  Programmation
  C

  [C] Tri par insertion

 

Sujets relatifs
[Resolu] [Mysql]Probleme d'insertion de string avec des anti slashs[RESOLU] Tri Tableau Multidimensionnel alimenté par LDAP [RESOLU]
insertion pages htmltri algorithmie
[PHP][SQL]Double insertion et récuperation de champInsertion de smileys
petit probleme d'insertion dans une bdd Mysqltri
Format date insertionProblème insertion d'image en html
Plus de sujets relatifs à : [C] Tri par insertion


Copyright © 1997-2022 Hardware.fr SARL (Signaler un contenu illicite / Données personnelles) / Groupe LDLC / Shop HFR