question sur le langage C

[invite0b0ee8b7]

Hello,

Voilà je me demandais si ici je pouvais exposer un problème que j'avais en langage C sur un programme où si c'est pas du tout le lieu ??

merci de la réponse et pi être à très bientôt si quelqu'un pense pouvoir m'aider sur du C !
-----

[JPL]

Il y a certainement des gens qui pourront t'aider (pas moi !) mais j'ai déplacé ta question vers un forum qui me paraît mieux adapté que celui que tu avais choisi.

[invite97a92052]

Ca dépend du niveau que tu demandes, mais je pense pouvoir t'aider !

[invite0b0ee8b7]

merci de bien vouloir m'aider !

en fait c'est pas grand chose ... j'ai un ti problème sur une fonction ... elle est censée me renvoyer en gros deux listes .. une par le return et l'autre qui est rentrée en paramètre en ressort modifiée et c'est justement la seconde qui me renvoit pas ce que je veux (je sais pas si je suis bien claire ... désolée ...).

en gros je veux que ma liste "l" prenne la valeur de la liste "l1" générée par la fonction mais au lieu de ça je n'ai que le dernier élement de cette liste ... je mets mon ti bout de code ce sera surement plus clair ^^ et je pointe d'une flèche les différentes places que j'ai testé sans succès pour "l=l1" ... merci d'avance !! (au passage insert() est une fonction qui permet l'ajout en tête et vide() qui vérifie si une liste est vide)

iste separation(liste l){

int pivot=l->val;
liste insert(liste,int);
liste l1=NULL,l2=NULL,p,t;
if(!vide(l)) {
p=l->suiv;
t=l->suiv;
pivot=l->val;
free(l);
--->l=l1;

while (p!=NULL) {
if(pivot>p->val){
l1=insert(l1,p->val);
---> l=l1;
p=p->suiv;
}
else{
l2=insert(l2,p->val);
p=p->suiv;
}
}
--->l=l1;
l2=insert(l2,pivot);
if(t->val>pivot)
l2=l1;
return l2;

}
}


et une dernière tite question comment je peux faire pour lors de l'affichage du résultat indiquer le temps de calcul ??

merciiiii

[A voir en vidéo sur Futura]

[invite97a92052]

Hello,

Bon, j'ai pas tout compris ce que doit faire exactement ton code. Elle sert à quoi pivot ?
Et tant que t'y es, balance tout ton code, et indenté si possible, je pense que je pourrais mieux t'aider !

[invite0b0ee8b7]

Bah en gros, avec une liste en entrée il la sépare en deux listes, une liste regroupant toutes les valeurs plus petites que le pivot et une autre avec les valeurs plus grandes que le pivot ! donc le pivot sert à séparer la liste en deux !!

le but du programme complet est de faire un tri façon quicksort sur les listes chaînées ! j'avais réussi à le faire fonctionner mais au lieu des inserer tête j'avais mis des insérer queue et à la fin ma liste était triée mais j'avais deux morceaux triés de façons décroissante collés l'un à l'autre alors je me suis dit qu'avec un insérer tête ça fonctionnerait mais j'ai un souci avec la fonction que j'ai envoyé avant !

je t'envoie le code complet mais je suis désolée pour la mise en page je vois pas comme faire ça bien

#include <stdio.h>
#include <stdlib.h>

typedef struct elem {
        int val;
        struct elem *suiv;
        } element;
typedef element *liste;

int main()
      {
      int vide(liste);
      void affiche(liste);
      liste saisie(liste);
      liste quicksort(liste);
      liste separation(liste);
      liste fusion(liste,liste);
      liste insert(liste,int);
      liste l,res,l1;
      l=(liste)malloc(sizeof(element));
      l=NULL;
      res=(liste)malloc(sizeof(element));
      res=NULL;
      l=saisie(l);
      res=separation(l);
      printf("\naffichage res : ") ;
      affiche(res);
      printf("\naffichage l : ") ;
      affiche(l);
      system("PAUSE");
      return 0;
      }

liste saisie(liste l)
      {
      liste inserq(liste,int);
      int rep=1;
      int i=1;
      printf("Entrer autant de valeurs que vous le souhaiter, pour arreter entrer la valeur 0 (elle ne sera pas entree dans la liste)\n");
      while(rep!=0)
            {
            printf("\nEntrer la %d eme valeur ",i);
            scanf("%d",&rep);
            if(rep!=0)
              l=inserq(l,rep);
            i=i+1;
            }
       return l;
       }

int vide(liste l)
      {
      return l==NULL;
      }

liste inserq(liste l, int e)
      {
      liste nouv,p;
      nouv=(liste)malloc(sizeof(element));
      nouv->val=e;
      nouv->suiv=NULL;
      if(!vide(l))
        {
        p=l;
        while(p->suiv!=NULL)
           p=p->suiv;
        p->suiv=nouv;
        }
      else
        l=nouv;
      return l;
      }

liste insert(liste l, int e){
      liste nouv;
      nouv=(liste)malloc(sizeof(element));
      nouv->val=e;
      nouv->suiv=NULL;
      if(!vide(l))
        nouv->suiv=l;
      return nouv;
}

void affiche(liste l)
     {
     while(l!=NULL)
          {
          printf("%d\t",l->val);
          l=l->suiv;
          }
     }


liste separation(liste l){

      int pivot=l->val;
      liste insert(liste,int);
      liste l1=NULL,l2=NULL,p,t;
      if(!vide(l)) {
         p=l->suiv;
         t=l->suiv;
         pivot=l->val;
         free(l);
         //l=l1;

         while (p!=NULL) {
              if(pivot>p->val){
                   l1=insert(l1,p->val);
                   l=l1;
                   printf("\naffiche l1\n");
                   affiche(l1);
                   p=p->suiv;
              }
              else{
                   l2=insert(l2,p->val);
                   printf("\naffiche l2\n");
                   affiche(l2);
                   p=p->suiv;
              }
         }
         //l=l1;
         l2=insert(l2,pivot);
         if(t->val>pivot)
           l2=l1;
         return l2;

      }
}

liste fusion(liste l1,liste l2){
      liste temp1=l1;

     if(l1==NULL)return l2;
     if(l2==NULL)return l1;
      while(temp1->suiv!=NULL)
            temp1=temp1->suiv;
      temp1->suiv=l2;
      return l1;
}

liste quicksort(liste l){
      if((vide(l)) || (l->suiv==NULL))
        return l;
      liste l3;
      l3=separation(l);
      l3=quicksort(l3);
      l=quicksort(l);
      l=fusion(l,l3);
      return l;

      }

[invitefef87329]

Bijur!

Je ne sais pas si les autres pourront t'aider mais je connais ce forum très sympathique: http://www.siteduzero.com/forums/index.php?showforum=9

Tiens, pourquoi ne pas mettre une rubrique "programation"??
a+

[zoup1]

La liste l que tu passes comme argument à la fonction est locale à la fonction separation est locale à la fonction separation. Tu peux la modifier à l'intérieur de la fonction elle-même mais cela ne sera pas répercuté en dehors de la fonction.

Si tu veux renvoyer une liste à travers l'argument de ta fonction il faut que tu passes non pas la variable elle-même mais un pointeur sur cette variable soit un liste *l; (on est d'accord, c'est un pointeur sur un pointeur). Il faut que tu appelles ta fonction en faisant ; res=separation(&l);
puis dans ta fonction il faut que tu utilises ce qui est pointé par ton paramètre donc par exemple p=(*l)->suiv;

[invite97a92052]

Un exemple de fonction séparation (qui insère en tête de liste donc)

void separation(liste l, liste* l1, liste* l2) {
	
	liste suiv;
	
	if(l == NULL) return;
	int pivot = l->val;
	
	while(l) {
		suiv = l->suiv;
		if(l->val < pivot) {
			l->suiv = *l1;
			*l1 = l;
		}
		else {
			l->suiv = *l2;
			*l2 = l;
		}
		l = suiv;
	}
}

Que tu appelles comme ceci :

liste l, l1=NULL, l2=NULL;
[remplissage de l...]
separation(l, &l1, &l2);

Mais je trouve ton code bien compliqué pour ce que tu veux faire...

Et il y a des confusions à certains endroits, comme ici :

      l=(liste)malloc(sizeof(element));
      l=NULL;
      res=(liste)malloc(sizeof(element));
      res=NULL;

Ce code provoque tout juste une fuite de mémoire, à part ça il est complètement inutile


Sinon, pour la saisie, voici par exemple une autre version plus simple je pense :

void saisie(liste* pl) {
	
	int val;
	
	puts("Entrez vos valeurs (0 pour arrêter)");
	while(scanf("%d", &val) && val != 0) {
		*pl = calloc(1, sizeof **pl);
		(*pl)->val = val;
		pl = &((*pl)->suiv);
	}
}

que tu appelles comme ceci :

liste l;
saisie(&l);

Si tu comprends pas un bout, hésite pas ! Mais je pense que tu t'emmelles dans les pointeurs à certains endroits.

[invite42dac78c]

quand tu mets l=l1, c'est le premier octet de l qui prends la valeur du premier de l1...

En C++, tu peux faire des surcharges d'opérateurs, et ça peut marcher... en C non...

tu dois faire une fonction


liste egal(liste a){
return a;
}

et la, ça devrait marcher... c'est une astuce qui peut aussi te permettre d'éviter des mallocs parfois...

[invite97a92052]

quand tu mets l=l1, c'est le premier octet de l qui prends la valeur du premier de l1...

En C++, tu peux faire des surcharges d'opérateurs, et ça peut marcher... en C non...

tu dois faire une fonction


liste egal(liste a){
return a;
}

et la, ça devrait marcher... c'est une astuce qui peut aussi te permettre d'éviter des mallocs parfois...

Heu, je crois que tu divagues
liste est un type défini comme étant un pointeur. Faire l=l1, c'est faire l'affectation à l de l'adresse pointée par l1, je ne vois pas où tu vas chercher ton histoire d'octets...


Sinon, pour pseunanou, je pense qu'il y a une autre erreur, pas dans le code cette fois, mais dans l'algo. Choisir le pivot arbitrairement comme ça, comme étant le premier élément de la liste, ça me parait douteux.
Imagine une liste "2-3-2"
Le pivot va être 2, donc en sortie de séparation tu auras une liste vide et une liste identique à celle de départ. Donc au fil des récursions (qui seront totalement inutiles !), tu feras exploser la pile !
Tu as des contraintes pour implémenter l'algo ? Faut-il se fier obligatoirement au schéma de ton code ?

En tous cas, c'est vrai qu'il est possible d'enlever plein d'allocations programmées de mémoire. À priori, les seules allocations nécessaires sont lors de la saisie (cf. la fonction separation de mon post précédent, cela ne demande aucune allocation)
Si tu veux, je peux essayer de remodeler ton code...

[invite42dac78c]

quand tu parles d'addresses alors met un & devant...

[invite97a92052]

typedef element *liste;

Un pointeur contient par définition une adresse, si tu mets un & devant, tu chopes l'adresse du pointeur...



...soit l'un de nous se vautre totalement, soit on parle pas de la même chose du tout


Tu répondais à quoi exactement dans ton message ?

[invite0b0ee8b7]

Bon bon bon merci à tous pour vos réponses !

Cependant j'ai quelques questions et quelques réactions ... essayons d'ordonner tout ça !!

g_h dans la version que tu m'as donné pour la séparation des listes :

void separation(liste l, liste* l1, liste* l2) {
	
	liste suiv;
	
	if(l == NULL) return;
	int pivot = l->val;
	
	while(l) {
		suiv = l->suiv;
		if(l->val < pivot) {
			l->suiv = *l1;
			*l1 = l;
		}
		else {
			l->suiv = *l2;
			*l2 = l;
		}
		l = suiv;
	}
}

j'arrive pas bien à comprendre le principe (je l'ai testée elle marche ...) ! en plus c'est assez confus car tu appelles une variable suiv donc de la même manière que le nom de ma variable qui pointe sur l'élément suivant d'une liste ... donc si tu pouvais m'expliquer en détails comment ça marche ... merci

sinon j'ai enlevé quelques allocations inutiles comme tu me l'avais conseillé !

et pi au niveau de l'algo c'est notre consigne qui est comme ça ... le prof veut qu'on prenne comme valeur pivot la première de la liste donc ça c'est pas moi qui ai décidé !!

voili voilou ! et encore merci pour vos idées !!!

[invite97a92052]

Bon bon bon merci à tous pour vos réponses !

Cependant j'ai quelques questions et quelques réactions ... essayons d'ordonner tout ça !!

g_h dans la version que tu m'as donné pour la séparation des listes :

void separation(liste l, liste* l1, liste* l2) {
	
	liste suiv;
	
	if(l == NULL) return;
	int pivot = l->val;
	
	while(l) {
		suiv = l->suiv;
		if(l->val < pivot) {
			l->suiv = *l1;
			*l1 = l;
		}
		else {
			l->suiv = *l2;
			*l2 = l;
		}
		l = suiv;
	}
}

j'arrive pas bien à comprendre le principe (je l'ai testée elle marche ...) ! en plus c'est assez confus car tu appelles une variable suiv donc de la même manière que le nom de ma variable qui pointe sur l'élément suivant d'une liste ... donc si tu pouvais m'expliquer en détails comment ça marche ... merci

sinon j'ai enlevé quelques allocations inutiles comme tu me l'avais conseillé !

et pi au niveau de l'algo c'est notre consigne qui est comme ça ... le prof veut qu'on prenne comme valeur pivot la première de la liste donc ça c'est pas moi qui ai décidé !!

voili voilou ! et encore merci pour vos idées !!!

Ok !
Le pointeur suiv, pour éviter les confusions, je vais l'appeller temp, ça ira mieux je pense.
Cela donne :

void separation(liste l, liste* l1, liste* l2) {
	
	liste temp;
	
	if(l == NULL) return;
	int pivot = l->val;
	
	while(l) {
		temp = l->suiv;
		if(l->val < pivot) {
			l->suiv = *l1;
			*l1 = l;
		}
		else {
			l->suiv = *l2;
			*l2 = l;
		}
		l = temp;
	}
}

alors voilà l'idée :
tu auras remarqué qu'il faut appeler la fonction en lui passant l'adresse de l1 et l2. En fait, separation() va "modifier à distance" les pointeurs l1 et l2 qui sont déclarés dans la fonction main()
Dès qu'on tombe sur un élément l dont la valeur est en dessous de celle de pivot, on la met dans l1

Pour celà, on va dire à l de pointer sur le premier élément de l1 (et au fur et à mesure, on se retrouvera donc avec une liste).
D'où l'importance d'initialiser l1 (comme l2) à NULL.
Ensuite, comme je le disais, on va "modifier à distance" ce pointeur l1 qui est déclaré dans main. Il va maintenant pointer vers l'élément que l'on vient de rajouter.
D'où le *l1 = l;

(et c'est la même chose pour l2)

temp sert juste à garder l'adresse de l'élément suivant, car le pointeur l->suiv est écrasé. Il faut donc prendre sa valeur et la mettre de côté pour continuer de parcourir la liste.

Il ne faut pas perdre de vue que les l1 et l2 du main() sont des liste, alors que le l1 et l2 de main sont des liste*, c'est à dire des pointeurs de liste. Ca peut embrouiller assez vite, je te l'accorde !
(-> modifier *l1 dans separation() revient exactement à modifier l1 dans main() )

En espérant t'avoir éclairci... !

[invite0b0ee8b7]

ah oui et je viens de remarquer qu'avec ta fonction separation, le programme plante si l'utilisateur veut entrer deux valeurs identiques dans la liste ... alors qu'avec la mienne ça plantait pas donc j'ai un problème de régler mais finalement un nouveau en plus !! ^^

et sinon personne n'a d'idée pour pouvoir afficher en meme temps que le résultat le temps de calcul ??

[invite97a92052]

Oui, excuse moi pour le temps :

float fDebut, fFin;

fDebut = ((float)clock()) / CLOCKS_PER_SEC;
[... ici ton code à exécuter...]
fFin = ((float)clock()) / CLOCKS_PER_SEC;

Et tu as le temps en secondes en calculant fFin - fDebut


Sinon, pour le bug, je me suis peut-être planté en décodant ton algo, je vais voir...

sinon, outre ce bug, voici comment j'aurais présenté toute l'affaire :

#include <stdio.h>
#include <stdlib.h>


typedef struct elem {
	int val;
	struct elem *suiv;
} element;
typedef element *liste;


void saisie(liste* pl) {
	
	int val;
	
	puts("Entrez vos valeurs (0 pour arreter)");
	while(scanf("%d", &val) && val != 0) {
		*pl = calloc(1, sizeof **pl);
		(*pl)->val = val;
		pl = &((*pl)->suiv);
	}
}

void separation(liste l, liste* l1, liste* l2) {
	
	liste suiv;
	int pivot;
	
	if(l == NULL) return;
	pivot = l->val;
	
	while(l) {
		suiv = l->suiv;
		if(l->val < pivot) {
			l->suiv = *l1;
			*l1 = l;
		}
		else {
			l->suiv = *l2;
			*l2 = l;
		}
		l = suiv;
	}
}

void aff(liste l) {
	while(l) {
		printf("%d\n", l->val);
		l = l->suiv;
	}
}

void vidage(liste l) {
	liste p;
	while(l) {
		p = l->suiv;
		free(l);
		l = p;
	}
}

liste fusion(liste l1, liste l2) {
	liste temp = l1;
	if(l1==NULL) return l2;
	
	while(temp->suiv) temp = temp->suiv;
	temp->suiv = l2;

	return l1;
}

liste quicksort(liste l){
	liste l1=NULL, l2=NULL;
	
	if(l == NULL || l->suiv==NULL)
		return l;

    separation(l, &l1, &l2);
    l1=quicksort(l1);
    l2=quicksort(l2);
    l=fusion(l1,l2);

    return l;
}


int main(void) {
	
	liste l=NULL;

	saisie(&l);
	
	if(l != NULL) {
		l = quicksort(l);
		aff(l);
		vidage(l);
	}

	system("pause");
	return 0;
}

[invite0b0ee8b7]

c'est un peu plus clair mais j'ai encore du mal avec cette histoire de pointeur ... donc je suis revenue à un truc plus simple mais que je comprends ^^

void separation(liste l, liste* l1, liste* l2) {
	liste t=NULL,p=NULL;

	if(vide(l))
      return;

	int pivot = l->val;
	while(l!=NULL) {
		if(l->val < pivot) {
           t=insert(t,l->val);
           l=l->suiv;
		}
		else {
           p=insert(p,l->val);
           l=l->suiv;
		}
	}
    *l1=t;
    *l2=p;
}

heu ... sinon merci pour l'heure

et pour le souci du programme qui plante en fait je l'avais pas avant ... parce que dans une première version j'avais fait le programme avec des inserq qui insérait les valeurs mais à la fin donc au bout du compte je me retrouvais avec une liste composée de deux listes triées à l'envers ... bon c'est pas très clair alors exemple :

je rentrais : 12 3 45 65 34 8 9 0
et il me ressortais : 12 9 8 3 65 45 34

et en faisant mon inserq j'avais réussi (sans pointeur) à avoir ma liste l modifiée à travers la fonction separation (ouais j'avais un peu magouillé mais ça marchait) alors je comprends pas pourquoi avec les insert ça pourrait pas fonctionner !!

enfin voilà !! j'attends pas de réponse à cette réaction mais c'était juste une tite réaction pour dire que je trouve ça bizarre parfois la programmation !

[invite97a92052]

Bon, ya une subtilité qui m'échappe (à la fin de ton separation() ) :

         if(t->val>pivot)
           l2=l1;
         return l2;

Pourquoi tu fais ça ?
"t", c'est le deuxième élément de la liste de départ...
Alors pourquoi si la valeur du 2eme élément est plus grande que pivot, il faut jeter le l2 que tu as créé à la trappe ? (et bonjour la fuite de mémoire !)

Est-ce que tu pourrais envoyer ton dernier code qui marche ?

[invite0b0ee8b7]

en fait ce test c'était avant quand je faisais mon programme avec inserq parce que sinon j'avais un bug ! quand le deuxième élement de la liste était plus grand que le pivot la liste que je renvoyais et la valeur que prennait la liste l étaient les mêmes or je voulais les deux listes distinctes ... alors c'est de la magouille pure et dure mais ça marchait comme ça !! m'enfin finalement je m'en sers plus car je dois faire des insert !

bah mon dernier code qui marche c'est le code avec ta fonction separation quelque peu modifiée et donc elle bug quand on entre deux valeurs identiques ... enfin le voici :

#include <stdio.h>
#include <stdlib.h>

typedef struct elem {
        int val;
        struct elem *suiv;
        } element;
typedef element *liste;


int vide(liste l){
      return l==NULL;
}

liste insert(liste l, int e){
      liste nouv=(liste)malloc(sizeof(element));
      nouv->val=e;
      nouv->suiv=NULL;
      if(!vide(l))
        nouv->suiv=l;
      return nouv;
}

liste saisie(liste l){
      int rep=1;
      int i=1;
      printf("Entrer autant de valeurs que vous le souhaiter, pour arreter entrer la valeur 0 (elle ne sera pas entree dans la liste)\n");
      while(rep!=0){
            printf("\nEntrer la %d eme valeur ",i);
            scanf("%d",&rep);
            if(rep!=0)
              l=insert(l,rep);
            i=i+1;
       }
       return l;
}

void affiche(liste l){
     while(l!=NULL) {
          printf("%d\t",l->val);
          l=l->suiv;
     }
}


void separation(liste l, liste* l1, liste* l2) {
	liste t=NULL,p=NULL;

	if(vide(l))
      return;

	int pivot = l->val;
	while(l!=NULL) {
		if(l->val < pivot) {
           t=insert(t,l->val);
           l=l->suiv;
		}
		else {
           p=insert(p,l->val);
           l=l->suiv;
		}
	}
    *l1=t;
    *l2=p;
}


liste fusion(liste l1,liste l2){
      liste temp1=l1;
      if(l1==NULL)
        return l2;
      if(l2==NULL)
        return l1;
      while(temp1->suiv!=NULL)
           temp1=temp1->suiv;
      temp1->suiv=l2;
      return l1;
}


liste quicksort(liste l){
      if((vide(l)) || (l->suiv==NULL))
        return l;
      liste l1=NULL,l2=NULL,l3;
      separation(l,&l1,&l2);
      l1=quicksort(l1);
      l2=quicksort(l2);
      l=fusion(l1,l2);
      return l;
}


int main(){
      int vide(liste);
      void affiche(liste);
      liste insert(liste,int);
      liste saisie(liste);
      liste quicksort(liste);
      liste separation(liste*);
      liste fusion(liste,liste);
      liste l=NULL;
      l=saisie(l);
      l=quicksort(l);
      affiche(l);
      system("PAUSE");
      return 0;
}

[invite97a92052]

Ok, alors 2-3 remarques :
- à aucun moment tu ne libères la mémoire allouée !
- je ne sais pas si tu as droit au C99, mais en C99 tu as un type bool (par exemple pour ta fonction vide() ) défini dans stdbool.h
- si tu es en mode C99, c'est int main(void) et non int main() (ok, c'est du pinaillage )
- ta variable l3 dans quicksort ne sert à rien

Sinon, pour le bug, je ne vois pas de solution "évidente" si on reste dans l'esprit de l'énoncé...
(on peut toujours faire très moche, mais c'est pas le but recherché je pense )

Si tu trouves quelque chose, ça m'intéresse... !

[invite0b0ee8b7]

en effet ma variable l3 ne sert à rien mais c'est parce que je m'en servais avant et j'ai simplement oublié de l'enlever

et non j'ai pas le droit au C99 sinon je m'amuserais pas à écrire cette fonction

j'ai rajouté un petit free(l) après avoir affiché ma liste ... mais on s'est pas trop penché sur la question de la libération de la mémoire ...

et le but du programme c'est qu'il fonctionne quand le prof le teste alors je m'en moque qu'il soit moche ! loool

il doit bien y avoir une solution !! chaque problème a une solution ... je vais y réfléchir et pi je te tiens au courant si je trouve ^^

en tout cas merci pour ces critiques et ton aide constructive !

[invite97a92052]

j'ai rajouté un petit free(l) après avoir affiché ma liste ... mais on s'est pas trop penché sur la question de la libération de la mémoire ...

Ok, dans ce cas Mais saches tout de même que pour 1 malloc() appelé, 1 free() doit être appelé.
Si ça t'intéresse, regarde la fonction vidage du post #17

et le but du programme c'est qu'il fonctionne quand le prof le teste alors je m'en moque qu'il soit moche !

lol, le prof ne te note pas sur le code ? (à moins que ça ne soit pas noté...)


Jvais essayer de me creuser la tête aussi... mais ça fait quelque temps que j'ai pas tripatouillé du C et des algos... !

Sinon, si tu pouvais nous dire l'intitulé exact de l'exo, ça pourrait apporter quelque chose, peut-être

[invite0b0ee8b7]

Si ça t'intéresse, regarde la fonction vidage du post #17

j'ai déjà regardé mais bon au lieu de rajouter une fonction je fais juste un petit free puisque j'ai supprimé toutes les allocations inutiles et qu'il n'en reste qu'une

lol, le prof ne te note pas sur le code ? (à moins que ça ne soit pas noté...)

si si c'est noté ... mais bon on a une séance où il teste le programme avec nous pour voir s'il fonctionne bien et je sens que ce test va y passer lool


heu pour l'intituler exact bah en gros on a une tite explication de ce qu'est le quicksort et pi on a 4 questions :
- donner l'algo récursif sur les tableaux
- définir le type liste
- donner l'algo récursif et le code en C du tri Quicksort sur une liste. l'utilisateur pourra saisir un nombre quelconque de valeurs et obtenir à l'écran le résultat ainsi que le temps de calcul
- établir un court rapport présentant ces étapes (m'enfin celle là n'a aucun intérêt pour le coup )

voili voilou mais je pense pas que ça change grand chose vu la précision de l'énoncé

[invite97a92052]

j'ai déjà regardé mais bon au lieu de rajouter une fonction je fais juste un petit free puisque j'ai supprimé toutes les allocations inutiles et qu'il n'en reste qu'une

faire free(l) ne libèrera pas toute la liste, ça libèrera juste le premier élément de la liste !

Sinon, voici ce à quoi je pensais pour du code "pas très beau"
J'ai modifié le type liste, separation() et quicksort()
Ce n'est pas optimal non plus, enfin bon, je te montre à titre informatif :

#include <stdio.h>
#include <stdlib.h>


typedef struct elem {
	int val;
	int triOK;
	struct elem *suiv;
} element;
typedef element *liste;


void aff(liste l) {
	while(l) {
		printf("%d\n", l->val);
		l = l->suiv;
	}
}

void saisie(liste* pl) {
	
	int val;
	
	puts("Entrez vos valeurs (0 pour arreter)");
	while(scanf("%d", &val) && val != 0) {
		*pl = calloc(1, sizeof **pl);
		(*pl)->val = val;
		pl = &((*pl)->suiv);
	}
}

void separation(liste l, liste* l1, liste* l2) {
	
	liste suiv, temp;
	static int pivot;
	static int yapudbug=0;
	
	if(l == NULL) return;

	if(!yapudbug) pivot = l->val;
	
	while(l) {
		suiv = l->suiv;
		if(l->val < pivot+yapudbug) {
			l->suiv = *l1;
			*l1 = l;
		}
		else {
			l->suiv = *l2;
			*l2 = l;
		}
		l = suiv;
	}
	
	if(*l1 == NULL) {
		temp = *l2;
		*l2 = NULL;

		yapudbug=1;
		separation(temp, l1, l2);
		yapudbug=0;

		if(*l2 == NULL)
			(*l1)->triOK=1;
	}

}


void vidage(liste l) {
	liste p;
	while(l) {
		p = l->suiv;
		free(l);
		l = p;
	}
}

liste fusion(liste l1, liste l2) {
	liste temp = l1;
	if(l1==NULL) return l2;
	
	while(temp->suiv) temp = temp->suiv;
	temp->suiv = l2;

	return l1;
}

liste quicksort(liste l){
	liste l1=NULL, l2=NULL;
	
	if(l == NULL)
		return l;

	if(l->triOK) {
		l->triOK = 0;
		return l;
	}

    separation(l, &l1, &l2);
    l1=quicksort(l1);
    l2=quicksort(l2);
    l=fusion(l1,l2);

    return l;
}


int main(void) {
	
	liste l=NULL;

	saisie(&l);
	
	if(l != NULL) {
		l = quicksort(l);
		aff(l);
		vidage(l);
	}

	system("pause");
	return 0;
}

A toi de voir ce que tu peux en tirer...


PS : j'utilise 2 variables déclarées static, je ne sais pas si tu as vu ça en cours...

[invite0b0ee8b7]

non les variables static c'est pas trop au programme mais si je vois à peu près ce que c'est !

ce qui est sûr c'est que le problème vient de cette histoire de pointeur vu qu'avant ça y'avait pas de souci ^^

bon aller on s'y remet !!

[invite97a92052]

Dommage, ça marchait bien
Sinon, tu dis à ton prof que t'es en avance sur le programme
static, ça veut dire que toutes les instances de la fonction partagent le même espace mémoire pour la variable en question (dans le cas d'une fonction récursive, ça peut être très utile pour stocker quelque chose qui ne chage pas au fil des appels)

Sérieusement, ce n'est pas un problème de pointeurs, c'est un problème d'algorithme, dans ces 2 cas le vieux code ne marche pas :

1) la liste commence et débute par le pivot, et tous les éléments intercalés ont une valeur supérieure ou égale à la valeur du pivot
2) comme le 1), mais la liste ne contient qu'une sucessions de pivots (2 ou plus)


Dans les 2 cas, la fonction séparation() ne fera rien, à part inverser la liste à chaque passage.
Vu que la liste fait plus de 1 élément de long, quicksort() est appelé en boucle infinie -> dépassement de pile, d'où le bug

Dans mon post précédent, je contourne le problème comme ceci :

- si séparation() n'a rien séparé, on est peut-être dans le cas 1) (mais pas forcément)
En ajoutant temporairement 1 au pivot, on peut retenter de séparer la liste. Le problème 1) est ainsi évité car les pivots vont s'en aller dans l'autre liste. (à ne pas faire en permanence, car sinon on aura le bug pour des valeurs inférieures ou égales)

-si la reséparation ne donne rien (toujours une des 2 listes vide), on est dans un cas 2) : que des pivots.
Or dans ce cas, la liste est triée (car que des pivots) -> on la marque comme triée, et puis basta !

Il y a sûrement moyen d'y arriver sans static (et même sans modifier le type liste), mais je te laisse te creuser la tête
(n'utilise pas de variables globales, ça marcherait, mais c'est pas non plus le must)

[invite0b0ee8b7]

1) la liste commence et débute par le pivot, et tous les éléments intercalés ont une valeur supérieure ou égale à la valeur du pivot

dans ce cas là le programme fonctionne très bien, je l'ai testé en entrant des valeurs toutes supérieures au pivot et pas de bug !

le seul bug c'est quand on entre deux valeurs identiques et pas forcément identiques au pivot (en remarque toutes valeurs est sensible de devenir pivot so ...)

enfin bon je vais voir ce que je peux faire et pi sinon je le laisserais comme ça !!! lool

[invite3ff5f352]

C'est le classique passage par valeur alors que tu devrais faire un passage par adresse. Il faut toujours faire un passage par adresse pour que la modification se repercute a l'exterieur de ta fonction.

[invite0b0ee8b7]

je fais bien un passage par adresse et pas par valeur