Algorithmes et Structures de Données

ième(supprimer(l, k), i) = ième(l, i+1)

⇒

1 ≤ k ≤ longueur(l) + 1 & 1 ≤ i < k

ième(insérer(l, k, e), i) = ième(l, i)

⇒

1 ≤ k ≤ longueur(l) + 1 & k = i

ième(insérer(l, k, e), i) = e

1 ≤ k ≤ longueur(l) + 1 & k < i ≤ longueur(l) + 1

⇒

⇒

ième(insérer(l, k, e), i) = ième(l, i - 1)

⇒

ADT Liste Récursive

Type Liste

Utilise Entier, Elément, Place

Opérations

Liste_vide : → Liste

fin : Liste → Liste

cons : Elément X Liste → Liste

premier : Liste → Elément

tète : Liste → Place

succ : Place → Place

contenu : Place → Elément

Pré-Conditions

(avec l : Liste, e : Elément)

tête(l) est défini ssi l ≠ Liste_vide()

fin(l) est défini ssi l ≠ Liste_vide()

premier(l) est défini ssi l ≠ Liste_vide()

Axiomes

(avec l : Liste, e : Elément, k : Entier)

premier(cons(e, l)) = e

fin(cons(e, l)) = l

longueur(Liste_vide()) = 0

longueur(cons(e,l)) ≡

longueur(l) + 1

ADT Pile

Type Pile

Utilise Entier, Elément

Opérations

Pile_vide: → Pile

Est_vide: Pile → booléen

empiler: Pile, élément → Pile

dépiler: Pile → File

sommet: Pile → élément

Pré-Conditions

(avec p : Pile, e : Elément)

dépiler(p) est définie ssi Est_vide(p)=faux

sommet(p) est définie ssi Est_vide(p)=faux

Axiomes

(avec p : Pile, e : Elément)

dépiler(empiler(p,e)) = p

sommet(empiler(p,e)) = e

Est_vide(Pile_vide()) = vrai

Est_vide(empiler(p,e)) = faux

ADT File

Type File

Utilise Entier, Elément

Opérations

File_vide: → File

Est_vide: File → Booléen

enfiler: File, Elément → File

défiler: File → File

sommet: File → Elément

Pré-Conditions

(avec p : File, e : Elément)

défiler(f) est définie ssi Est_vide(f) = faux

permier(f) est définie ssi Est_vide(f) = faux

Axiomes

(avec f : File, e : Elément)

défiler(enfiler(f,e)) = p

sommet(enfiler(f,e)) = e

Est_vide(File_vide()) = vrai

Est_vide(enfiler(f,e)) = faux

ADT Arbre Binaire

Type Arbre Binaire

Utilise Elément, Noeud

Opérations

Arbre_vide: → Arbre Binaire

Est_vide: Arbre Binaire → Booléen

<- , - , - ,> : Nœud x Arbre Binaire x Arbre Binaire → Arbre Binaire

racine: Arbre Binaire → Nœud

gauche : Arbre Binaire → Arbre Binaire

droit : Arbre Binaire → Arbre Binaire

contenu : Nœud → Elément

Exercices

Listes

1) Les formulations des types abstraits (ADT) Liste Itérative et Liste Récursive sont en fait

équivalentes, donc :

a. Exprimer premier, fin, et cons en fonction de ième, insérer et supprimer

b. Exprimer ième, insérer, supprimer, et longueur en fonction de premier, fin, et cons

2) Donner un algorithme récursif pour chacun des opérations suivantes de Liste Iterative :

longueur, ième, insérer, supprimer.

3)

Implémenter chacun les opérations nouvelles suivantes pour le type abstrait Liste Itérative

basé sur la représentation chainée :

a. Concaténation de deux listes l1 et l2; le résultat est stocké dans une nouvelle liste l3.

La signature de cette opération est donc :

concat: Liste x Liste  Liste

b. Chercher la dernière occurrence d’un élément donné et retourner sa place dans la

liste (0 s’il n’est pas dans la liste). La signature de cette opération est donc :

rechercher: Liste x Elément Entier

c.

Inverser une liste, c’est-à-dire le premier élément devient le dernier, le second

élément devient l’avant-dernier, etc.

inverser: Liste  Liste

La signature de cette opération est donc :

d. Trier les éléments d’une liste. On suppose que Elément est un type article qui

contient un champ key de type réel. Les éléments doivent être triés selon la valeur

de ce champ.

4) Modifier la représentation contigue du type abstrait Liste Itérative en utilisant un tableau

dynamique (à la place du tableau statique), ensuite implémenter toutes ses opérations en se

basant sur cette nouvelle représentation.

5) Modifier la représentation chainée du type abstrait Liste Itérative en utilisant une chaine

double-enchainée, ensuite implémenter toutes ses opérations basé sur cette nouvelle

représentation.

6) Modifier la représentation chainée du type abstrait Liste Itérative en utilisant une chaine

circulaire, ensuite implémenter toutes ses opérations en se basant sur cette nouvelle

représentation.

Piles

1) En utilisant les procédures et fonctions de manipulation du type Pile, écrire une procédure qui

enlève le ième élément d’une pile et laisse les autres éléments inchangés. La signature de cette

opération est donc : Procédure Enlever(p : Pile, i : Entier  p : Pile)

2) Lorsqu'on utilise un éditeur de texte, on dispose d'une touche qui permet d'effacer le caractère

que l'on vient de frapper (par exemple "BackSpace"). Notons '#' ce caractère.

Une autre touche permet de tout effacer jusqu'au début de la ligne. Notons '%' ce caractère.

On suppose aussi que la fin d'une ligne sera indiquée par la touche '$'.

Exemple :

"Jem# m'euh%Je m'#euh## suit#s trop#mp&#é$"

sera lu comme

"Je me suis trompé"

Ecrire un algorithme qui permette de lire une ligne de texte avec ce mécanisme en utilisant une

Pile. On écrira deux procédures une procédure LireLigne(P) et une procédure EcrireLigne(P).

On supposera que l'on ne saisit qu'une seule ligne de texte, de longueur quelconque.

Files

1) Fusionner deux files ordonnées d’entiers pour obtenir une file ordonnée d’entiers.

2) Les coefficients d’un polynôme et les exposants sont stockes dans une file. Ecrire un algorithme

Evaluer_polynome pour évaluer un polynôme, étant donné une file f contenant le polynôme et

une valeur x de type réel. On suppose que l’expression du plus haut degré ne dépasse pas 10.

Remarque importante : Toute manipulation d’une file doit passer par les opérations du type

abstrait File (c.a.d on ne doit pas manipuler une file par d’autres opérations qu’on a pas défini dans le

type abstrait File).

Arbres Binaires

5/

Evaluation d'expressions arithmétiques

Arbres Binaires de Recherche