1 LES PILES ET FILES. 2 Les Piles et Files Définition Ce sont des structures de données...

1

LES PILES ET FILES

2

Les Piles et Files

Définition Ce sont des structures de données ordonnées, mais qui ne permettent

l'accès qu'à une seule donnée. Les piles (stack LIFO : Last In First Out) correspondent à une pile

d'assiettes : on prend toujours l'élément supérieur, le dernier empilé. Les files (on dit aussi queues) (stack FIFO: First In First Out)

correspondent aux files d'attente : on prend toujours le premier élément, donc le plus ancien.

Elles servent à mémoriser des choses en attente de traitement. Elles sont souvent associées à des algorithmes récursifs.

3

Les Piles et Files

Définition

Il n'y a pas de structures spécifiques prévues dans les langages, il faut donc les créer.

Pour les piles on utilisera : un tableau unidimensionnel (statique ou dynamique) en cas de piles de

hauteur maximale prévisible (la hauteur de la pile est mémorisée par une variable entière).

une liste en cas de longueur très variable (on a un surcoût en mémoire d'autant de liens (pointeurs) que d'éléments empilés).

4

Les Piles et Files

Définition

Pour les files on utilise: un tableau (on nécessite deux variables : la position du premier et

celle du dernier). La gestion est alors un peu plus complexe que pour les piles, puisque le suivant de la fin du tableau est le début du tableau.

une liste (aussi simple que pour une pile).

5

Les Piles et Files

Fonctions de base

Pour les piles sont l'empilage et le dépilage, pour les files l'enfilage et le défilage. Dans les deux cas: on a une fonction d'initialisation, et une fonction indiquant si la

pile (file) est vide. Les fonctions de base dépendent de la méthode réelle de mise en oeuvre (tableau,

liste,...). On va pouvoir modifier facilement le type d'implantation en mémoire sans réécrire les

programmes.

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

Tableau statique – en cas de piles de hauteur maximale prévisible (la hauteur de la pile est mémorisée par une variable entière).

#define TypeEl float

35

#include <stdio.h> 1/3#define MAX_PILE 20typedef float TypeEl;typedef struct{ TypeEL v[MAX_PILE]; int top;} Stack;

void init(Stack *S){ S->top = 0;}

int full(Stack *S){ return (S->top >= MAX_PILE);}

La définition de type

Initialisation de la pile

Indication si la pile est pleine

Tableau statique

36

void push(Stack *S, TypeEL val) 2/3{ if(!full(S))

{ S->v[ S->top ] = val; /* òu bien: S->v[ (S->top)++ ] = val; */ (S->top)++;}

elseprintf("La pile est pleine\n");

}

float pop(Stack *S){ (S->top)--; return (S->v[S->top]);/* òu bien : return (S->v[--(S->top)]); */}

Empiler

Dépiler

Tableau statique

37

void MyStackPrint(Stack *S) 3/3 {

int i; if (S->top == 0)

printf("La pile est vide.\n"); else {

printf("Le contenu de la pile: "); for (i=0;i<S->top;i++) {

printf("%.3g ",S->v[i]); } printf("\n");

} }

Affichage du contenu

Tableau statique

38

l'implantation des fonctions de base est similaire

#include <stdio.h> 1/3#include <conio.h>#include <ctype.h>#define dim_file 100#define composante float

static composante file[dim_file];static int bas,sommet,taille;void init_file(void){ bas=sommet=taille=0;}

int file_vide(void){ return(taille==0); }

Tableau statique

static pour empêcher l'accès direct extérieur

Initialisation de la file

Indication si la file est vide

39

l'implantation des fonctions de base est similaire int enfiler(composante x) 2/3{ if(taille<dim_file)

{ file[sommet]=x; if(sommet < dim_file-1) { sommet++; taille++;return(0); }}

else{ puts("file saturee");return(1); }

}

Tableau statique

Enfiler

40

l'implantation des fonctions de base est similaire composante defiler(void) 3/3{ composante x;

if (taille>0) { x=file[bas];

bas++;taille--;

return(x); } else {puts("file vide");return(0);}}

Tableau statique

Défiler

41

Tableau dynamique

#define TypeEl float

42

typedef int stack_data; 1/4struct stack_rec { stack_data data; struct stack_rec *next; };struct stack_rec *top=NULL;

void stack_init(){ top=NULL;}int stack_empty(){ if (top==NULL) return(1); else return(0);}

La définition de type

Initialisation de la pile

Indication si la pile est pleine

Tableau dynamique

43

void stack_push(stack_data d) 2/4{ struct stack_rec *temp; temp = (struct stack_rec *)malloc(sizeof(struct stack_rec)); temp->data=d; temp->next=top; top=temp;}

EmpilerTableau dynamique

44

stack_data stack_pop() 3/4{

struct stack_rec *temp; stack_data d=0; if (top!=NULL) {

d=top->data; temp=top; top=top->next; free(temp);

} return(d);

}

Dépiler

Tableau dynamique

45

void Print() 4/4{ struct stack_rec *temp=top; stack_data d=0; while (temp!=NULL)

{d=temp->data; printf("\n%d",d); temp=temp->next;

}}void stack_clear(){ stack_data x; while (!stack_empty()) x=stack_pop();}

Affichage du contenu

Tableau dynamique

Vider une pile

46

Piles: implantation dans une liste chaînée

Liste chaînée - en cas de longueur très variable (ne pas oublier que dans ce cas on a un surcoût en mémoire d'autant de liens (pointeurs) que d'éléments empilés).

47

48

49

50

51

52

53

54

55

56

57

58

59

60

#define TypeEl int

typedef struct element{

TypeEl val;struct element* prec;

}elem;

typedef struct{

elem * sommet;} maPile;

typedef maPile * Pile;

Les définitions de type

61

62

Pile empilerPile (Pile p, TypeEl x, int *err){ /* objectif:empiler un élément dans une pile */

/* La pile p est correctement initialisée */elem * nouveau;if((nouveau =(elem*) malloc(sizeof(elem)))!= NULL){ *err=OK;

nouveau->val = x;nouveau->prec = NULL; if (p->sommet !=NULL){ nouveau->prec = p->sommet;

p->sommet = nouveau; } else{ p->sommet = nouveau;}return p;

}else{ *err=PAM;

return p;}

}

63

64

Pile depilerPile(Pile p, int *err){ /* objectif: enlever l'élément au sommet de la pile

méthode: détacher et libérer l'élément au sommethypothèse: la pile est correctement initialisée et non vide */

elem * top;if (p->sommet != NULL){ top = p->sommet;

p->sommet = p->sommet->prec;top->prec=NULL;free(top);*err=OK;return p;

}

*err=PV;return p;

}

65

66

TypeEl sommetPile (Pile p, int *err){ /* objectif: retourner l'élément au sommet de la pile

méthode: consultation de l'élément au sommet de la pilehypothèse: la pile est correctement initialisée et non vide */

if(p->sommet!=NULL){

*err=OK;return p->sommet->val ;

}

else{

*err=PV;return 0; /* une valeur quelconque*/

}

}

67

68

BOOL pileVide (Pile p, int *err){ /* objectif: vérifier si la pile est vide

méthode: tester le sommet de la pile sortie: VRAI si la pile est vide, FAUX sinon résultat: la pile est inchangée et *err=OKhypothèse: la pile est correctement initialisée */

*err=OK;

if(p->sommet == NULL) return VRAI;else return FAUX;

}

69

70

BOOL appartientPile (Pile p, TypeEl x, int *err){ /* objectif: trouver l'appartenance de x dans une pile

sortie: p est inchangée avec *err=OKrésultat: VRAI si x appartient à p et FAUX sinonhypothèse: la pile est correctement initialisée */

*err=OK;while(p->sommet != NULL){

if( p->sommet -> val == x )return VRAI;

p->sommet = p->sommet->prec;

} return FAUX;}

71

72

Pile remplacerPile (Pile p, TypeEl x, TypeEl y, int *err){ /* objectif: le premier x trouvé est remplacé par y

sortie: la pile mise à jour ou bien la pile non changéehypothèse: la pile est correctement initialisée */*err=OK;

while(p->sommet != NULL){

if( p->sommet -> val == x ){p->sommet->val = y; return p;}

p->sommet = p->sommet->prec;

} return p;}

73

Piles: Exemples d’application

Vérification de parenthèses Évaluation des expressions arithmétiques

La notation polonaise - Traduisons en notation polonaise, étape par étape, les expressions suivantes écrites en notation infixée.

(A + B) * C = [+AB]*C = *+ABCA + (B * C) = A + [*BC] = +A*BC

On traduit d'abord l'expression en notation suffixée On l'évalue par la suite

Récursivité Programmation – parcours de graphes