Upload
severin-robinet
View
105
Download
0
Embed Size (px)
Citation preview
Structures de donnéesIFT-2000
Abder AlikacemAbder Alikacem
Les structures de piles et de files
Département d’informatique et de génie logiciel
Édition Septembre 2009
! +
Bilan de la semaine 3 Les normes de programmation Le TP1
Le point
Liste avec tableau:1. Insertion et suppression sont O(n).2. Précédent et accès direct sont O(1).3. Tout l’espace est alloué à l’avance.4. Pas d’espace autre que les valeurs.
Liste dans une liste chaînée:1. Insertion et suppression sont O(1).2. Précédent et accès direct sont O(n).3. L’espace augmente avec la liste.4. Chaque élément requiert de l’espace pour les pointeurs
Comparaison des implantations de la liste
Laboratoire #4 (suite du lab#3…
Nous vous fournissons 3 packetages, un par projet/implantation que vous devez faire:
tableau dynamiqueliste doublement chaînéeliste circulaire
Implantation d’une liste ordonnée
Dans chacun d'eux, vous devez compléter le fichier .inl étant donné le modèle d'implantation décrit dans la partie privée de la classe Liste. Bien entendu, les 3 implantations demandées doivent être génériques. Ces 2 main() fournis sont pour tester les 3 packetages (séparément), un main() pour instancier une liste ordonnée d'entiers et un autre pour déclarer une liste d'objets définis dans la classe ClasseTests.h que nous vous fournissons également.
Rappel des éléments du C++ à étudier
Semaine 1
Du C au C++Les entrées/sorties (important pour cette semaine)L'espace de nommageLes types vector et string
Semaine 2
Concepts orientés objet Classe et objet
Semaine 3Programmation générique (template) La gestion des exceptions
Éléments du C++ à maîtriser
les éléments syntaxiques nouveaux par rapport au langage C notion de classe, constructeurs, destructeur constructeur de copie et surcharge de l'op. = (minimum exigé dans une classe) les attributs et méthodes d'une classe: friend, static, const la généricité (template)
Le point sur les normes de programmation
Normes de programmation:
• Commentaires d’interface• Commentaires d’implémentation• Découpage logique d’un programme• La gestion des exceptions• Style de programmation
Voir sur le site Web du cours, section Documentations/Normes de programmation:
•NormesProgrammation.pdf•Resume.h (à propos des commentaires Doxygen)
L'interface...
/**
* \brief
*
* \pre
* \pre
*
* \post
* \post
*
* \exception
* \exception
*/
Résumé des balises de Doxygen
Implémentation...
/**
* \fn
*
* \param[in]
* \param[out]
*
* \return
Section Documentations/Normes de programmation:
•Resume.h (à propos des commentaires Doxygen)
template <typename T> class Liste{
public://L'interface...
/**
* \brief Ajouter un nouvel élément dans la liste
*
* \pre il y a assez de mémoire pour ajouter l'élément x
* \pre la position d'ajout, pos, est comprise entre 1 et |L|+1
*
* \post la liste comprend un élément de plus
* \post la liste est inchangée sinon
*
* \exception range_error si la position est erronée
* \exception length_error si pas assez de mémoire
*/
void ajouter(const T& x, int pos) throw(range_error, length_error);
...
private:
...//Modèle d'implantation
};
Fichier Liste.h
Spécifications « C++ » (version Doxygen)
/**
* \fn void Liste<T>:: ajouter (const T& x, int pos)
*
* \param[in] x Élément à ajouter
* \param[in] pos Position où insérer l'élément
*
*/
template <typename T>
void Liste<T>::ajouter (const T& x, int pos) throw(out_of_range, length_error)
{
Commentaires d’implémentation (version Doxygen)
premiere derniere
…
depart
arriveeLabyrinthe
NoeudListePieces
class Piece{
ListePortes portes;bool parcourue;string nom;
};
class ListePortes{ Porte porte; noeudListePortes *acces;} ;
class Porte{ Piece *destination; Couleur color;}
Classes Chemin et FilePieces : ils servent pour la résolution de certaines méthodes demandées
TP1
Première partie: les piles
• Introduction et exemples d’application• Description en terme de type abstrait• Implantation
Piles et files
Piles :
LIFO : last in, first outDAPS : dernier arrivé, premier sorti
in out
pile
Files :
FIFO : first in, first outPAPS : premier arrivé, premier sorti
out in
file
Piles et files
Structures de données auxiliaires• car utilisées par d’autres structures
(comme les listes ordonnées)
Utilité :• support à des applications• support à d’autres structures de données• modélisation de la réalité• en informatique : système d’exploitation
gestion interneévaluation d ’expressions etc.
Pile = liste + gestion adaptée
manipulations (empiler et dépiler) par le même point d’accès
in
out
pile pile
out
in
• espace de mémorisation temporaire, avec conventions de manipulation (gestion) :
• ajouter un nouvel élément sur la pile (empiler)
• enlever un élément de la pile (dépiler)
• regarder le premier élément de la pile
• indiquer si la pile est vide
• regarder si un élément est sur la pile
• remplacer un élément sur la pile
les noms anglais pour ces opération sont: PUSH—EMPILER, POP—DÉPILER, TOP—SOMMET, PEEP—EXAMINER et CHANGE—CHANGER.
pile
Piles
Préoccupation de la programmation par objet
initialiser une pile (constructeurs); détruire une pile de ses éléments (destructeur); Constructeur de copie; Surcharge de l’opérateur =
Piles
pile
La classe Piletemplate <typename T>class Pile{public:
// constructeurs et destructeursPile(); //constructeurPile(const Pile&) throw(bad_alloc); //constructeur copie~Pile(); //destructeur
// Modificateursvoid empiler(const T&) throw (bad_alloc);T depiler() throw(logic_error);
//Sélecteursbool estVide() const;int taille() const;T& sommet() const throw (logic_error); // élément au sommet
//surcharge d'opérateursPile<T>& operator = (const Pile<T>&) throw
(bad_alloc);friend ostream& operator << (ostream& , const Pile& );
private: … //Modèle d’implantation};
Piles : implantation dans un tableau
template <typename T, int MAX = 100 >class Pile {public:
Pile(const int max = MAX) throw (bad_alloc);// constructeur... ~Pile (); // destructeur
private : T* tab; int sommet; int tailleMax;
};
Implantation dans un tableau dynamique
Piles : implantation dans un tableau
template <Typename T>Pile<T> :: Pile (int max) throw (bad_alloc){
tab = new T [max];sommet = -1;tailleMax =max;
}
template <class T>Pile<T> :: ~Pile () { if (tab!=0) delete [ ] tab;}
Constructeur
Destructeur
Piles : implantation dans un tableau
template <typename T>T Pile<T> :: depiler() throw (logic_error){
if (!estVide()) return tab[sommet--];else
throw logic_error("Depiler: la pile est vide!");}
template <typename T>bool Pile<T> :: estVide () const {
return (sommet == -1);}
dépiler
Sélecteur : vide
Piles : implantation dans un tableautemplate <typename T>void Pile<T> :: empiler(const T& e) throw (length_error){
if (sommet+1 < tailleMax) { sommet ++;
tab[sommet] = e; }else throw length_error("Empiler:la pile est
pleine\n");
}
empiler
Remarque : on suppose que l ’opérateur d ’affectation existe ou est surchargé dans la classe qui correspond au paramètre T.
=> intérêt de la surcharge des opérateurs
Piles : implantation dans un tableau
template <typename T>Pile<T>& Pile<T> :: operator = (const Pile<T>& p) {
if (tab!=0) delete [ ] tab; //on nettoie thistab=new T [p. tailleMax];
tailleMax =p.tailleMax;for (int i=0; i< tailleMax;i++)
tab[i]=p.tab[i];sommet=p.sommet;
return (*this);//retourner : une référence sur l ’objet courant}
Surcharge de l’op. =
Piles : implantation dans un tableau
template <typename T>Pile<T> :: Pile (const Pile<T>& p) { tab=new X [p. tailleMax];
tailleMax =p. tailleMax;for (int i=0; i< tailleMax;i+=1)
tab[i]=p.tab[i];sommet=p.sommet;
}
Constructeur de copie
Piles : implantation dans une liste chaînée
template <typename T>class Noeud{public:
Noeud (const T& data_item, Noeud * next_ptr = 0) :el(data_item), suivant(next_ptr) {}//constructeur
~Noeud () {}; //destructeur qui ne fait rien
};
friend class Pile <T>;
private :T el;Noeud<T> * suivant;
Version 1Implantation dans une liste chaînée
Piles : implantation dans une liste chaînée
template <typename T>class Pile {public: Pile (); // Constructeur Pile (const pile<X>&) throw (bad_alloc); // Constructeur par
copie ~Pile (); // Destructeur
Pile<T>& operator=(const Pile<T>& P); // P1 = Pvoid empiler (const T& a) throw (bad_alloc); T depiler () throw (logic_error);
T& sommet() const throw (logic_error); // sélecteur : valeur //placée au sommet
bool vide() const; //sélecteur : est vide?
};
private :Noeud<T>* sommet; // pointeur sur le sommet de la pileint cpt; // Nombre d'élements de la pile void detruire (); //Méthode privée utile pour le destructeur
// et l’op. =
Version 1
Piles : implantation dans une liste chaînée
template <typename T>class Pile {public:
Pile (); Pile (const Pile<T>&) throw (bad_alloc); ~Pile (); Pile<T>& operator=(const Pile<T>& P); //..
private:class Noeud{public: T el;
Noeud * suivant;Noeud (const T& data_item, Noeud * next_ptr = 0) :el(data_item), suivant(next_ptr) {}
};typedef Noeud * elem;elem sommet; //sommet de la pileint cpt; void detruire ();
};
Version 2Class Nœud interne
Piles : implantation dans une liste chaînée
template <typename T>Pile<T>::Pile (){ sommet =0; cpt = 0;}
template <class X>Pile<X>:: ~Pile(){ if (sommet != 0) detruire( );}
template <typename T>void Pile<T>::detruire () {
Noeud<T>* p;while (sommet != 0){
p=sommet->suivant;delete sommet;sommet=p;
}}
constructeur
destructeur
Les piles
Comparaison des 2 implantations Toutes les implantations des opérations d’une pile utilisant un tableau
ou une liste chaînée prennent un temps constant i.e. en O(1). Par conséquent, d’un point de vue d’efficacité, aucune des deux implantations n’est mieux que l’autre. D’un point de vue de complexité spatiale, le tableau doit déclarer une taille fixe initialement. Une partie de cet espace est perdue quand la pile n’est pas bien remplie. La liste peut augmenter ou rapetisser au besoin mais demande un extra espace pour mémoriser les adresses des pointeurs.
Applications des piles
• Vérification de parenthèses• Reconnaissance syntaxique• Calcul arithmétique
Deuxième partie: les files
• Introduction et exemples d’application• Description en terme de type abstrait• Implantation
Files
Files :
FIFO : first in, first outPAPS : premier arrivé, premier sorti
Manipulations (enfiler et défiler) par des points d’accès opposés
in out
file
out in
file
Files
Description en termes de type abstrait
Le rôle d'une file est de permettre la mise en attente d'informations dans le but de les récupérer plus tard. La première information à être récupérée est celle qui a été mise en attente en premier.
Primitives de manipulation:
1. ajouter un nouvel élément dans la file (enfiler); 2. ôter l'élément le plus ancien de la file (défiler); 3. indiquer si la file d'attente est vide;4. retourner le premier et dernier élément;Etc..
Préoccupation de la programmation par objet
initialiser une file (constructeurs); détruire une file de ses éléments (destructeur); Constructeur de copie; Surcharge de l’opérateur =
Files
in
file
La classe Filetemplate<typename T>class File{public:
// constructeurs et destructeurs:File() throw(bad_alloc); //constructeurFile(const File &) throw(bad_alloc); //constructeur copie~File();// modificateursvoid enfiler(const T&) throw (length_error);T defiler() throw(logic_error);// sélecteurs
int taille() const { return cpt;} bool estVide() const { return cpt==0; } bool estPleine() const { return cpt==TailleMax; }
T& premier() const throw (logic_error); // élément en tête de la fileT& dernier() const throw (logic_error); // élément en queue de la file// surcharges d'opérateursFile<T>& operator = (const File<T>&) throw (bad_alloc);friend ostream& operator << (ostream& f, const File& q);
private: // ...Modèle d'implantation};
T ê t e Q u e u e
Insérer 'Robert'
T Q
P a u l
R e n é
M a r c
P a u l
P a u l R e n é
R e n é M a r c
M a r c
M a r c
M a r c
M a r c
J e a n
J e a n
J e a n
A n n e
A n n e
T
T
T
T
T
T
T
Q
Q
Q
Q
Q
Q
QD ébordement
V ide
Insérer 'Paul'
Insérer 'Jean'
Insérer 'René'
Extraire 'Paul'
Extraire 'René'
Insérer 'A nne'
Insérer 'Marc'
Implantation par tableau circulaire
Implantation: liste circulaire
q = (q + 1) modulo MAXELT
Files: implantation dans un tableau
Implantation dans un tableau dynamique
template <typename T, in MAX = 100 >class File {public:
File(const int max = MAX) throw (bad_alloc);// constructeur ... ~File (); // destructeur
private : T* tab; int tete;int queue; int tailleMax;int cpt;
};
Tableau tab réservé dans le tas
Constructeur avec un paramètre : taille maximum
Files: implantation dans un tableau
template <Typename T>File<T> :: File (int max) throw (bad_alloc){
tab = new T [max];tete = 0;queue = 0;cpt = 0;tailleMax =max;
}
template <class X>File<X> :: ~File () { if (tab!=0) delete [ ] tab;}
Constructeur
Destructeur
Files: implantation dans un tableau
template <typename T>T File<T> :: defiler() throw (logic_error){
if (cpt!=0){
T elementaDefiler = tab[tete];tete = (tete+1)% tailleMax;cpt--; return elementaDefiler;
}else
throw logic_error("Defiler: la file est vide!");}
défiler
Files: implantation dans un tableau
template <typename T>T File<T> :: enfiler(const T& e) throw (length_error){
if(cpt<tailleMax){
tab[queue]= e;queue = (queue+1)%tailleMax;cpt++;
}else
throw length_error(« Enfiler: la file est pleine!");}
enfiler
Files: implantation par listes
Implantation dans une liste chaînéetemplate <typename T>class File {public:
File (); File (const File<T>&) throw (bad_alloc); ~File (); File<T>& operator=(const File<T>& P); //..
private:class Noeud{public: T el;
Noeud * suivant;Noeud (const T& data_item, Noeud * next_ptr = 0) :el(data_item), suivant(next_ptr) {}
};typedef Noeud * elem;elem tete; // pointeur sur la tête de la fileeleme queue; // Pointeur en queue de fileint cpt; // cardinalité de la file
};
Files: implantation par listes
template <typename T>Pile<T>::Pile (){ tete =0; queue = 0; cpt = 0;}
template <class X>File<X>:: ~File(){ if (tete != 0) {
Noeud<T>* p;while (tete != 0){
p=tete->suivant;delete tete;tete=p;
}}
constructeur
destructeur
Files prioritaires
Gestion d’une seule file• insertion se fait selon la priorité• éléments toujours triés selon leur priorité
in
file
41 84 1in
file
11 44 8
Files prioritaires
Gestion de plusieurs files• 1 file par niveau de priorité (sous-liste)• une liste triée selon le niveau de priorité avec un
bloc descripteur pour la sous-liste correspondante
A B C D
D1 D2
B1 B2 B3 B4
A1 A2 A3
… … …
Applications des files
Modélisation du phénomène:• banque• chaîne de montage• etc.
En informatique:• traitement « batch » (en lots)• gestion des listes d’impression
Principes d’une simulation
Tantque toujours fairesi f n’est pas vide
alors:tâche = defile(f);exécuter tâche;
Fin Tantque
Si exécution(tâche) alors:f = enfiler(tâche,f);
Processus consommateur
Processus producteur
simulation: élément =
<événement,temps> priorité = temps
in
file
41 84 1in
file
11 44 8
Laboratoire #5
Le but de ce laboratoire est l’implantation de l’interface d’une pile et d’une file génériques. Parmi les exemples de cette semaine, nous vous avons fourni des implantations d’une pile dans un tableau dynamique et d’une file dans une liste simplement chaînée. Il est question ici de refaire l’implantation d’une pile et d’une file dans une liste simplement chaînée et dans un tableau dynamique respectivement. Il est question également de l’implantation d’une pile dans un modèle hybride et d’une file prioritaire.
Téléchargez l'ensemble de l'énoncé. Vous y trouverez entre autres, 2 packetages, une pour une pile et l'autre pour une file. Pour chacun d'eux, vous devez compléter le fichier .inl étant donné le modèle d'implantation décrit dans la partie privée de la classe décrite dans chaque packetage. Nous vous fournissons un main() pour tester chaque implantation.