Le tri par arborescence découle directement de ia théorie des graphes dont nous rappelons quelques notions : - Un graphe est composé de sommets et d'arcs les reliant.
- Une arborescence est un arbre dont chaque sommet (à l'exception du plus haut appelé racine) est l'extrémité terminale d'un seul arc.
- Un noeud est un sommet qui est l'origine d'au moins un arc vers un sommet inférieur.
- Les feuilles sont les derniers sommets qui ne dépendent d'aucun autre sommet.
Le tri par arborescence consiste à transformer la suite des informations du tableau à trier en une structure arborescente en générant les pointeurs de gauche, de droite et de sommet. Il comporte deux parties : - la création de l'arborescence qui consistera à mettre à jour les pointeurs en fonction de la c!é de tri. Le premier élément est pris pour racine et chaque élément suivant est mis à gauche s'il est plus petit et à droite s'il est plus grand, en mettant à jour les pointeurs "gauche", "droite" et "père" ;
- la lecture de l'arborescence ainsi créée en partant de la feuille la plus à gauche qui sera l'élément le plus petit et en se servant des différents pointeurs pour
- remonter.
Dans le programme, nous utilisons trois tableaux : - D$() le tableau à trier (alphanumérique dans notre cas),
- R$() le tableau de résultats.
- G() contiendra les pointeurs de gauche de l'élément.
- D() contiendra les pointeurs de droite de l'élément.
- PER() contiendra les pointeurs de sommet de l'élément.
Exemple : soit trier le tableau de la figure 1. 
Fig. 1 Supposons que les 4 premiers éléments soient rangés en arborescence et proposons de ranger les deux suivants. Ajoutons 4790 4790 est comparé à la racine 5320, il est plus petit et le pointeur gauche est non nul, on descend à gauche.
4790 est comparé à 4980, il est plus petit et le pointeur gauche est non nul, on descend à gauche.
4790 est comparé à 3870, il est plus grand et le pointeur droit est nul, on le met donc à droite.
On met le pointeur droit de 3870 à 5 et le père de 4790 à 4. Ajoutons 6320 6320 est comparé à 5320, il est plus grand et le pointeur droit est non nul, on descend à droite. 6320 est comparé à 7490, il est plus petit et le pointeur gauche est nul, on le met donc à gauche. Le pointeur gauche de 7490 est mis à 6 et le père de 6320 est mis à 2. Quant à l'efficacité de cette méthode, elle se rapproche de la méthode de Shell-Metzner (voir tableau) et est nettement plus performante que la méthode par dichotomie. Nbre d'art. 30 150 300 600
Sélectio 3,9s 79s 295s
Dichotomie 3,9s 55s 194s
Shell-Metz 1,7s 18s 33,8s 86s
Arboresc. 1,7s 17s 38s 100s
CPC n°7
| ★ AMSTRAD CPC ★ DOWNLOAD ★ |
 | Aucun fichier de disponible:
» Vous avez des fichiers que nous ne possédons pas concernent cette page ? | | ★ AMSTRAD CPC ★ A voir aussi sur CPCrulez , les sujets suivants pourront vous intéresser... |
CPCrulez[Content Management System] v8.7-desktop/c
Page créée en 364 millisecondes et consultée 1908 foisL'Amstrad CPC est une machine 8 bits à base d'un Z80 à 4MHz. Le premier de la gamme fut le CPC 464 en 1984, équipé d'un lecteur de cassettes intégré il se plaçait en concurrent du Commodore C64 beaucoup plus compliqué à utiliser et plus cher. Ce fut un réel succès et sorti cette même années le CPC 664 équipé d'un lecteur de disquettes trois pouces intégré. Sa vie fut de courte durée puisqu'en 1985 il fut remplacé par le CPC 6128 qui était plus compact, plus soigné et surtout qui avait 128Ko de RAM au lieu de 64Ko. |
|
|
|
