Discussion :

[autre]

Bonsoir,

J'aimerais trier ma liste par la date la plus proche à la date la plus loin
en utilisant ces structures:

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
typedef struct{
	int j;
	int m;
	int a;
}dat;
typedef struct{
	int h;
	int mn;
}heu;
typedef struct{
	char objet[25];
	char lieu[25];
	dat date;
	heu heure;
}evnt;
typedef struct cellule{
	evnt valeur;
    struct cellule *suivant;
}cellule;
typedef cellule *liste;

Merci d'avance.

[Obsidian]

Regarde du côté de qsort().

[plxpy]

sauf que si c'est organisé en liste (certes, très rudimentaire), qsort va mettre "un beau bordel" au niveau du champ "suivant" dans les cellules, non ? (ou alors j'ai loupé quelque chose). D'ailleurs, que mettre en premier (de mémoire) paramètre ? Qsort ne peut pas être utilisé ici, les "cellules" ne sont pas jointives, les unes derrière les autres, en mémoire.

Un tableau "tout bête" serait peut-être plus approprié et permettrait d'utiliser qsort. Si la liste est incontournable (dans le sens obligatoire), le tri va être plus sport ...

[Obsidian]

Oui, c'est vrai que j'ai répondu sans faire défiler le code source et que j'ai omis le fait qu'il s'agit d'une liste chaînée.

[plxpy]

C'est pas grave, ça nous arrive à tous, moi le premier.

Je ne résiste pas à mettre ici un lien vers une vidéo montrant comment fonctionnent le tri à bulle et un quick-sort [ame="http://www.youtube.com/watch?v=vxENKlcs2Tw&feature=fvwrel"]Visualization of Quick sort[/ame].

[autre]

Merci pour vos réponses, mais comment transformer une liste en un tableau ? càd une case de tableau, qu'est ce qu'elle contient ?

[Obsidian]

Merci pour vos réponses, mais comment transformer une liste en un tableau ? càd une case de tableau, qu'est ce qu'elle contient ?

Elle contient ce que tu veux, pourvu que ce soit un type connu par le C et que toutes les cases soient du même type. Lorsque tu écris « char objet[25] » pour stocker un nom, tu définis en réalité un tableau de 25 caractères consécutifs.

Dès lors, rien ne t'empêche de faire un tableau de structures. Il est alors aussi facile de permuter ses cases que s'il s'agissait de types natifs ordinaires. Tu peux écrire une fonction qui « compare deux cases » en comparant en réalité les membres de ces structures respectives, et la passer à qsort() qui, elle, effectuera le tri en fonction des résultats renvoyés par ta fonction de comparaison.

[autre]

mais comment déclarer un tableau de structure et c'est quoi qsort() ?

[souviron34]

un tableau de structures est comme un tableau normal :

Code C :

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

1
2
3
typedef struct ... {...} MaStruct ;
 
MaStruct Table[10] ;

par exemple


Pour qsort, il suffit de regarder le man pages :

qsort

[Sve@r]

mais comment déclarer un tableau de structure et c'est quoi qsort() ?

Salut
qsort() est une fonction générique permettant de trier un tableau de n'importe quoi.
Elle fonctionne sur le principe que les éléments d'un tableau sont toujours contigus en mémoire. Donc qu'on peut, en passant par des manipulation d'octets, permuter 2 éléments mal rangés.
Donc cette fonction ne sait pas ce qu'elle manipule mais comme elle connait le nombre d'éléments et la taille de chaque élément, elle sait permuter 2 éléments.
Tout ce que l'utilisateur a à faire est d'écrire une fonction xxx() qui sait comparer 2 éléments. Et ça il peut le faire parce que lui il sait ce qu'il manipule.
Donc il écrit sa fonction xxx() selon le schéma suivant: xxx() renvoie
-1 si élément1 < élément2
0 si élément1 = élément2
1 si élément1 > élément2
Puis il appelle qsort en lui passant
- l'adresse du tableau
- le nombre d'éléments
- la taille d'un élément
- l'adresse de la fonction xxx()
Et à partir de là, qsort() se débrouille pour tout trier.

Accessoirement ta question initiale n'a aucun sens. Car on utilise généralement une liste pour avoir des éléments toujours triés (l'insertion d'un élément au milieu de la liste étant très facile puisque cela ne déplace que 2 pointeurs). Donc avoir une liste d'éléments non triés est complètement idiot puisque la liste n'est utile que si les éléments sont toujours triés. S'ils ne le sont pas, alors la liste n'a plus du tout d'utilité et autant revenir au tableau simple (qu'on peut agrandir à coup de realloc et éventuellement trier plus tard avec qsort)...

Je ne résiste pas à mettre ici un lien vers une vidéo montrant comment fonctionnent le tri à bulle et un quick-sort

Très amusant surtout le petit match final. Il faut toutefois se le passer plusieurs fois pour bien percevoir l'effet récursif du qsort...

[anacharsis]

salut !

as-tu bien besoin de trier ta liste ? l'ordre initial est peut-être important. ce qui ne coûte pas cher, c'est de créer un tableau d'index (pointeur vers cellule) et de trier par qsort (ou autre) ce tableau, sans avoir à toucher à ta liste.

A+