CodeS-SourceS
Rechercher un code, un tuto, une réponse

Création d'un conteneur c++ : liste chainee

Soyez le premier à donner votre avis sur cette source.

Vue 26 812 fois - Téléchargée 927 fois

Description

Ceci est un exercice de style :
Pour respecter le principe de réutilisation, il est bien entendu recommandé d'utiliser
autant que possible les conteneurs de la "STL", ainsi que ses Algorithmes et Fonctions

L'objectif de cet article est de créer un conteneur d'éléments
Les éléments seront de types quelconques (utilisation des Templates)
Il devra être pratique et efficace pour les opérations suivantes :
- créer un nouveau conteneur
- ajouter un nouvel élément - à la fin ou derrière un élément donné
- retirer un élément au conteneur
- parcourir les éléments en vue de les afficher ou d'effectuer toute autre opération dessus
- rechercher un élément par sa valeur
- compter les éléments
- vider le conteneur
Les fuites mémoires devront être évitées

"PARTIE I:"
Création d'un conteneur à simple chaînage sur des int
Accepte des insertions
"PARTIE Ibis:"
Accepte l'opération Compte() qui renvoie le nombre d'éléments
"PARTIE II:"
Création d'un conteneur à double chaînage sur des int
Accepte des insertions et des destructions
"PARTIE III:"
Refactoring et Factorisation du code
"PARTIE IV:"
Généricité : un conteneur valide pour tous les types de valeurs

Source / Exemple :


#include <iostream.h>
namespace vieuxLion
{
class Liste;//déclaration forward nécessaire pour "friend"

/* "PARTIE I: "
On commencera par choisir la liste chaînée comme support
Elle est meilleure que le simple tableau pour les insertions et suppressions
Dans cette première partie, on raisonnera avec le type 'int' pour les valeurs des éléments

On créera une classe Element dont le rôle est de supporter la valeur ET les chaînages avant et arrières
sur les éléments suivant et précédent
L'élément suivant sera utilisé pour le parcours de la liste (en avant)
L'élément précédent sera utile en cas de destruction d'élément (pour mettre à jour le pointeur suivant du précédent)
 ou en cas de parcours arrière
Cette classe aura donc trois données membres (deux seulement dans cette partie I) et un constructeur correspondant

  • /
class Element { friend Liste;//l'accès aux données des Elements est OK pour la Liste private: int valeur_;//la valeur de l'élément est pour l'instant limitée à 'int' Element* suivant_; public: Element(int valeur): valeur_(valeur), suivant_(NULL){} }; /*On créera ensuite une classe Liste composée des Elements Pour des raisons d'efficacité, il est bon de mémoriser la tête et la queue de la liste La tête sera utile pour parcourir la liste à partir du bébut La queue sera utile pour insérer efficacement un nouvel élément à la fin
  • /
class Liste { private: Element* tete_; Element* queue_;//la mémorisation de la queue est pratique pour les Ajouts Liste (const Liste& l);//empêche la copie par Ctor void operator=(const Liste& l);//empêche la copie par affectation public: Liste(); ~Liste(); Element* Ajouter(int valeur, Element* pE=NULL);//ajouter derrière pElt void Vider();//détruire la liste ainsi que les objets pointés void Afficher() const;//parcours et affichage des éléments }; /* Il est à noter que la liste contient des pointeurs sur les éléments et qu'en cas de copie, la copie des pointeurs n'est pas recommandée (problème d'aliassing) Il serait donc nécessaire de surcharger les opérateurs = et Ctor de copie... La solution la plus simple ici, est d'interdire la copie On rendra donc private les deux opérations. Implémentation : Le Ctor de Liste crée une liste vide Le Dtor de Liste nettoie les éléments (s'il y en a) La technique de parcours de la liste est toujours la même : démarrer à la tête puis naviguer sur le suivant, etc...
  • /
Liste::Liste() { tete_ = NULL; queue_ = NULL;} Liste::~Liste() { Vider(); } Element* Liste::Ajouter(int valeur, Element* pE ) {//pE est l'élément derrière lequel se fait l'insertion if (!pE) pE = queue_ ;//par défaut, ajout en queue Element* pNew = new Element(valeur);//création de l'Elt à partir de la valeur if (tete_==NULL) { tete_ = queue_ = pNew;//le premier est aussi le dernier, il est le seul} else { pNew->suivant_ = pE->suivant_;//le suivant du nouveau est 'le suivant de pE' pE->suivant_ = pNew;//le nouveau devient le suivant de 'pE' if (pE==queue_) queue_ = pNew; } return pNew; } void Liste::Afficher() const //afficher toute la liste { if (tete_ == NULL) cout << "la liste est vide..." << endl; else { cout << "la liste contient : " << endl; Element* iter = tete_; do { cout << "\t" << iter->valeur_ << endl; iter = iter->suivant_; } while (iter); } } void Liste::Vider() // Vider toute la liste { if (tete_ == NULL) { cout << "la liste est deja vide" << endl; return; } else { Element* iter = tete_; Element* pSuivant; do { pSuivant = iter->suivant_; delete iter; iter = pSuivant; } while (iter); } tete_ = queue_ = NULL; cout << "la liste est videe" << endl; } }//namespace vieuxLion using vieuxLion::Liste; using vieuxLion::Element; int main() { cout << "creer une liste (vide)" << endl; Liste l; cout << "ajouter un nouvel element cree par valeur (1)" << endl; Element* pE1 = l.Ajouter(1); cout << "ajouter un nouvel element cree par valeur (2)" << endl; Element* pE2 = l.Ajouter(2); cout << "afficher la liste" << endl; l.Afficher(); cout << "inserer un Element (3) derriere un autre (1)" << endl; Element* pE3 = l.Ajouter(3, pE1); cout << "afficher la liste" << endl; l.Afficher(); cout << "rechercher un element par valeur (3)" << endl; cout << "ajouter des nouveaux elements (3,4,5,6)" << endl; l.Ajouter(3);l.Ajouter(4);l.Ajouter(5);l.Ajouter(6); l.Afficher(); //Le Ctor de copie est inhibé //Liste l2 = l; //L'operator= est inhibé //Liste l3; //l3 = l; cout << "Vider la liste" << endl; l.Vider(); return 0; } /* "PARTIE I bis:" Dans cette partie, nous nous proposons de gérer l'opération Compte La solution consistant à effectuer un parcours complet des éléments pour compter étant TRES inefficace, il faudra ajouter un compteur 'compte_' comme attribut Ce compteur sera initialisé à 0 dans le Ctor, puis incrémenté lors de chaque insertion. Il sera remis à 0 dans la méthode Vider() La méthode Compte() sera très efficace : elle renverra simplement l'attribut compte_ Cf code source 'ClassList-Ibis.CPP' du ZIP "PARTIE II:" Amélioration de la classe Liste pour accepter les destructions d'éléments - L'argument de la destruction est un pointeur sur un élément existant Le problème est que la destruction d'un élément provoque une rupture de chaîne. Il est nécessaire de raccrocher les deux bouts. Ce qui signifie : positionner le suivant de l'élément détruit comme nouveau suivant de l'élément "précédant" l'élément détruit Dans notre implémentation, il est facile de connaître le suivant mais le précédent n'est pas prévu. => Rajoutons le de façon à obtenir une liste doublement chaînée. - Il est pratique de fournir aussi une fonction de destruction par valeur: L'argument sera la valeur portée par l'élément plutôt que le pointeur Elle servira dans les cas où l'on n'a pas mémorisé le pointeur renvoyé par l'Ajout. On fournira alors de plus une méthode "helper" chargée de trouver le pointeur correspondant à partir d'une valeur - elle renverra le premier pointeur trouvé dont la valeur correspond. Pour des raisons d'efficacité, il est bon de pouvoir fournir à cette méthode le point(eur) de départ. Ainsi, elle pourra servir à trouver tous les éléments de valeur donnée par des appels successifs sans repartir de la 'tête'. On la nommera 'ChercherPremier' - On ajoutera une fonction pour vérifier l'existence d'un pointeur donné La méthode sera nommée 'Existe' : elle devra parcourir la liste jusqu'à trouver l'élément. Cf code source 'ClassList-II.CPP' du ZIP "PARTIE III (technique avancée - facultatif)" : Refactoring interne léger Lors de la création de la pile et lors de son vidage il faut ramener les trois variables membres à zero on peut créer une méthode privée pour faire cela void init(){ tete_ = queue_ = NULL; compte_=0;} Elle sera appelée dans le Ctor et dans Vider() Refactoring interne plus lourd Remarquez la similitude des méthodes Afficher, Vider et ChercherPremier. Toutes font un parcours de la liste. Comment peut-on faire pour partager ce code ? Le point commun est le parcours La différence est le traitement à faire sur chacun des éléments La solution suivante crée une méthode 'iterer' appelée par les trois précédentes. Elle sera chargée de parcourir la liste et de rappeler pour chaque élément une fonction spécialisée (nommée par exemple affiche, detruire et compare) La technique est réalisable avec une méthode 'iter' prenant en argument un pointeur de fonction vers les fonctions spécialisées. La contrainte est que ces fonctions devront avoir le même prototype Nous avons choisi le suivant : la fonction spécialisée doit - connaitre l'élément : elle le reçoit par pointeur - pouvoir arrêter le parcours : elle reçoit un booléen par référence - connaître l'élément de comparaison : elle le reçoit par pointeur. ceci est seulement utilisé dans le cas de l'appel par la méthode ChercherPremier, pour savoir si l'élément est de la bonne valeur. On mettra donc une valeur par défaut à NULL pour cet argument Voici la déclaration du pointeur de fonction : typedef void (Liste::*PFN)(Element *, bool&, Element* p=NULL); Cf code source 'ClassList-III.CPP' du ZIP "PARTIE IV" : Génericité Pour traiter des valeurs différente de 'int', la solution normalisée est de passer par des Templates La technique est de rajouter 'template <class T>' devant chaque classe et fonction puis de remplacer toutes les occurences des 'int' à rendre génériques par 'T'. Pour tester, on créera une classe Scalaire et une classe Composee Elle devront être munies des opérateurs == et << qui sont utilisés dans la Liste. Cf code source 'ClassList-IV.CPP' du ZIP
  • /

Conclusion :


inspiré par le bon source en C de COBRA84
sur cette tentative, il s'agit de C++

Codes Sources

A voir également

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.