Une liste doublement chainee, circulaire et templates

Soyez le premier à donner votre avis sur cette source.

Snippet vu 12 686 fois - Téléchargée 30 fois

Contenu du snippet

Une liste doublement chainée circulaire avec 1 pointeur sur le début, 1 pointeur sur la fin et 2 autres pointeurs permettant de ce promener dans la liste.
Pourquoi avoir rajouter ces 2 pointeurs ? J'en avais besoin donc je les ai implémentés, supprimez les si vous n'en avez pas besoin (ce qui est le cas la plupart du temps je pense).

Source / Exemple :


#ifndef CHAIN_H
#define CHAIN_H

#include <iostream>

using namespace std;

enum{FREE,WORKING};

template <class T>
class Chain
{
public:
    class Maillon;

private:
    int nbMaillons;
    Maillon* deb;
    Maillon* fin;

public:
    Maillon* ptrw;
    Maillon* ptrr;

    Chain();

    void ajouterEnFin(T chaine);
    void ajouterEnDeb(T chaine);
    void retirerEnFin();
    void retirerEnDeb();

    void getNextr();
    void getPrecr();
    void getNextw();
    void getPrecw();

    int nbElem();
    void vider();
    Chain(const Chain & d);
    void afficher();
};

template <class T>
struct Chain<T>::Maillon
{
    Maillon* suiv;
    Maillon* prec;
    T  data;
    bool state;

    Maillon(T chaine);
    T getData();
    void setData(T chaine);
    bool getState();
    void setState(bool newstate);
};

template<class T>
Chain<T>::Chain() : deb(0), fin(0)
{
    nbMaillons=0;
}

template<class T>
void Chain<T>::ajouterEnFin(T chaine)
{

    Maillon *nouv=new Maillon(chaine);

    if(nbMaillons==0)
    {
        fin=nouv;
        ptrr=ptrw=deb=nouv;
        nouv->prec=nouv;
        nouv->suiv=nouv;
    }
    else
    {
        fin->suiv=nouv;
        deb->prec=nouv;
        nouv->prec=fin;
        nouv->suiv=deb;

        fin=nouv;
    }
    nbMaillons++;

}

template<class T>
void Chain<T>::ajouterEnDeb(T chaine)
{
    Maillon *nouv=new Maillon(chaine);

    if(nbMaillons==0)
    {
        ptrr=ptrw=deb=nouv;
        fin=nouv;
        nouv->prec=nouv;
        nouv->suiv=nouv;
    }
    else
    {
        fin->suiv=nouv;
        deb->prec=nouv;
        nouv->suiv=deb;
        nouv->prec=fin;

        ptrr=ptrw=deb=nouv;
    }
    nbMaillons++;
}

template<class T>
void Chain<T>::retirerEnFin()
{
    if(nbMaillons!=0)
    {
        if(nbMaillons>1)
        {
            fin=fin->prec;
            delete fin->suiv;

            fin->suiv=deb;
            deb->prec=fin;
        }
        else
            delete fin;

        nbMaillons--;
    }
}

template<class T>
void Chain<T>::retirerEnDeb()
{
    if(nbMaillons!=0)
    {
        if(nbMaillons>1)
        {
            ptrr=ptrw=deb=deb->suiv;
            delete deb->prec;

            deb->prec=fin;
            fin->suiv=deb;
        }
        else
            delete deb;

        nbMaillons--;
    }
}

template<class T>
void Chain<T>::getNextr()
{
    ptrr=ptrr->suiv;
}

template<class T>
void Chain<T>::getNextw()
{
    ptrw=ptrw->suiv;
}

template<class T>
void Chain<T>::getPrecr()
{
    ptrr=ptrr->prec;
}

template<class T>
void Chain<T>::getPrecw()
{
    ptrw=ptrw->prec;
}

template<class T>
int Chain<T>::nbElem()
{
    return nbMaillons;
}

template<class T>
void Chain<T>::vider()
{
    for( ;nbMaillons!=1;nbMaillons--)
    {
        fin=fin->prec;
        delete fin->suiv;
    }
    delete fin;
    nbMaillons--;
}

template<class T>
Chain<T>::Chain(const Chain & d)
{
    Maillon* tmp=d.deb;
    nbMaillons=0;

    if(d.nbMaillons==0)
        return;

    Maillon* n=new Maillon(tmp->data);
    nbMaillons++;
    deb=n;
    fin=n;

    for(int i=1; i<d.nbMaillons;i++)
    {
        tmp=tmp->suiv;

        ajouterEnFin(tmp->data);
    }

}

template<class T>
void Chain<T>::afficher()
{
    Maillon* temp=deb;

    if(nbMaillons==0)
    {
        cout << "Empty chain" << endl;
        return ;
    }

    for(int i=0; i<nbMaillons-1; i++)
    {

        cout << temp->data << " -> " ;
        temp=temp->suiv;
    }

    cout << temp->data << endl;
}

/******************************************************************************/

template<class T>
Chain<T>::Maillon::Maillon(T chaine)
        : suiv(0), prec(0)
{
    state=FREE;
    data=chaine;
}

template<class T>
T Chain<T>::Maillon::getData()
{
    return data;
}

template<class T>
void Chain<T>::Maillon::setData(T chaine)
{
    data=chaine;
}

template<class T>
bool Chain<T>::Maillon::getState()
{
    return state;
}

template<class T>
void Chain<T>::Maillon::setState(bool newstate)
{
    state=newstate;
}

#endif

_______________________________________________________
//Un petit exemple d'utilisation

#include "chain.h"

#include <iostream>

using namespace std;
int main()
{
    char* c="Hello";
    
    Chain<char*> d;
    
    d.ajouterEnDeb(c);
    d.ajouterEnFin("world");
    d.ajouterEnFin("!!!");
    d.deb->setData("coucou");
    
    d.getNextr();
    d.ptrr->setState(WORKING);
    cout <<  d.ptrr->getState() << endl;
    
    d.retirerEnDeb();
    d.retirerEnFin();
    d.retirerEnDeb();
    d.retirerEnDeb();
    
    
    
    d.afficher();
    
    Chain<char*> d2(d);
    d2.afficher();
    
    return 0;
}

Conclusion :


Cette source n'est pas (trop) commentée, mais je pense qu'elle est assez simple. Demandez-moi si vous ne comprenez pas quelquechose.

Je savais pas trop dans quelle catégorie mettre cette source. Si vous trouvez une meilleure place, dites le moi!
Ajouter un commentaire Commentaires
Messages postés
1
Date d'inscription
samedi 2 février 2008
Statut
Membre
Dernière intervention
7 mars 2008

j'ai besoin des listes circulaires mais je ne sais que le C, je ne sais ni le java ni le C++, pouvez vous m'aidez ???
Messages postés
286
Date d'inscription
vendredi 5 décembre 2003
Statut
Membre
Dernière intervention
22 avril 2012
2
Turnerom: en fait, struct et class sont identiques à un détail près: la visibilité. Par défaut, tout est public dans une struct, alors que c'est private dans une class.
Econs: c'est certain mais le plus gros du boulot est fait. Il y a moyen facilement de gérer n'importe quel type, même de nouvelles classes, ... en utilisant les traits et les allocateurs. voir http://www.cppfrance.com/codes/UTILISATION-TECHNIQUE-TRAITS_37173.aspx

A++ et bon coding !
Messages postés
2
Date d'inscription
lundi 9 février 2004
Statut
Membre
Dernière intervention
13 novembre 2007

slt
dis moi qu'est ce que signifie les variables:

ptrr

ptrw

Au plaisir de te relire.
ps: je sais que ce sont des points, mais aurais tu un nom plus explicite pour eux. MErci d'avance
Messages postés
3
Date d'inscription
samedi 24 juillet 2004
Statut
Membre
Dernière intervention
29 août 2006

Bon, finalement j ai perdu ce que j avais fait et je voulais recuperer ta liste chainee mais le source n'a pas l'air d'être mis à jour, pourrais tu m indiquer ou ajouter le "};" pour fermer la classe Chain, car lorsque je la met ligne 45, ca pose probleme après dans ton main pour le d.deb->setData("coucou");, il y a un probleme d'acces a un membre privé

Merci de ton aide
Messages postés
3
Date d'inscription
samedi 24 juillet 2004
Statut
Membre
Dernière intervention
29 août 2006

ok, merci pour l info, j etais justement parti voir la classe list de STL (plutot que vector ;-) )
Afficher les 12 commentaires

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.