8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 1/31
1
Partie 2:
Les structures de données
1
Chapitre3:
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 2/31
2
A: Les piles
1/ Définition:La pile est une liste ordonnée d’éléments danslaquelle on ne peut introduire ou enlever unélément qu'à une extrémité. Cette extrémité estappelée tête de pile ou sommet de pile .
Toutes les opérations sont effectuées sur lamême extrémité =>LIFO.
E m
p i l e r : a j o u t
à l a t ê t e
E
B
D
F
A
B
C
D
E
F
d é p i l e r : r e t r a i t
à l a t ê t e
Bout fermé
Ex: Dans un navigateur, une pile sert à mémoriser les pagesWeb visitées. L'adresse de chaque nouvelle page visitée est
empilée. L'utilisateur dépile en cliquant le bouton« pageprécédente ». Idem pour annuler dernier frappe…
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 3/31
3
Il n’y a pas de limite au nombre d’éléments qu’on peutempiler pour une implémentation par liste chaînée.Par contre, on ne peut dépiler d’une pile vide.
EX: Utiliser une fonction PileVide(p) qui retourne VRAI sila pile est vide sinon FAUX.
A/ Les piles
Une pile est une liste pour laquelle on peut : • Ajouter un élément au début
= empiler l'élément = le mettre au sommet de la pile==> fonction PUSH
• Supprimer un élément du début= dépiler l' élément = l'enlever du sommet
==> fonction POP• tester si la pile est vide,… etc
2/ Opérations courantes: Empiler, Dépiler.
MAIS à laquelle on ne peut: • Ni ajouter un élément à la fin; ni au milieu;
• Ni supprimer un élément à la fin; ni du au milieu.
!
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 4/31
4
On procède par une succession de dépilement/empilement …
7
6
54
3
2
1
6
54
3
2
1
54
3
2
1
4
3
2
1
64
3
2
1
7
64
3
2
1
Dépiler Dépiler Dépiler Empiler Empiler
Ex: Suppression de l'entier 5 d'une pile d'entiers
3/ Insertion/suppression d'un élément à la fin/milieu
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 5/31
5
4/ Implémentation d'une pile
Une pile est une liste + Une liste s'implémente de 2 façons=> 2 façons pour la pile aussi
Une représentation par un tableau :
• Stockage contigüe dans la mémoire• taille maximale définie d'avance. • Une variable supplémentaire pour stocker l'indice du sommet, …
Une représentation par liste chaînée :• taille de la pile peut être modifiée• Le maillon possède un lien vers l'élément précédent,• Un pointeur sur le premier élément désigne la pile et représente le
sommet de cette pile
• Une pile vide est représentée par le pointeur NULL , …
Structure mapile{type1 nomvariable1;type2 nomvariable2; …. structure mapile *précédent ; } ;
Maillontypique
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 6/31
6
5/ Ex. d'opérations courantes sur les piles
Fonction Argument(s) Retour
Pilevide : teste si une pile est vide Pile Booléen
sommet: permet de consulter l'élémentsitué au sommet! n'a pas de sens si pile vide
Pile Elément
empiler :ajoute un élément dans la pile
Pile ,Elément
Pile
dépiler :enlève l'élément situé au sommet.
! n'a pas de sens si pile vide
Pile Pile
•Elément peut être un entier, une chaîne, une structure, …. selon ladéfinition du maillon qui constitue la pile•Les algorithmes sont des exemples, et ne sont pas uniques.•Ils sont à adapter au modèle de structure énnoncé dans vos exercices
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 7/317
6/ Consulter le sommet d'une pile
Algorithme fonction sommetE: structure maillon * mapileS: entier R-----------------------------------DébutSi (mapile == NULL)
afficher (rien à afficher!);retourner NULL ;
Sinon
R = mapile->contenu;retourner R;FinSI
Fin
Ex: Ecrire l'algorithmed'une fonction sommet,retournant la valeur dusommet d'une pile d'entiers
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 8/318
7/ Fonction empiler
Principe•Créer un nouvel élément ,
•y mettre les données.•Faire pointer ce nouvel élément sur la pile.•Retourner le pointeur sur ce nouvel élément
Algorithme fonction empiler
E: structure maillon *p, entier xS: structure maillon *p-------------------------------------------Début
structure maillon * nv;nv->contenu=x;
nv->précédent=p;retourner nv;
Fin
Analogue àAjouter en
tête d'uneliste chaînée
Pour un maillon de type:
La fonction empiler serait = >
structure maillon {entier contenu;structure maillon * précédent;
};
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 9/319
8/ Fonction dépiler (avec retour de l'adresse du nv sommet)
Principe•Vérifier que la pile n'est pas vide•Copier le sommet dans unevariable auxiliaire•Faire pointer le pointeurpile sur l'avant dernier élément
•Libérer le sommet
Question: Est-il nécessaire de faire unecopie du sommet (i)?
Algorithme fonction dépilerE: structure maillon *p
S: structure maillon *p-------------------------------------------DébutSi (p=NULL)alors
Afficher("rien à dépiler!");retourner NULL;
sinonstructure maillon * t = p;p=p->precedent;
Libérer(t);retourner p;
FinsiFin
9/ Fonction ViderPile
Déduire l'algorithme d'une fonctionqui permet de vider toute la pile.
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 10/3111
Exercice: Pour une pile d'entiers, traduire en langage c lesfonctions pilevide, sommet, dépiler, empiler.
mapile
10 20
505
struct maillon {int valeur;struct maillon *precedent;
};
typedef structmaillon maillon ;
typedefmaillon *Pile;
NULL
Les (typedef) ne sontpas obligatoires!
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 11/3112
int sommet(Pile p) {
if ( pilevide(p))printf("Erreur: pile vide !");…
elsereturn p->valeur;
}
Pile depiler(Pile p) {
if ( pilevide(p)) {printf("rien à dépiler!\n");return NULL;}
else {maillon * pc = p;p=p->precedent;free(pc);return p;}}
Pile empiler(Pile p, int e) {Cellule * pc;pc=(maillon *)malloc(sizeof(maillon ));pc->valeur=e;pc->suivant=p;return pc; }
int pilevide(Pile p){if (p==NULL)
return 0;else
return 1;}
Des exemple de solutions….
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 12/3113
Ne pas oublier de créer le tout premier pointeur avant d'essayer d'empiler …
// définition du modèle de structure…
//définition des fonctions précédentes…..
main () {Pile mapile = NULL;
mapile = empiler(mapile,50);mapile = empiler(mapile,5);mapile = empiler(mapile,20);
printf("%d est au sommet\n", sommet(mapile));mapile = depiler(mapile);mapile = depiler(mapile);printf("%d est au sommet\n", sommet(mapile));
}
Faut créer"la premiere brique"
Quel est le type de mapile?
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 13/3114
B/ Les files
le premier élément inséré est aussi le premier retiré.Accès FIFO (First In Fist Out).
1/ Définition:Une file est une liste dans laquelle on insère des nouveaux
éléments à la fin (queue) et où on enlève des éléments au début(tête de file).
A EB D FA B C D E F
Enfiler: ajout à la findéfiler : retrait à la tête
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 14/3115
A/ Les piles
Une file est une liste pour laquelle on peut par exemple: • Ajouter un élément à la fin
= enfiler l'élément = le mettre à la fin de la file• Supprimer un élément du début
= défiler l' élément = l'enlever de la tête• Tester si la file est vide, …
2/ex. d'opérations courantes sur les files: Enfiler, défiler
MAIS à laquelle on ne peut:
• Ni ajouter un élément au début;• Ni ajouter un élément au milieu;
• Ni supprimer un élément à la fin;• Ni supprimer un élément au milieu. !
Comme pour les piles, l'insertion/suppression=> une succession
d'opérations défiler/enfiler.
y a-t-il une limite aunombre d’élémentsqu’on peut enfiler/
défiler?
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 15/3116
3/ Implémentation d'une fileUne file est une liste + Une liste s'implémente de 2 façons=> 2 façons pour la file aussi
Une représentation par un tableau
• Les éléments de la file sont rangés dans un tableau• Stockage contigüe sur la mémoire.• Deux entiers représentent les positions de la tête/la queue de la
file
Une représentation par liste chaînée :• Le maillon possède un lien vers l'élément suivant,• Un pointeur tête pointant sur le premier élément désigne la file
et représente la tête de cette file
• Un pointeur queue pointant sur le dernier élément représente laqueue de cette file
3/ Implémentation des files
Il faudra donc:les maillons chaînés + pointeur sur la tête +pointeur sur la queue
Peuvent être groupés dans une structure
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 16/3117
Implémentation d'une file (suite)
Les algorithmes qui suivront sont écrits pour le maillon ci dessous.Les maillons tête et queue sont groupés dans une structure File.
structure maillon {entier contenu;structure maillon * suivant;
};
structure File {structuremaillon *tete;structuremaillon *queue;
} ;File f;
f n'est pas un pointeur On écrira f .tete=... f .queue=…
type File :structure à deux champs(pointeurs de tête et de
queue de file)
N'appartient pas à lafile elle-même,
Faudra mettre à jourles valeurs contenuesdans cette structure à
chaque ajout/retrait
Un maillon contient unélément et un pointeur sur
l'élément suivant, ilconstituera la file
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 17/3118
4/ Ex. d'opérations courantes sur les piles
Fonction Argument(s) Retour
filevide: teste si une file est vide file Booléentête: permet de consulter l'élément situéen tête de file ;! n'a pas de sens si la file vide
file Elément
enfiler : ajoute un élément à la file file , Elément filedéfiler :enlève l'élément situé à la tête.! n'a pas de sens si file vide
file file
Tout comme pour les piles:•Elément peut être un entier, une chaîne, une structure, …. selon ladéfinition du maillon qui constitue la file•Les algorithmes sont des exemples, et ne sont pas uniques.
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 18/3119
Algorithme fonction filevideE: structure File fS: entier.-----------------------------------------------Début
Si (f.tete=NULL) et (f.queue=NULL)alors
retourner 0;Sinon
retourner 1Finsifin
5/ Fonction Créer une file vide 6/ Fonction filevide
Une file est vide est si lesdeux pointeurs tête etQueue sont NULL.
Algorithme fonction creefilevideE: RienS: structure File f-------------------------------------Début
File f; //créef.tete=NULL; //initialise
f.queue=NULL;retourner f;
fin
On ne crée pas les maillons.Seule la structure File
(tête+queue ) est à initialiser
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 19/3120
7/ Fonction enfiler Algorithme fonction enfilerE: structure File f, entier x
S: structure File fDébutstructure maillon * nv; //Créer un nouvel élément ,
nv->contenu=x; //Y mettre les données.
nv->suivant=NULL; //pointer sur NULL puisqu'il devient le dernier.si(filevide(f)) // vide tète=queue=cet élément unique
f.tete=f.queue=nv;Sinon
(f.queue)->suivant=nv; //le dernier devient avant dernier, avant nv
f.queue=nv; //mise à jour: queue est maintenant nv
Finsiretourner f;Fin
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 20/3121
8/ Fonction défiler (avec retour de l'adresse du nv sommet)
Algorithme fonction défilerE: structure File f,S: structure File f
DébutSi (filevide(f)) alors
Afficher("rien à défiler!"); retourner NULL;sinon
Structure maillon * tmp;tmp=f.tete; //on copie la tetef.tete=(f.tete) -> suivant; // la tête est maintenant le second élémentlibérer (tmp);
si (f.tete=NULL) alors// et si ce maillon défilé était le seul dans//cette file?
f.queue=NULL; // faudrait mettre queue à NULL aussifinsiretourner f ; //retourner f puisqu'elle fut modifiée
Finsi; Fin
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 21/3122
•Un arbre est une structure arborescente composée d’éléments appelésnœuds ;
•Chaque nœud est constitué : – d’un champ de donnée ; – d’un ou plusieurs pointeurs vers des nœuds.
•Un arbre est donc une racine et une suite(éventuellement vide) de sous arbres A1, …, An.
•Il existe un unique chemin allant de la racine a n'importe quel nœud del'arborescence.
C/ LES ARBRES
1/ Définition d'un arbre: un arbre est un graphe acyclique orienté
• possédant une unique racine, et•tel que tous les nœuds -sauf la racine- ont un unique parent.
La donnée du pointeur sur le nœud racine défini tout l'arbre , tout commela donnée de l'adresse de la tête d'une liste chaînée définit toute la liste
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 22/3123
2/ Terminologie…
•un noeud interne est un nœud qui a au moins un fils •une feuille d’un arbre est un nœud sans fils ;
dite aussi une extrémité ;•les ancêtres d’un nœud a sont les nœuds qui sont sur le cheminentre la racine (incluse) et a (inclus) ;•les descendants d’un noeud a sont les nœuds qui appartiennent
au sous-arbre de racine a ;
Ex:
Les feuilles de l'arbre à côté sont:
Les nœuds internes sont:
Les ancêtres de 13 sont:
Les ancêtres propres de 13 (càd 13 noninclus) sont:
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 23/3124
•la profondeur d’un nœud est la longueur du chemin allant dela racine à ce nœud
La profondeur de la racine est donc nullela profondeur d’un nœud autre que la racine vaut =1+ la
profondeur de son père;
•Un niveau est un ensemble de nœuds internes ou de feuillessitués à la même profondeur (5 et 20 par ex)
•la hauteur d’un arbre: profondeur maximum des nœuds ;
elle vaut dans cet exemple 4
Un arbre est dit équilibré, si les lessous-arbres gauche et droit ont des
hauteurs qui diffèrent au plus de 1
Longueur désigneles liens et non
pas les nœuds
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 24/31
26
3/ Arbre binaire de recherche (un exemple d'arbres)
Conditions:•les nœuds appartiennent à un ensemble totalement ordonné.
•Binaire => Chaque nœud a au plus 2 nœuds les données contenues dans le sous arbre gauche de tout nœudinterne a sont inférieures ou égales à la donnée contenue dansle nœud a lui même, qui est à son tour inférieure ou égale aux
données contenues dans le sous-arbre droit de a.
2 < 516 <20
5 <10
Fils Gauche < nœud < fils droit
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 25/31
27
Ex: est ce un arbre binaire de recherche?
Fils Gauche < nœud < fils droit
Cet arbre est il binaire?
Si oui, est ce un ABR?
Est il équilibré?
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 26/31
28
4/ Implémentation d'un arbre (ex.)
•Les données ( valeurs contenues dans le nœud ),•Un lien vers chaque nœud fils,
Un arbre vide permet de caractériser les feuilles.
•Les données•Un lien vers le premier nœud fils ( fils gauche généralement ),•Un lien vers le nœud frère ( premier nœud frère sur la droite ).
•Les données•Un lien vers le nœud père, puisque chaque nœud possède UN père.
La structure élémentaire utilisée pour construire l'arbre peut êtrel'une des suivantes:
TAF: Dessiner un schéma illustratif des ces trois exemples
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 27/31
29
Structure noeud{
entier contenu;Structure nœud * fils_gauche;Structure nœud * fils_droit;};
structure nœud * arbre ;
arbre->contenu=2;arbre->fils_gauche->contenu=7;arbre->fils_droit->contenu=5;
arbre->fils_gauche->fils_gauche->contenu=2;arbre->fils_droit->fils_gauche->contenu=8;arbre->fils_gauche->fils_droit->contenu=6;
arbre->fils_droit->fils_droit->contenu=3;
5/ Implémentation d'un arbre (Exemple)
Schématisercet arbre.Est-ce un
ABR?Est un arbreéquilibré?
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 28/31
30
Ecrire une fonctionrécursive taille quicalcule le nombre denœuds d’arbre.
Si l’arbre est vide, lafonction retourne 0.
Si l’arbre contient au moinsun noeud, la fonctionretourne la somme destailles du sous-arbregauche et du sous-arbredroit plus 1
6/ Exemple d'opérations: la Taille de l’arbre
Algorithme fonction taille E: structure nœud * arbre S: entier--------------------------------------
Début structure nœud * t = arbre;
Si(t=NULL) alors Retourner 0
Sinon
retourner 1 +taille(t->fils_gauche)+ tail le(t->fi ls_droit);
Finsi fin
7/ P d' b
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 29/31
31
7/ Parcours d'un arbre
Parcours en largeur
Le parcours en largeur correspond à un parcours par niveau de
nœuds de l'arbre.= > 2-7-5-2-6-9-5-11-4
Le parcours d'un arbre peut se faire de différentes façon.• En largeur
• En profondeura. En préfixeb. En suffixec. En infixe
RMQ: Ces exemples -valables pour un arbre binaire- sont à généraliser au casd'arbres n-aires …
P f d
8/14/2019 Les Piles Files Arbres(1)
http://slidepdf.com/reader/full/les-piles-files-arbres1 30/31
32
Parcours en profondeur
Le parcours en pré ordre, d it aussi en ordre pré fixe.· Lire la racine ;
· parcourir en pré ordre le premier sous- arbre ;…. · parcourir en pré ordre le dernier sous-arbre.
=> 2 7 2 6 5 11 5 9 4 : racine en premier
Le parcours en post ordre, dit aussi en ordre suffixe:· parcourir en le premier sous- arbre ;….. · parcourir en le dernier sous-arbre ;· Lire la racine.
=> 2 5 11 6 7 4 9 5 2 : racine en dernier
Parcours en ordre infixe:
Traiter le fils gauche, le nœud courant , puis le fils droit..=> 2 7 5 6 11 2 5 4 9