[C] Tri par insertion

Recherche :

Mot : Pseudo : Filtrer
Bas de page
Auteur	Sujet : [C] Tri par insertion

sophie74

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 :

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "list.h"
list cons(CONTENT v, const list l) {
list newlist;
newlist=(list)malloc(sizeof(list_c*));
if(newlist==NULL)
{
fprintf(stderr,"Liste vide" );
exit(1);
}
else
{
newlist->car=v;
newlist->cdr=l;
return(newlist);
}
}
unsigned length(const list l) {
unsigned somme=0;
list temp=l;
if(temp==NULL)
return(somme);
else
{
somme=1;
while (temp->cdr!=NULL)
{
somme+=1;
temp=temp->cdr;
}
return(somme);
}
}
void free_list(list l) {
list maliste=l->cdr;
if(l!=NULL)
{
free(l);
free_list(maliste);
}
}
void affiche_list(const list l) {
list tmp = l;
printf("Liste (" );
if (tmp != NULL) {
for (tmp=l;tmp->cdr!=NULL;tmp=tmp->cdr) {
printf("%d, ",tmp->car);
}
printf("%d",tmp->car);
}
printf(" )\n" );
}
list insert_sort(bool compare(CONTENT, CONTENT), const list l) {
if (l == NULL) {
/* Pas de liste */
return (NULL);
}
affiche_list(l);
list newlist=NULL; /* liste () */
list current = NULL; /* curseur */
newlist=cons(l->car,newlist); /* liste contenant le 1er element de l */
/* Prochain element de la liste */
current = l->cdr;
while (current != NULL) {
if (compare(newlist->car, current->car) == true) {
/* Si compare vaut true, on insere apres */
printf("Insere %d en queue de liste, element precedent %d\n",
current->car, newlist->car);
newlist = inser_fin(current->car, newlist);
/* for (tmp=newlist;tmp->cdr!=NULL;tmp=tmp->cdr) {}
tmp->cdr = cons(current->car, NULL);*/
} else {
int i=0;
/* On insere "au milieu" */
printf("Insere %d au milieu de liste\n",
current->car);
list curseur = NULL;
list tmp = NULL;
for (curseur = newlist; compare(curseur->car, current->car) ; curseur = curseur->cdr) {
tmp = curseur;
}
printf("curseur trouve\n" );
printf("Insere %d en tete de liste, element suivant %d\n",
current->car, curseur->car);
curseur = cons(current->car, curseur);
tmp->cdr = curseur;
}
current = current->cdr;
}
affiche_list(newlist);
return(newlist);
}

Publicité

skeye

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 -

sophie74

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:

couak

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 :

list tri_insertion (list l)
{
return insert (l->car, tri_insertion(l->cdr));
}
list insert (CONTENT t, list l)
{
if ( (l==NULL) || (compare(t, l->car)==true))
{
return cons (t, l);
}
else
{
return cons (l->car, insert(t, l->cdr))
}
}

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

pains-aux-raisins

Fatal error

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

sophie74

pains-aux-raisins a écrit :

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

T'as pas tort

Merci couak, je teste ça de suite

sophie74

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 :

list tri_insertion (list l)
{
return insert (l->car, tri_insertion(l->cdr));
}
list insert (CONTENT t, list l)
{
if ( (l==NULL) || (compare(t, l->car)==true))
{
return cons (t, l);
}
else
{
return cons (l->car, insert(t, l->cdr))
}
}

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)

Giz

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]

Giz

sophie74 a écrit :

Code :

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "list.h"
list cons(CONTENT v, const list l) {
list newlist;
//ci dessous, n'y a-t-il pas kkchose qui chie dans la colle la ?
newlist=(list)malloc(sizeof(list_c*));
if(newlist==NULL)
{
fprintf(stderr,"Liste vide" );
exit(1);
}
else
{
newlist->car=v;
newlist->cdr=l;
return(newlist);
}
}

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

masklinn

í dag viðrar vel til loftárása

malloc renvoie un pointeur non?

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

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody

Publicité

Giz

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.

masklinn

í dag viðrar vel til loftárása

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

---------------
Stick a parrot in a Call of Duty lobby, and you're gonna get a racist parrot. — Cody

matafan

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.

couak

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)

++fab

victime du syndrome IH

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 :

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

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

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

FORUM HardWare.fr

Programmation

[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 html	tri algorithmie
[PHP][SQL]Double insertion et récuperation de champ	Insertion de smileys
petit probleme d'insertion dans une bdd Mysql	tri
Format date insertion	Problème insertion d'image en html
Plus de sujets relatifs à : [C] Tri par insertion

Page générée en 0.122 secondes