Bonjour,
J'ai réussi à faire la premiere question sachant que je ne suis pas sur si c'est bon ou pas .
pour le reste j'ai trop galéré du coup j'aimerai avoir votre point de vue s'il vous plaît.
Merci d'avance ^^
Voici deux exemples de l’utilité de cette structure :
- Associer des numéros de carte d’étudiant à des noms d’étudiants :
<(3459, « Jean Dupont »), (8491, « Marie Martin »),…>
(C = Integer, V = String)
- Associer des numéros d’IP à des infos d’utilisateurs :
<(« 238.124.22.53 », « Thomas Dubois, 11 rue des graviers, Rennes »),
(« 74.125.136.99 », « Google, 1600 amphiteatre parkway, MountainView »),…>
On vous fournit une classe abstraite (c.a.d. que vous ne pouvez que la sous-classer)
TableCorrespondance :
public abstract class TableCorrespondance<C extends Comparable<C>, V> {
/**
* Crée une association entre une clé et une valeur.
* Si une association (cle, autre valeur) existe déjà, elle est écrasée.
*
* @param cle Clé de l'association, supposée non nulle
* @param valeur Valeur de l'association, supposée non nulle
*/
public abstract void associe(C cle, V valeur) ;
/**
* Supprime l'association (cle, valeur) si elle existe, sinon ne fait
rien
*
* @param cle
*/
public abstract void supprime(C cle) ;
/**
* Renvoie la valeur associée à la clé indiquée.
*
* @param cle Clé à rechercher
* @return Valeur associée à cle, null sinon
*/
public abstract V get(C cle) ;
}
1. Ecrivez une sous-classe TCList de TableCorrespondance. TCList doit implémenter
toute les méthodes de TableCorrespondance en exploitant un ArrayList des
collections standard Java. Vous pourrez, pour vous aider, créer une classe interne Paire ou
exploiter la classe correspondante fournie par Java (à vous de la trouver).
2. Fournissez des jeux de test pour les différentes méthodes de TCList<String, Integer>.
3. Ecrivez maintenant une sous-classe TCTree de TableCorrespondance. TCTree doit
implémenter toute les méthodes de TableCorrespondance en utilisant un arbre binaire
de recherche (vu en cours) sur les clés. Vous devez implémenter vous-même l’arbre binaire
de recherche, et ne pas recourir aux collections standard Java.
NB : la suppression vous demandera un peu de réflexion. La page wikipedia sur les arbres
binaires de recherche vous donnera la méthode à suivre, à vous de l’implémenter.
4. Fournissez des jeux de test pour les différentes méthodes de TCTree<String, Integer>.
5. Comparez la performance de vos deux implémentations de tables de correspondances :
- Mesurez le temps de 1 000 000 d’insertions de couples de nombres aléatoires
compris entre 1 et 1 000 000.
- Mesurez ensuite le temps moyen d’accès (= get) pour 1 000 000 d’accès à des valeurs
aléatoires entre 1 et 1 000 000.
- Reportez les valeurs et discutez les résultats
- Les expériences précédentes utilisent N = 1 000 000 d’accès/insertions. Si vous en
avez le temps, essayez avec d’autres valeurs de N, et dessinez vos résultats dans des
courbes avec les valeurs de N en abscisse et les valeurs de temps (temps d’insertion,
temps moyen d’accès) en ordonnée. Commentez ces courbes.
