Une liste hétérogène doublement chainée

Soyez le premier à donner votre avis sur cette source.

Vue 4 467 fois - Téléchargée 891 fois

Description

Voici en C++ la gestion d'une liste doublement chainée où le type de chacun des maillons peut être différent d'un maillon à l'autre. Dans cette version les 5 types pris en compte sont : int, double, bool, std::string et int2. Il doit être assez facile d'ajouter d'autres types de maillons et/ou d'autres fonctions. Cela fonctionne sous Windows x86 et la portabilité doit être contrôlée. La gestion de listes homogènes doublement chainées avec des maillons qui sont tous du même type est très facile à trouver sur Internet et la STL avec std::list en fournit un très bon moyen. Mais pour des listes mixtes ayant des maillons de types différents les références sont rares même si leur utilisation est elle aussi plus rare. Le type composé int2 a pour contenu un tableau de 2 entiers. Il est défini par une classe int2. Il est implémenté dans maillon.hpp avec le type 5. A noter que l'implémentation du type composé int2 se fait aussi simplement que celle des types scalaires et de manière tout à fait analogue. Le programme principal mixte.exe, en mode console, est un exemple pour montrer comment utiliser maillon.hpp et le fichier maillon.txt fournit quelques explications complémentaires.

Source / Exemple :


//  programme de démonstration pour l'utilisation de maillon.hpp
    
#include "maillon.hpp"
#include "pause.hpp"
    
int main () {
    List machaine;           // une liste mixte doublement chainée
    Maillon<int>    m0, m3;  // 2 maillons de type : int
    Maillon<double> m1;      // un maillon de type : double
    Maillon<int>    mt2[2];  // 2 maillons de type : int ( type 1 ) 
    Maillon<double> mt5[2];  // 2 maillons de type : double ( type 2 )
    Maillon<bool>   m4;      // un maillon de type : bool ( type 3 )
    Maillon<std::string> m7; // un maillon de type : std::string ( type 4 )
    Maillon<int2>   m6;      // un maillon de type : int2 ( type 5 )
    Link*   plnk;
    int     premier, nm, i;
    int2    i2;
    double  x;
    std::cout << "Au point 1 le nombre de maillon(s) = " << machaine.nbLinks() << std::endl;
    m0.setVal(10);
    machaine.addTail(m0.ad());     // on met m0 qui vaut 10 dans machaine ( au rang 0 )
    m1.setVal(1.1);
    machaine.addTail(m1.ad());     // on y ajoute m1 qui vaut 1.1
    std::cout << "Au point 2 le nombre de maillon(s) = " << machaine.nbLinks() << std::endl;
    for(i=0; i<2; i++) {           // on y ajoute 2 maillons de type : int
        mt2[i].setVal(100+100*i);  // 100 et 200
        machaine.addTail(mt2[i].ad());
    }
    for(i=0; i<2; i++) {           // on y ajoute 2 maillons de type : double
        mt5[i].setVal(4.4+1.1*i);  // 4.4 et 5.5
        machaine.addTail(mt5[i].ad());
    }
    std::cout << "Au point 3 le nombre de maillon(s) = " << machaine.nbLinks() << std::endl;
//***    composition actuelle de machaine ( 6 maillons ) : 10  1.1  100  200  4.4  5.5
//***    on va retirer dans machaine 2 maillons et y insérer 2 nouveaux maillons :
    mt5[0].unplug();               // on retire le maillon nommé mt5[0] qui vaut 4.4
    machaine.unplug(2);            // on retire le 3-ième maillon de machaine qui vaut 100
    m3.setVal(333);
    machaine.insert(m3.ad(), 3);   // on insère le maillon m3 qui vaut 333 en 4-ième position
    m4.setVal(true);
    machaine.insert(m4.ad(), 4);   // on insère le maillon m4 qui vaut true en 5-ième position
//***    composition actuelle de machaine :  10  1.1  200  333  1  5.5   ( 1 pour : true )
//***    on ajoute un maillon de type Maillon<int2>
    i2.set(0, 66);
    i2.set(1, 606);
    m6.setVal(i2);
    machaine.insert(m6.ad(), 1+machaine.rang(machaine.last()));  // après le dernier
//***    et pour finir on ajoute à la fin une std::string
    m7.setVal("c'est fini !");
    machaine.insert(m7.ad(), 1+machaine.rang(machaine.last()));  // après le dernier
    std::cout << "Au point 4 le nombre de maillon(s) = " << machaine.nbLinks() << std::endl;
//***    composition actuelle de machaine :  10  1.1  200  333  1  5.5  [66, 606]  c'est fini !
//***    parcours de machaine dans sa composition actuelle : 
    std::cout << "Contenu actuel de la liste :" << std::endl;
    nm=-1;
    plnk=machaine.first();
    while(plnk!=(Link*)0) {
       nm=nm+1;
       std::cout << "- le maillon " << nm << " est de type : " << plnk->type()
                 << " et vaut : " << plnk->prnt() << std::endl;
       plnk=plnk->next();
    } 
//***    on vérifie le type du premier maillon et on extrait sa valeur avec : 
    if(machaine.nieme(0)->type()==1) {
        premier = (*(Maillon<int>*)machaine.nieme(0)).getVal();
        std::cout << "Le premier maillon ( rang 0 ) vaut : " << premier << std::endl; 
    }
//***    et on peut faire de même pour tout autre maillon. 
//***    enfin, on va chercher le pointeur d'un maillon d'après sa valeur : 
    x=5.5;
    plnk=machaine.find(&x);
    std::cout << "Le maillon qui vaut : " << x << " a le rang : " << machaine.rang(plnk) << std::endl;
//*** 
    pause();
    return 0;
}

Conclusion :


Je suppose qu'il est possible de faire mieux ou autrement. Vos remarques et/ou corrections sont les bienvenues.

Codes Sources

A voir également

Ajouter un commentaire Commentaires
Messages postés
329
Date d'inscription
samedi 18 décembre 2004
Statut
Membre
Dernière intervention
7 octobre 2021
2
CptPingu : Merci d'avoir montré que la STL avec std::list permet de construire une liste doublement chainée avec des maillons de type différent d'un maillon à l'autre. Je ne le savais pas. Plusieurs solutions valent mieux qu'une seule. Et cela permet aussi de choisir en fonction des besoins de chacun.
Messages postés
3833
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
11 juin 2021
124
Soit dit en passant, il est possible d'obtenir ce comportement en utilisant:
- std::list (tout types)
ou
- std::list (types sélectionnés)

Mais il est vrai qu'il faut ajouter une dépendance supplémentaire. Je le signale juste pour ceux qui incluraient déjà la bibliothèque boost dans leurs projets.
Messages postés
3833
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
11 juin 2021
124
Bonjour.

Le code est parfaitement portable (à part le system("pause"), mais ce n'est pas grave du tout). D'une manière générale, tant qu'on utilise pas des appels systèmes, les chances de rester portable sont grandes :)

Je te propose une version utilisant purement la STL. Il y a donc un peu moins de code:

#include
#include <list>

class GenericNode
{
public:
virtual const std::string& type() const = 0;
virtual void print(std::ostream& out) const = 0;
virtual ~GenericNode()
{
}
};

template <typename T>
class Node : public GenericNode
{
public:
Node(const std::string& type, T value)
: type_(type), value_(value)
{
}

virtual const std::string& type() const
{
return type_;
}

T value() const
{
return value_;
}

virtual void print(std::ostream& out) const
{ out << "value_ " << value_ << ", type " << type_;
}

virtual ~Node()
{
}

private:
const std::string type_;
T value_;
};

std::ostream& operator<<(std::ostream& out, const GenericNode* node)
{
node->print(out);
return out;
}

#define NODE(Type,Value) new Node<Type>(#Type, Value)

int main()
{
typedef std::list<GenericNode*> list_type;
typedef typename list_type::const_iterator list_iter;

list_type list;
list.push_back(new Node("int", 30));
list.push_back(new Node<double>("double", 30.5));
list.push_back(new Node<std::string>("std::string", "String example"));

list.push_back(NODE(std::string, "Simplifed by macro"));

int i = 1;
for (list_iter it = list.begin(); it != list.end(); ++it, ++i)
std::cout << i << ": " << *it << std::endl;

std::cout << "List size: " << list.size() << std::endl
<< "First type: " << list.front()->type()
<< ", First value: " << static_cast<Node*>(list.front())->value() << std::endl;

return 0;
}

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.