cours - partie 3
8
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
8
pages
Catalan
Documents
Le téléchargement nécessite un accès à la bibliothèque YouScribe Tout savoir sur nos offres
Plan Piles > Définition Algorithme Une pile est une structure de données telle que : Types abstraits de données L’ajout d’un élément se fait au sommet Pointeursde la pile. Listes La suppression d’un élément se fait également au sommet de la pile.Piles Files C’est une structure de données en LIFO « Last In, First out » ou « dernier entré, Trispremier sorti ». Complexité01/09/2006 1 01/09/2006 2Piles > Représentation en mémoire Piles > Opérations Créer_pile : ⇒ PileAdresses Empiler : Pile ⊗ Element⇒ Pile Dépiler : Pile ⇒ PileSommet500 Dupond Sommet : Pile ⇒ Element Toto100 Pile_vide : Pile ⇒ Booléen1000Titi350Paul /01/09/2006 3 01/09/2006 41Piles > Algorithme avec allocation Piles > Algorithme avec allocation dynamique > Représentation en dynamique >Structure de données mémoireEnregistrement Place{Elt : Pointeur[Element];PlaceSuivant : Pointeur[Place];Sommet}/Enregistrement Pile {Sommet : Pointeur[Place];}Element01/09/2006 5 01/09/2006 6Piles > Algorithme avec allocation Piles > Algorithme avec allocation dynamique > Créer_pile dynamique > Créer_pile Créer_pile : ⇒ PileFonction créer_pile : Pile;{Resultat : Pile;/SommetPile->Sommet = null;}01/09/2006 7 01/09/2006 82Piles > Algorithme avec Piles > Algorithme avec allocation dynamique > Empiler allocation dynamique > Empiler Empiler : Pile ⊗ Element⇒ PileFonction Empiler(P :Pile; Elt : Element) : Pile;{Ins : Place;Ins->Elt = &Elt; ...
Voir
Publié par
Langue
Catalan
Plan
Algorithme Types abstraits de données Pointeurs Listes Piles Files Tris Complexité
01/09/2006
Piles > Représentation en mémoire
Adresses
500
100
1000
350
01/09/2006
Sommet
Dupond
Toto
Titi
Paul
/
1
3
Piles > Définition
Une pile est une structure de données telle que : L’ajout d’un élément se fait au sommet de la pile. La suppression d’un élément se fait également au sommet de la pile.
C’est une structure de données en LIFO « Last In, First out » ou « dernier entré, premier sorti ».
01/09/2006
Piles > Opérations
Créer_pile :⇒Pile Empiler : Pile⊗Element⇒Pile Dépiler : Pile⇒Pile Sommet : Pile⇒Element Pile_vide : Pile⇒Booléen
01/09/2006
2
4
1
Piles > Algorithme avec allocation dynamique >Structure de données
Enregistrement Place{ Elt : Pointeur[Element]; Suivant : Pointeur[Place]; }
Enregistrement Pile { Sommet : Pointeur[Place]; }
01/09/2006
5
Piles > Algorithme avec allocation dynamique > Créer_pile
Sommet
01/09/2006
/
7
Piles > Algorithme avec allocation dynamique > Représentation en mémoire
Sommet
01/09/2006
Place
Element
Piles > Algorithme avec allocation dynamique > Créer_pile
Créer_pile :⇒Pile
Fonction créer_pile : Pile;{ Resultat : Pile; Pile->Sommet = null; }
01/09/2006
/
6
8
2
Piles > Algorithme avec allocation dynamique > Empiler
Sommet
01/09/2006
X
Piles > Algorithme avec allocation dynamique > Pile_vide
Sommet
Sommet
01/09/2006
/
/
/
9
11
Piles > Algorithme avec allocation dynamique > Empiler
Empiler : Pile⊗Element⇒Pile
Fonction Empiler(P :Pile; Elt : Element) : Pile;{ Ins : Place; Ins->Elt = &Elt; Ins->Suivant = P->Sommet; P->Sommet = &Ins; Retourne P; } 01/09/2006
Piles > Algorithme avec allocation dynamique > Pile_vide
Pile_vide : Pile⇒Booléen
Fonction pile_vide (P: Pile) : Booléen;{ Resultat : Booléen; Resultat = (P->Sommet == null); Retourne Resultat; }
01/09/2006
10
12
3
Piles > Algorithme avec allocation dynamique > Dépiler
Sommet
01/09/2006
X
Piles > Algorithme avec allocation dynamique > Sommet
Sommet
01/09/2006
/
/
13
15
Piles > Algorithme avec allocation dynamique > Dépiler
Dépiler : Pile⇒Pile
Fonction Dépiler (P : Pile) : Pile;{ Si (!Pile_vide(P)) Alors { P->Sommet = Valeur[Pile->Sommet]->Suivant; } FinSi Retourne P; }
01/09/2006
Piles > Algorithme avec allocation dynamique > Sommet
Sommet : Pile⇒Element
Fonction Sommet (P :Pile) : Pointeur [Element];{ Resultat : Pointeur[Element]; Si (Pile_vide(P)) Alors { Resultat = null } Sinon { Resultat = valeur[P->Sommet]->Elt; } FinSi
Retourne resultat }
01/09/2006
14
16
4
Plan
Algorithme Types abstraits de données Pointeurs Listes Piles Files Tris Complexité
01/09/2006
17
Files > Représentation en mémoire > Représentation en mémoire
Adresses
500
100
1000
350
01/09/2006
Debut
Fin
Dupond
Toto
Titi
Paul
/
19
Files > Définition
Une file est une structure de données telle que : L’ajout d’un élément se fait à la fin de la file. La suppression d’un élément se fait au début de la file.
C’est une structure de données en FIFO « First In, First out » ou « premier entré, premier sorti ».
01/09/2006
Files > Opérations
Créer_file :⇒file Ajouter : file⊗Element⇒file Retirer : file⇒file Premier : file⇒Element File_vide : File⇒Booléen
01/09/2006
18
20
5
Files > Algorithme avec allocation dynamique > Structure de données
Enregistrement Place{ Elt : Pointeur[Element]; Suivant : Pointeur[Place]; }
Enregistrement Liste { Debut : Pointeur[Place]; Fin : Pointeur[Place]; }
01/09/2006
Files > Algorithme avec allocation dynamique > Créer_file
Debut
Fin
01/09/2006
/
/
21
23
Files > Algorithme avec allocation dynamique > Représentation en mémoire
Debut
01/09/2006
Place
Element
Fin
Files > Algorithme avec allocation dynamique > Créer_file
Créer_file :⇒file
Fonction Créer_file : File;{ Resultat : File; Resultat ->Debut = null; Resultat->Fin = null; Retourne Resultat; }
01/09/2006
/
22
24
6
Files > Algorithme avec allocation dynamique > File_vide
Debut
Fin
01/09/2006
/
/
25
Files > Algorithme avec allocation dynamique > Ajouter
Debut
01/09/2006
Fin
X
/X
/
27
Files > Algorithme avec allocation dynamique > File_vide
File_vide : File⇒Booléen
Fonction File_Vide(F: File) : Booleen;{ Retourne F->(Debut == null); }
01/09/2006
26
Files > Algorithme avec allocation dynamique > Ajouter
Ajouter : file⊗Element⇒file
Fonction Ajouter(F : File; Elt : Element) : File;{ Ins : Place; Ins->Elt = &Elt; Ins->Suivant = null;
Si (File_Vide(F)) Alors{ F->Debut = &Ins } Sinon { Valeur[F->Fin]->Suivant = &Ins; } FinSi
F->Fin = &Ins;
Retourne F; } 01/09/2006
28
7
Files > Algorithme avec allocation dynamique > Retirer
Debut
01/09/2006
X
Fin
/
29
Files > Algorithme avec allocation dynamique > Premier
Debut
01/09/2006
Fin
/
31
Files > Algorithme avec allocation dynamique > Retirer
Retirer : file⇒file
Fonction Retirer(F :File) : File;{ Si (!File_Vide(F)){ F->Debut = Valeur[F->Debut]->Suivant; Si (F->Debut == null){ F->Fin = null; } FinSi } FinSi Retourne F; }
01/09/2006
30
Files > Algorithme avec allocation dynamique > Premier
Premier : file⇒Element
Fonction Premier (F : File) : Pointeur[Element];{ Resultat:Pointeur[Element]; Si (File_vide(F)) Alors { Resultat = null; } Sinon { Resultat = Valeur[F->Debut]->Elt; } Retourne Resultat; }
01/09/2006
32
8
