Problème tri d'une liste chainée

Fermé
laidi-aya Messages postés 1 Date d'inscription dimanche 25 octobre 2015 Statut Membre Dernière intervention 25 octobre 2015 - 25 oct. 2015 à 14:25
chris79 Messages postés 97 Date d'inscription lundi 3 octobre 2005 Statut Membre Dernière intervention 1 février 2016 - 29 oct. 2015 à 17:45
bonjour à tous
Je veux trier une liste chaînée par ordre croissant en suivant ce principe:
Tant qu'il reste des éléments dans la liste originale:
  • chercher le maximum de la liste.
  • libérer ce maximum.
  • ajouter ce maximum dans la liste triée


j'ai fait ce code mais il marche pas et je vois pas ou est l'erreur
#include <stdio.h>
#include <stdlib.h>

/*les types*/
typedef struct  cellule
{
   int info;
   struct cellule * svt;
} liste;

/*les fonctions*/

    /*la saisie de la liste*/
liste * creation_liste ()

{ int i,n,k,m;
liste *tete,*p,*q;
printf("\t\tCreation de la liste\n\n");
printf("\tLe nombre des elements ");
scanf("%d",&n);
printf ("\n\t\tLa 1ere valeur "); /*la tete*/
scanf("%d",&k);
p=(liste*)malloc(sizeof (liste));
if  (!p) {printf("erreur d'allocation\n"); exit(-1);}
else
{p->info=k;
tete=p;
for(i=2;i<=n;i++)
    {printf ("\t\tLa %deme valeur ",i);
    scanf("%d",&m);
     q=(liste*)malloc(sizeof(liste));
     if  (!q) {printf("erreur d'allocation\n"); exit(-1);}
     else
     {q->info=m;
     p->svt=q;
     p=q;
    }
p->svt=NULL;
}}
return tete;
}

    /*l'affichage de la liste*/
void affich_liste (liste * tete)

{liste *p;
p=tete;
printf("\t");
while (p!=NULL)
  {
      printf("%d  ",p->info);
      p=p->svt;

  }
printf("\n");
}


   /*le tri de la liste*/
int cherche_max(liste* tete)
{int max; liste *p,*k;
p=tete->svt;
max=tete->info; k=tete;
    /*recherche du max*/
    while (p!=NULL)
        {
            if (p->info > max) max=p->info;
            p=p->svt;
        }
return max;
}
    /*liberation du max*/
liste * liberer_max (liste* tete,int max)
 {liste *p,*k;
 p=tete->svt; k=tete;
 while (p!=NULL && p->info!=max)
 {
     p=p->svt;
     k=p;
 }

    if (max==tete->info) {p=tete->svt;
                          free(tete);
                          tete=p;}
    else {k->svt=p->svt;
         free(p);}

return tete;
 }
      /*creation de la liste triee*/
liste * liste_triee(int max, liste * tete_n) // le probleme est ici
{liste *q;
if (tete_n==NULL)
    {
    tete_n=(liste*)malloc(sizeof(liste));
    if  (!tete_n) {printf("erreur d'allocation\n"); exit(-1);}
    else
    {tete_n->info=max;
    tete_n->svt=NULL;}
    }
    else
    {q=(liste*)malloc(sizeof(liste));
    if  (!q) {printf("erreur d'allocation\n"); exit(-1);}
    else
    {q->info=max;
    q->svt=tete_n;
    *tete_n=*q;}
    }
return tete_n;
}


int main()
{liste *tete,*k,*tete_n=NULL; int rep,max;
tete=creation_liste();
affich_liste(tete);
k=tete;
while(k!=NULL)
{
max=cherche_max(k);
k=liberer_max(k,max);
tete_n=liste_triee(max,tete_n);
}
affich_liste(tete_n);

return 0;
}






SVP qui peut m'aider
A voir également:

1 réponse

chris79 Messages postés 97 Date d'inscription lundi 3 octobre 2005 Statut Membre Dernière intervention 1 février 2016 25
29 oct. 2015 à 17:45
Salut,

Tu as différents problèmes dans ton code. Je vais juste énumérer les plus problématiques :
- dans ta fonction liste_triée : lorsque la liste existe déjà, tu rajoutes un nouvel élément en tête...mais tu ne mets pas correctement à jour l'élément tete_n :
Tu écris :
*tete_n=*q;

alors qu'il faut juste définir la tête comme pointant sur le nouvel élément :
tete_n=q;

--> cela devrait déjà faire avancer ton histoire.

- Le problème principal de ton programme est lié aux prototypes de fonctions :
--> ta fonction cherche_max cherche le max mais ne retourne pas l'adresse de l'élément. Du coup lorsque tu veux libérer l'élément dans liberer_max tu te retrouves à rechercher une nouvelle fois le max :( :(

--> Prototypes suggérés :
*liste cherche_max(liste* tete)

qui prend en paramêtre la tête de la liste et retourne un pointeur sur l'élément qui contient le max.

liste * liberer_max (liste* tete,liste *elementContenantLeMax)

qui prend en parametre la tete de la liste et l'élément à supprimer (issu de la fonction précédente). Retourne un pointeur sur la tete qui aura eventuellement été mis à jour dans la fonction.

Voilà voilou.

++
0