Tri sur liste chainée

Version imprimable

25/05/2007, 17h21
SevSof

1 pièce(s) jointe(s)

Tri sur liste chainée

Bonjour,
je n'arrive pas à faire un tri sur liste chainée. Il ne faut pas le faire lors de la saisie, mais à la demande de l'utilisateur (car je travaille sur une structure donc il faut pouvoir trier par nom, prénom, identifiant...).
C'est la seule partie du programme que je n'arrive pas à faire, et ça fait maintenant une semaine que je suis dessus!

Si quelqu'un pouvait m'aider, ce serait vraiment sympa!

sinon, j'ai une autre question (mais pas besoin de créer un topic juste pour ça, c'est pas bien important!), j'utilise la fonction strcmp , ou encore system("pause") mais je n'ai pas besoin de mettre de bibliothèque, il compile. Mais certaines fois, quand j'enregistre mon programme sous un autre nom, il ne veut plus compiler... Pourquoi?

mon programme est en pièce jointe.

j'espère recevoir de l'aide, car là, je ne sais vraiment plus comment faire!
25/05/2007, 17h42
Emmanuel Delahaye

Citation:

Envoyé par SevSof

je n'arrive pas à faire un tri sur liste chainée. Il ne faut pas le faire lors de la saisie, mais à la demande de l'utilisateur (car je travaille sur une structure donc il faut pouvoir trier par nom, prénom, identifiant...).

La façon classique de trier une liste chainée est le tri par insertion, puisque l'insertion est justement une facilité des listes chainées. Tu as un algo ?

Citation:

sinon, j'ai une autre question (mais pas besoin de créer un topic juste pour ça, c'est pas bien important!), j'utilise la fonction strcmp , ou encore system("pause") mais je n'ai pas besoin de mettre de bibliothèque, il compile. Mais certaines fois, quand j'enregistre mon programme sous un autre nom, il ne veut plus compiler... Pourquoi?

8O Bibliothèque ? Je suppose que tu veux dire 'header' ou 'fichier d'en-tête' comme <string.h> ou <stdlib.h> ?

Il faut inclure ces fichiers, sinon, le comportement est indéfini. Tout peut arriver.
25/05/2007, 19h45
SevSof

Citation:

La façon classique de trier une liste chainée est le tri par insertion, puisque l'insertion est justement une facilité des listes chainées. Tu as un algo ?

mmh... je ne pense pas, car il ne faut pas trier seulement par rapport au nom de famille, mais aussi par rapport au prénom, par rapport à l'identifiant...
Et dans ce cas, je ne vois pas comment faire, j'ai déjà fait des recherches et j'avais vu que le tri par insertion était souvent expliqué, mais je ne pensais pas que ça convienne pour ce programme. Mais si c'est ça, ça doit se trouver facilement.

Citation:

Bibliothèque ? Je suppose que tu veux dire 'header' ou 'fichier d'en-tête' comme <string.h> ou <stdlib.h> ?

Il faut inclure ces fichiers, sinon, le comportement est indéfini. Tout peut arriver.

il me semblait que ça s'appelait bibliothèque... je dois confondre, désolée.
Mais c'est bizarre que ça veuille bien compiler, non?

Merci pour tes réponses.
25/05/2007, 19h58
muad'dib

Je ne sais pas si c'est une bonne idée mais peut-être que tu pourrais créer une seconde liste chainée dont tu trierais les éléments par insertion : au fur et à mesure que tu ajoutes tes éléments à ta nouvelle liste, tu effaces les anciens et hop ! Te voila avec une nouvelle liste triée ! Qu'en dis-tu ?

Citation:

Envoyé par SevSof

mmh... je ne pense pas, car il ne faut pas trier seulement par rapport au nom de famille, mais aussi par rapport au prénom, par rapport à l'identifiant...
Et dans ce cas, je ne vois pas comment faire, j'ai déjà fait des recherches et j'avais vu que le tri par insertion était souvent expliqué, mais je ne pensais pas que ça convienne pour ce programme. Mais si c'est ça, ça doit se trouver facilement.
.

Ben c'est pareil.. Je suppose que tu tries par rapport à l'un OU à l'autre, non ??

A mon avis, ce que je ferais, il y a 2 moyens :
1) le bête et méchant :

tu passes à travers ta liste (un peu comme tu as fais dans ta fonction tri en commentaires) en faisant 2 while...

Dans la routine de tri tu crées un tableau d'indicateurs (ou dans la structure à trier tu crée un indicateur), pour indiquer "déjà traité".

Pseudo-code :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 Initialiser tous les indicateurs à 0 variable continuer à vrai Tant que continuer = vrai continuer = faux elt = NULL pour debut liste à fin liste si indicateur = 1 prochain element sinon elt = element indicateur de element = 1 pour suivant à fin liste si indicateur = 1 prochain element sinon si valeur a tester de cet_element < valeur a tester de elt indicateur de element = 0 elt = cet_element indicateur de cet_element = 1 fin si fin si fin pour fin si fin pour si elt != NULL imprimer elt continuer = vrai fin si fin tant que
2) une méthode plus rusée (mais plus costaud) :

Si on ne veut pas modifier la liste originale :

tu fais un tableau des adresses des elements, en faisant une structure

NOEUD **Tableau_adr ;

et en copiant les adresses des elements de la liste (Tableau[0] = premier, .. Tableau[N-1]=dernier).

Et ensuite tu utilises un qsort pour trier les adresses, soit en sauvegardant en variable globale le type de tri et en faisant un switch sur le type de tri dans la routine de tri, soit sans variable globale en faisant autant de routines de tri qu'il y a de champs possibles, et en faisant le switch à l'endroit où tu va appeller le tri

Et là tu n'as plus qu'à passer dans ton tableau de i à N...
.

25/05/2007, 20h49
Emmanuel Delahaye

Citation:

Envoyé par muad'dib

Je ne sais pas si c'est une bonne idée mais peut-être que tu pourrais créer une seconde liste chainée dont tu trierais les éléments par insertion : au fur et à mesure que tu ajoutes tes éléments à ta nouvelle liste, tu effaces les anciens et hop ! Te voila avec une nouvelle liste triée ! Qu'en dis-tu ?

Oui, c'est la méthode que je sous-entendais...
25/05/2007, 21h22
Jean-Marc.Bourguet

Citation:

Envoyé par Emmanuel Delahaye

La façon classique de trier une liste chainée est le tri par insertion

Moi qui pensais que c'était le tri par fusion.
25/05/2007, 22h21
Emmanuel Delahaye

Citation:

Envoyé par Jean-Marc.Bourguet

Moi qui pensais que c'était le tri par fusion.

Euh, tri-fusion, c'est pas quand on met 2 listes dans une seule ?
25/05/2007, 23h26
SevSof

En fait, lors de l'execution de programme, on a un menu, et on peut choisir de trier, après avoir rentré un certain nombre de personnes.
J'avais pas l'impression que c'était clair.
Donc oui, c'est par rapport à l'un ou l'autre.

ça me semble vraiment compliquée (les deux méthodes), je n'ai fait que 6 mois de C (enfin, meme pas, j'ai commencé début février!)

La 2ème méthode, je la laisse tomber, par contre la première, j'ai pas trop compris...
A quoi sert "déjà traité"?

Je vais regarder plus en profondeur ton algo demain.

Merci pour vos réponses
25/05/2007, 23h32
Leole

La méthode la plus simple ce serait de re-créer une autre chaine a côté en triant en entrant les éléments pour pas te casser la tête...
[edit] proposé au dessus en fait , et mon message est pas très francais :oops:
26/05/2007, 08h24
Jean-Marc.Bourguet

Citation:

Envoyé par Emmanuel Delahaye

Euh, tri-fusion, c'est pas quand on met 2 listes dans une seule ?

C'est une des opérations de base du tri par fusion. L'autre étant de découper une liste en segments croissant.

Le tri par fusion est en N log N tandis que celui par insertion est en N carré, ce qui peut avoir un effet.
26/05/2007, 18h24
HanLee
1. Bon, pour trier par rapport au nom, prénom, c'est tout simple. Il te suffit de définir une relation d'ordre totale de préférence. Quand on trie des éléments, on les trie selon une relation d'ordre (ordre croissant pour les entiers, décroissants, lexicographique).

Donc, il te faudrait une fonction de 2 variables qui te permette de dire si un élément est plus petit qu'un autre.

Tu connais les pointeurs de fonctions ?

2. Ensuite le tri fusion, le principe c'est simple à réaliser avec des listes, c'est récursif, et performant au niveau complexité (et la pile ne risque pas d'exploser).

Soit une liste.
- Si ta liste est vide ou ne contient qu'un seul élément, on peut la considérer comme triée. Donc tu ne fais rien.
- Sinon, tu sépares ta liste en 2 sous-listes de taille comparable (égales à + ou - 1 près).
- Tu appliques l'algorithme de tri récursivement aux deux sous-listes (l'algorithme termine forcément, car on diminue strictement la taille des listes jusqu'à 0 ou 1 élément).
- Tu peux donc considérer que tes 2 listes sont triées. Il te suffit maintenant de les fusionner de manière à ce que la nouvelle liste respecte la relation d'ordre utilisée, et c'est fini.

salut,
pourquoi pas le tri à bulle??
voici un code j'espere que ca t'aidera:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
void tri_bulle( cel *l)
{int echange=0,temp;
cel *p;
while (echange==0)
	{echange=1;
	p=l;
		{while(p->succ!=NULL)//repeter tant qu'on est pas arriver à la fin de la liste
			{if (p->cle<p->succ->cle)
				{temp=p->cle;//permutation dans la liste
				p->cle=p->succ->cle;
				p->succ->cle=temp;
				echange=0;//sert comme condition de continuité pour le while(le premier)}
			}
		p=p->succ;//avancer d'une cellule a une autre}
	}
}void tri_bulle( cel *l)
{int echange=0,temp;
cel *p;
while (echange==0)
	{echange=1;
	p=l;
		{while(p->succ!=NULL)//repeter tant qu'on est pas arriver à la fin de la liste
			{if (p->cle<p->succ->cle)
				{temp=p->cle;//permutation dans la liste
				p->cle=p->succ->cle;
				p->succ->cle=temp;
				echange=0;//sert comme condition de continuité pour le while(le premier)}
			}
		p=p->succ;//avancer d'une cellule a une autre}
	}
}

A+

26/05/2007, 20h01
diogene

Le tri d'une liste est le même problème (et le même algorithme) que le tri d'un tableau. Un algo de tri repose en général sur les propriétés suivantes de la collection :
- La collection possède un premier élément (pour un tableau, celui d'indice 0, pour une liste , la tête de la liste), un dernier élément et on peut déterminer si un élément est le dernier élément de la collection. Chaque élément (sauf le dernier) à un élément suivant et à partir d'un élément on peut trouver l'élément suivant (sauf si c'est le dernier)
- On sait échanger la position des éléments dans la collection (dans le cas d'une liste, c'est une simple modification des pointeurs de chaînage)
- On a une relation d'ordre pour comparer les éléments de la collection.

Si on a un algo de tri de tableau et qu'on repère ces fonctionnalités , il suffit de les modifier pour celles d'une liste et obtenir le tri de la liste. Le tri peut se faire sur-place sans tableau ou sans liste supplémentaires
26/05/2007, 20h04
muad'dib

Citation:

Envoyé par ranell

pourquoi pas le tri à bulle??

Cet algorithme de tri est très très bof en termes de performances ..:?
26/05/2007, 23h11
Leole

Citation:

Envoyé par muad'dib

Cet algorithme de tri est très très bof en termes de performances ..:?

L'OCT est le meme que le tri par insertion non ?
27/05/2007, 00h45
muad'dib

Citation:

Envoyé par Leole

L'OCT est le meme que le tri par insertion non ?

Par OCT tu entends complexité? Si oui la complexité des 2 algorithmes est en O(n2), mais comme il va créer une nouvelle liste et insérer les éléments au fur et à mesure aux bons endroits, il y aura moins de comparaisons et d'échanges qu'avec le tri à bulles.
De toute façon le tri à bulles est déprécié et ne devrait plus être utilisé dans les codes.