Corrigé du TP 2 : listes chaînées

#ifndef Noeud_h
#define Noeud_h
 
#include <string>
 
struct Noeud
{
        Noeud* precedent;
        std::string valeur;
        Noeud* suivant;
};
 
#endif // Noeud_h

#ifndef Liste_h
#define Liste_h
 
#include <string>
 
#include "Noeud.h"
 
class Liste
{
public :
    // Cree une liste vide
    Liste();
    // Constructeur par copie
    Liste(Liste const & autre);
    // Affectation
    Liste & operator=(Liste const & autre);
    // Destructeur
    ~Liste();
 
    // Nombre d'elements
    int size() const;
    // Liste vide ?
    bool empty() const;
 
    // Ajout en tete (avant le premier element)
    void push_front(std::string const & chaine);
    // Ajout en queue (apres le dernier element)
    void push_back(std::string const & chaine);
 
    // Ajout n'importe ou (avant le n-ieme element)
    void insert(int position, std::string const & chaine);
    // Ajout n'importe ou (avant le noeud)
    void insert(Noeud * position, std::string const & chaine);
    // Suppression d'un element
    void erase(Noeud* position);
    // Suppression d'un element
    void erase(int position);
 
    // Acces au noeud du début
    Noeud const * begin() const;
    Noeud * begin() ;
    // Acces au noeud de la fin
    Noeud const * end() const;
    Noeud * end() ;
private :
    Noeud * ancre;
    int taille;
 
    void copie(Liste const & autre);
 
    void ajouteDansVide(std::string const & chaine);
};
 
#endif // Liste_h

#include "Liste.h"
 
#include <string>
 
#include "Noeud.h"
 
Liste::Liste()
: ancre(0), taille(0)
{
    ancre = new Noeud;
    ancre->precedent = ancre;
    ancre->suivant = ancre;
}
 
Liste::Liste(Liste const & autre)
: ancre(0), taille(0)
{
    ancre = new Noeud;
    ancre->precedent = ancre;
    ancre->suivant = ancre;
 
    copie(autre);
}
 
Liste &
Liste::operator=(Liste const & autre)
{
    if(this != &autre)
    {
        while(!empty())
        {
            erase(0);
        }
        copie(autre);
    }
    return (*this);
}
 
Liste::~Liste()
{
    Noeud* courant = begin();
    while(courant != end())
    {
        Noeud* suivant = courant->suivant;
        delete courant;
        courant = suivant;
    }
 
    delete ancre;
}
 
int
Liste::size() const
{
    return taille;
}
 
bool
Liste::empty() const
{
    return (taille==0);
}
 
void
Liste::ajouteDansVide(std::string const & chaine)
{
    Noeud* nouveau = new Noeud;
    nouveau->valeur = chaine;
 
    nouveau->precedent = ancre;
    nouveau->suivant = ancre;
 
    ancre->precedent = nouveau;
    ancre->suivant = nouveau;
}
 
void
Liste::push_front(std::string const & chaine)
{
    if(empty())
    {
        ajouteDansVide(chaine);
    }
    else
    {
        Noeud* nouveau = new Noeud;
        nouveau->valeur = chaine;
 
        nouveau->precedent = ancre;
        nouveau->suivant = ancre->suivant;
 
        ancre->suivant->precedent = nouveau;
        ancre->suivant = nouveau;
    }
 
    ++taille;
}
 
void
Liste::push_back(std::string const & chaine)
{
    if(empty())
    {
        ajouteDansVide(chaine);
    }
    else
    {
        Noeud* nouveau = new Noeud;
        nouveau->valeur = chaine;
 
        nouveau->suivant = ancre;
        nouveau->precedent = ancre->precedent;
 
        ancre->precedent->suivant = nouveau;
        ancre->precedent = nouveau;
    }
 
    ++taille;
}
 
void
Liste::insert(int position, std::string const & chaine)
{
    Noeud * endroit = begin();
    for(int i=0; i<position; ++i)
    {
        endroit = endroit->suivant;
    }
    insert(endroit, chaine);
}
 
void
Liste::insert(Noeud * position, std::string const & chaine)
{
    Noeud* nouveau = new Noeud;
    nouveau->valeur = chaine;
 
    nouveau->precedent = position->precedent;
    nouveau->suivant = position;
    position->precedent = nouveau;
    position->suivant->precedent = nouveau;
 
    ++taille;
}
 
void
Liste::erase(Noeud* position)
{
    position->precedent->suivant = position->suivant;
    position->suivant->precedent = position->precedent;
 
    delete position;
}
 
void
Liste::erase(int position)
{
    Noeud* endroit = begin();
    for(int i=0; i<position; ++i)
    {
        endroit = endroit->suivant;
    }
 
    erase(endroit);
}
 
Noeud const *
Liste::begin() const
{
    return ancre->suivant;
}
 
Noeud *
Liste::begin()
{
    return ancre->suivant;
}
 
Noeud const *
Liste::end() const
{
    return ancre;
}
 
Noeud *
Liste::end()
{
    return ancre;
}
 
void
Liste::copie(Liste const & autre)
{
    for(Noeud const * courant = autre.begin(); courant != autre.end();
        courant = courant->suivant)
    {
        push_back(courant->valeur);
    }
}

#include <iostream>
#include <ostream>
 
#include "Liste.h"
 
std::ostream &
operator<<(std::ostream & stream, Liste const & l)
{
    Noeud const * courant = l.begin();
    while(courant != l.end())
    {
        stream << courant->valeur << " ";
        courant = courant->suivant;
    }
    return stream;
}
 
int
main()
{
    Liste l;
    l.push_front("a");
    l.push_front("b");
    l.push_front("c");
    std::cout << l << std::endl;
 
    Liste l2(l);
    std::cout << l2 << std::endl;
 
    Liste l3;
    l3 = l2;
    std::cout << l3 << std::endl;
 
    l.erase(0);
    l2.erase(1);
    l3.erase(2);
    std::cout << l << std::endl;
    std::cout << l2 << std::endl;
    std::cout << l3 << std::endl;
 
}

#include <iostream>
#include <list>
#include <string>
#include <ostream>
 
std::ostream &
operator<<(std::ostream & stream, std::list<std::string const & l)
{
    for(std::list<std::string>::const_iterator it = l.begin();
        it != l.end(); ++it)
    {
        stream << *it << " ":
    }
    return stream;
}
 
int
main()
{
    std::list<std::string> l;
    l.push_back("x");
    l.push_back("y");
    l.push_back("z");
    std::cout << l << std::endl;
 
    std::list<std::string> l2(l);
    std::cout << l2 << std::endl;
 
    std::list<std::string> l3;
    l3 = l2;
    std::cout << l3 << std::endl;
 
    l.erase(l.begin());
    l2.erase( ++l.begin() );
    l3.erase( --l.end() );
    std::cout << l1 << std::endl;
    std::cout << l2 << std::endl;
    std::cout << l3 << std::endl;
}