Ayant déjà vu plein de listes chaînées postées ici, parfois bizzares dans leur développement, je me suis décidé à en développer une un peu plus évoluée...
Cette liste chaînée est entièrement orientée objet.
Elle utilise la technique des traits (voir mon précédent post http://www.cppfrance.com/codes/UTILISATION-TECHNIQUE-TRAITS_37173.aspx)
La liste contient un noeud de début, vide, et un noeud de fin, également vide.
Les données sont stockées dans des noeuds internes.
Chaque classe de noeud descend d'une classe abstraite Noeud:
------------------
| Noeud |
------------------
|
|
--------------------------------------
| | |
\/ \/ \/
-------------- ---------------- ------------
| NoeudDebut | | NoeudInterne | | NoeudFin |
-------------- ---------------- ------------
La liste délègue ses actions aux noeuds (stockage, affichage).
Pour stocker les valeurs dans les noeuds internes, j'ai créé une classe template Donnee.
Voici comment cela se passe:
* Création de la liste:
-----------------------
| Liste chainée |
----------------------- ------------------
| _debut (NoeudDebut) |---------->| Objet NoeudFin |
----------------------- ------------------
* Après insertion d'un élément:
---------------------
| Liste chainée |
--------------------- -----------------
| _debut |---------->| Noeud interne |
--------------------- ----------------- ------------------
| _suivant |------>| Objet NoeudFin |
----------------- ------------------
Et ainsi de suite. Suivant le résultat de la comparaison effectuée sur les données en début d'insertion, le noeud interne sera inséré avant ou après le noeud courant (avant pour une donnée plus grande ou égale, après pour une donnée plus petite).
Chaque noeud interne pointe sur un objet de type Donnee:
-----------------
| Noeud interne |
----------------- ----------------
| _donnee |------>| Objet Donnee |
----------------- ----------------
Donc, en résumé:
---------------------
| Liste chainée |
--------------------- -----------------
| _debut |---------->| Noeud interne |
--------------------- ----------------- ------------------
| _suivant |------>| Objet NoeudFin |
| _donnee | ------------------
-----------------
|
|
\/
----------------
| Objet Donnee |
----------------
Toutes les classes sont basées sur les templates:
Donnee<T, traits=Trait<T> >
Noeud<T>
NoeudDebut<T>
NoeudInterne<T>
NoeudFin<T>
ListeChainee<T>
Donc, pour déclarer une liste d'entiers: ListeChainee<int> li;
Ensuite, pour insérer, il suffit d'appeler la méthode insere(int donnee) ou insere(const Donnee<int>& donnee). Le type Donnee est bien sûr instanciable (donc, pour l'exemple: Donnee<int> i(5), par exemple).
ATTENTION: le type Donnee ne contient pas de constructeur par défaut !
Le header traits.h fourni fonctionne pour tous les types de base. Il est aussi spécialisé pour le type char*. Il suffit simplement de le modifier et d'ajouter de nouveaux types pour étendre les possibilités de la liste.
Pour la recherche, la suppression, la modification et la suppression, cela reste simple.
Le .zip contient la source pour Dev-C++ et le Makefile pour Linux. J'ai juste testé sous Win XP et Linux RedHat 9 avec le main.cpp fourni.
Merci de poster vos commentaires, ainsi que les bugs éventuels.
NB: les schémas ne passent apparement pas... Si vous les voulez, envoyez-moi un message...