exemple d'une liste chainée

motta_745 · 23/12/2008, 20h01

Bonjour
J'aimerai bien créer une liste chainée mais ça marche pas , veuillez svp me corriger et merci beaucoup :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<string.h>
#include<iostream.h>
#include<stdio.h>
using namespace std;

class Membre
{
protected:
    int abscisse;
    int ordonnee;
    Membre * suivant;
public:
    Membre(int inabscisse,int inordonnee);
    Membre();//constructeur par defaut
    ~Membre(){};
    void ajout(int valeur1,int valeur2);
    void suppression();
};   


Membre::Membre()
{
    abscisse = 0;
    ordonnee = 0;
    suivant = 0;
}
Membre::Membre(int inabscisse,int inordonnee)
{
    abscisse = inabscisse;
	ordonnee = inordonnee;
	suivant = 0;
}

void Membre::ajout(int valeur1,int valeur2)
{
Membre *nouveau = new Membre;
nouveau->abscisse = valeur1;
nouveau->ordonnee = valeur2;
nouveau->suivant = suivant;
suivant = nouveau;
}


int main()
{
Membre *tete = new Membre;
Membre *cour;
tete->suivant = cour;
for(int i=0;i<=6;i++)
{
     cour->ajout(2,5);//remplir le cour
     cour = cour->suivant;
}
cour->suivant=0;

Membre *parcourir=tete;
while (parcourir != 0)
{
    cout << parcourir->abscisse << "   " << parcourir->ordonnee << endl;
    parcourir = parcourir->suivant;
}

return 0;
}

**I_believe_in_code** · 23/12/2008, 22h46

Bonjour motta_745,

plusieurs questions me viennent en lisant ton code :

1) à quel moment cour est-elle instanciée ?

2) quel est le rôle de tete ?

3) pourquoi tete est-elle un Membre "vide" (0, 0, 0) ?

4) Quand tu appelles cour->ajout (2, 5), un nouveau Membre est ajouté à la suite de cour... en tout cas si le code s'exécute jusque-là. A ce moment-là, à quoi sert cour, puisque on n'a jamais rien stocké dedans ?

**koala01** · 23/12/2008, 23h47

Salut, et bienvenue sur le forum (à tous les deux

)

L'un des principes fondamentaux à garder en tête, c'est de correctement séparer les responsabilités...

Il faudrait donc avoir au minimum deux classes, l'une prenant les responsabilités qui incombent aux élément de la liste, et l'autre prenant les celles qui incombent... à la liste elle-même.

Comme ici, tu ne présente qu'une seule classe, qui mélange allègrement les responsabilités de deux choses tout à fait distinctes, il ne faut pas s'étonner outre mesure si cela ne fonctionne pas à moitié aussi bien que ce que cela devrait

D'un autre coté, je serais bien tenté de répondre "il est normal que cela ne marche pas, la liste n'a pas de jambes", tant la description de ton problème manque de clarté

Si donc tu essayais de préciser un tout petit peu le problème auquel tu es confronté, nous pourrions envisager d'être beaucoup plus précis dans l'aide que nous sommes disposés à t'apporter

Je te conseillerais bien de lire et de t'imprégner de la signification de ma signature, puis de respirer un bon coup avant - pour finir - d'essayer de nous donner une explication claire et précise de "ce qui ne va pas"

La dessus, je te laisse à ta méditation

motta_745 · 24/12/2008, 00h33

merci pour vos reponses et surtout la deuxieme

en fait je veux construire une liste chainée qui contient deux entiers et un pointeur sur l'element suivant .mais mn vrai probleme est que lorsque je la crée ma liste chainée je la perd car j'ai pas la tete pour parcourir ma liste chainée pour afficher les elements .
veuillez svp me donner un exemple d'une petite liste chainée qui a une tete qui sert comme point de depart du parcour de la liste.

Merci beaucoup

**koala01** · 24/12/2008, 02h08

Envoyé par motta_745

merci pour vos reponses et surtout la deuxieme

en fait je veux construire une liste chainée qui contient deux entiers et un pointeur sur l'element suivant

Mais, comme je l'ai dit plus haut, cela n'est pas du ressort de la liste chainée... cela, c'est du ressort exclusif... de l'élément de liste chainée

.mais mn vrai probleme est que lorsque je la crée ma liste chainée je la perd car j'ai pas la tete pour parcourir ma liste chainée pour afficher les elements .

C'est bien la preuve que la liste doit être indépendante des éléments qu'elle contient

veuillez svp me donner un exemple d'une petite liste chainée qui a une tete qui sert comme point de depart du parcour de la liste.

Merci beaucoup

Ma bonté me perdra...

Enfin, voici la base d'une "saine" conception

Nous allons commencer par déterminer les responsabilités.

Une liste chainée est ce que l'on appelle un conteneur (une "collection") d'objets, et les objets contenus sont à considérés comme les "éléments de la collection".
La responsabilité de l'élément consiste à permettre de gérer les valeurs de manière cohérente, ce qui signifie qu'il doit être en mesure:

de s'initialiser
(normalement)de se copier
(normalement) d'assigner un élément existant à une variable du type adéquat
étant donné que tu sais ce que contient chaque élément, de permettre - au minimum - de récupérer les valeurs, sous la forme de constantes (cela impliquera que, pour modifier un élément, il s'agira de le supprimer de la liste et d'y placer un autre élément nouvellement créé)
de permettre d'accéder à l'élément suivant dans la liste
de définir le lien vers l'élément suivant (normalement, ce ne devrait être accessible que depuis la liste)
de se détruire

Quant à la liste, sa responsabilité principale est de permettre la gestion cohérente des éléments qui la composent.

Cela implique qu'elle doit permettre:

De s'initialiser
(normalement) De se copier au départ d'une liste existante
(normalement) d'assigner une liste existante à une variable de type adéquat
De rajouter un élément en fin de liste
(éventuellement) d'insérer un élément entre deux
(éventuellement) de trier les éléments selon un ordre précis
(éventuellement) de supprimer un élément donné
(éventuellement) de faire savoir combien d'éléments elle contient (donner sa "taille)
de faire savoir si la fin de la liste a été atteinte (ici, le fait d'arriver sur un pointeur NULL sera le signe que le dernier élément vient d'être dépassé)
de se vider de l'ensemble des éléments qu'elle contient
d'accéder au premier élément
de se détruire
... sans doute d'autres choses auxquelles je n'aurais pas songé

*Idéalement* il serait bon de faire en sorte que l'élément fasse partie intégrante de la liste, car un élément ne sert à rien en dehors de la liste qui le gère... mais bon... nous pouvons toujours faire sans

*Idéalement* il serait aussi bon de prévoir des valeurs qui permettent de représenter ce qui suit le dernier élément valide, de manière à pouvoir travailler avec des références et non des pointeurs, mais nous allons aussi faire "sans"

Il faut maintenant décider d'identifiants qui permettent de se faire une idée facilement du but des classes que nous allons créer.

Je propose, tout naturellement les noms de types Element et Liste (c'est pas très original, mais, au moins on saura directement de quoi on parle

)

Il est ensuite temps de réfléchir à ce que chaque classe doit contenir.

Pour remplir tous ses rôles, la classe Element devra donc contenir:

les deux entiers qu'elle doit gérer (tu t'en serais douté)
un pointeur vers l'élément suivant (tu t'en serais aussi douté)
un constructeur permettant l'initialisation correcte (ca aussi tu t'en serait douté)
une méthode permettant d'accéder à l'élément suivant (pourquoi pas l'opérateur ++
un "accesseur" vers la première valeur
un "accesseur" vers la deuxième valeur
un "mutateur" du lien vers l'élément suivant
(normalement) d'un constructeur par copie (ici, nous allons rendre l'élément non copiable)
(normalement) d'un opérateur d'assignation (ici, nous allons rendre l'élément non assignable)

La définition de la classe Element prendra donc cette forme:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Element
{
    /* Ce à quoi tout le monde a acces */
    public:
        /* Le constructeur */
        Element(int abs, int ord);
        /* Le destructeur */
        ~Element();
        /* les accesseurs */
        int abscisse() const;
        int ordonnee() const;
        /* les deux qui suivent devraient aussi avoir une
         * version constante
         */
        Element* next();
        /* et parce que j'aime bien :D */
        Element* operator++() ;
        /* comme indiqué, il faudrait normalement réserver l'acces à cette
         * méthode à la classe Liste :P
         */
        void setNext(Element*);
    /* Ce que la classe garde jalousement pour elle */
    private:
        /* les deux entier */
        int abs;
        int ord;
        /* le lien vers l'élément suivant */
        Element* suiv;
        /* Le fait de rendre le constructeur par copie et l'opérateur 
         * d'assignation privé et de ne pas les définir
         * fait qu'ils seront inutilisables et que la classe n'est donc 
         * ni copiable, ni assignable
         */
        Element& operator = (const Element&);
        Element& Element&(const Element&);
};

Le constructeur va etre implémenté de manière à initialisé abs et ord avec les valeurs fournies en arguement et suiv à NULL pour être sur de ne pas aller "chatouiller" là mémoire là où il ne le faut pas, sous la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Element::Element(int abs, int org):abs(abs),ord(ord),suiv(NULL)
{
}

Le destructeur ne fait rien

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
Element::Element()
{
}

Les accesseurs renvoie la valeur correspondante

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int Element::abscisse() const
{
    return abs;
}
int Element::ordonee() const
{
    return ord;
}
Element* Element::next()
{
    return suiv;
}
Element* Element::operator ++()
{
    return suiv;
}

Et le mutateur assigne l'adresse de l'élément recu en paramètre à l'élément suivant

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
void Element::setNext(Element* newnext)
{
    suiv=newnext;
}

Vient, pour finir, le temps de s'intéresser à ce qui est nécessaire pour permettre à la classe Liste de travailler sereinement

Il lui faut:

Un constructeur par défaut
un constructeur par copie (mais nous allons aussi la rendre non copiable)
un opérateur d'assignation (mais nous allons aussi la rendre non assignable)
une méthode "ajoute"
une méthode "insère" (que je ne ferai pas apparaitre)
une méthode "supprime" (que je ne ferai pas apparaitre)
une méthode "vide"
une méthode "premier"
une méthode "taille"
un destructeur
un pointeur sur le premier élément
un pointeur sur le dernier élément(de manière à assurer l'ajout en temps constant)
un entier représentant en permanence le nombre d'éléments

Elle sera donc définie sous une forme proche de
cl

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
ass Liste
{
    /* ce à quoi tout le monde a accès */
    public:
        /* le constructeur */
        Liste();
        /* le destructeur */
        ~Liste();
        /* permet d'ajouter un élément */
        void ajoute(int abs, int ord);
        /* permet de vider la liste */
        void vide();
        /* permet d'accéder au premier élément */
        Element* premier();
        /* permet de savoir le nombre d'éléments contenus */
        size_t taille() const;
    /* ce qu'elle garde jalousement pour elle */
    private:
        Element* first; // le premier
        Element* last; // le dernier
        size_t size; // le nombre
        /* cf plus haut */
        Liste(const Liste&);
        Liste& operator = (const Liste&);
}

Le constructeur initialise correctement la liste

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
 
Liste::Liste():first(NULL), last(NULL), size(0)
{
}

Le destructeur détruit tous les éléments (il ne peuvent pas continuer à exister si la liste est détruite: cela représenterait une fuite mémoire)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
Liste::~Liste()
{
    vide();
}

Lorsque l'on ajoute un élément, si la liste est vide, l'élément rajouté est tout à la fois le premier et le dernier élément, sinon, il devient le dernier élément

Le nombre d'élément est incrémenté de 1

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
void Liste::ajoute(int abs, int ord)
{
    Element* temp=new Element(abs,ord);
    if(!first)
        first = temp;
    if(last)
        last->setNext(temp);
    last = temp;
    size++;
}

Pour vider la liste, il faut détruire tous les éléments qu'elle contient

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Liste::vide()
{
    /* nous aurons besoin d'un lien temporaire */
    Element* temp;
    while(first)
    {
        /* le lien temporaire pointe sur celui qui suit le premier */
        temp = first++;
        /* on détruit le premier */
        delete first;
        /* et le lien temporaire devient le nouveau premier */
        first = temp;
    }
    size = 0;
}

la méthode taille renvoie... le nombre d'éléments contenu

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
size_t Liste::taille() const
{
    return size;
}

Le tout sera utilisé sous la forme de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
 
int main()
{
    Liste list;
    list.ajoute(2,3);
    list.ajoute(4,5);
    list.ajoute(12,56);
    cout<<list.size()<<endl;
    for(Element* ite=list.first();ite!=NULL;++ite)
        cout<<ite->abscisse()<<" "<<ite->ordonee()<<endl;
}

Il y a beaucoup de choses améliorables (du point de vue de la "const correctness" et de la résistance aux exceptions, sans compter que toutes les méthodes qui renvoie un objet de type Element renvoient un pointeur dessus) et je ne promet pas, ayant écrit ceci à la volée, qu'il n'y a pas une ou l'autre erreur de typographie

Mais, l'un dans l'autre, tu devrais en avoir assez pour arriver à t'en sortir