Discussion :

[Damoun]

Bonsoir

Voila je ne comprend pas tres bien le trie par insertion d'une liste chainee.
C'est assez flou, quelqu'un aurais une explication pas a pas car la permierre structure c'est assez facile de la placer lol, mais apres, je ne vois pas trop pour les autres, placer avant, apres.
J'ai deja compris qu'il allai falloir changer les adresses des ou point les pointeur sur la structure suivante mais le reste O_o

Merci

[Obsidian]

D'une part, le tri par insertion, ça consiste à faire comme si tu triais des livres sur une étagère : tu pars de la gauche, tu prends le premier livre et tu le mets « à sa place » parmi les livres déjà triés. Par définition, tout ce qui se trouve à gauche du livre courant est déjà trié, parce que c'est ce que tu as déjà traité, et tout ce qui est à droite ne l'est pas encore parce que tu ne les as pas encore examinés. Donc, tu fais une seule passe de gauche à droite et pour chaque livre, tu recherches sa position entre le début de l'étagère (à gauche) et ta position courante.

C'est simple et efficace mais cela implique de pouvoir faire une insertion, ce qui n'est pas toujours (voire rarement) possible. Par contre, les listes chaînées sont particulièrement adaptées à cela. Chaque « maillon » a une position fixe et arbitraire en mémoire, et chacun contient un champs « suivant » qui donne la position du prochain maillon. Pour intercaler un maillon C entre deux maillons A et B, il suffit de faire pointer C vers B, en copiant le champ « suivant » de A dans celui de C, puis de faire pointer A vers C, en plaçant l'adresse de C dans le champ « suivant » de A.

[Damoun]

Mais la liste chainee doit deja etres complette, ou le tri ce fais au fur a mesure qu'on remplie cette liste ?

[Obsidian]

Dans le cas des listes chaînées, ces deux cas reviennent exactement au même.

À ceci près tout de même que si on travaille sur une liste déjà construite, il faut penser à « retirer » l'élément que l'on classe avant de l'insérer autre part (ce qui veut dire qu'il faut penser à faire pointer l'élément précédent sur le suivant).

[Pouet_forever]

Bah par définition tu fais un tri une fois, mais si tu rajoutes des choses après tu n'auras aucune certitude que ta liste soit triée.
C'est un peu comme si tu triais ton étagère.
Tu la trie bien au départ mais si tu rajoutes des livres à la fin sans les ranger au fur et à mesure ton étagère sera désordonnée

Bah pour la liste c'est pareil, tu la trie et ensuite si tu veux la garder triée soit tu insères des éléments en fin et tu fais un tri sur toute ta liste, ou soit dès que tu insères un élément tu le mets à la bonne place.
A toi de choisir

[Damoun]

Ok,c'est deja un peu plus claire.

Donc en fait des que j'insert une nouvelle structure, je fais un strcmp du data de la structure next par rapport au data de la structure a trier, et en fonction de ce que me renvoie strcmp, je sais ou la placer, c'est a peu pres sa non ?

un petit exemple de la liste chainee dont je parle

Code :

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

1
2
3
4
5
6
 
struct             list
{
    char          *data;
    struct list   next;
};

[Pouet_forever]

Hé bien tu n'as pas vraiment beaucoup de possibilités en fait ...
La liste chaînée (simple) ne te permet que de la parcourir dans un seul sens mais pas dans le sens inverse. Du coup le coup de la dichotomie et compagnie tu peux oublier :'(
Donc pour ajouter correctement ton élément il faut que tu fasses un strcmp sur chaque élément de ta liste et dès que strcmp te renvoies une valeur négative tu sais qu'il faut le placer ici

De plus ta structure ne fais pas office de liste chaînée. Pour faire une liste chaînée il faut que la structure contienne un pointeur sur elle-même et non une structure de elle-même

Du coup ça donnerais ça :

Code :

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

1
2
3
4
5
struct             list
{
    char          *data;
    struct list   *next;
};

[Damoun]

Oui, petite oublie dans la frappe ^^

Ok, donc deja je part sur une bonne piste, merci pour votre aide