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] listes chainées - FR
La seconde transforme à l'inverse une liste chainée de nb éléments en un tableau dynamique Faire un programme de test Exercice 3 Ecrire une fonction qui
[PDF] Exercices des chapitres 9, 10 et 11 Sommaire - MIAGE de Nantes
Sommaire Exercices 01-**- Fonction de comptage dans une liste chaînée 07 -**- Procédure de suppression d'un élément d'une liste chaînée à une position donnée http://wwwens uqac ca/~rebaine/8INF805/courslistespilesetfiles pdf
[PDF] GPA665
Ainsi, cette méthode aide à ne pas faire d'accès mémoire incorrect Page 4 Exercice 4 Fonction qui copie entièrement une liste chaînée dans une autre
[PDF] Langage C : énoncé et corrigé des exercices IUP GéniE - LAMSADE
Les exercices 1 à 1 6, 20 à 2 5 , 2 9 à 33, 4 2 à 43 sont corrigés Ecrire une f onction l on g ueur-chaine 1 q ui ad m ette en para mè tre un ta bl eau de caract è res E l ement - Liste pointe s u r l' é l ément s u i v ant de l' é l ément co u rant */
[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] Solutionnaire pour les exercices sur les listes chaînées et les files
On pourrait remplacer les lignes « Effacer le contenu de Courant » et « Mettre Courant à NULL » par « Dépiler (Courant) » Page 2 4 Voici un algorithme récursif
[PDF] 31 Listes Chaînées - Département EEA
23 oct 2019 · 1 4 Chaînes de Caractères en Langage C 6 1 5 Conversion 3 2 Listes Doublement Chaînées 13 B 9 Exercice de base sur les pointeurs (attaché au PDF) ou
[PDF] TD 7 - Les listes II Structures de données (IF 122) Comme la - IRIF
Comme la semaine dernière, on s'intéresse à des listes chaînées d'objets de Exercice 7 (TD/TP) Écrire une méthode triInsert qui trie par insertion une liste de
[PDF] TD 3 et 4 Listes - IGM
Nous nous proposons à travers ce TD d'étudier la liste, un modèle de données classique qui permet de décrire une La liste chaînée est une structure de données que l'on retrouve fréquemment en informatique Exercice 1 En quoi les
[PDF] les liste chainée en c pdf
[PDF] les liste chainée en java
[PDF] les loisirs fiche pédagogique
[PDF] les loisirs vocabulaire
[PDF] les mille et une nuits
[PDF] les mille et une nuits pdf
[PDF] les montagnes de la france
[PDF] les mots d'un ' langage soutenu en français
[PDF] les multiplexeurs exercices corrigés
[PDF] les musées de paris
[PDF] les nombres complexes cours 2 bac
[PDF] les nombres complexes cours bac
[PDF] les nombres complexes cours bac pc
[PDF] les nombres complexes cours cm2
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.