Discussion :

[Revaroa]

Bonjour,

Voila, j'ai quelques difficultés à commencer un exo sur les listes avec sentinelle.
Il faut que je créer 3 classes : Cell, Iterateur et Liste.
Les méthodes de la classe liste ne doit pas modifier la structure de liste mais font appel aux méthodes de la classe Iterateur qui feront les modifications.

Pour l'instant je suis qu'au début j'ai juste la classe Cell et Iterateur.

Voici mon code pour une cellule.

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
 
Cell.h
class Cell{
    public :
    // Constructeur
    Cell(int const& valeur=0);
 
    private :
    int m_valeur;
    Cell *m_suivant;
};
 
Cell.cpp
// Constructeur
Cell::Cell(int val) : m_valeur(val), m_suivant(0){}

Ensuite pour la classe Iterateur (j'ai mis en commentaire ce qui est demandé)

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
 
Iterateur.h
class Iterateur{
    public :
    // Constructeur prend une liste en entrée
    Iterateur(Liste &liste);
 
    // Pointe au debut de la liste
    void allerDebut();
 
    private :
    // un pointeur vers le début de liste (vers la sentinelle)
    Cell *m_debut;
    // un pointeur vers la cellule avant la cellule courante
    Cell *precedent;
};

Ensuite, je bloque sur l'initialisation du constructeur Iterateur.

Code :

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

1
2
 
Iterateur::Iterateur(Liste &liste) : m_debut(new Cell()), m_precedent(m_debut){}

Besoin d'aide, s'il vous plaît quelqu'un pourrait me dire ce qui va, ce qui ne va pas et comment je pourrais m'y prendre?

Merci.

[dalfab]

Bonjour,

Il faut créer la classe Liste avant la classe Iterateur.
L'Iterateur va devoir gérer la sentinelle (créée par un new et détruite par le destruction de l'Iterateur)
La sentinelle doit être placée à la fin de la liste dès la création l'Iterateur, et retirée de la liste par le destructeur.
La sentinelle doit être remplie à chaque début de parcours avec le critère de recherche.
L'Iterateur gère à la fois la sentinelle et le pointeur courant qui lui sera initialisé au début du parcours.
Pendant le parcours, le pointeur courant évolue.
Je pense que c'est l'Iterateur qui doit gérer le test d'élément trouvé.

Il faut créer la classe Liste avant la classe Iterateur. Si c'était une std :: list<> par exemple, alors tout serait là pour écrire l'Iterateur, sinon l'Iterateur ne pourra être rempli qu'après avoir défini la Liste.

Besoin d'aide, s'il vous plaît quelqu'un pourrait me dire ce qui va, ce qui ne va pas et comment je pourrais m'y prendre?

Donc ça va, il ne manque que les choses dans Iterateur qui le relient à la Liste et à la recherche.

[Revaroa]

Bonjour,

Merci pour ta réponse, je vais essayer de le faire en suivant ces conseils.

Je reposterai si besoin.

[Revaroa]

Bonjour,

Désolé, j'ai fait autre chose entre temps (projet).

Alors je reviens avec la classe liste :

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
 
#ifndef LISTE_H_INCLUDED
#define LISTE_H_INCLUDED
 
#include "Iterateur.h"
 
class Liste{
 
    /* Cette liste n'est jamais vide 
     * car elle possède au moins une cellule sentinelle
     * qui est rajoutée en tête de liste dès la création de la liste.
     */
 
    public :
    // Constructeur,
    Liste();
 
    // Insère un élément en début de liste
    void insererEnTete(int element);
 
    // Insère un élement en fin de liste
    void insererEnQueue(int element);
 
    // Détermine si un élément appartient à la liste
    bool appartient(int element) const;
 
    // Supprime un élément de la liste (et donc la cellule associée)
    void supprimer(int element);
 
    // Affiche l'ensemble de la liste
    void affiche(std::ostream& flux) const;
 
};
 
std::ostream & operator<<(std::ostream &flux, Liste const& liste);
 
#endif // LISTE_H_INCLUDED

Pour le constructeur, la liste est vide au départ donc on a juste besoin d'un constructeur par défaut et donc la classe Liste n'aurait aucun attributs.
C'est bien ça? ou mon raisonnement est faux.

Merci.

[dalfab]

Pour le constructeur, la liste est vide au départ donc on a juste besoin d'un constructeur par défaut et donc la classe Liste n'aurait aucun attributs.
C'est bien ça? ou mon raisonnement est faux.

La liste est vide au départ : oui
La classe Liste est une collection, elle doit gérer le stockage et le chainage^{nouvelle orthographe!} des objets.

Ton commentaire dans Liste est contradictoire avec ta classe Iterateur.

• Ou bien, la Liste peut être vide, et l'Iterateur ajoute une sentinelle pendant un parcours;
• Ou bien, la Liste contient sa sentinelle, et l'Iterateur n'a pas a en créer une.

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
66
67
68
69
class ElemListe
{
public:
     int             valeur;
private:
     ElemListe *suivant = nullptr;
     ElemListe *precedent = nullptr;
     friend class Liste;
};
 
class Liste
{
     ElemListe *premier = nullptr;
     ElemListe *dernier = nullptr;
 public :
    // Constructeur,
    Liste() {}
 
    // Destructeur
    ~Liste() {
        while ( premier ) {
            ElemListe *suivant = premier->suivant;
            delete premier;
            premier = suivant;
        }
    }
 
    // Insère un élément en début de liste
    void insererEnTete(int element) {
        premier = new ElemListe{element,premier,nullptr};
        if ( !dernier )
            dernier = premier;
    }
 
    // Insère un élement en fin de liste
    void insererEnQueue(int element) {
        dernier= new ElemListe{element,nullptr,dernier};
        if ( !premier )
            premier = dernier;
    }
 
    const ElemListe* localiser(int element) const; // peut se faire par Iterateur et sentinelle
    ElemListe* localiser(int element) { // idem sur une liste modifiable
        return const_cast<ElemListe*>(localiser(element));
    }
 
    // Détermine si un élément appartient à la liste
    bool appartient(int element) const {
        return localiser(element) != nullptr;
    }
 
    // Supprime un élément de la liste (et donc la cellule associée)
    void supprimer(int element) {
        ElemListe* position = localiser(element);
        if ( position ) {
            if ( position->suivant )
                position->suivant->precedent = position->precedent;
            if ( position->precedent )
                position->precedent->suivant = position->suivant;
            if ( premier == position )
                premier = position->suivant;
            if ( dernier == position )
                dernier = position->precedent;
        }
    }
 
    // Affiche l'ensemble de la liste
    void affiche(std::ostream& flux) const;
};

Mais en posant que la sentinelle est toujours dans la Liste et n'est pas créée par l'Iterateur, le code ci-dessus se simplifie énormément. La liste n'a plus qu'un pointeur celui sur la sentinelle (son suivant est le premier, son précédent est le dernier de la liste!) et il n'est jamais nul.

[Revaroa]

Bonjour,

Ton commentaire dans Liste est contradictoire avec ta classe Iterateur.

• Ou bien, la Liste peut être vide, et l'Iterateur ajoute une sentinelle pendant un parcours;
• Ou bien, la Liste contient sa sentinelle, et l'Iterateur n'a pas a en créer une.

Voici l'énoncé : TPListe.pdf

Je comprends que c'est le premier point

• Ou bien, la Liste peut être vide, et l'Iterateur ajoute une sentinelle pendant un parcours;

Par rapport à cette partie de l'énoncé
Cette classe gère deux pointeurs :

- un pointeur vers le début de liste (vers la sentinelle),
- et un pointeur vers la cellule avant la cellule courante.

Mais je comprends aussi que c'est le second point car toujours par rapport à l'énoncé :
Cette liste n’est jamais vide car elle possède au moins une cellule sentinelle qui est rajoutée en tête de liste dès la création de la liste

Je crois que mon problème c'est de ne pas bien comprendre l'énoncé.

Merci de votre patience.

[dalfab]

La liste a toujours une sentinelle.
Donc l'Iterateur n'a pas besoin d'en créer une, il ne doit pas faire new, il doit seulement mémoriser la position de la sentinelle.