View
48
Download
1
Category
Preview:
DESCRIPTION
Leçon 6 : Structures de données dynamiques. IUP 2 Génie Informatique Méthode et Outils pour la Programmation Françoise Greffier. Structures de données dynamiques. Notion de conteneur Généricité Implantation dynamique d ’une pile surcharge de l ’opérateur = - PowerPoint PPT Presentation
Citation preview
Leçon 6 : Structures de données dynamiques
IUP 2 Génie Informatique
Méthode et Outils pour la Programmation
Françoise Greffier
Structures de données dynamiques
Notion de conteneurGénéricitéImplantation dynamique d ’une pile
surcharge de l ’opérateur = surcharge du constructeur par copie
Implantation : chaînage arrière
Des structures de données classiques
Exemples : liste, pile, file attente, arbres, graphes ...
Exemples :Une liste d’étudiants, de notes, de courses
Il existe des algorithmes classiques associées à ces structures de données : parcours, insertion, suppression ...
La bibliothèque standard (Standard Template Library : STL) fournit au programmeur des classes prédéfinies qui offrent :• des structures de données classiques• associées à leurs opérations classiques
Conteneur
Un conteneur est une classe très générale modélisant une collection d’éléments
de n’importe quel type.
Il existe deux grandes catégories de conteneurs :• les séquences• les conteneurs associatifs
Les opérations de base y sont incluses :- ajouter un élément (insert)- supprimer un élément (erase)- sélecteur vide? (empty) etc ...
Les conteneurs modélisants des structures de données classiques (liste, pile, file d ’attente, graphe …) sont implantées en bibliothèque.
Des composants réutilisables
http://www.sgi.com/tech/stl/
Les séquences
On distingue trois séquences : vector (tableau)list (liste) et deque (suite circulaire)
Une séquence est un conteneur dans lequel les éléments sont organisés linéairement (il y a un premier, un suivant … , un dernier).
Les classes
vector, list et deque se distinguent par les opérations d ’accès et par un compromis entre les coûts des accès, insertions et suppressions.
vector<int> v(3); // Declare a vector of 3 elements.
v[0] = 7; v[1] = v[0] + 3; v[2] = v[0] + v[1]; // v[0] == 7, v[1] == 10, v[2] == 17
reverse(v.begin(), v.end()); // v[0] == 17, v[1] == 10, v[2] == 7
Les séquences : un exemple Conteneur : vector
Les séquences : types abstraits
Les classes (conteneur) :
- pile : stack- file d ’attente : queue- file d ’attente prioritaire : priority_queue
A partir des séquences de base, on dérive trois types abstraits : pile, file d ’attente et file d ’attente prioritaire.
Les conteneurs associatifs
Contrairement aux séquences, les conteneurs associatifs peuvent identifier leurs éléments par la valeur d ’une clé. Cette clé a parfois pour valeur une partie de la valeur de l ’élément.
Ces conteneurs sont particulièrement adaptés dans des applications où l ’on doit rechercher des éléments connaissant leur clé.
Un conteneur associatif offre la possibilité de rechercher rapidement les éléments mémorisés par leur clé.
Les conteneurs associatifs
Ces conteneurs sont « paramétrés » avec le type de la clé correspondant. .
Opérations sur les clés :recherche : find (complexité logarithmique)Comptage selon la clé : count
On doit avoir une relation d ’ordre total sur les clés
Les conteneurs associatifs
On trouve quatre conteneurs associatifs• set : clé = valeur de l ’élément• multiset : set avec occurrences multiples• map : élément = (clé,v)•multimap : map avec occurrences multiples sur clé
Opérations utilisant les clés :recherche : find (complexité logarithmique)Comptage selon la clé : count
Conteneur pile
Nous étudions dans ce chapitre le conteneur : pile• Spécification• Implantation
Un conteneur est un objet contenant d ’autres objets
Une pile
A une pile sont associées 4 opérations qui la caractérisent
Empiler un composant Dépiler
Consulter(sommet)
Vrai oufaux
Sélecteur vide(état)
Valeur placée ausommet
FINALEMENT :Une pile permet de traiter
des composants dans l ’ordreinverse de leur apparition
La classe pileclass pile{ public :pile(void); // constructeur ~pile(void); // destructeur
// IC non vide X& sommet (void); // Sélecteur => valeur placée au sommet de IC bool vide(void); // Sélecteur => (IC vide?)
void empiler(const X&);// x est ajouté au sommet de IC
// IC non vide void depiler(void); // composant placé au sommet est suppriméprivate : … };
Réutilisabilité
On cherche à écrire des objets réutilisables.
On aimerait concevoir une classe qui modélise une pile de portée générale : une pile n’importe quels composants.
==> Concevoir une classe générique
pile<char> Pcar;
pile <personne> Ppersonne;
Facteurs de qualité d ’un logiciel
Réutilisabilité
Possibilité d ’obtenir toutes les occurrences d ’une classe s ’appliquant à différents types, en ne décrivant qu’une seule fois la classe.
Une classe décrit une famille d ’objets :• Cohérente• Lisible• Extensible• Réutilisable
template en C++Le mot clé template permet l ’écriture de fonctions génériques ou de classes génériques.template <class X>class pile{ public :pile(void); // constructeur
void empiler(const X&);// x est ajouté au sommet de IC
private : int taille; X* t;//si implantation dans un tableau de X}; //t est un tableau dynamique
Paramètre génériqueFormel
void main (void) { pile <char> Pcar;char* ch;ch=new char[20];cout << "\n entrez une chaîne :"; cin >> ch;int l=length(ch);for (int i=0;i<l;i+=1)
Pcar.empiler(ch[i]);//==============================cout << "\n Chaîne inversée :";while (!Pcar.vide()) {
cout << Pcar.sommet();Pcar.depiler(); }
delete [ ] ch;}
Utilisation d ’une classe génériqueParamètre générique
effectif
Le paramètre générique effectif d ’une classe peut être un identificateur de type prédéfini ou un identificateur de classe.
Les paramètres
Une classe générique peut avoir plusieurs paramètres.Syntaxe :template <class A, class B>
Les paramètres
template <class X, int max=100>class pile{ public : ...// IC non vide X sommet (void); // Sélecteur => valeur placée au sommet de IC
void empiler(const X&);// x est ajouté au sommet de IC
private : int taille;X T[max]; // si implantation dans un tableau}; // statique
Les paramètres peuvent avoir des valeurs par défaut
void main (void) { pile <char,20> Pcar;//pile de 20 caractères maximum
pile <personne> PPersonne;//pile de 100 personnes maximum
...}
Utilisation d ’une classe générique
template <class X >
X min (const X& A,const X& B){if (A<B) return(A);return (B);}
Exemple de fonction générique
void main (void){int i,j,m;cin >> i,j;int m=min <int>(i,j);...}
L ’opérateur < doit être surchargé dans les classes quiutiliseront le modèle min
Le compilateurinstancie une fonctionint min (const int&, const int&)
Implantation de la classe pile
Implantation dans un tableau statique
private : int taille;X T[max]; // si implantation dans un tableau}; // statique
pbs : Evaluation de maxLimite de la mémoire statique
==> gestion dynamique
Implantation de la classe pile
Implantation dans un tableau dynamique
private : int taille;X* t; // si implantation dans int maximum; }; // un tableau dynamique
Tableau t réservé dans le tas
Constructeur avec un paramètre : taille maximum
==> bonne implantation si on peut évaluer la taille maximum à l’utilisation de la pile
Utilisation de la pile
void main (void) { pile <char> Pcar(25);
char* ch;ch=new char(26);cout << "\n entrez une chaîne :"; ...}
Implantation de la pile# include <iostream.h>template <class X>class pile {public:
pile (int);// constructeur : init taille maxi
... ~pile (void); // destructeur
private : X* t; // si implantation dans int indexSommet; // un tableau dynamiqueint maximum;};
Implantation de la pile
template <class X>pile<X> :: pile (int max) {
t = new X [max];indexSommet = -1;maximum =max;
}
template <class X>pile<X> :: ~pile (void) { if (t!=NULL) delete [ ] t;}
Constructeur
Destructeur
Implantation de la pile
template <class X>void pile<X> :: depiler(void){
if (!vide())indexSommet -= 1;}
template <class X>bool pile<X> :: vide (void){
return (indexSommet == -1);}
dépiler
Sélecteur : vide
Implantation de la pile
template <class X>void pile<X> :: empiler(const X& e){
if (indexSommet+1 < maximum){ indexSommet += 1;
t[indexSommet] = e;}
}
empiler
Remarque : on suppose que l ’opérateurd ’affectation existe ou est surchargé dans La classe qui correspond au paramètre X.
=> intérêt de la surcharge des opérateurs
pile<char> p1;
...
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.
A V E C
p1.t
p2.tpile<char> p2;
p2=p1;
Problème : Toute modification du tableau
des caractères empilés dans la pile p1
se répercute dans la pilep2 (et inversement)
Surcharge de l’opérateur d’affectation
Surcharge de l’opérateur d’affectation
pile<char> p1;
...
Pour réaliser une vraie copie de pile par affectation, il fautsurcharger l ’opérateur implicite.
A V E C
p1.t
pile<char> p2;
p2=p1;
p2.t
A V E C
Surcharge de l’opérateur d’affectation
template <class X>class pile {public:
pile<X>& operator = (const pile<X>&);// opérateur d ’affectation
Le comportement habituel de l’opérateur = autorise à enchaîner les affectations : p1=p2=p3;=> la fonction retourne une référence et l ’argument est une référence.
p1 = P2 <=> p1.operator = (p2);
Implantation
template <class X>pile<X>& pile<X> :: operator = (const pile<X>& p) { if (t!=NULL) delete [ ] t; //on nettoie this
t=new X [p.maximum];
maximum=p.maximum;for (int i=0; i<maximum;i+=1)
t[i]=p.t[i];indexSommet=p.indexSommet;
return (*this);//retourner : une référence sur l ’objet courant}
Le constructeur par copie est une méthode implicite dans toute classe.
Surcharge du constructeur par copie
Cette méthode est appelée automatiquement dans les opérations suivantes : Création et initialisation d ’une nouvelle instance
X I2=I1;X I2(I1);
passage d ’un argument par valeur retour d ’une fonction
return (I);// une copie de I est retournée
Surcharge du constructeur par copie
Prototype :class C {public :
C (const C&);// 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 clône de l ’instance qui le déclenche.
Implantation
template <class X>pile<X> :: pile (const pile<X>& p) { t=new X [p.maximum];
maximum=p.maximum;for (int i=0; i<maximum;i+=1)
t[i]=p.t[i];indexSommet=p.indexSommet;
}
Implantation de la classe pile
Implantation par chaînage de cellules
A NULL
V
E
C P.PtrSommet
A NULL
V
E P.PtrSommet
P.depiler( )
Implantation de la classe pile
Les conteneurs doivent-ils stocker nécessairement des composants ou des pointeurs sur les composants ?
Quand le conteneur stocke les composants, et que ceux-ci sont homogènes, alors les données peuvent être recopiées dans la structure. Cette gestion est simplifiée.
Exemple : une pile d ’entiers 8591
Implantation de la classe pile
Quand le conteneur stocke des pointeurs sur les composants :
On peut stocker des données non homogènes.
On évite les copies multiples des données (intéressant si la taille du composant est importante) .
La gestion des composants (création, destruction est à la charge du programmeur).
Les conteneurs doivent-ils stocker nécessairement des composants ou des pointeurs sur les composants ?
Exemple : une pile de nombres 81/59+3i3,1416
Un nombre peut être un entier,un réel, un complexe, un rationnel.
# include <iostream.h>template <class X>class cellule{public:cellule(X*, cellule< X>*);//constructeur~cellule (void); //destructeur X composant (void); //sélecteur => valeur du composant
};
Classe cellule
friend class pile <X>;private :
X* ptr;cellule<X> * ptrprec;
template <class X> class pile {public: pile (void); // IC vide est créée
pile (const pile<X>&); // Constructeur par copie
~pile (void); // IC est détruite
pile<X>& operator=(const pile<X>& P); // IC = P
void empiler (const X& a); // a est empilé dans IC //IC non vide
void depiler (void); // l'élément placé au sommet de IC est supprimé //IC non vide
X& sommet (void); // sélecteur : valeur placée au sommet
bool vide(void); //sélecteur : ( IC est vide?)
};
Classe pile
private :cellule<X>* ptrSommet; // pointeur sur la cellule sommet
Implantation de la classe pile
template <class X>pile<X>::pile (void){ ptrSommet = NULL;}
template <class X>pile<X>:: ~pile(void){ if (ptrSommet != NULL) detruire( );}
template <class X>void pile<X>::detruire (void) {
cellule<X>* p;while (ptrSommet != NULL){
p=ptrSommet->ptrprec;delete (ptrSommet);ptrSommet=p;}
}
constructeur
destructeur
Implantation de la classe pile
//IC void detruire (void); //détruire toutes les cellules de la pile IC
template <class X>cellule<X>:: ~cellule (void){ if (ptr!=NULL) delete ptr;}
Pour que l ’espace occupé par les composants pointés dans chaque cellule soit libéré lorsque la fonction détruire est appliquée, il faut que le destructeur de cellule ait cet effet :
Chaque fois que l ’instruction delete est appliquée sur un pointeur de cellule, alors le destructeur de la classe cellule est activé.Libère l ’espace occupé par le
composant pointé par ptr
Recommended