Cours sur les Piles et les Files
Cours sur les Piles et les Files
Computer Science - Data Structures · lab
Voir tous les documents en programmationTous les cours en programmation
Fiche de révisionGuide de TP
Rédigée à partir de ce document, puis vérifiée avant publication.
Ce laboratoire porte sur les structures de données avancées que sont les piles et les files. Il permet d’apprendre leur définition, leur mode de fonctionnement, ainsi que leur implémentation en mémoire, tant en représentation contiguë qu’en représentation chaînée. Le travail pratique propose de manipuler ces structures, de comprendre leurs opérations fondamentales, et de comparer leurs usages. Pour réaliser ce TP, il est nécessaire de maîtriser les bases du langage C, notamment la gestion des tableaux, des pointeurs, et la manipulation dynamique de la mémoire.
Dans cette étape, vous allez créer une pile utilisant un tableau de taille fixe MAX (ici 100). La pile est gérée par un indice sommet qui indique la première case libre du tableau.
Commencez par définir la structure :
#define MAX 100
typedef struct pile {
Type_element Tableau[MAX];
int sommet; // indice de la première case libre, entre 0 et MAX
} Pile;
Implémentez ensuite les opérations suivantes :
Pile CreerPileVide() {
Pile P;
P.sommet = 0;
return P;
}
int EstPileVide(Pile P) {
return (P.sommet == 0);
}
int EstPilePleine(Pile P) {
return (P.sommet == MAX);
}
Type_element tete(Pile P) {
if (!EstPileVide(P))
return P.Tableau[P.sommet - 1];
else
printf("Erreur : Pile vide\n");
}
Pile Empiler(Pile P, Type_element e) {
if (!EstPilePleine(P)) {
P.Tableau[P.sommet] = e;
P.sommet++;
} else {
printf("Erreur : Pile pleine\n");
}
return P;
}
Pile Depiler(Pile P) {
if (!EstPileVide(P)) {
P.sommet--;
} else {
printf("Erreur : Pile vide\n");
}
return P;
}
Cette étape vous permet de comprendre la gestion d’une pile dans un tableau fixe, ainsi que les risques liés aux débordements (pile pleine) et sous-débordements (pile vide).
Cette étape consiste à implémenter la pile sous forme d’une liste chaînée, où chaque cellule contient une valeur et un pointeur vers l’élément suivant. Le sommet de la pile est représenté par un pointeur vers la première cellule.
Définissez la structure :
typedef struct cellule {
Type_element Val;
struct cellule *succ;
} Cellule;
typedef Cellule* Pile;
Implémentez les opérations :
Pile CreerPileVide() {
Pile P = NULL;
return P;
}
int EstPileVide(Pile P) {
return (P == NULL);
}
Type_element tete(Pile P) {
if (!EstPileVide(P))
return P->Val;
else
printf("Erreur : Pile vide\n");
}
Pile Empiler(Pile P, Type_element e) {
Cellule *NC = (Cellule *)malloc(sizeof(Cellule));
if (NC) {
NC->Val = e;
NC->succ = P;
P = NC;
} else {
printf("Erreur : mémoire insuffisante\n");
}
return P;
}
Pile Depiler(Pile P) {
if (!EstPileVide(P)) {
Cellule *NC = P;
P = P->succ;
free(NC);
} else {
printf("Erreur : Pile vide\n");
}
return P;
}
Cette représentation permet d’éviter les problèmes de taille fixe, mais nécessite une gestion dynamique de la mémoire.
La file est une structure où l’ajout se fait en fin (queue) et la suppression en début (tête). Pour éviter les décalages coûteux, la représentation circulaire utilise un tableau et les indices sont gérés modulo MAX.
Définissez la structure :
#define MAX 100
typedef struct file {
Type_element Tab[MAX];
int Tete;
int Queue;
} File;
Implémentez les opérations :
File CreerFileVide() {
File f;
f.Tete = 0;
f.Queue = 0;
return f;
}
int EstFileVide(File f) {
return (f.Tete == f.Queue);
}
int EstFilePleine(File f) {
return ((f.Queue + 1) % MAX == f.Tete);
}
Type_element LireFile(File f) {
if (!EstFileVide(f))
return f.Tab[f.Tete];
else
printf("Erreur : File vide\n");
}
File Enfiler(Type_element e, File f) {
if (!EstFilePleine(f)) {
f.Tab[f.Queue] = e;
f.Queue = (f.Queue + 1) % MAX;
} else {
printf("Erreur : File pleine\n");
}
return f;
}
File Defiler(File f) {
if (!EstFileVide(f)) {
f.Tete = (f.Tete + 1) % MAX;
} else {
printf("Erreur : File vide\n");
}
return f;
}
Cette méthode optimise l’utilisation de l’espace mémoire et évite les décalages.
La file est ici implémentée par une liste chaînée avec deux pointeurs : Tête (début) et Queue (fin). Cela facilite l’ajout en fin sans parcourir toute la liste.
Définissez la structure :
typedef struct cellule {
Type_element valeur;
struct cellule *suivant;
} Cellule;
typedef struct file {
Cellule *Tete;
Cellule *Queue;
} File;
Implémentez les opérations :
File CreerFileVide() {
File f;
f.Tete = NULL;
f.Queue = NULL;
return f;
}
int EstFileVide(File f) {
return (f.Tete == NULL);
}
Type_element LireFile(File f) {
if (!EstFileVide(f))
return f.Tete->valeur;
else
printf("Erreur : File vide\n");
}
File Enfiler(Type_element e, File f) {
Cellule *NC = (Cellule *)malloc(sizeof(Cellule));
if (NC) {
NC->valeur = e;
NC->suivant = NULL;
if (!EstFileVide(f)) {
f.Queue->suivant = NC;
} else {
f.Tete = NC;
}
f.Queue = NC;
} else {
printf("Erreur : mémoire insuffisante\n");
}
return f;
}
File Defiler(File f) {
if (!EstFileVide(f)) {
Cellule *NC = f.Tete;
f.Tete = f.Tete->suivant;
free(NC);
if (f.Tete == NULL) {
f.Queue = NULL;
}
} else {
printf("Erreur : File vide\n");
}
return f;
}
Cette représentation est très flexible, permettant une taille dynamique, mais nécessite une gestion attentive de la mémoire.