TP
G n ricit & collections en JAVA
Objectifs
Sinitier au concept de g n ricit .
Apprendre manipuler
g n riques
les collections
Temps allou
Outils
4h30
Eclipse
La g n ricit
Exercice 1 : Pile g n rique en repr sentation cha n e
Vous disposez du code suivant repr sentant limpl mentation dune pile
// interface Pile
interface Pile {
public boolean estVide()~
public Object dernier()~
public void depiler()~
public void empiler(Object o)~
}
/* Le recours une interface peut sexpliquer par la possibilit apr s
de faire
le choix de la repr sentation physique voulue (chain e ou contig e) */
// Repr sentation chain e : listes de Object
class Noeud {
Object info~
Noeud suivant~
}
// impl menter les Pile avec des listes (repr sentation chain e)
class PileListe implements Pile{
private Noeud sommet~
public PileListe(){
sommet = null~
}
public boolean estVide(){
return (sommet == null)~
}
public Object dernier(){
return sommet.info~
}
public void empiler(Object o){
Noeud n = new Noeud()~
n.info = o~
n.suivant = sommet~
sommet = n~
}
public void depiler(){
sommet = sommet.suivant~
1
Publicité
}
}
class TestPile{
public static void main(String[]args){
PileListe p = new PileListe()~
for(int i = 0 ~ i < 10 ~ i++)
p.empiler(new Integer(i))~
while(!p.estVide()){
System.out.println((Integer) p.dernier())~
p.depiler()~
}
// Tester aussi p.empiler("L'entier " + i)~
/* System.out.println((Integer) p.dernier())~
=> Erreur l'ex cution de casting
=> System.out.println(p.dernier())~
=> Ouverture sur les exceptions */
/* Remplacer while(!p.estVide()) par for(int i = 0 ~ i < 20 ~ i++)
=> Erreur l'ex cution lors du d pilement d'une pile vide
=> Ouverture sur les exceptions mais surtout sur la g n ricit */
}
}
Donnez la version g n rique de limpl mentation de la pile
Les collections g n riques
2
Les types g n riques servent particuli rement dans les collections de donn es. Dans
lAPI Java, la plupart de ces structures de donn es de bases sont d j impl ment es
dans le package java.util, qui fournit une petite hi rarchie.
Notez que toutes ces interfaces sont d finies de mani re g n rique : il faut donc
sp cifier le type quelles utilisent lorsquon les impl mente et quon les manipule.
Linterface de base est Collection qui d signe nimporte quel regroupement
dobjets.
o Un Set est une collection qui nautorise pas la duplication dun
l ment.
o Une List est un ensemble d l ments ordonn s, cest dire une
s quence d l ments.
o Une Queue est une collection qui conserve un ordre de manipulation,
selon une logique FIFO. Elle est particuli rement utile pour traiter des
suites d v nements.
Une Map nest pas une collection : cest un objet qui associe des clefs ` des
valeurs. Une table de hachage par exemple, sera vue comme une Map. Dautre
part les Set et les Map peuvent tre Sorted, cest ` dire que leurs l ments
seront constamment ordonn s et que cet ordre sera conserv m me apr s
des op rations dajout ou de retrait d l ments.
3
Quelques impl mentations de ces interfaces sont fournies, et dont le nom indique la
m thode utilis e pour leur impl mentation: ArrayList, LinkedList, HashSet,
HashMap, ...
Dautre part la classe Collections (avec un s) regroupe un grand nombre de
fonctions statiques utiles aux manipulations de ces structures de donn es.
Enfin, il faut noter que linterface Collection tend linterface Iterable. Cette derni re
demande juste quun objet puisse obtenir un Iterator avec la m thode iterator(). Un
Publicité
Iterator doit impl menter les m thodes hasNext() et next() (optionnellement
remove()). Le gros avantage dun objet Iterable est quon peut le manipuler avec la
construction foreach :
List<Integer> l = new LinkedList<Integer>();
/ do something with l /
for (Integer i : l) {
/ do something with i /
}
Exercice 2 : Pile et collection g n rique (ArrayList)
Vous disposez maintenant du code suivant repr sentant limpl mentation contigu
dune pile.
public class PileTab {
int pos~
int [] tab~
public PileTab(){
tab = new int[4]~
this.pos = 0~
}
public void add(int e){
if (this.pos == tab.length){
System.out.println("Ajout impossible de "+e)~
//System.exit( 1)~
}
else {
4
tab = e~
this.pos ++~
}
}
public int remove(){
int elem = tab ~
this.pos ~
return elem~
}
public boolean estVide(){
return this.pos == 0~
}
public int size(){
return this.pos~
}
public void affiche(){
for (int i = 0~ i<this.pos~ i++){
System.out.println(this.tab )~
}
}
public int getSommet(){
return this.tab ~
}
}
Question :
1) Testez cette classe dans votre programme principal
2) Transformer ce code en un type param tr PileGen de fa on ce quon
Publicité
puisse ajouter nimporte quel type dobjet dans la pile. Le champ tableau
devient un champ ArrayList <T> dont la taille est extensible, donc vous
navez plus besoin du champ pos, vous pouvez utiliser directement la
m thode size() de lArrayList. Dans la m thode daffichage, vous utiliserez la
m thode classique de parcours.
3) Testez La classe PileGen dans votre programme principal en
Exercice 3 : Pile et collection g n rique (LinkedList)
Voici une interface d finissant un type abstrait "Pile de <A>" avec les fonctionnalit s
classiques d'une pile :
public interface IPile <A> {
boolean estVide()~
void empile(A a)~
A depile()~ // retourne l' l ment en sommet de pile et d pile
int nbElements()~
5
A sommet()~ // retourne le sommet de pile mais ne le d pile pas
}
1) crivez une classe g n rique CPile qui impl mente l'interface IPile. Vous
stockerez les l ments de la pile dans une liste cha n e (instance de
java.util.LinkedList, voir en annexe quelques m thodes publiques de cette
classe).
2) crivez un petit programme qui cr e et manipule des piles en instanciant la
classe g n rique de diff rentes fa ons (par exemple pile de String, pile de
Integer, &).
Exercice 4 : Compr hension de larchitecture des t ches
Larchitecture des t ches est donn e la figure 1 o le d tail des classes
TacheElementaire et TacheComplexe nest pas donn .
Une t che est caract ris e par un nom et un co t. Une t che est soit une t che
l mentaire, soit une t che complexe qui est alors compos e de soust ches.
Il est ainsi possible dajouter une soust che une t che complexe, ajouter(Tache)
ou de supprimer une soust che, supprimer(Tache). Le co t dune t che complexe
est la somme des co ts des t ches qui la composent.
1) crire en Java la classe TacheElementaire qui est une r alisation de
linterface Tache.
6
public interface Tache {
/* Obtenir le nom de la t che. /
String getNom()~
/* Obtenir le co t de la t che. /
int getCout()~
}
D finition dune t che complexe
Nous nous int ressons maintenant la classe TacheComplexe, en particulier sa
relation avec linterface Tache. Une t che complexe est compos e dun nombre
quelconque de t ches. On d cide dutiliser linterface java.util.Collection pour
stocker les soust ches. On lutilisera bien entendu dans sa version g n rique.
Comme on souhaite pouvoir parcourir toutes les soust ches dune t che complexe,
la classe TacheComplexe r alise linterface java.lang.Iterable.
2) Indiquer quel est le principal int r t de la g n ricit .
3) crire en Java la classe TacheComplexe.
4) crire un programme qui cr e des t ches et des t ches complexes et qui
affiche leur co t total.
Publicité
Exercice 5 : Collection g n rique HashMap
Lobjectif de cet exercice est de r aliser un annuaire pour m moriser des num ros
de t l phone et des adresses. Chaque entr e est repr sent e par une fiche
plusieurs champs : un nom, un num ro et une adresse.
Travail faire :
1) crire la classe Fiche. Celleci devra avoir un constructeur 3 param tres
pour initialiser lensemble des attributs de la classe et 1 constructeur 1
param tre auquel on passera le nom (Les autres champs sont initialises par
d faut a 1 (num ro) et null (adresse)).
La classe Annuaire comporte une table associative (HashMap<String , Fiche>) qui
sera faite dassociations (un nom , une Fiche).
7
2) crire la classe Annuaire dont le constructeur permettra la cr ation dune
table associative de type HashMap. Celle ci doit comporter les m thodes
suivantes :
a. public void getNBconttacts() qui retourne le nombre de contacts
dans lannuaire
b. public void addContact(Fiche f)qui ajoute un contact partir
dune fiche pass en param tre.
c. public void addContact(String s, int n, String a) qui ajoute
un contat a partir dun nom, dun num ro et dune adresse pass s en
param tre.
d. public void addContact(String s) qui ajoute un contact partir
du nom pass en parameter (num ro et adresse par d faut)
e. public int getnumero(String name)qui retourne le num ro de
telephone associ au nom pass en param tre
f. public void affiche()qui affiche les contacts dans lannuaire.
3) R alisez une classe Test afin dy tester toutes vos m thodes
Annexe
8
la classe LinkedList
java.util
Class LinkedList<E>
java.lang.Object
java.util.AbstractCollection<E>
java.util.AbstractList<E>
java.util.AbstractSequentialList<E>
java.util.LinkedList<E>
Type Parameters :
E the type of elements held in this collection
Quelques m thodes publiques :
LinkedList() Constructs an empty list.
void addFirst(E o) Inserts the given element at the beginning of this list.
E element() Retrieves, but does not remove, the head (first element) of this
list.
Throws : NoSuchElementException if this queue is empty.
E getFirst() Returns the first element in this list.
Throws:
NoSuchElementException if this list is empty.
9