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

On se propose d'implémenter le tri fusion en place de listes chaînées en abordant la généricité.

À 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.

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 Singly.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.

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

Déposez le fichier Singly.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

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.

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 élément 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!

Complétez la classe MergeSortString offrant 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.
Vous devriez obtenir le résultat suivant :


    Testing merge: [OK]
    Testing sort: [OK]

Déposez le fichier MergeSortString.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

Complétez la classe Occurrence dont chaque objet possède les champs : avec un constructeur Occurrence(String word, int count) et les méthodes suivantes : Testez votre code en exécutant le fichier Test23.java, vous devriez obtenir le résultat suivant :

    Test de la méthode «count», cela peut prendre quelques secondes :
    Comptage des mots du texte contenu dans le fichier «dummy.txt»
    Comptage des mots du roman «Le tour du monde en 80 jours» (J. Verne)
    Comptage des mots du roman «Dracula» (B. Stoker)
    Comptage des mots du roman «Ulysses» (J. Joyce)
    [OK]

Déposez le fichier Occurrence.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

Adapter le code de la classe MergeSortString pour compléter la classe MergeSort offrant les méthodes suivantes : Exécutez le programme contenu dans le fichier Test31.java pour tester les méthodes génériques merge et sort. Vous devriez obtenir le résultat suivant :

    Testing generic merge: [OK]
    Testing generic sort: [OK]

Déposez le fichier MergeSort.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

À l'aide de la méthode générique sort (qui trie les éléments d'une liste dans l'ordre croissant) complétez, dans la classe Occurrence, les méthodes suivantes: Pour cela, il faut ajouter à la classe Occurrence une 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. Après quelques secondes vous devriez obtenir le résultat suivant :

    Test de la méthode «sortedCount», ce test va prendre quelques secondes :
    Comptage des mots du texte contenu dans le fichier «dummy.txt»
    Comptage des mots du roman «Le tour du monde en 80 jours» (J. Verne)
    Comptage des mots du roman «Dracula» (B. Stoker)
    Comptage des mots du roman «Ulysses» (J. Joyce)
    [OK]

Déposez le fichier modifié Occurrence.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. Complétez la classe Median dont l'unique méthode 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, vous devriez obtenir le résultat suivant :

    Testing median: [OK]

Déposez le fichier Median.java :

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


Une solution vous est proposée.