Une liste doublement chainee, circulaire et templates

Commenter

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!

A voir également

S'inscrire maintenant

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.

Du même auteur (turnerom)