Discussion :

[kazuzu]

Bonjours,

voici le problème :

je lit dans un fichier le nom et l'age de plusieurs personne et je compose une
liste chainée de ces personne, le but est de trié cette liste chainée dans l'ordre alphabétique mais je voudrai me passé de l'algorithme traditionnel de tri.
En fait ce que je veux c'est que quand je lit une personne, le maillon de la liste se place directement au bon endroit.
par exemple : le premier maillon contient "Durand 40" , le second "Fernand 32", le troisième "Carlos 37".
le troisième maillon est donc "Carlos 37" et lors de la lecture je voudrai qu il mette directement "Carlos 37" entre "Durand 40" et "Fernand 32", etc ...

J'aurai besoin d'un peu d'aide pour me mettre sur la piste.
Merci d'avance.

[diogene]

La structure de donnée à utiliser dépend des détails et des contraintes du problème.

L'insertion d'un maillon dans la structure de donnée se fera en deux étapes :
- recherche du point d'insertion dans la structure de donnée
- insertion en ce point (réalisation du chainage entre les maillons concernés)
On peut envisager aussi la suppression d'un maillon (ne serait-ce que pour détruire la structure de donnée et récupérer la mémoire)

Quelques méthodes classiques :

1- la liste est simplement chainée, c'est à dire que chaque maillon ne comporte qu'un pointeur vers le maillon suivant. On ne sait donc pas déterminer facilement le maillon qui précède un maillon donné. Dans ce cas, il faut déterminer le point d'insertion comme le maillon derrière lequel on doit placer le nouveau pour pouvoir réaliser le nouveau chainage. A noter que l'insertion en tête de liste constitue un cas particulier qui ne répond pas à ce critère.
La même contrainte s'appliquera au cas de la suppression d'un maillon : connaitre le maillon précédant celui que l'on veut supprimer. La donnée du maillon à supprimer n'est donc plus suffisante (elle ne donne comme information que le maillon qui le suit) et il faut obtenir indépendamment le maillon qui le précède.

2- La liste est doublement chainée : chaque maillon a un pointeur vers le maillon suivant et un pointeur vers le maillon précédent. La contrainte du cas précédent n'existe donc plus et on peut choisir comme point d'insertion le maillon derrière lequel on doit placer le nouveau ou celui devant lequel on doit le placer.Là aussi, considérer les cas particuliers (liste vide, insertion en tête, insertion en queue, insertion au milieu,...).
Par contre, la suppression d'un maillon est plus simple et plus rapide, puisque la donnée du maillon à supprimer suffit à déterminer le maillon qui suit et celui qui le précède. Ceci permet de reconstituer le chainage facilement.

3- Une alternative est de construire non plus une liste mais un arbre binaire de recherche. Son avantage est la facilité et la rapidité de l'insertion (le parcours pour déterminer le point d'insertion est en général bien plus court). Cette solution est pénalisée par la relative "complexité" de la suppression d'un maillon.

Finalement, le choix de la structure de donnée peut se faire en considérant
- la rapidité lors des insertions ou de la recherche d'un maillon précis (solution 3)
- la facilité des suppressions (solution 2)
- l'économie en quantité mémoire utilisée (solution 1)

[kazuzu]

merci diogène cela m'a éclairé la façon de faire afin de placer les éléments au bon endroits de la chaine, où je devrai par conséquent utilisé une structure itérative et une conditionnelle.
Encore merci.