Informatique -- Tronc Commun TD 4 -- Listes chainées: tri et arbres
Benjamin Werner, Eric Schost
29 novembre 1999
On continue à s'entrainer à la manipulation de listes chainées. Mais
aujourd'hui nous allons écrire des programmes de tri, et pour cela on
utilise d'autres structures de données à base de pointeurs: des arbres
binaires et des listes de listes.
On commencera néanmoins par un mini-exo sur le passage de paramètres.
1 Mini-exo: passage de pointeurs en paramètres
Pour l'homogénéïté, je propose que tout le monde utilise la
définition de listes donnée dans Liste.java (et ce
pour l'ensemble du TD). C'est essentiellement la définition vue la
semaine dernière.
Dans le programme donné, affiche est la méthode standart
d'affichage de listes. Il s'agit de deviner ce que fait le
programme suivant, puis de vérifier en compilant et exécutant. Prévenez-nous si
vous ne comprenez pas le résultat obtenu.
2 Tri par tas
C'est un algorithme de tri pour listes chainées, dont le temps
d'exécution est en O(n.log(n)), où n est la longueur de la
liste. Il utilise une structure de donnée auxiliaire: les arbres
binaires.
2.1 Arbres binaires
Un arbre binaire est une autre manière de ranger des entiers, qui
ressemble aux listes. En fait, un arbre binaire est:
soit l'arbre vide (cad. le pointeur null)
soit un entier et deux sous-arbres; le gauche et le droit.
La différence avec les listes est qu'il y a deux sous-arbres et non
pas une sous-liste.
Lisez la suite de l'énoncé, puis définissez la classe des arbres.
2.2 Insertion dans un arbre
On appelle tas un arbre semi-ordonné, c'est-à-dire que l'entier
à la racine est plus petit que les entiers des deux sous-arbres; et
deux plus les deux sous-arbres sont eux-mêmes des tas.
Ecrivez une méthode insere qui insère un entier dans un tas. Le
principe de l'algorithme est donné par les équations ci-dessous, où
<> désigne l'arbre vide, et <t1,a,t2> est l'arbre contenant
l'entier a et les deux sous-arbres t1 et t2.
ins(a,<>)
=
< <>,a,<> >
ins(a,<t1,b,t2>)
=
<ins(a,t2),b,t1> si b<a
ins(a,<t1,b,t2>)
=
<ins(b,t2),a,t1> si a<b
Remarquez bien que l'on préserve la notion de tas. L'inversion
droite-gauche sera utile par la suite, pour garder l'arbre
``équilibré''.
2.3 Transformer une liste en tas
Pour trier une liste quelconque l, la première étape est alors de la
transformer en tas. Pour cela, il suffit de partir de l'arbre vide et
d'y insérer au fur et à mesure les éléments de l.
Ecrivez la méthode correspondante.
2.4 Transformer un tas en liste triée
On commence par définir une méthode qui fusionne deux listes
triées. C'est quasiment la méthode union du TD précédent.
Ensuite il est facile de transformer un tas en liste triée:
la liste vide correspond à l'arbre vide
pour l'arbre <t1,a,t2>, on traduit récursivement les deux
sous-arbres t1 et t2, on
fusionne les listes obtenues, et on rajoute a en tête.
Ecrivez la méthode correspondante et la méthode de tri.
S'il vous reste du temps, il est sans doute plus intéressant de
s'attaquer à la question suivante, où l'on cherche à animer le tri par
tas. Sinon, vous devez pouvoir rapidement ecrire un autre programme
de tri, très efficace.
On utilise une autre structure de donnée auxiliaire: les listes
de listes.
Ensuite:
on commence par prendre la liste à trier et on la transforme en
une liste de liste (dont chaque élément a un seul élément),
puis on parcourt cette liste de liste, et on fusionne ses
éléments deux-à-deux; on re-commence jusqu'à ce que la liste de liste
ne contienne plus qu'un élément.
Par exemple, pour trier [3; 1; 2; 4] les étapes sont:
Un bon exercice est d'afficher graphiquement un arbre, tel que défini
en 2.
On affiche les deux sous arbres cote-à-cote, puis on affiche l'entier
à la racine et on dessine deux lignes pour relier cette racine aux
sous-arbres. Une ébauche de programme se trouve
ici:Aff.java
(avec des rappels sur la bibliothèque MacLib).
Après on peut utiliser plus ou moins d'astuces pour un affichage plus
ou moins joli.