INF 411 - TD 8
Tri fusion en place et généricité


Votre opinion sur le cours de ce lundi : Votre opinion sur le TD de la semaine dernière :

 Login :  Mot de passe :

But

Implémenter le tri fusion en place de listes chaînées génériques, et l'appliquer au calcul de la distribution des mots d'un texte (fonction qui renvoie le nombre d'apparitions d'un mot dans un texte), et au calcul d'une valeur médiane d'un ensemble de valeurs numériques.

À télécharger

Extraire le contenu du fichier src.zip dans le répertoire src du projet.
Extraire le contenu du fichier text.zip à la racine du projet.

Avertissement

Afin de minimiser les risques d'erreurs de manipulation lors des dépôts de fichiers (nécessaires à la correction automatique), toutes les classes que vous avez à modifier sont réunies dans un même fichier (TD8.java) que vous devez déposer après chaque question.

On rappelle néanmoins qu'en dehors de circonstances exceptionnelles, on écrit plutôt des classes différentes dans des fichiers différents, tant pour la lisibilité du code que pour l'efficacité de la compilation.

Activer assert dans votre machine virtuelle Java

Vérifier que les assert's sont activés en exécutant le programme TestAssert.java. En cas de problème, suivez la procédure ci-dessous.

Cliquez sur Window -> Preferences puis sur l'onglet Java -> Installed JREs de la fenêtre qui apparaît. Cliquez sur la machine virtuelle que vous utilisez (il ne devrait y en avoir qu'une seule installée). Cliquez sur le bouton Edit. Dans la barre Default VM argument écrivez -ea (pour enable assert). Cliquez sur Ok.

1 Listes chaînées

La classe Singly<E>, écrite dans le fichier TD8.java, implémente les listes chaînées d'objets de la classe E. On choisit de représenter la liste vide par la valeur null. Chaque objet a deux champs publics : La classe Singly<E> offre un constructeur ainsi que d'autres méthodes utilisées dans les tests, que vous pouvez ignorer.

Question 1 : Complétez les méthodes Testez votre code en exécutant le fichier Test1.java.

Déposez le fichier TD8.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2 Tri fusion en place de listes chaînées de chaînes de caractères

Nous allons maintenant manipuler des listes de chaînes de caractères, autrement dit des objets de la classe Singly<String>.

2.1 Principe du tri fusion en place

La fusion en place (merge) de deux listes chaînées ordonnées l1 et l2 se fait sans créer ni détruire de cellules. Comme le suggère l'illustration qui suit, l'algorithme ne fait que modifier, au besoin, les pointeurs qui indiquent les cellules suivantes. En particulier, les listes l1 et l2 sont détruites.

2.2 Implémentation

Les listes chaînées l1 et l2 sont deux « réserves » dont on « prend » des éléments pour les « mettre » dans une liste auxiliaire accu. L'algorithme est donc le suivant : Indication : « prendre » le premier élément d'une liste x pour le « mettre » à la fin d'une liste accu dont le dernier maillon est pointé par last se fait en modifiant quatre pointeurs, comme le suggère le dessin ci-dessous. En particulier, vous ne devez pas créer de nouvelles cellules, c'est-à-dire ne pas utiliser d'instructions new Singly<String>.


Attention : bien que logiquement équivalents, les tests length(l) == 0 et l == null n'ont pas la même complexité algorithmique: faites le bon choix!

Question 2.2 : Dans la classe MergeSortString complétez les méthodes statiques suivantes : Notez que cette classe ne contient que des méthodes statiques.

Exécutez le fichier Test22.java qui teste les méthodes merge et sort.

Déposez le fichier TD8.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

2.3 Application : nombres d'apparitions des mots dans un texte

Chaque objet de la classe Occurrence possède les champs : Question 2.3 : Dans la classe Occurrence, complétez la méthode qui renvoie la liste des mots présents dans une liste avec leur multiplicité. On commencera par trier la liste passée en argument, afin que les mots identiques se retrouvent consécutifs. Aucun ordre n'est spécifié concernant la liste renvoyée. Testez votre code en exécutant le fichier Test23.java.

Déposez le fichier TD8.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3 Tri fusion en place de listes chaînées quelconques

On peut trier les éléments d'une liste dès lors qu'ils sont totalement ordonnés, autrement dit dès que leur classe implémente l'interface Comparable.

3.1 Implémentation générique

Question 3.1 : Adapter le code de la classe MergeSortString pour compléter les méthodes suivantes dans la classe MergeSort : Exécutez le programme contenu dans le fichier Test31.java pour tester les méthodes génériques merge et sort.

Déposez le fichier TD8.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3.2 Application : les mots les plus fréquents

Question 3.2 : À l'aide de la méthode générique sort (qui trie les éléments d'une liste dans l'ordre croissant) complétez les méthodes suivantes dans la classe Occurrence : Pour cela il faut compléter, dans la classe Occurrence, la méthode Attention : l'entête class Occurrence implements Comparable<Occurrence> indique au compilateur que les objets de la classe Occurrence sont ordonnés.

Testez votre code en exécutant le programme contenu dans le fichier Test32.java. L'exécution du test nécessite quelques secondes.

Déposez le fichier modifié TD8.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer

3.3 Application : valeur médiane d'une liste de flottants

On se propose d'appliquer maintenant notre tri générique dans un contexte différent.

Un flottant m est une valeur médiane d'une liste de flottants lorsque :

On donne la classe Pair.java.

Question 3.3 : Dans la classe Median, complétez la méthode qui renvoie l'intervalle des médianes possibles sous la forme d'une paire. Si la liste est vide, la méthode renvoie la paire dont les deux composantes sont égales à la valeur spéciale Double.NaN (un acronyme pour «Not a Number»). Testez votre code en exécutant le programme contenu dans le fichier Test33.java.

Déposez le fichier TD8.java :

Le nom du fichier à déposer
Il faut se connecter avant de pouvoir déposer