[PDF] TD n 9 - Correction Une liste est donc une

View - Download TD n 9 - Correction

Previous PDF

Next PDF

Universit´e Paris DiderotJAVA

MASS L2Ann´ee 2007-2008

TD n ◦9 - Correction

Listes

Une liste est une structure permettant de stocker des ´el´ements, un peu `a la mani`ere d"un

tableau. Une liste est compos´ee d"´el´ements, un ´el´ement ´etant constitu´ee d"une valeur (valeur que

l"on souhaite stocker) et d"une r´ef´erence vers un autre ´el´ement. Une liste est donc une chaine

d"´el´ement (d"o`u le terme liste chain´ee). Dans toute la suite du TD, nous allons travailler avec les 2 classes suivantes : class Liste{ public Element debut; public Liste() debut=null; class Element{ public int valeur; public Element suivant; Par exemple, la liste3-1-2sera represent´ee de la fa¸con suivante : Liste debut

3suivant1suivant2null

Exercice 1Listes simplement chain´ees

1. Dans la classeListe, ´ecrire une m´ethodevoid affiche()permettant d"afficher les valeurs

de tous les ´el´ements de la liste.

Correction :

Rep´erez bien le sch´ema utilis´e pour parcourir la liste. void affiche() if (debut==null) return; //la liste est vide... 1 Element e=debut;System.out.println(e.valeur);while(e != null){ e=e.suivant;

System.out.println(e.valeur);

les instructions

Element e=debut;

while(e != null) e=e.suivant; sont le noyau central de toutes les m´ethodes it´eratives permettant de parcourir une liste.

2.´Ecrire une m´ethodeboolean estVide().

Correction :

Il s"agit simplement de tester si la liste contient des ´el´ements ou pas : boolean estVide() return (debut==null)

3. Dans la classeElement, ´ecrire une m´ethode r´ecursive permettant d"afficher l"´el´ement cou-

rant et tous ses successeurs.

Correction :

pour afficher l"´el´ement courant et tous ses successeurs, ilfaut : (a) afficher l"´el´ement courant.

(b) afficher l"´el´ement suivant et tous ses successeurs (s"il y a un ´el´ement suivant.)

on a donc la m´ethode r´ecursive suivante, dans la classeElement. void afficheRec()

System.out.println(e.valeur);

if (suivant != null) suivant.afficheRec();

Muni de cette m´ethode, nous pouvons ´ecrire d"une autre fa¸con la m´ethode d"affichage de la classe

Liste:

void affiche() if (debut==null) return; debut.afficheRec(); 2

attention, il faut tout de mˆeme bien v´erifier quedebutn"est pas null, sinon, on aurait une erreur

`a l"ex´ecution en appelantdebut.afficheRec();.

Question subsidiaire, que se passerait-il si on rempla¸caitafficheRec()par la m´ethode suivante :

void afficheRec2() if (suivant != null) suivant.afficheRec();

System.out.println(e.valeur);

4. Dans la classeListe, ´ecrire une m´ethodeint longueur()renvoyant la longeur de la liste.

Correction :

Nous pouvons faire ¸ca it´erativement :

int longueur() if (debut==null) return 0; //la liste est vide...

Element e=debut;

int c=1; while(e != null) e=e.suivant; c++; return c;

ou it´erativement, en remarquant que la longueur d"une liste, c"est 1 plus la longueur de la liste

partant de l"´el´ement suivant. //dans la classe Element int longueurRec() if (suivant==null) return 1; return 1+suivant.longueurRec(); //dans la classe Liste int longueur2() if (begin==null) return 0; return debut.longueurRec(); Dans toutes les questions suivantes, nous travaillerons maintenant dans la classeListe. 3

5.´Ecrire une m´ethodevoid supprDebut()supprimant le premier ´el´ement de la liste.

Correction :

Repartons de l"exemple donn´e au d´ebut :

Liste debut

3suivant1suivant2null

Supprimer le premier ´el´ement revient juste `a modifier le chainage des ´el´ements de la liste, pour

aboutir au sch´ema suivant : Liste debut

3suivant1suivant2null

L"ancien premier ´el´ement n"est alors plus accessible, etjavava le supprimer tout seul : Liste debut

1suivant2null

et on a bien la liste de d´epart dont on a supprim´e le premier ´el´ement.

D"un point de vue code, on doit donc modifier la flˆeche correspondant `adebutdans l"objet de type

Liste, et la faire pointer vers le second ´el´ement (c"est-`a-diredebut.suivant). En rajoutant un test

au cas o`u la liste est vide, cel`a donne : void supprDebut() if (debut != null) debut=debut.suivant;

L"op´eration de suppression au d´ebut d"une liste s"effectue en temps constant, alors qu"elle serait

lin´eaire dans le cas d"un tableau (il faut cr´eer un tableauplus petit, recopier le tableau courant

dedans sans le premier ´el´ement...). 4

6.´Ecrire une m´ethodevoid ajoutDebut(int i)ajoutant un ´el´ement au d´ebut de la liste

de valeuri.

Correction :

Ici, si l"on rajoute 0 par exemple, on veut aboutir au sch´emasuivant : Liste debut

0suivant

3suivant1suivant2null

Il y a donc 2 choses `a faire :

(a) cr´eer un nouvelElement, contenant la bonne valeur.

Element e=new Element();

e.valeur=i; Liste debut

0suivant

3suivant1suivant2null

(b) refaire les chainages correctement. Sur sch´ema il y a deux flˆeches `a mettre en place : il faut

quedebutr´ef´erence le nouveau premier ´el´emente, et quee.suivantr´ef´erence l"ancien premier

´el´ement. Allons-y :

debut=e; Liste debut

0suivant

3suivant1suivant2null

et l`a, c"est le drame : nous n"avons plus de moyen d"acc´eder`a l"ancien premier ´el´ement (celui

qui contient 3). On voudrait ´ecriree.suivant=quelquechose, mais il n"y a plus moyen que quelquechoser´ef´erence le bonElement. 5

Il y a deux solutions pour rem´edier `a ¸ca :- On peut garder une r´ef´erence vers l"ancien premier ´el´ement, pout pouvoir y acc´eder au

moment venu :

Element a=debut;

debut=e; Liste debut a

0suivant

3suivant1suivant2null

et maintenant, on peut ´ecrire : e.suivant=a; Liste debut a

0suivant

3suivant1suivant2null

La m´ethode est alors la suivante :

void ajoutDebut(int i)

Element e=new Element();

e.valeur=i;

Element a=debut;

debut=e; e.suivant=a; 6 - On peut aussi bouger les flˆeches dans l"autre ordre : e.suivant=debut; Liste debut

0suivant

3suivant1suivant2null

et maintenant debut=e; Liste debut

0suivant

3suivant1suivant2null

void ajoutDebut(int i)

Element e=new Element();

e.valeur=i; e.suivant=debut; debut=e;

Dans tous les cas, l"op´eration d"insertion au d´ebut d"uneliste s"effectue en temps constant, alors

qu"elle serait lin´eaire dans le cas d"un tableau. 7

7.´Ecrire une m´ethodeint val(int i)qui renvoie la valeur du i`eme´el´ement de la liste.

Quelle est sa complexit´e? Quels sont les avantages et inconv´enients de l"utilisation d"une liste par rapport `a un tableau?

Correction :

L"acc´es direct au i`eme´el´ement n"est pas possible : il faut passer par tous les ´el´ements pr´ec´edents.

On peut faire ¸ca it´erativement :

int val(int i) if (i > longueur) return -1; //il faudrait renvoyer une erreur...

Element e=debut;

//on avance i-1 fois for (int k=0; k longueur) return -1; //il faudrait renvoyer une erreur... return debut.valRec(i); L"acc´es `a un ´el´ement quelconque est donc plus couteux que dans le cas d"un tableau.

Il y donc des cas o`u on aura int´erˆet `a utiliser listes plutˆot que tableaux (beaucoup d"ajouts

d"´el´ements, peu d"acc`es al´eatoires), et des cas o`u ce sera l"inverse. 8

Exercice 2Listes doublement chain´ees

Ins´erer et supprimer `a la fin d"une liste simplement chain´ee est une op´eration couteuse et

peu naturelle. Nous allons donc de nouvelles classes permettant de d´ecrire des listes doublement chain´ees : class ListeD{ public ElementD debut; public ElementD fin; class ElementD{ public int valeur; public ElementD suivant; public ElementD precedent; 1. ´Ecrire une m´ethodevoid supprFin()supprimant le dernier ´el´ement de la liste.

Correction :Je ne vais pas d´etailler autant la correction pour cette partie. Tracer les sch´emas

correspondant `a ces algorithmes, c"est un tr`es bon exercice (il y a maintenant deux flˆeches partant

de chaqueElement). Il y a un double chainage, donc il faut ˆetre beaucoup plus attentif `a ce qu"on

fait. void supprFin() //liste vide if (fin == null) return; //liste r´eduite `a un seul ´el´ement if (fin == debut) debut=null; fin=null; return; fin.precedant.suivant=null; //fin.precedant est l"avant-dernier ´el´ement fin=fin.precedant; 9

2.´Ecrire une m´ethodevoid ajoutFin(int i)ajoutant un ´el´ement `a la fin de la liste de

valeuri.

Correction :

void ajoutFin(int i)

ElementD e=new ElementD();

e.valeur=i; //liste vide if (fin == null) debut=e; fin=e; e.suivant=null; e.precedant=null; return; e.precedant=fin; fin.precedant.suivant=e; fin=e; 10

3.´Ecrire une m´ethodevoid inserer(int i, int v)qui ins`ere un ´el´ement de valeurven

i `emeposition.

Correction :

Un peu plus p´enible `a ´ecrire tr`es proprement, il y a pleinde cas `a v´erifier... Je vais supposer que

nous avons ´ecrit des m´ethodes pour calculer la longueur etins´erer au d´ebut. void inserer(int i, int v) // cas particuliers if (i<=1) {ajoutDebut(v); return;} if (i>longueur()) {ajoutFin(v); return;} //cas g´en´eral : on commence par r´ecup´erer les (i-1)`eme // et i`eme ´el´ements, c`ad ceux auxquels il va falloir toucher // aux fl^eches.

Element e=debut;

//on avance i-2 fois for (int k=0; kElement tmp1=e;

Element tmp2=e.suivant;

// on veut maintenant ins´erer entre les ´el´ements // tmp1 et tmp2. //on cr´e´e le nouvel ´el´ement

ElementD nouveau=new ElementD();

nouveau.valeur=i; // on refait les chainages nouveau.suivant=tmp2; nouveau.precedant=tmp1; tmp2.precedant=nouveau; tmp1.suivant=nouveau; 11quotesdbs_dbs14.pdfusesText_20

[PDF] classement des langage de programmation 2019

[PDF] classement des langage de programmation 2020

[PDF] classement indice de développement humain 2019

[PDF] classement pisa 2019 belgique

[PDF] classement revues cnrs 2019 pdf

[PDF] classement ville france qualité de vie

[PDF] classes and object in java

[PDF] classes objects and methods in java

[PDF] classic cocktail recipes with pictures pdf

[PDF] classic wow use trinket macro

[PDF] classification and nomenclature of organic compounds pdf

[PDF] classification des bactéries microbiologie pdf

[PDF] classification handbook opm

[PDF] classification of haloalkanes and haloarenes class 12

[PDF] clear ie cache windows 7