Tri sur liste chainée

**SevSof** · 25/05/2007, 17h21

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!

**Emmanuel Delahaye** · 25/05/2007, 17h42

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 ?

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?

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.

**SevSof** · 25/05/2007, 19h45

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.

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.

**muad'dib** · 25/05/2007, 19h58

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 ?

**souviron34** · 25/05/2007, 20h11

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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...

.

**Emmanuel Delahaye** · 25/05/2007, 20h49

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...

**Jean-Marc.Bourguet** · 25/05/2007, 21h22

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.

**Emmanuel Delahaye** · 25/05/2007, 22h21

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 ?

**SevSof** · 25/05/2007, 23h26

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

**Leole** · 25/05/2007, 23h32

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

**Jean-Marc.Bourguet** · 26/05/2007, 08h24

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.

**HanLee** · 26/05/2007, 18h24

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.

**ranell** · 26/05/2007, 19h54

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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+

**diogene** · 26/05/2007, 20h01

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

**muad'dib** · 26/05/2007, 20h04

Envoyé par ranell

pourquoi pas le tri à bulle??

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

**Leole** · 26/05/2007, 23h11

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 ?

**muad'dib** · 27/05/2007, 00h45

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.

Tri sur liste chainée

C

Discussions similaires

Partager

Partager