Exercices des chapitres 9 10 et 11 Sommaire
Ecrire une procédure qui supprime un élément d'une liste chaînée à une position donnée. Page 3. DVD-MIAGE. Exercices. Algorithmique. Exercices ch. 9 10
Langage C : énoncé et corrigé des exercices IUP GéniE
chaine + D E C ALA G E ;. /* S i l a l ettre pointée est min u sc ul e et apr's ' z ... 3 - Affi c h age récursi f d 'une pile implémentée en liste c h a î née.
Talib24
1.4 LISTE CHAINEE. Le premier exercice est corrigé. Exercice 33 Ecrire un programme qui gère les listes chainées. Pour cela vous créerez un type de structure
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.
Liste chaˆınée dindividus [pn02] - Exercice
Aide simple. Elle crée un Noeud puis met `a jour les liens selon que la liste est vide ou non. Page 9. Unisciel algoprog – Liste chaınée d'individus [pn02] May
Exercices avec Solutions
Si Non FDF(G) Alors Ecrire(F0) Fsi ;. Fait ;. Fermer(G) ; Fermer(F) ;. Fin ;. Page 65. Les Listes Chainées. Exercices Corrigés d'Algorithmique – 1ére Année MI
LIFAPSD : Algorithmique Programmation et Structures de données
L'objectif de ce TP est d'écrire une nouvelle implémentation de liste chaînée c. Créez un fichier Makefile et écrivez-y les lignes nécessaires pour compiler ...
LISTES CHAINEES
Exercice 9. 1. Proposer le code de la fonction insereDerniereCellule(L nC) qui permet d'insérer une cellule à la fin de la liste ainsi que le code de la
serie TD3-ProgII-SMI4-1819
Exercice 1. Le but de cet exercice est d'implémenter en C une pile de nombres entiers sous forme de liste chaînée (on parlera de pile chaînée). Pour cela
Langage C : énoncé et corrigé des exercices IUP GéniE
Exercice 20 Déc l arer et initia l iser deux ta bl eaux de caract è res (c T ab 1 et c T ab 2 ) . Puis : 1. Ecrire une f onction l on g ueur-chaine 1 q ui
Talib24
1.4 LISTE CHAINEE. Le premier exercice est corrigé. Exercice 33 Ecrire un programme qui gère les listes chainées. Pour cela vous créerez un type.
Exercices des chapitres 9 10 et 11 Sommaire
Ecrire une procédure qui supprime un élément d'une liste chaînée à une position donnée. Page 3. DVD-MIAGE. Exercices. Algorithmique. Exercices ch. 9 10
Exercice 1 : Tableau dynamique et liste chaînée (8 points)
12 janv. 2018 Question 1.1 : Traduire cette procédure en C++. void mystere (const TableauDynamique & tab int n
Liste chaˆ?née dindividus [pn02] - Exercice
C++ - Liste chaˆ?née d'individus (Solution). Mots-Clés Gestion dynamique de mémoire Liste
TD n 9 - Correction
Liste debut. 3 suivant. 1 suivant. 2 null. Exercice 1 Listes simplement chainées. 1. Dans la classe Liste écrire une méthode void affiche() permettant
Algo vol.2 - Sujets.pdf
12 oct. 2004 La plupart des exercices consistent à écrire une fonction implémentant un ... La manipulation de listes chaînées (simplement et doublement).
1 Manipulation de listes chaînées en C
9 nov. 2020 Une liste chaînée permet de gérer un collection ordonnée de données de ... Exercice 1 Écrire une fonction dont l'en-tête est. Liste cons(int ...
Exercices avec Solutions
Les Listes Chainées . EXERCICE 1. Ecrire un algorithme qui demande un nombre à l'utilisateur puis calcule et affiche le carré de ce nombre.
Table des matières
Tester dans un programme. Exercice 9. Ecrire une fonction qui permet de fusionner deux listes chainées. La fusion se fait en alternant un élément d'une
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.Element e=debut;
//on avance i-2 fois for (int k=0; kElement tmp2=e.suivant;
// on veut maintenant ins´erer entre les ´el´ements // tmp1 et tmp2. //on cr´e´e le nouvel ´el´ementElementD nouveau=new ElementD();
nouveau.valeur=i; // on refait les chainages nouveau.suivant=tmp2; nouveau.precedant=tmp1; tmp2.precedant=nouveau; tmp1.suivant=nouveau; 11quotesdbs_dbs17.pdfusesText_23[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