2 null Exercice 1 Listes simplement chainées 1 Dans la classe Liste, écrire une méthode void affiche() permettant d'afficher les valeurs de tous les éléments de
Previous PDF | Next PDF |
[PDF] Liste chaˆınée dindividus [pn02] - Exercice - Unisciel
C++ - Liste chaˆınée d'individus (Solution) Mots-Clés Gestion La classe Element définit le type des éléments dans la liste chaınée Définissez une classe
[PDF] listes chainées - FR
Que la liste chainée soit bâtie avec des pointeurs ou des entiers, c'est Le fait d' insérer plutôt qu'ajouter un élément dans la liste suppose un classement
[PDF] Listes chaînées
classe pour la liste elle-même, qui contient une référence vers son premier élément class Liste { ElementListe premier; } Si premier est à null, la liste est vide
[PDF] • Listes chaînées • Piles
Une liste chaînée est une suite de couples formés Listes chaînées en Java class class Pol { int coeff, degre; Pol suivant; Pol(int c, int d, Pol p) { coeff = c;
[PDF] Plan Langage C • struct • Definition récursive de type • sizeof
X, Petite classe 5 Plan Langage C • struct • Definition récursive de type • sizeof • malloc • Listes chaînées Algorithmique • Listes, piles, files
[PDF] liste - LIFAP3 – Algorithmique et programmation avancée
Une liste est une structure de données à accès séquentiel liste = < > (liste vide) Une liste chaînée représente un ensemble d'éléments class Liste {
[PDF] Tableau dynamique et liste chaînée - CNRS
12 jan 2018 · Travaillez au brouillon d'abord de sorte à rendre une copie propre – nous ne Exercice 1 : Tableau dynamique et liste chaînée (8 points) Pour rappel, la classe Arbre a une seule donnée membre : adRacine de type
[PDF] TD n 9 - Correction
2 null Exercice 1 Listes simplement chainées 1 Dans la classe Liste, écrire une méthode void affiche() permettant d'afficher les valeurs de tous les éléments de
[PDF] TD Listes - Formations en Informatique de Lille
Liste Vide 1 5 10 34 (c) Liste chainée à 4 éléments, de type Integer, l' interface List de java, les classes ≪Maillon≫ et ≪ListeChainée≫ seront paramétrées
pdf Chapitre 2 Les listes chainées
03/04/2020 Pr B BOUDA: Structures de données en C 7 Définition d’une liste simplement chainée Une liste simplement chaînée peut être vu comme: Une structure de contrôle (Liste) Une structure d’éléments enchaînés (Element) Listes simplement chaînées Introduction Définition d’une liste simplement chainée
[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 composite materials ppt
[PDF] classification of haloalkanes and haloarenes class 12
Universit´e Paris DiderotJAVA
MASS L2Ann´ee 2007-2008
TD n ◦9 - CorrectionListes
Une liste est une structure permettant de stocker des ´el´ements, un peu `a la mani`ere d"untableau. 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 debut3suivant1suivant2null
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 instructionsElement 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(); 2attention, 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. 35.´Ecrire une m´ethodevoid supprDebut()supprimant le premier ´el´ement de la liste.
Correction :
Repartons de l"exemple donn´e au d´ebut :
Liste debut3suivant1suivant2null
Supprimer le premier ´el´ement revient juste `a modifier le chainage des ´el´ements de la liste, pour
aboutir au sch´ema suivant : Liste debut3suivant1suivant2null
L"ancien premier ´el´ement n"est alors plus accessible, etjavava le supprimer tout seul : Liste debut1suivant2null
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...). 46.´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 debut0suivant
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 debut0suivant
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 debut0suivant
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. 5Il 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 a0suivant
3suivant1suivant2null
et maintenant, on peut ´ecrire : e.suivant=a; Liste debut a0suivant
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 debut0suivant
3suivant1suivant2null
et maintenant debut=e; Liste debut0suivant
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. 77.´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; kIl 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. 8Exercice 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; 92.´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; 103.´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.