View
109
Download
2
Category
Preview:
Citation preview
Structures de donnéesIFT-2000
Abder AlikacemAbder Alikacem
Les listes ordonnéesProgrammation générique
en C++
Semaine 3, suite et fin
Département d’informatique et de génie logiciel
Édition Septembre 2009
! +
Deuxième partie
Retour au type abstrait liste ordonnée, implantation par: des tableaux dynamiques (lab#3) des listes simplement chaînées des listes doublement chaînées des listes circulaires (anneaux)
Les listes ordonnées
Implantation dans une liste chaînée
// fichier Noeud.h// déclaration de la classe Noeud
#ifndef NOEUD_H#define NOEUD_H
class Noeud;typedef Noeud * elem;
template <typename T>class Noeud{ //Un noeud typique de la listepublic:
T el; //L'élément de base de la listeelem suivant; //Un pointeur vers le noeud suivantNoeud (const T& data_item, elem next_ptr = 0) :
el(data_item), suivant(next_ptr) {}~Nœud(){};
};#endif
elsuivant
Les listes ordonnées
Implantation dans une liste chaînée#ifndef LISTE_H#define LISTE_H#include "Noeud.h"#pragma warning( disable : 4290 )
template <typename T>class Liste {public:
Liste(){debut = 0;} // constructeur~Liste(); // destructeurListe(const Liste&) throw(bad_alloc); // constructeur de copievoid ajouter(T x, int pos) throw(range_error, bad_alloc);int taille() const;bool appartient(constT& x,) const;//Surcharge d'opérateursListe<T>& operator = (const Liste<T>&) throw (bad_alloc);friend ostream& operator << (ostream&, const Liste& );
private:elem debut; // Pointeur vers le dernier noeud de la liste
} ; #endif
Implantation dans une liste chaînée
Une meilleure version: utilisation d’une classe interne//…template <typename T>class Liste {public:
//ConstructeursListe(){debut = 0;} // constructeur Liste(const Liste&) throw(bad_alloc); // constructeur de copie~Liste(); // destructeur//Surcharge d'opérateursListe<T>& operator = (const Liste<T>&) throw (bad_alloc);
private:class Noeud{ //Un noeud typique de la listepublic: T el; //L'élément de base de la liste Noeud * suivant; //Un pointeur vers le noeud suivant Noeud (const T& data_item, Noeud * next_ptr = 0) :
el(data_item), suivant(next_ptr) {}};typedef Noeud * elem;elem debut; //Pointeur vers le premier noeud de la liste
} ;
Implantation dans une liste chaînée
template <typename T> Liste<T>:: ~Liste() { elem courant = debut; while(courant!=0) {
debut=debut->suivant; delete courant;courant=debut;
}}
~Liste() // destructeur
Destructeur
Implantation dans une liste chaînée
template <typename T>void Liste<T>:: ajouter(T x, int pos) throw(range_error, bad_alloc){
elem courant; //pointeur de service pour se promener dans la listeelem nouveau; //pour l'adresse de la nouvelle structure pour entreposer xint cpt=1; //compteur de boucle
//Vérification des hypothèses (préconditions)
//La positionif(pos<1 || pos > taille() +1) throw range_error( ..:Position d'ajout erronée");
//La mémoirenouveau = new Noeud(x); //on appelle le constructeur de la classe Noeud
//suite prochaine diapositive
ajouter() // l’ajout d’élément
Implantation dans une liste chaînée
//Cas où l'ajout se fait en première positionif(pos==1){
nouveau->suivant=debut;debut = nouveau;return ;
}//Ajout dans une autre quelconque positioncourant = debut; //on se positionne au début de la liste chaînéewhile (cpt< pos - 1){
courant=courant->suivant; //on passe à la structure suivante..cpt++; //...et on compte
}//A: courant pointe la structure d'avant le nouvel ajoutnouveau->suivant = courant->suivant; //on chaîne la nouvelle structure …courant->suivant = nouveau;//on chaîne la structure qui doit précéder …
}
ajouter() // l’ajout d’élément
Implantation dans une liste chaînée
template <typename T>void Liste<T>:: enleverEl(const T& x) throw(logic_error){ elem trouve = debut; elem pred;
//on prend pour acquis que l'opérateur != s'applique sur x, le mieux est … while (trouve != 0 && trouve->el != x ) {
pred = trouve; // pour marquer le noeud prédécesseur à celui qui contient xtrouve = trouve->suivant;
}
if (trouve== 0) throw logic_error("EnleverEl: x n'est pas dans la liste"); else { //suite prochaine diapositive
enleverEl() // enlever la première occurrence d’un élément
Implantation dans une liste chaînée
else {
if (debut == trouve){ / x est au début de la liste
debut = debut->suivant;}else{ // ..il est ailleur
pred->suivant = trouve->suivant;}
// on "coupe" la structure supprimée de la listetrouve->suivant = 0;//libération de la mémoire associée à la structure supprimée delete trouve;
}}
enleverEl() // enlever la première occurrence d’un élément
Implantation dans une liste chaînée
template <typename T>Liste<T>& Liste<T>::operator = (const Liste<T>& source)throw(bad_alloc){
//nettoyage ...if (debut!=0){ elem temp= debut;
while (debut !=0){
debut = temp->suivant;delete temp;temp = debut;
}}
//suite prochaine diapositive
Operator = () // surcharge de l’op. d’affectation
Implantation dans une liste chaînée
if (source.debut== 0)debut = 0; // la liste originale est vide
else { //la copie try{
//copie le permier noeud debut = new Noeud(source.debut->el); // copie le reste de la liste elem nouveau = debut; for(elem temp = source.debut->suivant; temp != 0;temp = temp->suivant) {
nouveau->suivant = new Noeud(temp->el);nouveau = nouveau->suivant;
}
}catch(exception&){ //suite dans la prochaine diapositive
Operator = () // surcharge de l’op. d’affectation
Implantation dans une liste chaînée
catch(exception&){ //Si on arrive ici c'est qu'il y a une erreur d'allocation //On doit donc libérer la mémoire déjà allouée elem temp= debut;
while (temp!=0){
debut = temp->suivant;delete temp;temp = debut;
} //On relance alors l'exception pour indiquer qu'une erreur est survenue throw; } }//else return (*this);}
Operator = () // surcharge de l’op. d’affectation
Implantation dans une liste chaînée
template <typename T>class Liste {public:
//..
friend ostream& operator << (ostream& f, const Liste& l){elem courant=l.debut; while(courant!=0){
f << courant->el << " "; courant=courant->suivant;
} return f;}
private://..
} ;
Operator << () // surcharge de l’op. <<
Les listes chaînées circulaires permettent de rendre l’écriture de certains algorithmes d’une manière plus efficace.
sommet
. . .
Implantation dans une liste circulaire (anneau)
Cependant, il est plus intéressant d’avoir un pointeur dernier au lieu d’un pointeur sommet
dernier
. . .
Listes circulaires (les anneaux)template <typename T>class Liste {public: //...
friend ostream& operator << (ostream& f, const Liste& l){if(l.dernier == 0) return f;elem courant = l.dernier->suivant; while(courant!=l.dernier){
f << courant->el << " "; courant=courant->suivant;
} f << l.dernier->el; return f;}
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 dernier; /*Pointeur vers le dernier noeud de la liste*/
} ;
Dans les situations où il est souvent nécessaire d’atteindre des éléments d'une chaîne qui se trouvent quelques positions avant un élément donné, on peut alors adjoindre, à chaque élément, un pointeur supplémentaire vers son prédécesseur.
SommetG SommetD
…
Implantation dans une liste doublement chaînée
Nœud typique d’une liste chaînée :
Nœud typique d’une liste doublement chaînée :
Info Lien
PtrG Info PtrD
Implantation dans une liste doublement chaînée
template <typename T>class Liste {public:
//..
private: class Noeud{ //Un noeud typique de la liste public:
T el; //L'élément de base de la listeNoeud * suivant; //Un pointeur vers le noeud suivantNoeud * precedent; //Un pointeur vers le noeud précédent
Noeud (const T& data_item, Noeud * next_ptr = 0, Noeud * pred_ptr =0) : el(data_item), suivant(next_ptr), precedent(pred_ptr){}
}; typedef Noeud * elem; elem sommetG; //Pointeur vers le sommet à gauche elem sommetD; //...vers le sommet droit int cpt; //cardinalité de la liste} ;
Liste doublement chaînée
Ajouter un élément• Ajouter N avant P :
……
P
N
Ajouter un élément• Ajouter N avant P :
Pprecedentsuivant = NNprecedent = PprecedentNsuivant = PPprecedent = N
……
P
N
Liste doublement chaînée
Ajouter un élément• Ajouter N avant P :
PPprecedentprecedentsuivant = Nsuivant = NNprecedent = PprecedentNsuivant = PPprecedent = N
……
P
N
Liste doublement chaînée
Ajouter un élément• Ajouter N avant P :
Pprecedentsuivant = NNNprecedent = Pprecedent = PprecedentprecedentNsuivant = PPprecedent = N
……
P
N
Liste doublement chaînée
Ajouter un élément• Ajouter N avant P :
Pprecedentsuivant = NNprecedent = PprecedentNNsuivant = Psuivant = PPprecedent = N
……
P
N
Liste doublement chaînée
Ajouter un élément• Ajouter N avant P :
Pprecedentsuivant = NNprecedent = PprecedentNsuivant = PPPprecedent = Nprecedent = N
……
P
N
Liste doublement chaînée
Ajouter un élément• Ajouter N avant P :
Pprecedentsuivant = NNprecedent = PprecedentNsuivant = PPprecedent = N
……
P
N
Liste doublement chaînée
Ajouter un élément• Ajouter N après le sommet droit :
…
P
N
…
Liste doublement chaînée
template <typename T>class Liste {public:
//..
private: … elem sommetG; elem sommetD; int cpt;} ;
Ajouter un élément• Ajouter N après le sommet droit :
sommetDsommetDsuivant = Nsuivant = NNprecedent = sommetDsommetD = NNsuivant = 0
…
P
N
…
Liste doublement chaînée
Ajouter un élément• Ajouter N après le sommet droit :
sommetDsuivant = NNNprecedent = sommetDprecedent = sommetDsommetD = NNsuivant = 0
…
P
N
…
Liste doublement chaînée
Ajouter un élément• Ajouter N après le sommet droit :
sommetDsuivant = NNprecedent = sommetDsommetD = NsommetD = NNsuivant = 0
…
P
N
…
Liste doublement chaînée
Ajouter un élément• Ajouter N après le sommet droit :
sommetDsuivant = NNprecedent = sommetDsommetD = NNNsuivant = 0suivant = 0
…
P
N
…
Liste doublement chaînée
Ajouter un élément• Ajouter N après le sommet droit :
sommetDsuivant = NNprecedent = sommetDsommetD = NNsuivant = 0
…
P
N
…
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud avant P
……
P
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud avant P
N = PprecedentPprecedent = PprecedentprecedentPprecedentsuivant = PNsuivant = 0Nprecedent = 0delete NN = 0
……
P
N
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud avant P
N = PN = PprecedentprecedentPprecedent = PprecedentprecedentPprecedentsuivant = PNsuivant = 0Nprecedent = 0delete NN = 0
……
P
N
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud avant P
N = PprecedentPPprecedentprecedent = P = PprecedentprecedentprecedentprecedentPprecedentsuivant = PNsuivant = 0Nprecedent = 0delete NN = 0
……
P
N
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud avant P
N = PprecedentPprecedent = PprecedentprecedentPPprecedentprecedentsuivantsuivant = P = PNsuivant = 0Nprecedent = 0delete NN = 0
……
P
N
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud avant P
N = PprecedentPprecedent = PprecedentprecedentPprecedentsuivant = PNNsuivant = 0suivant = 0NNprecedent = 0precedent = 0delete NN = 0
……
P
N
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud avant P
N = PprecedentPprecedent = PprecedentprecedentPprecedentsuivant = PNsuivant = 0Nprecedent = 0delete delete NNN = 0N = 0
……
P
N
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud P
……
P
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud P
Pprecedentsuivant = PsuivantPsuivantprecedent = PprecedentPprecedent = 0Psuivant = 0delete P
……
P
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud P
PPprecedentprecedentsuivant = Psuivant = PsuivantsuivantPsuivantprecedent = PprecedentPprecedent = 0Psuivant = 0delete P
……
P
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud P
Pprecedentsuivant = PsuivantPPsuivantsuivantprecedent = Pprecedent = PprecedentprecedentPprecedent = 0Psuivant = 0delete P
……
P
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud P
Pprecedentsuivant = PsuivantPsuivantprecedent = PprecedentPPprecedent = 0precedent = 0PPsuivant = 0suivant = 0delete P
……
P
Liste doublement chaînée
Supprimer un élément• Supprimer le nœud P
Pprecedentsuivant = PsuivantPsuivantprecedent = PprecedentPprecedent = 0Psuivant = 0delete P
……
P
Liste doublement chaînée
Supprimer un élément• Supprimer le sommet gauche
…
N
…
Liste doublement chaînéetemplate <typename T>class Liste {public:
//..
private: … elem sommetG; elem sommetD; int cpt;
} ;
Supprimer un élément• Supprimer le sommet gauche
N = sommetGN = sommetGsommetG = sommetGsuivantsommetGprecedent = 0Nsuivant = 0delete NN = 0
…
N
…
Liste doublement chaînée
Supprimer un élément• Supprimer le sommet gauche
N = sommetGsommetG = sommetGsommetG = sommetGsuivantsuivantsommetGprecedent = 0Nsuivant = 0delete NN = 0
…
N
…
Liste doublement chaînée
Supprimer un élément• Supprimer le sommet gauche
N = sommetGsommetG = sommetGsuivantsommetGsommetGprecedent = 0precedent = 0Nsuivant = 0delete NN = 0
…
N
…
Liste doublement chaînée
Supprimer un élément• Supprimer le sommet gauche
N = sommetGsommetG = sommetGsuivantsommetGprecedent = 0NNsuivant = 0suivant = 0delete NN = 0
…
N
…
Liste doublement chaînée
Supprimer un élément• Supprimer le sommet gauche
N = sommetGsommetG = sommetGsuivantsommetGprecedent = 0Nsuivant = 0deletedelete N NN = 0N = 0
…
N
…
Liste doublement chaînée
Liste avec tableau:1. Insertion et suppression sont en O(n).2. Accès direct est en 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 en O(1).2. Accès direct est en 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
Éléments du C++ à consulter
Semaine 1
Du C au C++Les entrées/sorties (important pour cette semaine)
Semaine 2
Concepts orientés objet Classe et objetL'espace de nommageLes types vector et string
Semaine 3
Programmation générique (template) La gestion des exceptions
Éléments du C++ à maîtriser
Les éléments syntaxiques nouveaux par rapport au langage Cdéclaration et initialisation de variablesle type bool, l’attribut constsurcharge de fonctions et arguments par défauttranstypage, espace de nommage et opérateur de résolution de portée
Notion de classe, constructeurs, destructeur
les attributs de masquage
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)
Nom de la classe Catégorie Descriptiondomain_error logique Lancée s'il se produit une erreur de domaine mathématique.invalid_argument logique Lancée si un des arguments d'une fonction est invalide.length_error logique Lancée si un objet aura une taille invalide. out_of_range logique Lancée si il y a une erreur avec un indice.
logic_error logique Lancée lors de n'importe quel autre problème de logique du programme.
Gestion des exceptions
#include <stdexcept>
Résumé des balises de Doxygen
L'interface...
/**
* \brief
*
* \pre
* \pre
*
* \post
* \post
*
* \exception
* \exception
*/
Implémentation
...
/**
* \fn
*
* \param[in]
* \param[out]
*
* \return
Section Documentations/Normes de programmation:
•Resume.h (à propos des commentaires Doxygen)
En-tête de fichiers
/**
* \file Liste.cpp
* \brief Le code des opérateurs de la liste.
* \author Abder
* \version 0.1
* \date septembre 2009
*
* Implémentation de la classe générique Liste.
*
*/
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(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 (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 (T x, int pos) throw(out_of_range, length_error)
{
Commentaires d’implémentation (version Doxygen)
Structures de donnéesIFT-2000
Abder AlikacemAbder Alikacem
Les structures de piles et de files
Semaine 4
Département d’informatique et de génie logiciel
Édition Septembre 2009
! +
Première partie: les piles
• Introduction et exemples d’application• Description en terme de type abstrait• Implantation
Piles :
LIFO : last in, first outDAPS : dernier arrivé, premier sorti
in out
pile
Les primitives de manipulation ajouter un nouvel élément sur la pile (empiler, push) enlever un élément de la pile (dépiler, pop) regarder le premier élément de la pile (sommet, top) indiquer si la pile est vide regarder si un élément est sur la pile (examiner, peep) remplacer un élément sur la pile (changer, change)
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 =
La classe Piletemplate <typename T>class Pile{public:
// constructeurs et destructeursPile(); //constructeurPile(const Pile&) throw(bad_alloc); //constructeur copie~Pile(); //destructeur
// Modificateursvoid empiler(T) throw (bad_alloc);T depiler() throw(logic_error);
//Sélecteursbool estVide();int taille();T& sommet() 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 (void) { if (tab!=0) delete [ ] tab;}
Constructeur
Destructeur
Piles : implantation dans un tableau
template <typename T>T Pile<T> :: depiler(void) throw (logic_error){
if (!estVide()) return tab[sommet--];else
throw logic_error("Depiler: la pile est vide!");}
template <typename T>bool Pile<T> :: estVide (void){
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 (void) throw (logic_error); // sélecteur : valeur //placée au sommet
bool vide(); //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) {}
};
Noeud * 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.
Deuxième partie: les files
• Introduction et exemples d’application• Description en terme de type abstrait• Implantation
Files :
FIFO : first in, first outPAPS : premier arrivé, premier sorti
out in
file
Files
Primitives de manipulation:
ajouter un nouvel élément dans la file (enfiler); ôter l'élément le plus ancien de la file (défiler); indiquer si la file d'attente est vide; retourner le premier et dernier élément;
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 =
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(T) throw (length_error);T defiler() throw(logic_error);// sélecteurs
int taille() { return cpt;} bool estVide() { return cpt==0; } bool estPleine() { return cpt==TailleMax; }
T& premier() throw (logic_error); // élément en tête de la fileT& dernier() 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, int 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 (void) { 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
Laboratoire #4 (suite du lab#3)
Nous vous fournissons 3 packetages, un par projet/implantation que vous devez faire:
tableau dynamique (Lab#3)liste 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.
Recommended