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

Structures de donnéesIFT-2000

Abder AlikacemAbder Alikacem

Retour sur les listes ordonnées

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

Édition Septembre 2009

! +

Plan

Retour au type abstrait liste ordonnée, implantation par: des tableaux dynamiques des listes simplement chaînées des listes doublement chaînées des listes circulaires (anneaux)

Retour aux structures de données génériques

Retour à la gestion des exceptions

Allocation de mémoire

structure simple Un tableau séquentialité des adresses

faciles à gérer

Les tableaux un inconvénient important.

Spécification de sa taille

Solution: l’allocation dynamique de la mémoire

• Un tableau alloué du monceau (tas ou heap)• Taille décidé par l’utilisateur

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

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

template <typename T>class Liste {public:

//…private:

int tailleMax; // taille maximum de la listeint cpt; // cardinalité de la listeT * tab; // tableau "dynamique" contenant les éléments de la liste

} ;

#include "Liste.inl"

Liste ordonnée

Implantation dans un tableau dynamique

Implantation dans un tableau dynamique

private : int tailleMax; int cpt;T* tab; // implantation dans un tableau

dynamique };

Tableau tab 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

Liste ordonnée

Gestion du tableau dynamique

Il faut donc modifier le constructeur d’une liste:• allouer un tableau sur le tas et dont le pointeur sera assigné à au

membre privé tab.

template <typename T>Liste<T>::Liste (int max)

throw(bad_alloc) {

tailleMax=max;cpt = 0;tab = new T [tailleMax];

}

Le destructeur de la liste :• Libération de l’espace du tableau pointé par tab

template <typename T>Liste<T>::~Liste () // Destructeur{

delete [] tab ;cpt = tailleMax = 0;

}

Constructeur

Destructeur


Il ne faut pas oublier le constructeur de copie:• allouer un tableau sur le tas et dont le pointeur sera assigné

à au membre privé tab puis copier de l’instance source

template <typename T>Liste<T>:: Liste(const Liste<T>& source) throw

(bad_alloc): tailleMax(source.tailleMax){

cpt= source.cpt;tab = new T [tailleMax];for (int position =0; position < source.cpt; ++position)

tab[position]= source.tab[position];}

Constructeur de copie


et la surcharge de l’opérateur = • allouer un tableau sur le tas et dont le pointeur sera assigné

à au membre privé tab puis copier de l’instance source, ne pas oublier de nettoyer…

template <typename T>Liste<T>& Liste<T>::operator = (const Liste<T>& l) throw(bad_alloc)

{if (tab!=0) delete [] tab; //nettoyer ...tab=new T [l.tailleMax];for (int i=0; i< l.cpt; i++)

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

return (*this);}

Surcharge de l’opérateur =

Les listes ordonnées

Une approche traditionnelle par rapport à l’usage de tableaux pour

implanter une liste est à travers l’utilisation des pointeurs. Cette approche fait en sorte que la mémoire est allouée d’une manière dynamique dans le sens que les cellules mémoire sont allouées au besoin. Les éléments d’une liste seront tout simplement chaînés entre eux. Il existe plusieurs types de listes chaînées dépendant de la manière dont on se déplace dans la liste :

1. les listes chaînées simples,2. les listes doublement chaînées,3. les listes circulaires.

Implantation par une liste chaînée

Pourquoi les listes chaînées

Les tableaux sont un type de données très utile en programmationmais présentent 2 limitations :

1. Les données sont contiguës (les unes derrières les autres) et donc l’insertion d’un nouvel élément au milieu du tableau demande la recopie (le décalage) de tous les éléments suivants.

=) insertion en O(n)

2. Augmenter la taille (par exemple si elle n’est pas connue a priori) nécessite la création d’un nouveau tableau

=) O(n)

3. Les éléments doivent être placés de façon contigüe (dans un seul gros bloc) en mémoire, ce qui fait qu’on ne peut pas « remplir les trous » en mémoire.


C’est la liste de base dont chaque élément appelé noeud contient deux

parties :1. une partie contenant l’information proprement dite2. et une partie appelée pointeur qui lie le noeud au noeud suivant.

Implantation dans une liste chaînée

Implantation :

• Les tableaux

• Les listes chaînées.

Représentation :

• inclure dans chaque nœud un pointeur sur le nœud qui le suit logiquement (mais pas nécessairement physiquement).


Le noeud étant un objet distinct, il est intéressant de définir une classe pour les nœuds (classe Noeud).

La classe Noeud contient deux constructeurs, un qui prend une valeur initiale pour la partie information et l’autre non. Elle contient également un destructeur qui ne fait rien de spécial.

Il est facile de voir les opération d’insertion et de suppression se font en un temps constant (O(1)) puisqu’elles consistent essentiellement en des mises à jour de pointeurs.




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



#ifndef LISTE_H#define LISTE_H#include "Noeud.h"#pragma warning( disable : 4290 )


Liste(){debut = 0;} // constructeur~Liste(); // destructeurvoid ajouter(T x, int pos) throw();int taille() const;bool appartient(T x,) const;

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>int Liste<T>:: taille() const{ elem ptr; //Pour parcourir la liste int compte(0); //Pour compter les pointeurs non nuls

ptr = debut;

while (ptr != 0) {

compte++;ptr = ptr->suivant;

}

return compte;

}

taille() // taille de la liste


template <typename T>bool Liste<T>:: appartient(T& x) const{ elem courant = debut;

while (courant!=0) {

if (courant->el == x) return true;courant = courant->suivant;

}

return false;}

appartient() // recherche


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 Noeudnouveau->suivant = 0;

//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(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); debut->suivant = 0;

// 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;nouveau->suivant = 0;

} nouveau->suivant = 0;

}catch(exception&){ //suite dans la prochaine diapositive



catch(exception&){ //suite dans la prochaine diapositive //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; }

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

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

Les listes

Remarque

La liste doublement chaînée peut être implantée de la même façon que la liste simplement chaînée. La partie publique reste inchangée. Cependant, les fonctions d’insertion, suppression et les différents constructeurs sont à redéfinir.

Les autres fonctions sur les listes chaînées simples peuvent être utilisées sans changement dans le cadre des listes doublement chaînées.

Liste doublement chaînée

Exemple d’une gestion des 2 pointeurs de chaînage

SG = new … SG= sommetG

SG precedent = 0 SD= sommetD

SG item = info

SD = SG et Demander info

Tant que info sentinelle

debut

SD suivant = new …

SD suivant precedent = SD

SD = SD suivant

SD item = info

Demander info

fin

SD suivant = 0


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 P :

……

P

N



Nsuivant = PsuivantPsuivantprecedent = NPsuivant = NNprecedent = P

……

P

N



NNsuivant = Psuivant = PsuivantsuivantPsuivantprecedent = NPsuivant = NNprecedent = P

……

P

N



Nsuivant = PsuivantPPsuivantsuivantprecedent = Nprecedent = NPsuivant = NNprecedent = P

……

P

N



Nsuivant = PsuivantPsuivantprecedent = NPPsuivant = Nsuivant = NNprecedent = P

……

P

N



Nsuivant = PsuivantPsuivantprecedent = NPsuivant = NNNprecedent = Pprecedent = P

……

P

N



Nsuivant = PsuivantPsuivantprecedent = NPsuivant = NNprecedent = P

……

P

N


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

…

P

N

…



sommetDsuivant = NNprecedent = sommetDsommetD = NNsuivant = 0

…

P

N

…



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

…


Ajouter un élément• Ajouter N avant le sommet gauche :

…

P

N

…



Nsuivant = sommetGsommetGprecedent = NsommetG = NNprecedent = 0

…

P

N

…



NNsuivant = sommetGsuivant = sommetGsommetGprecedent = NsommetG = NNprecedent = 0

…

P

N

…



Nsuivant = sommetGsommetGsommetGprecedent = Nprecedent = NsommetG = NNprecedent = 0

…

P

N

…



Nsuivant = sommetGsommetGprecedent = NsommetG = NsommetG = NNprecedent = 0

…

P

N

…



Nsuivant = sommetGsommetGprecedent = NsommetG = NNNprecedent = 0precedent = 0

…

P

N

…



Nsuivant = sommetGsommetGprecedent = NsommetG = NNprecedent = 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 après P

……

P



N = PsuivantPsuivant = PsuivantsuivantPsuivantprecedent = PNsuivant =0Nprecedent = 0delete N N = 0

……

P

N



N = PN = PsuivantsuivantPsuivant = PsuivantsuivantPsuivantprecedent = PNsuivant = 0Nprecedent = 0delete NN = 0

……

N

P



N = PsuivantPPsuivantsuivant = P = PsuivantsuivantsuivantsuivantPsuivantprecedent = PNsuivant = 0Nprecedent = 0delete NN = 0

……

N

P



N = PsuivantPsuivant = PsuivantsuivantPPsuivantsuivantprecedentprecedent = P = PNsuivant = 0Nprecedent = 0delete NN = 0

……

N

P



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

……

N

P



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

……

N

P


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

…



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

…

N

…



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

…


Supprimer un élément• Supprimer le sommet droit

• Le même algorithme que pour supprimer le sommet gauche, mais en échangeant les rôles des pointeurs precedent et suivant et en remplaçant sommetG par sommetD.


Implantation dans une liste circulaire (anneau)

Une liste où le pointeur NULL du membre suivant dernier élément est remplacé par l’adresse du premier élément est appelée liste circulaire.

Dans une liste circulaire tous les noeuds sont accessibles à partir de n’importe quel autre noeud. Une liste circulaire n’a pas de premier et de dernier noeud. Par convention, on peut prendre le pointeur externe de la liste vers le dernier élément et le suivant serait le premier élément de la liste.

Une liste circulaire peut être simplement chaînée ou doublement chaînée. Notez que la concaténation de deux listes circulaires peut se faire sans avoir à parcourir les deux listes.

Implantation par une liste circulaire

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

. . .

Manipulations :• L’insertion, la suppression et le défilement des anneaux sont très similaires à

ceux que nous avons vus pour les chaînes linéaires.• Il ne faut pas oublier de mettre correctement à jour le pointeur dernier dans les

opérations d'insertion ou de suppression en fin d’anneau.• Lors d’une insertion après un élément donné, il faut tester si l'insertion s'est faite en

"fin d'anneau" pour ajuster le pointeur dernier.

Listes circulaires (les anneaux)

Caractéristiques :• Un article particulier est accessible depuis un article quelconque.• La chaîne n'a ni début ni fin.• Le premier élément est égal au pointeur dernier‑>lien.• L'emploi d'une liste circulaire présente cependant un inconvénient majeur : il faut

faire attention de ne pas créer des boucles infinies.• Ces boucles sont possibles si l'on néglige la détection correcte de la fin de

parcours.• Une façon de faire consiste à associer l'existence de toute liste circulaire avec la

présence obligatoire d'un article spécial appelé tête de liste ou élément de tête.

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

} ;

Anneau bidirectionnel

Sommet

…

Listes circulaires (les anneaux)

L’implantation de la liste par tableau impose le choix d’une taille maximum de la liste. Beaucoup d’espace risque d’être inutilisé. Dans le cas de l’implantation par liste chaînée, l’espace est alloué uniquement aux éléments qui appartiennent effectivement à la liste.

Dans le cas de l’implantation par tableau aucune mémoire supplémentaire n’est nécessaire pour stocker un élément de la liste. Dans le cas de liste chaînée, un espace pour le pointeur est ajouté pour chaque élément de la liste.

L’accès à un élément par sa position est plus rapide dans le cas de l’implantation par tableau, il se fait en un temps constant (O(1)). Dans le cas de la liste chaînée, nous devons parcourir la liste du début jusqu’à la position désirée (O(n)).

Les insertions et les suppressions d’éléments sont plus coûteuses dans le cas dans l ’implantation par tableau car elles nécessitent des déplacements d’éléments.

Comparaison des implantations de la liste

Liste avec tableau:1. Insertion et suppression sont O(n).2. Précédent et accès direct sont O(1).3. Tout l’espace est alloué à l’avance.4. Pas d’espace autre que les valeurs.

Liste dans une liste chaînée:1. Insertion et suppression sont O(1).2. Précédent et accès direct sont O(n).3. L’espace augmente avec la liste.4. Chaque élément requiert de l’espace pour les pointeurs

Comparaison des implantations de la liste

Ce que j’ai appris aujourd’hui!

Les bases de la formalisation des données : les structures de données

abstraites

La structures de données abstraites la plus utilisée en informatique (en plus des tableaux et des types élémentaires) : les listes.

A pouvoir faire des modèles génériques de traitements ou de classes, indépendamment du type, ce que l’on appelle de la programmation

générique.

Comment déclarer de tels modèlesComment en créer des instancesComment spécialiser certains modèles

Documents

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