Structures de données IFT-2000 Abder Alikacem Types de données abstraits (2) Semaine 1...

Structures de donnéesIFT-2000

Abder AlikacemAbder Alikacem

Types de données abstraits (2)Semaine 1

Département d’informatique et de génie logiciel

Édition Septembre 2009

• Exemple d’un TDA: une liste ordonnée

• Utilités• Spécifications• Implantation

• Structures de données génériques • Gestion des exceptions

Introduction

L’objectif de cette partie du cours est de commencer à décrire des représentations des structures de base utilisées en informatique telles les listes. Ces derniers seront vus en termes de types abstraits.

Un autre objectif recherché est de donner des exemples de séparations des représentations logiques à travers les TDA des implémentations physiques.

Enfin, un dernier objectif est de décrire les outils du langage C++ qu’on aurait besoin pour implanter les structures de données dans notre cours.

Les listes

Les listes sont des structures informatiques qui permettent de garder en mémoire des données en respectant un certain ordre: on peut ajouter, enlever ou consulter un élément en début ou en fin de liste, vider une liste ou savoir si elle contient un ou plusieurs éléments.

La structure de liste particulièrement souple et dont les éléments sont accessibles à tout moment. Toute suite d’informations inscrites les unes après les autres est une liste. Exemple : liste d’étudiants, liste d’inventaire, liste des absents, …

Les listes

Une liste est définie comme étant une suite ordonnée d’éléments. L’ordre signifie que chaque élément possède une position dans la liste.

Une liste: structure récursive

( a (b ( c (d))))

Une liste peut être vu comme une structure récursive :liste = élément + liste OU liste = vide

Liste ordonnée d’éléments (int)• L = <8,1,5,4,6>

• L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6

• <8,1,5,4,6> <8,1,4,6,5>

Utilité?

Un exemple de liste: une liste ordonnée

Réq.#1:2000 chemises1000 pantalons1500 cravates...

Réq.#2Réq.#3

Réq.#1

• L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6

• <8,1,5,4,6> <8,1,4,6,5>

Utilité?• liste de réquisitions

• L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6

• <8,1,5,4,6> <8,1,4,6,5>

Utilité?• liste de réquisitions• file d’attente

Liste ordonnée d’éléments (int)• L = <8,1,5,4,6>• L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6• <8,1,5,4,6> <8,1,4,6,5>

Utilité?• liste de réquisitions• file d’attente• Parcours d’un graphe

Manipulations (opérateurs):• L • L = ? (i.e., L = 0?)• x L?• Li

• x = L?

• L L +i x• L -i L• L L - x• L = L’?• L L’?• L L’?• lister L

L = <8,1,5,4,6>

Opérateurs sur les listes

Manipulations (opérateurs):• LL • L = ? (i.e., L = 0?)• x L?• Li

• x = L?

L = <8,1,5,4,6>

Opérateur: nombre d’éléments?

Opérateur: liste vide?

Manipulations (opérateurs):• L • L = L = ?? (i.e., L = 0?)• x L?• Li

• x = L?

L = <8,1,5,4,6>

Opérateur: appartenance

Manipulations (opérateurs):• L • L = ? (i.e., L = 0?)• x x L? L?• Li

• x = L?

L = <8,1,5,4,6>

4 L? Oui!9 L? Non!

Manipulations (opérateurs):• L • L = ? (i.e., L = 0?)• x L?• LLii

• x = L?

L = <8,1,5,4,6>

L1 = 8, L2 = 1, L3 = 5, L4 = 4, L5 = 6

Opérateur: accès

Opérateur: rang (indice)

• x = Lx = L??

L = <8,1,5,4,6,1>

81, 12, 53, 44, 65, 90

Opérateur: ajout

• x = L?

• L L L + L +ii x x• L -i L• L L - x• L = L’?• L L’?• L L’?• lister L

L = <8,1,5,4,6>

L L +1 9: <9,8,1,5,4,6>L L +2 9: <8,9,1,5,4,6>L L +3 9: <8,1,9,5,4,6>L L +4 9: <8,1,5,9,4,6>L L +5 9: <8,1,5,4,9,6>L L +6 9: <8,1,5,4,6,9>L L +7 9: <>

Opérateur: retrait du rang

• x = L?

• L L +i x• L L - -ii L L• L L - x• L = L’?• L L’?• L L’?• lister L

L = <8,1,5,4,6>

L -1 L: <1,5,4,6>L -2 L: <8,5,4,6>L -3 L: <8,1,4,6>L -4 L: <8,1,5,6>L -5 L: <8,1,5,4>L -6 L: <8,1,5,4,6>

Opérateur: retrait d’élément

• x = L?

• L L +i x• L -i L• L L L - x L - x• L = L’?• L L’?• L L’?• lister L

L = <8,1,5,4,6,1>

L L - 8: <1,5,4,6,1>L L - 1: <8,5,4,6,1>L L - 5: <8,1,4,6,1>L L - 4: <8,1,5,6,1>L L - 6: <8,1,5,4,1>L L - 9: <8,1,5,4,6,1>

• x = L?

• L L +i x• L -i L• L L - x• L = L’?L = L’?• L L’?• L L’?• lister L

L = <8,1,5,4,6>L’ = <8,1,4,6,5>

Opérateur: test d’égalité

Opérateur: inclusion stricte

• x = L?

• L L +i x• L -i L• L L - x• L = L’?• L L L’? L’?• L L’?• lister L

L = <8,4,5>L’ = <8,1,4,6,5>

L = <8,1,4,6,5>L’ = <8,1,4,6,5>

Opérateur: inclusion

• x = L?

• L L +i x• L -i L• L L - x• L = L’?• L L’?• L L L’? L’?• lister L

L = <8,4,5>L’ = <8,1,4,6,5>

L = <8,1,4,6,5>L’ = <8,1,4,6,5>

• x = L?

• L L +i x• L -i L• L L - x• L = L’?• L L’?• L L’?• lister Llister L

L = <8,1,5,4,6>

8,1,5,4,6

Opérateur: listage

Autres opérateurs?

Opérateur: sous-liste

Autres opérateurs?

• sous-liste de L, de i, pour une longueur de n: L[i,n]

L = <8,1,5,4,6>

L[2,3] = <1,5,4>

Opérateur: sous-liste

Autres opérateurs?

• sous-liste de L, de i, pour une longueur de n: L[i,n]

• concaténation de listes: L + L’

L = <8,1,5,4,6>

L[2,3] = <1,5,4>

L = <8,1,5,4,6>L’ = <1,9>

L + L’ = <8,1,5,4,6,1,9>

Opérateur: concaténation

Spécifications « langage C »

L L +i x

• prototype de la fonction implantant l’opérateur:• Liste ajouterListe(Liste l, TypeEl x, int i, int *err);

• préconditions conditions devant être vraies au départ pour assurer le bon fonctionnement de l ’opérateur

• l ne doit pas être pleine et i [1,|L|+1]

• postconditions conditions étant vraies (observables) après l’application (correcte) de l’opérateur

• l contient x et *err = OK si les préconditions sont respectées• l est inchangée sinon et

*err contient:PAM si L est pleine,PERR si i [1,|L|+1]

• valeur retournée en output de l’application de l ’opérateur:• l mise à jour ou l inchangée en cas d'erreurs

Spécifications « C++ »

L L +i x

• prototype de la méthode implantant l’opérateur:• void ajouter(TypeEl x, int i) throw(range_error, length_error);

• préconditions conditions devant être vraies au départ pour assurer le bon fonctionnement de l ’opérateur

• La liste ne doit pas être pleine et i [1,|L|+1]

• postconditions conditions étant vraies (observables) après l’application (correcte) de l’opérateur

• La liste contient x si les préconditions sont respectées• La liste est inchangée sinon et :

• Exceptions les exceptions lancées par la méthode lors d’un problème

• si L est pleine,• si i [1,|L|+1]

• valeur retournée en output de l’application de l ’opérateur:• aucune

Spécifications version dOxygen

L L +i x

• prototype de la méthode implantant l’opérateur:• void ajouter(TypeEl x, int i) throw(range_error, length_error);

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

Spécifications du type liste: -i

L -i L

• prototype: Liste enleverListe (Liste l, int i, int *err);

• préconditions:• i [1,|L|]

• postconditions:• l est inchangée si i [1,|L|] avec *err = PERR

• l contient un élément de moins, l’élément Li avec *err=OK, sinon

• valeur(s) retournée(s):• l mise à jour ou inchangée en cas d'erreurs

L -i L

• prototype: void enlever(int i) throw(range_error);

• postconditions:

• La liste contient un élément de moins, l’élément Li si la précondition n’est pas satisfaite

• La liste est inchangée si i [1,|L|] sinon• Exception:

• si la position est erronée• valeur retournée:

• aucune

L -i L

• prototype: void enlever(int i) throw(range_error);

/** * \brief Enlever l’élément en position i dans la liste * * \pre i est compris entre 1 et |L| * * \post la liste comprend un élément de moins * \post la liste est inchangée sinon * * \exception range_error si la position est erronée * */

dOxygen

Spécifications du type liste: -

L L - x

• prototype: Liste enleverElListe (Liste l, TypeEl x, int *err);

• préconditions:• Aucune

• postconditions:• l contient un élément x de moins (le premier rencontré), l

inchangée si x L et *err = OK

• valeur retournée:• l inchangée si x n’appartenait pas à l • l mise à jour sinon

L L - x

• prototype: void enleverEl (TypeEl x);

• préconditions:• Aucune

• postconditions:• La liste contient un élément x de moins (le premier

rencontré), inchangée si x L• Exception

• aucune

• valeur retournée:• aucune

L L - x

• prototype: void enleverEl (TypeEl x);

/** * \brief EnleverEl dans la liste la première occurrence de x * * \post la liste comprend un élément de moins * \post la liste est inchangée si x à la liste * * */

dOxygen

Spécification du type liste: Li

• prototype: TypeEl elementListe(Liste l, int i, int *err);

• postconditions:• l est inchangée avec *Err = OK• l est inchangée et *Err = PERR si i [1,|L|]

• valeur(s) retournée(s):

• Une copie de Li si la précondition est respectée

• Une valeur quelconque sinon

• prototype: TypeEl elementPos(int i) throw(range_error);

• postconditions:• La liste est inchangée si i [1,|L|] • La liste est inchangée sinon

• Exception : • Si la position est erronée

• valeur(s) retournée(s):

• Une copie de Li si la précondition est respectée

• Une valeur quelconque sinon

• prototype: TypeEl elementPos(int i) throw(range_error);;

/** * \brief retourner l’élément en position i dans la liste * * \pre i est compris entre 1 et |L| * * \post la liste est inchangée * \post l’élément en position i est retournée, une valeur quelconque sinon * * \exception range_error si la position i est erronée * */

dOxygen

Implantation du type liste ordonnée

Implantation par tableau statique

La liste peut être implantée à l'aide d'un tableau. Dans ce cas, il faut prévoir une taille maximum pour le tableau. L'opération d'impression des éléments d'une liste et de recherche d'un élément se font en temps linéaire. La recherche du k-ième élément se fait O(1) i.e. en un temps constant. Cependant les insertions et les suppressions d'éléments sont plus coûteuses. Par exemple, l'insertion à la position 0 nécessite le déplacement de tous les éléments de la liste pour libérer la position 0.

Par conséquent la création d'une liste à l'aide de n insertions successives à partir de la position 0 nécessite un temps en O(n2) (pourquoi?).

Implantation par tableau

/******************************************************************** ModeleImplantationListe.h i.e. modèle d’implantation du type Liste ordonnée

Version 1.0 Janvier 2007

(c) IFT-10541 Structures de données

********************************************************************/#ifndef _LISTEC__H#define _LISTEC__H#define MAX_LISTE 100

typedef enum {FAUX, VRAI} Bool; /*le type booléen*/typedef int TypeEl; /* le type de base de la liste */typedef struct{

TypeEl tab[MAX_LISTE]; /* représentation physique de la liste */

int cpt; /* la cardinalité de la liste */} Liste; /* le type liste ordonnée */#endif

Implantation par tableauEn langage C

Création de listes

déclaration:• Liste L1, L2;

initialisation:• L1 = initListe(&err);• L2 = initListe(&err);

Liste initListe(int * err){

Liste l; /*A: L’espace mémoire est suffisant.*/

l.cpt = 0;*err = OK;return l;

En langage C

Destruction de listes

destruction:

• detruireListe(L1, &err);• detruireListe(L2, &err);

Liste detruireListe(Liste l, int * err){

return l;}

En langage C

Interface du type Liste

Interface d’un type abstrait (invariable)

/********************************************************************Liste.h i.e. interface du type Liste ordonnée

Version 1.0 Janvier 2007

(c) IFT-10541 Structures de données ********************************************************************/#include "ModeleImplantationListe.h"#define OK 0 /* tout est correct */#define LNI 1 /* liste non initialisée */#define PAM 2 /* pas assez de mémoire*/#define PERR 3 /* position erronée */

Liste initListe(int *err);/*****************************************************************prototype : Liste initListe(int *err)précondition : …etc..

En langage C

Implémentation/********************************************************************

Liste.c Version 1.0 Janvier 2007

(c) IFT-10541 Structures de données ********************************************************************/#include "Liste.h"Liste ajouterListe (Liste l, TypeEl x, int pos, int *err){/* objectif: ajouter l'élément x à la liste l en position pos

méthode: décaler vers la droite tous les éléments à partir de la fin de la liste,

jusqu'à ce que pos soit atteintbesoins: La liste l, l'élément x, l'indice d'insertion pos et MAX_LISTE,

la taille maximale de la listeconnu: MAX_LISTEentrée: l, x, possortie: La liste l mise à jour (si *err = OK), la liste l inchangée sinon.résultat: *err=OK si les pré sont respectées, PAM si pas assez de place,

PERR sila position est erronée

hypothèse: Pos est compris entre 1 et la taille de la liste + 1 (|L| + 1)inclusivement, il y a assez de place pour ajouter x.

En langage C

Implémentation

Liste ajouterListe (Liste l, TypeEl x, int pos, int *err){ …

if (l.cpt >= MAX_LISTE){

/* La liste est pleine. */*err = PAM;return l;

}/*A: La liste n'est pas pleine */

if ((pos < 1) || (pos > (l.cpt + 1))){

/* Les paramètre fournis sont invalides. */*err = PERR;return l;

/*A: pos >= 1 et pos <= taille de la liste + 1 */*err = OK;

//etc...return l;

En langage C

En langage C++……

D’abord, quelques différences entre C++ et C en ce qui concerne le cours

C• malloc(sizeof(float)*25)• free(x)• realloc(x,sizeof(float)*25);• typedef struct

{ // […]} MaStruct;void fonction(MaStruct *m,float x);

• Aucun équivalent pour « private: », il faut user de discipline.

• float f(float a, int x, int *err){ if(x<a) { *err=PROBLEME; return 0.0f; } // […]}

• int x;for(x=0;x<2;x++)

C++• new float[25]• delete x ou delete[] x• Pas d’équivalent pour « realloc »• struct MaStruct

{ void fonction(float x);};

• Possibilité de rendre des membres privés à l’aide de « private: »

• float f(float a, int x){ if(x<a) throw PROBLEME; // […]}

• for(int x=0;x<2;x++)

struct Nombres{

Nombres();void ajout(float nouv_nbr);// etc.

private:float x[100];int n;

typedef struct{

float x[100];int n;

} Nombres;CodeErreur initNombres(Nombres *n);CodeErreur ajoutNombres(Nombres *n , float nouv_nbr);// etc.

typedef enum { OK, Erreur } CodeErr;typedef struct{

int matricule,nb_cours,age;char nom[50];

} Etudiant;typedef struct{

Etudiant etudiants[40000];int n;

} Universite;CodeErr initUniversite(Universite *u);CodeErr ajoutUniversite(Universite *u,

Etudiant et);int trouve_age(const Universite *u,

int matricule);void detruitUniversite(Universite *u);

struct Etudiant{public:

int matricule,nb_cours,age;char nom[50];

};struct Universite{public:

Universite();void ajout(Etudiant et);int trouve_age(int matricule) const;~Universite();

private:Etudiant etudiants[40000];int nb_etudiants;

CodeErr initUniversite(Universite *u){

u->n=0;return OK;

}CodeErr ajoutUniversite(Universite *u, Etudiant

if(u->n==40000) return Erreur;u->etudiants[u->n++] = et;return OK;

}int trouve_age(const Universite *u,

int matricule){

int i;for(i=0;i<u->n;i++)

if(u->etudiants[i].matricule==matricule)

return u->etudiants[i].age;return -1; // Convention pour matricule introuvable.

}void detruitUniversite(Universite *u){}

Universite::Universite(){

n=0;}void Universite::ajout(Etudiant et){

if(n==40000)throw runtime_error(‘’L’université

est pleine!’’);etudiants[n++]=et;

}int Universite::trouve_age(int matricule) const{

for(int i=0;i<n;i++)

if(etudiants[i].matricule==matricule)return etudiants[i].age;

return -1; // Convention pour matricule introuvable.

}Universite::~Universite(){}

Encapsulation. struct (C) vs classe (C++)

//Fichier ModeleImplantationListe.h#ifndef _LISTEC__H#define _LISTEC__H#define MAX_LISTE 100typedef enum {FAUX, VRAI} Bool;

typedef struct{

int tab[MAX_LISTE];int cpt;

} Liste; #endif

//Fichier Liste.h#include "ModeleImplantationListe.h"#include "CodesErreur.h"

Liste initListe(int * err);/* */int tailleListe(Liste l, int *err);/* */Bool estVideListe(Liste l, int *err);/* */Liste ajouterListe(Liste l, int x, int pos, int *err);/* */// etc..

// Fichier Liste.h#include <iostream> using namespace std;

#ifndef _LISTEC__H#define _LISTEC__H#define MAX_LISTE 100

class Liste { private: int tab[MAX_LISTE]; int cpt; public: Liste(); //constructeur ~Liste(); //destructeur void ajouter (int x, int pos); int taille() const ; bool estVide() const; //etc…};#endif

Version de base

Note 1 Remarquez que le mot clé const est utilisé à la fin des déclarations de fonction membres de la classe Liste en mode lecture seule, à savoir taille () et estVide(). Afin de mieux protéger un programme, il y a tout intérêt à déclarer comme constantes les fonctions qui ne sont pas censées modifier l’état des objets auxquels elles sont liés. On bénéficiera ainsi d’une aide supplémentaire du compilateur qui empêchera tout ajout de code modifiant l’état de l’objet dans la fonction.

Implantation de la classe Liste en C++//Liste.cpp

#include "Liste.h"

Liste::Liste(){ cpt = 0;}

bool Liste::estVide() const{ return taille()==0;}

Liste:: ~Liste(){ cpt=0; //Note..}

int Liste::taille() const{ return cpt;}

#include "Liste.h "

void Liste::ajouter (int x, int pos){ if(cpt==MAX_LISTE) return;

if (pos < 1 || pos > taille() +1) return;

pos--; for (i = (cpt - 1); i >= pos; i--) {

tab[i+1] = tab[i]; }

tab[pos] = x; cpt++;

Utilisation de la classe Liste//Main.cpp

#include "Liste.h"

int main(){

Liste l; //appel automatique du constructeur

l.ajouter(1,1); l.ajouter(2,2); l.ajouter(3,3);

if(l.estVide()) cout << "liste vide" << endl;else cout << "liste non vide" << endl;

cout << l.taille() << endl;

l.~Liste(); //destruction de la liste, inutile…

// etc..

return 0;}

#ifndef _LISTEC__H#define _LISTEC__H

#include <iostream> using namespace std;

#define MAX_LISTE 5// Le type Listeclass Liste{ public: Liste(); //constructeur ~Liste(); //destructeur Liste(const Liste &); //constructeur de copie Liste& operator = (const Liste&); // surcharge de l’opérateur = void ajouter(int x, int pos); bool estVide() const; int taille() const; friend ostream& operator << (ostream&, const Liste& p); Liste& operator = (const Liste&);

private:int tab[MAX_LISTE]; int cpt;

};#endif

Définition de la classe Liste en C++ (version 2)

• Constructeur de copie • Surcharge op. =

Le constructeur par copie est une méthode implicite dans toute classe.

Cette méthode est appelée automatiquement dans les opérations suivantes :

Création et initialisation d ’une nouvelle instanceX I2=I1;X I2(I1);

passage d ’un argument par valeur retour d ’une fonction

return (I);// une copie de I est retournée

Constructeur de copie

class Liste {public :

Liste (const Liste&);// constructeur par copie...

Par défaut, cette méthode implicite réalise une copie des valeurs qui correspondent à la section private de la classe.

Si l ’implantation d ’un objet est dynamique le constructeur par copie, réalisera par défaut une copie de pointeur.

==> Surcharger cet opérateur afin qu’il crée un vrai clone de l ’instance qui le déclenche.

Liste :: Liste (const Liste& l) { cpt = l.cpt; for (int i=0; i<cpt;i+=1)

tab[i]=l.tab[i];

ostream& operator << (ostream& f, const Liste& l){ for (int i=0; i<l.cpt;i++)

f << l.tab[i]<<" "; return f;}

Implémentation (version 2)#include "Liste.h"

int main(){ //on crée une instance d'une liste Liste l;

l.ajouter(1,1); //ajout de 1 en pos =1 //...

//copie de l'appel du constructeur de copie Liste l1(l);

//Affichage de la copie cout << l1 << endl;

//... return 0;}

Surcharge de l’opérateur =

Liste l1;

L ’opérateur d ’affectation est une méthode implicite dans toute classe. Par défaut, il réalise une copie des valeurs qui correspondent à la section private de la classe.

2 5 8 3

l1.tab

l2.tab

Liste l2;

l2=l1;Problème : Toute

modification du tableau des entiers

dans la liste l1se répercute dans la liste

l2 (et inversement)

Liste l1;

Pour réaliser une vraie copie de pile par affectation, il fautsurcharger l ’opérateur implicite.

2 5 8 3

l1.tab

Liste l2;

l2=l1;

l2.tab

2 5 8 3

class Liste {public:

Liste operator = (const Liste&);// opérateur d ’affectation

Le comportement habituel de l’opérateur = autorise à enchaîner les affectations : l1=l2=l3;=> la fonction retourne une référence et l ’argument est une référence.

l1 = l2 <=> l1.operator = (l2);

Liste& operator = (const Liste&){ cpt = l.cpt; for (int i=0; i<cpt;i+=1)

tab[i]=l.tab[i];

return (*this);//retourner : une référence sur // ’objet courant}

Implémentation (version 2)#include "Liste.h"

int main(){ //on crée une instance d'une liste Liste l;

l.ajouter(1,1); //ajout de 1 en pos =1 //...

Liste l1; l1 = l; // appel de l’op. = surchargé

//Affichage de la copie cout << l1 << endl;

//... return 0;}

Surcharge de l’op. =

Forme canonique de Coplien

On dit qu'une classe est sous forme canonique de Coplien si elle contient les éléments suivants :

template <typename T>class Liste {public: Liste(const int = MAX_LISTE) throw(bad_alloc); // constructeur Liste(const Liste&) throw(bad_alloc);// constructeur de copie ~Liste(); // destructeur Liste<T>& operator = (const Liste<T>&) throw (bad_alloc); //surcharge de =

Remarque

On fera de sorte que toutes les classes que nous Implanterons auront ces méthodes au minimum.

#pragma warning( disable : 4290 )#define MAX_LISTE 5

#pragma warning( disable : 4290 )

// Le type Listeclass Liste{ public:

Liste(); //constructeur~Liste(); //destructeurListe(const Liste&); //constructeur de copievoid ajouter(int x, int pos) throw(int); // lancement d’un intbool estVide() const;int taille() const;friend ostream& operator << (ostream&, const Liste& p);

Liste& operator = (const Liste&);

private:int tab[MAX_LISTE];int cpt;

Définition de la classe Liste en C++ (version 3.1)

Gestion des exceptions Usage d’un int

void Liste::ajouter (int x, int pos) throw(int){ if (cpt==MAX_LISTE) throw 1;

if (pos < 1 || pos > this->taille() +1) throw 2 ;

//…}

Implémentation (version 3.1)

int main(){ Liste l;

try //on essaie un ajout{l.ajouter(1,1); l.ajouter(2,2); l.ajouter(4,8); // erreur..//…

} catch(int& code) { cerr << "ERREUR: " << code << endl;return 0;

} .... return 0;}

#include <iostream> using namespace std;#include <stdexcept>

Liste(); //constructeur~Liste(); //destructeurListe(const Liste&); //constructeur de copievoid ajouter(int x, int pos) throw(out_of_range, length_error); bool estVide() const;int taille() const;friend ostream& operator << (ostream&, const Liste& p);

Gestion des exceptions Usage d’une classe de la librairie stdexcept

void Liste::ajouter (int x, int pos) throw(out_of_range, length_error); {

if (cpt==MAX_LISTE) throw length_error("Ajouter:La liste est pleine");

if (pos < 1 || pos > this->taille() +1) throw out_of_range("Ajouter:Position d'ajout

erronée"); //…}

} catch(exception& e) { cerr << "ERREUR: " << e.what() << endl; return 0; } .... return 0;}

Liste(); //constructeur~Liste(); //destructeurListe(const Liste&); //constructeur de copievoid ajouter(int x, int pos) throw(Erreur); bool estVide() const;int taille() const;friend ostream& operator << (ostream&, const Liste& p);

Gestion des exceptions Usage d’une classe

Erreur

class Erreur: public exception{

public:Erreur(int numero=0,std::string phrase="", int niveau=0) throw()

:m_numero(numero),m_phrase(phrase),m_niveau(niveau){}

virtual const char* what() const throw(){ return m_phrase.c_str();} int getNiveau() const throw(){ return m_niveau;} int getNumero() const throw(){ return m_numero;}

virtual ~Erreur() throw(){}

private:int m_numero; //Numéro de l'erreurstring m_phrase; //Description de l'erreurint m_niveau; //Niveau de l'erreur

Suite..

void Liste::ajouter (int x, int pos) throw(out_of_range, length_error); {

if (cpt==MAX_LISTE) throw Erreur(1, «Ajouter:La liste est pleine", 2);

if (pos < 1 || pos > this->taille() +1) throw Erreur(2, « Ajouter: Position d'ajout

erronée",2); //…}

} catch(const Erreur& e) { cerr<< "ERREUR: "<< e.what()<<endl; cerr<<"Niveau: "<<e.getNiveau()<<endl; cerr <<"Numero: "<<e.getNumero()<<endl; return 0; } .... return 0;}

Note 2 Il faut savoir que vous n'êtes pas le seul à lancer des exceptions. Certaines fonctions standards lancent elles aussi des exceptions. Toutes les exceptions lancées par les fonctions standards dérivent de la classe exception, ce qui permet avec un code générique de rattraper toutes les erreurs qui pourraient potentiellement arriver.

Exemple:

catch(const std::exception& e){ std::cerr << "ERREUR: " << e.what() << std::endl;}

Ceci est possible grâce au polymorphisme. On attrape un objet de type std::exception, mais grâce aux fonctions virtuelles et à la référence (les deux ingrédients), c'est la fonction what() de la classe fille qui sera appelée, ce qui est justement ce que l'on souhaite. :)

Gestion des exceptions

La bibliothèque standard peut lancer 5 types d'exceptions différents résumés dans le tableau suivant :

Nom de la classe Descriptionbad_alloc Lancée s'il se produit une erreur lors d'un new.

bad_cast Lancée s'il se produit une erreur lors d'un dynamic_cast. (On verra plus tard ce que c'est)

bad_exception Lancée si aucun catch ne correspond à un objet lancé.

bad_typeid Lancée s'il se produit une erreur lors d'un typeid.(On verra plus tard ce que c'est)

ios_base::failure Lancée s'il se produit une erreur avec un flux.

Note 3

Le fichier stdexcept contient 9 classes d'exceptions séparées en 2 catégories, les exceptions "logiques" (logic errors) et les exceptions "d'exécution" (runtime errors).

Toutes les exceptions présentées dérivent de la classe std::exception et possèdent un constructeur prenant en argument une chaîne de caractère permettant de décrire le problème.

#include <stdexcept>

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. Par exemple si la classe Pile vue précédemment a une taille dépassant la taille de la mémoire.out_of_range logique Lancée si il y a une erreur avec un indice. Par exemple si on essaye d'accéder à une case inexistante d'un tableau.logic_error logique Lancée lors de n'importe quel autre problème de logique du programme.range_error exécution Lancée lors d'une erreur de domaine à l'exécution.overflow_error exécution Lancée si il y a une erreur d'overflow.underflow_error exécution Lancée si il y a une erreur d'underflow.runtime_error exécution Lancée pour tout autre type d'erreur non-prévue survenant à l'exécution.

Sinon, vous ne savez pas quoi choisir, prenez simplement runtime_error.

#include <stdexcept> suite..

Programmation générique

La classe Liste de tout à l’heure se présentait comme suit :

class Liste{ public:

private:int tab[MAX_LISTE];…

Si l’on veut une liste de double?

+ c’est exactement le même code saufqu’il faut remplacer le type de la données pouvant être stockéedans un tableau + duplication de code !!

Introduction

Définition de la classe Liste en C++ (version 4) #include <iostream>

using namespace std;#pragma warning( disable : 4290 )

template <typename T>class Liste{ public:

Liste(); //constructeur~Liste(); //destructeurListe(const Liste&); //constructeur de copievoid ajouter(T x, int pos)throw(out_of_range, length_error);bool estVide() const;int taille() const;friend ostream & operator << (ostream & f, const Liste & l){

for (int i=0; i<l.cpt;i++) f << l.tab[i]<<" ";return f;

private:static const int MAX_LISTE = 5; //Remplace le #define MAX_LISTET tab[MAX_LISTE]; int cpt;

};#include "Liste.inl"

Liste générique

#define MAX_LISTE 5

template <typename T>class Liste{ public:

Liste(); //constructeur~Liste(); //destructeurvoid ajouter(T x, int pos)throw(out_of_range,

length_error);

private:T tab[MAX_LISTE]; int cpt;

Paramètre génériqueFormel

template <typename T, in max = 100>class Liste{ public:

Liste(); //constructeur~Liste(); //destructeurvoid ajouter(T x, int pos)throw(out_of_range,

length_error);//…

private:T tab[max]; int cpt;

Paramètres génériquesFormels

#include "Liste.h"

template <typename T>Liste<T>::Liste(){

cpt = 0;}

template <typename T>bool Liste<T>::estVide() const{

return taille()==0;}

template <typename T>void Liste<T>::ajouter (T x, int pos) throw(out_of_range, length_error){

…this->tab[pos] = x;this->cpt++;

Implémentation (version 4)

Liste.inl

Utilisation de la classe Liste générique

int main(){

Liste<int> l; // ou Liste<int, 100>

try{l.ajouter(1,1); //ajout de 1 en pos =1l.ajouter(2,2); //ajout de 2 en pos =2l.ajouter(3,3); //ajout de 3 en pos =3l.ajouter(4,8); //erreur, position erronéel.ajouter(4,1); //ajout de 4 en pos =1l.ajouter(5,3); //ajout de 5 en pos =3l.ajouter(6,6); //erreur, liste pleine

}catch(exception &e){

cerr << "ERREUR: " << e.what() << endl;return 0;

Paramètre génériqueeffectif

• il faut prévoir le pire cas• si grandes fluctuations gaspille d’espace• limitation majeure en ajout d’éléments

• besoins variables?

Limitations d’une implantation par tableau

allocation dynamique (de mémoire)Utilité des pointeurs et objets pointéesCours de la semaine prochaine

private : int cpt;

T tab[max]; // implantation dans un tableau}; // statique

Structures de données IFT-2000 Abder Alikacem Types de données abstraits (2) Semaine 1...

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

Structures de données IFT-2000 Abder Alikacem Semaine 12 (2 ième partie) Les B-arbres Département d’informatique et de génie logiciel Édition septembre

Structures de données IFT-2000 Abder Alikacem Les graphes Semaine 5, suite et fin… Département dinformatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-2000 Abder Alikacem Les graphes (3) Semaine 7 Département dinformatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-2000 Abder Alikacem Arbres de recouvrement minimum Département dinformatique et de génie logiciel Édition Septembre 2009 JFK

Structures de données IFT-10541 Abder Alikacem Du C au C++ Département dinformatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-2000 Abder Alikacem La récursivité Département d’informatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-10541 Abder Alikacem Trace de l’algorithme de Dijkstra Département d’informatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-10541 Abder Alikacem Semaine 7 Les algorithmes de recherche Département dinformatique et de génie logiciel Édition septembre

Structures de données IFT-2000 Abder Alikacem Les graphes Semaine 5 Département dinformatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-2000 Abder Alikacem Semaine 12 Les arbres rouges et noir Département dinformatique et de génie logiciel Édition septembre 2009

Structures de données IFT-10541 Abder Alikacem Introduction au langage C++ Département d’informatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-10541 Abder Alikacem Programmation orienté objet en C++ Module 2 Département dinformatique et de génie logiciel Édition Septembre

Structures de données IFT-2000 Abder Alikacem Introduction Semaine 1 Département d’informatique et de génie logiciel Édition Septembre 2009

Programme de baccalauréat en informatique Algorithmique et programmation IFT-17582 Abder Alikacem Abder Alikacem Semaine 13 La récursivité Département

Structures de données IFT-10541 Abder Alikacem Les piles Département dinformatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-2000 Abder Alikacem Les structures de piles et de files Département dinformatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-2000 Abder Alikacem Les graphes (1) Semaine 6 Département dinformatique et de génie logiciel Édition Septembre 2009

Structures de données IFT-2000 Abder Alikacem Retour sur les listes ordonnées Département dinformatique et de génie logiciel Édition Septembre 2009

Programme de baccalauréat en informatique Algorithmique et programmation IFT-17582 Abder Alikacem Abder Alikacem Semaine 3 Bâtir un algorithme Département