Structures de données et de fichiers
|
Enoncé 1 : Listes linéaires chaînées - Piles Corrigé 1
Exercice 1 : listes unidirectionnelles
Ecrire l'algorithme itératif qui inverse une liste L unidirectionnelle.
Exercice 2 : listes bilatérales
Rappeler le modèle de liste bilatérale. Ecrire les algorithmes suivants :
(a) Rechercher l'élément x s'il existe.
(b) Supprimer l'élément x s'il existe.
Exercice 3 : les piles à éléments de longueur variable
Soit à implémenter une pile o� chaque élément renferme un nombre variable d'entiers.
(a) Définir le modèle.
(b) Implémenter le modèle avec la représentation mixte(contigu� et chaînée) suivante :
TYPE T = STRUCTURE
Nbr : ENTIER { Nombre d'éléments }
Tab : TABLEAU[1..N] DE ENTIER
FIN
TYPE Maillon = STRUCTURE
Valeur : T
Adr : POINTEUR ( Maillon )
FIN
VAR P : POINTEUR (Maillon) { P constitue la pile }
Donc, la pile est représentée par une liste linéaire P de maillons. Chaque maillon renferme le couple (Nbr, Tab[1..N]) o� seuls les Nbr premiers éléments de Tab sont significatifs.
(c) Proposer une représentation chaînée possible puis traduire les opérations du modèle dans cette représentation.
(d) Traduire les opérations du modèle dans la représentation suivante :
TYPE Pile = STRUCTURE
Som : ENTIER { nombre d'éléments }
Eléments : TABLEAU[1..N] DE ENTIER
FIN
Un élément de la pile occupe alors ( n+2 ) éléments du tableau. Dans la première position, on range le nombre d'éléments et dans la seconde position l'indice du sommet précédent.
Exercice 4 : le modèle 2-piles.
Il est possible de garder deux piles dans un même tableau T(1..N) , si l'une pousse de la position 1 du tableau et l'autre de la position N. Définir le modèle 2-piles et l'implémenter.
* * * * *
