Une classe qui gère un ArrayList trié d'entiers
Il s'agit de définir une classe représentant un trié d'entiers.
La classe, appelée ArrayListTrie étendra ArrayList<Integer> ; la classe ArrayList se trouve dans le paquetage java.util ; elle modélise une collection d'objets ; elle est générique ce qui fait qu'on peut préciser le type des objets de la collection ; un ArrayList<Integer> doit contenir uniquement des Integer. Ne pas connaître les classes génériques ne devrait pas vous gêner pour cet exercice ; il suffit de mettre dans l'en-tête de la classe extends ArrayList<Integer>.
Les méthodes suivantes seront prévues :
- void inserer(int entier) : insére un entier dans la liste en respectant un ordre croissant sur les entiers. On conseille d'utiliser ici l'algorithme suivant (qui suit le principe du tri par insertion) : notons n l'entier à insérer et k l'indice le plus grand des éléments de l'ArrayList ; on compare n à l'entier p qui se trouve à l'indice k dans la liste ; si n est plus grand que p, on met n à l'indice k + 1 dans la liste ; sinon, on décale p d'un indice vers la droite en l'écrivant à l'indice k + 1 de la liste (puisque n viendra avant p) et on compare n avec l'entier q qui se trouve à l'indice k - 1 de la liste ; si n est plus grand que q, on écrit n à l'indice k qui est sa bonne place définitive, sinon on décale q d'un indice vers la droite en l'écrivant à l'indice k ; et ainsi de suite en remontant vers la gauche de la liste jusqu'à trouver la bonne place pour n ou bien arriver à la gauche de la liste ; il reste à écrire cela avec une boucle portant sur un indice décroissant à partir de k.
- void supprimer(int entier) : retire un entier donné, si un tel entier est dans la liste. Si l'entier figure plusieurs fois, une seule occurrence est retirée.
- public String toString() : retourne une chaîne de caractères décrivant la liste, en redéfinissant la méthode toString héritée de la classe ArrayList.
- void afficher() : affiche à l'écran la liste triée des entiers en utilisant la méthode toString.
On rappelle que si une variable n de type int est utilisée à un endroit où un Integer est attendu, le compilateur s'en aperçoit et transforme n en l'Integer contenant la valeur de n et vice-versa.
La classe ArrayList possède les méthodes suivantes :
- size() retourne le nombre d'éléments rangés dans la liste ; les éléments de la liste sont rangés dans des indices compris entre 0 et size() - 1 ;
- get(int i) retourne l'élément qui se trouve à l'indice i ;
- s'il s'agit de ArrayList<,E>, add(E element) ajoute element à la fin de la liste et augmente en conséquence la taille de celle-ci ;
- s'il s'agit de ArrayList<E>, set(int i, E element) remplace l'élément se trouve à l'indice i par element ; on ne peut pas insérer un élément au-delà de l'indice size() - 1 ; il faudra y faire attention dans la méthode inserer..
On récupérera le fichier EssaiArrayListTrie.java qui contient une méthode main qui permet de tester la classe ArrayListTrie que vous aurez écrite. Lors de l'exécution de ce programme de test, on pourra dans une boucle entrer :
- la lettre i suivie de données à insérer
- la lettre s suivie de données à supprimer
- la lettre a pour afficher le contenu du tableau
- la lettre q pour quitter
Corrigé pour la classe ArrayListTrie