Structures de données IFT-2000 Abder Alikacem Les listes ordonnées Programmation générique en C++ Semaine 3, suite et fin Département dinformatique et

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


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

} ;


template <typename T> Liste<T>:: ~Liste() { elem courant = debut; while(courant!=0) {

debut=debut->suivant; delete courant;courant=debut;

}}

~Liste() // destructeur

Destructeur


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


//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


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


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


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


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



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);}




//..

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


//..

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


Pprecedentsuivant = NNprecedent = PprecedentNsuivant = PPprecedent = N

……

P

N



PPprecedentprecedentsuivant = Nsuivant = NNprecedent = PprecedentNsuivant = PPprecedent = N

……

P

N



Pprecedentsuivant = NNNprecedent = Pprecedent = PprecedentprecedentNsuivant = PPprecedent = N

……

P

N



Pprecedentsuivant = NNprecedent = PprecedentNNsuivant = Psuivant = PPprecedent = N

……

P

N



Pprecedentsuivant = NNprecedent = PprecedentNsuivant = PPPprecedent = Nprecedent = N

……

P

N



Pprecedentsuivant = NNprecedent = PprecedentNsuivant = PPprecedent = N

……

P

N


Ajouter un élément• Ajouter N après le sommet droit :

…

P

N

…



//..

private: … elem sommetG; elem sommetD; int cpt;} ;


sommetDsommetDsuivant = Nsuivant = NNprecedent = sommetDsommetD = NNsuivant = 0

…

P

N

…



sommetDsuivant = NNNprecedent = sommetDprecedent = sommetDsommetD = NNsuivant = 0

…

P

N

…



sommetDsuivant = NNprecedent = sommetDsommetD = NsommetD = NNsuivant = 0

…

P

N

…



sommetDsuivant = NNprecedent = sommetDsommetD = NNNsuivant = 0suivant = 0

…

P

N

…



sommetDsuivant = NNprecedent = sommetDsommetD = NNsuivant = 0

…

P

N

…


Supprimer un élément• Supprimer le nœud avant P

……

P



N = PprecedentPprecedent = PprecedentprecedentPprecedentsuivant = PNsuivant = 0Nprecedent = 0delete NN = 0

……

P

N



N = PN = PprecedentprecedentPprecedent = PprecedentprecedentPprecedentsuivant = PNsuivant = 0Nprecedent = 0delete NN = 0

……

P

N



N = PprecedentPPprecedentprecedent = P = PprecedentprecedentprecedentprecedentPprecedentsuivant = PNsuivant = 0Nprecedent = 0delete NN = 0

……

P

N



N = PprecedentPprecedent = PprecedentprecedentPPprecedentprecedentsuivantsuivant = P = PNsuivant = 0Nprecedent = 0delete NN = 0

……

P

N



N = PprecedentPprecedent = PprecedentprecedentPprecedentsuivant = PNNsuivant = 0suivant = 0NNprecedent = 0precedent = 0delete NN = 0

……

P

N



N = PprecedentPprecedent = PprecedentprecedentPprecedentsuivant = PNsuivant = 0Nprecedent = 0delete delete NNN = 0N = 0

……

P

N


Supprimer un élément• Supprimer le nœud P

……

P



Pprecedentsuivant = PsuivantPsuivantprecedent = PprecedentPprecedent = 0Psuivant = 0delete P

……

P



PPprecedentprecedentsuivant = Psuivant = PsuivantsuivantPsuivantprecedent = PprecedentPprecedent = 0Psuivant = 0delete P

……

P



Pprecedentsuivant = PsuivantPPsuivantsuivantprecedent = Pprecedent = PprecedentprecedentPprecedent = 0Psuivant = 0delete P

……

P



Pprecedentsuivant = PsuivantPsuivantprecedent = PprecedentPPprecedent = 0precedent = 0PPsuivant = 0suivant = 0delete P

……

P



Pprecedentsuivant = PsuivantPsuivantprecedent = PprecedentPprecedent = 0Psuivant = 0delete P

……

P


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;

} ;


N = sommetGN = sommetGsommetG = sommetGsuivantsommetGprecedent = 0Nsuivant = 0delete NN = 0

…

N

…



N = sommetGsommetG = sommetGsommetG = sommetGsuivantsuivantsommetGprecedent = 0Nsuivant = 0delete NN = 0

…

N

…



N = sommetGsommetG = sommetGsuivantsommetGsommetGprecedent = 0precedent = 0Nsuivant = 0delete NN = 0

…

N

…



N = sommetGsommetG = sommetGsuivantsommetGprecedent = 0NNsuivant = 0suivant = 0delete NN = 0

…

N

…



N = sommetGsommetG = sommetGsuivantsommetGprecedent = 0Nsuivant = 0deletedelete N NN = 0N = 0

…

N

…


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


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


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


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. =


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


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


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


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


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


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


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.

https://cours.ift.ulaval.ca/fileadmin/cours/200909_2000_8360083603/prive/Semainier/Semaine%203/Lab3/ClasseTests.zip

Documents

Structures de données IFT-2000 Abder Alikacem Les listes ordonnées Programmation générique en C++ Semaine 3, suite et fin Département dinformatique et