Cours 3: Le type Pile.
Voici la signature du type abstrait Pile .
Pile creer_pile();
Element_pile sommet_pile(Pile p);
Pile empiler_pile(Pile p, Element_pile e);
Pile depiler_pile(Pile p);
unsigned int est_vide_pile(Pile p);
// p: Pile; e: Element_pile;
// préconditions
// depiler_pile(p) est-défini-ssi est_vide_pile(p) == 0
// sommet_pile(p) est-défini-ssi est_vide_pile(p) == 0
// axiomes
// depiler_pile(empiler_pile(p, e)) == p
// sommet_pile(empiler_pile(p, e)) == e
// est_vide_pile(creer_pile()) != 0
// est_vide_pile(empiler(p, e)) == 0
Les préconditions imposent qu'on ne puisse ni dépiler, ni consulter
le sommet d'une pile vide.
Le premier axiome indique qu'en empilant puis dépilant, on laisse
la pile inchangée (l'élément dépilé est donc celui qui vient d'être empilé).
Le second axiome montre qu'après avoir empilé un élément e , on le trouve
au sommet de la pile.
Le troisième axiome affirme qu'une nouvelle pile est vide à sa création.
Le quatrième axiome précise qu'une pile n'est plus vide après un empilement.
Une pile est-elle une variété de liste?
Dans l'affirmative, on dérive la définition du type Pile de celui du type
Liste.
L'empilement et le dépilement peuvent se concevoir comme des accès à la tête
de liste: empiler écrit en tête ( inserer_liste(l, 0, e) ) alors que
dépiler supprime la tête ( supprimer_liste(l, 0) ).
Cela montre qu'une pile est une liste dans laquelle on accède en tête.
L'empilement peut encore s'exprimer comme une écriture en queue
( inserer_liste(l, longueur_liste(l), e) et le dépilement comme la
suppression de l'élément de queue ( supprimer_liste(l, longueur_liste(l) - 1) .
Cela montre qu'une pile est aussi une liste dans laquelle on accède en queue.
Voici une implémentation de pile en table (la taille de la pile est fixée
à sa création), exprimée à partir de la spécification d'une liste en table.
// fichier pile_en_table.c
#include <stdio.h>
#include "pile_en_table.h"
#include "liste_en_table.h"
Pile creer_pile() {
Liste l;
l = creer_liste();
return (Pile)l;
}
Element_pile sommet_pile(Pile p) {
// précondition est_vide_pile(p) == 0
if (est_vide_pile(p)) {
fprintf(stderr, "sommet_pile: pile vide\n");
exit(1);
}
return lire_liste((Liste)p, longueur_liste((Liste)p) - 1);
}
Pile empiler_pile(Pile p, Element_pile e) {
unsigned int longueur;
longueur = longueur_liste((Liste)p);
Liste l;
if (longueur == TAILLE_LISTE) {
fprintf(stderr, "empiler_pile: pile pleine\n");
exit(1);
}
l = inserer_liste((Liste)p, longueur, e);
return (Pile)l;
}
Pile depiler_pile(Pile p) {
// précondition est_vide_pile(p) == 0
Liste l;
if (est_vide_pile(p)) {
fprintf(stderr, "depiler_pile: pile vide\n");
exit(1);
}
l = supprimer_liste((Liste)p, longueur_liste((Liste)p) - 1);
return (Pile)l;
}
unsigned int est_vide_pile(Pile p) {
return (!longueur_liste((Liste)p));
}
Le code ci-dessus fait apparaître que nous avons privilégié des accès en
queue de liste pour effectuer empilement et dépilement. Cela vient de
l'implémentation des listes en table. Dans l'implémentation du cours
précédent, une suppression en tête de liste se traduit par un tassement
du tableau et une insertion en tête provoque un décalage du tableau d'un cran à droite.
En revanche, une suppression en queue n'effectue qu'une mise à jour de la longueur
de la liste et une insertion en queue ne fait qu'écrire l'élément à sa place.
Voici le fichier pile_en_table.h
// fichier pile_en_table.h
#include "pile.h"
#include "liste_en_table.h"
#define TAILLE_PILE TAILLE_LISTE
Voici le fichier pile.h .
// fichier pile.h
#include "pile_def.h"
#include "element_pile_def.h"
Pile creer_pile();
Element_pile sommet_pile(Pile p);
Pile empiler_pile(Pile p, Element_pile e);
Pile depiler_pile(Pile p);
unsigned int est_vide_pile(Pile p);
// p: Pile; e: Element_pile;
// préconditions
// depiler_pile(p) est-défini-ssi est_vide_pile(p) == 0
// sommet_pile(p) est-défini-ssi est_vide_pile(p) == 0
// axiomes
// depiler_pile(empiler_pile(p, e)) == p
// sommet_pile(empiler_pile(p, e)) == e
// est_vide_pile(creer_pile()) != 0
// est_vide_pile(empiler(p, e)) == 0
Voici le fichier pile_def.h
// fichier pile_def.h
typedef void *Pile;
Voici le fichier main_table.c qui met en œuvre le type
pile en table.
On peut remarquer la façon dont on s'assure que la pile n'est pas pleine
avant de tenter un empilement. La constante TAILLE_PILE est définie et
rendue visible par le fichier pile_en_table.h . Comme on ne
dispose d'aucune fonction donnant le nombre d'éléments empilés (cela ne fait
pas partie de notre spécification d'une pile), on tient à jour
un compteur de la profondeur de pile.
// fichier main_table.c
#include <stdio.h>
#include "element_int_pile.h"
#include "pile_en_table.h"
#define TAILLE_REP 128
main() {
Pile p;
Element_pile e;
int i;
unsigned int profondeur;
char rep[TAILLE_REP];
p = creer_pile();
profondeur = 0;
do {
afficher_menu();
fgets(rep, TAILLE_REP, stdin);
if (rep[0] == 'q') exit(0);
switch (rep[0]) {
case 'd':
if (est_vide_pile(p)) printf("pile vide\n");
else {
p = depiler_pile(p);
profondeur--;
}
break;
case 'e':
if (profondeur == TAILLE_PILE) printf("pile pleine\n");
else {
sscanf(&rep[1], "%d", &i);
e = creer_element_pile();
e = ecrire_element_pile(e, i);
p = empiler_pile(p, e);
profondeur++;
}
break;
case 's':
if (est_vide_pile(p)) printf("pile vide\n");
else printf("%d\n", lire_element_pile(sommet_pile(p)));
break;
case 'v':
if (est_vide_pile(p)) printf("vrai\n");
else printf("faux\n");
break;
}
} while (1);
}
afficher_menu() {
printf("menu:\n");
printf(" (q)uitter\n");
printf(" (e)mpiler (i)\n");
printf(" (d)épiler\n");
printf(" la pile est-elle (v)ide?\n");
printf(" afficher le (s)ommet de pile\n");
}
Voici le makefile.
# fichier make_pile_en_table
main_table: main_table.o liste_en_table.o pile_en_table.o element_int_pile.o
cc -o main_table main_table.o liste_en_table.o pile_en_table.o element_int_pile.o
main_table.o: main_table.c pile_en_table.h pile.h pile_def.h element_pile_def.h element_int_pile.h
cc -c main_table.c
pile_en_table.o: pile_en_table.c pile_en_table.h pile.h pile_def.h liste_en_table.h liste.h liste_def.h element_pile_def.h
cc -c pile_en_table.c
liste_en_table.o: liste_en_table.c liste.h liste_en_table.h liste_def.h element_pile_def.h
cc -c liste_en_table.c
element_int_pile.o: element_int_pile.c element_int_pile.h element_pile_def.h
cc -c element_int_pile.c
Voici maintenant une implémentation de pile en liste chaînée.
// fichier pile_en_chaine.c
#include <stdio.h>
#include "pile.h"
#include "liste.h"
Pile creer_pile() {
Liste l;
l = creer_liste();
return (Pile)l;
}
Element_pile sommet_pile(Pile p) {
// précondition est_vide_pile(p) == 0
if (est_vide_pile(p)) {
fprintf(stderr, "sommet_pile: pile vide\n");
exit(1);
}
return lire_liste((Liste)p, 0);
}
Pile empiler_pile(Pile p, Element_pile e) {
Liste l;
l = inserer_liste((Liste)p, 0, e);
return (Pile)l;
}
Pile depiler_pile(Pile p) {
// précondition est_vide_pile(p) == 0
Liste l;
if (est_vide_pile(p)) {
fprintf(stderr, "depiler_pile: pile vide\n");
exit(1);
}
l = supprimer_liste((Liste)p, 0);
return (Pile)l;
}
unsigned int est_vide_pile(Pile p) {
return (!longueur_liste((Liste)p));
}
On remarquera que cette fois on a opté pour des accès
en tête de liste (on insère et on supprime au rang 0).
En effet, des accès en queue auraient provoqué un parcours de la liste.
Voici le fichier main_chaine.c de mise en œuvre.
// fichier main_chaine.c
#include <stdio.h>
#include "element_int_pile.h"
#include "pile.h"
#define TAILLE_REP 128
main() {
Pile p;
Element_pile e;
int i;
char rep[TAILLE_REP];
p = creer_pile();
do {
afficher_menu();
fgets(rep, TAILLE_REP, stdin);
if (rep[0] == 'q') exit(0);
switch (rep[0]) {
case 'd':
if (est_vide_pile(p)) printf("pile vide\n");
else p = depiler_pile(p);
break;
case 'e':
sscanf(&rep[1], "%d", &i);
e = creer_element_pile();
e = ecrire_element_pile(e, i);
p = empiler_pile(p, e);
break;
case 's':
if (est_vide_pile(p)) printf("pile vide\n");
else printf("%d\n", lire_element_pile(sommet_pile(p)));
break;
case 'v':
if (est_vide_pile(p)) printf("vrai\n");
else printf("faux\n");
break;
}
} while (1);
}
afficher_menu() {
printf("menu:\n");
printf(" (q)uitter\n");
printf(" (e)mpiler (i)\n");
printf(" (d)épiler\n");
printf(" la pile est-elle (v)ide?\n");
printf(" afficher le (s)ommet de pile\n");
}
Voici le fichier make_pile_en_chaine .
# fichier make_pile_en_chaine
main_chaine: main_chaine.o liste_en_chaine.o pile_en_chaine.o element_int_pile.o
cc -o main_chaine main_chaine.o liste_en_chaine.o pile_en_chaine.o element_int_pile.o
main_chaine.o: main_chaine.c liste.h liste_def.h pile.h pile_def.h element_pile_def.h element_int_pile.h
cc -c main_chaine.c
pile_en_chaine.o: pile_en_chaine.c liste.h liste_def.h pile.h pile_def.h element_pile_def.h
cc -c pile_en_chaine.c
liste_en_chaine.o: liste_en_chaine.c liste.h liste_def.h element_pile_def.h
cc -c liste_en_chaine.c
element_int_pile.o: element_int_pile.c element_int_pile.h element_pile_def.h
cc -c element_int_pile.c