Structures de données IFT-2000 Abder Alikacem Les structures de piles et de files Département...

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.