TD n 9 - Correction PDF Une liste est donc une

PILES FILES ET LISTES CHAÎNÉES

- top():. Retourne l'objet du dessus de la pile sans le retirer; si la pile est vide

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

Corrigé de lexamen de Structures de données Session Ordinaire

Exercice 1. 1. Quatre exemples de structures de données linéaires : les tableaux les listes chaînées

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.

Langage C : énoncé et corrigé des exercices IUP GéniE

1.2 CHAINES DE CARACTERES . Liste - Entier- > prem=Liste - Entier- > der=Liste - Entier- > co u r = E l ...

Algorithmes et structures de données : TD 8 Corrigé - Tableaux

Algorithmes et structures de données : TD 8 Corrigé. Tableaux dynamiques - Listes linéaires simplement chaınées - Complexité Comparer avec l'exercice ...

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

Questionnaire dexamen+Corrigé - INF1101 Algorithmes et structure

INF1101 --- Examen final +Corrigé--- Automne 1999. Page 7 de 16 La classe LChaindc représente une liste doublement chaînée circulaire avec élément factice.

Solutionnaire pour les exercices sur les listes chaînées et les files

Voici une méthode pour insérer un élément au début d'une liste simplement chaînée. On garde le pointeur de la Tête dans un pointeur temporaire.

Exercices des chapitres 9 10 et 11 Sommaire

On considérera dans les exercices sauf cas contraire une liste chaînée de ce type : Corrigés. Algorithmique. Exercices ch. 9

Exercices des chapitres 9 10 et 11 Sommaire

07-**- Procédure de suppression d'un élément d'une liste chaînée à une position donnée . Corrigés. 01-**- Fonction de comptage dans une liste chaînée .

Algorithmes et structures de données : TD 8 Corrigé - Tableaux

Algorithmes et structures de données : TD 8 Corrigé. Tableaux dynamiques - Listes linéaires simplement cha?nées - Complexité asymptotique. Rappel :.

Langage C : énoncé et corrigé des exercices IUP GéniE

Langage C : énoncé et corrigé des exercices 1.2 CHAINES DE CARACTERES . ... Les exercices 1 à 1 6 20 à 2 5

PSD 2015/2016 Corrigé type série 4- Listes chainées 1 Exercice 1

Corrigé type série 4- Listes chainées Ecrire un sous algorithme qui inverse une liste chaînée dont la tête est tête. Procedure invers (Var tete : P) ;.

Exercices avec Solutions

Les Tableaux (Vecteurs – Matrices) et Chaines de caractères . Les Listes Chainées . ... Exercices Corrigés d'Algorithmique – 1ére Année MI 5. EXERCICE 1.

SUJET + CORRIGE

Liste doublement chainée. 9. Total: 30. Exercice 1 : Mise en bouche. (7 points). (a) (1 point) Deux nombres sont opposés si leur somme est égale `a 0.

Exercices corrigés

Affichez chaque élément d'une liste en utilisant une boucle for. Écrire une fonction compterMotsayant un argument (une chaîne de caractères) er qui.

Corrigé E.D. Algorithmes et Structures de Données n° 2 Thème : Les

Corrigé E.D. Algorithmes et Structures de Données n° 2. Thème : Les Listes. Exercice II.1 Manipulation d'une liste chaînée circulaire r.valeur = d3.

TD n 9 - Correction

Une liste est donc une chaine d'élément (d'o`u le terme liste chainée). Dans toute la suite du TD nous allons travailler avec les 2 classes suivantes :.

TD 7 - Les listes II Structures de données (IF 122) Comme la

Dans une liste doublement chaînée chaque cellule contient à la fois un pointeur vers l'élément suivant (suiv) et un pointeur vers l'élément précédent ( p re c )

Solutionnaire pour les exercices sur les listes chaînées et les files

>Solutionnaire pour les exercices sur les listes chaînées et les filesWebVoici une méthode pour insérer un élément au début d’une liste simplement chaînée On garde le pointeur de la Tête dans un pointeur temporaire On fait ensuite pointer le début de la liste au nouveau nœud à insérer Puis on met le suivant de cet objet au pointeur temporaire gardé Temporaire := Tête Tête := Nouveau Tête

TD : LES LISTES CHAINEES

>TD : LES LISTES CHAINEESWebP a g e 2 4 typedef struct { Etudiant info; struct Classe *suiv; }Classe ; //La fonction Ajout_Etudiant permet d'ajouter un nouvel étudiant dans la tête de la classe

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 : Listequotesdbs_dbs2.pdfusesText_2

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

Universit´e Paris DiderotJAVA

MASS L2Ann´ee 2007-2008

Listes

3suivant1suivant2null

Exercice 1Listes simplement chain´ees

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

Correction :

System.out.println(e.valeur);

Element e=debut;

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

Correction :

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

Correction :

System.out.println(e.valeur);

Liste:

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 :

Element e=debut;

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

Correction :

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

3suivant1suivant2null

3suivant1suivant2null