Discussion :

[lafrankette]

Bonjour,

J avance ds mon exercice sur les listes chainees...

Je redonne mon header:

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
#ifndef MYLINKEDLIST_H
#define MYLINKEDLIST_H
 
#include <iostream>
#include <string>
 
struct node 
{
	std::string str;
	node *next;
};
 
 
class MyLinkedList{
	private:
		 node *m_start;
 
	public:
		MyLinkedList(); //default constructor
		MyLinkedList(const MyLinkedList& other);  //copy constructor
		MyLinkedList operator=(const MyLinkedList& other);//operator =
		void Add(const std::string& s );
		bool Remove(const std::string& s);
		bool InList(const std::string& s) const;
		void PrintList() const;
		int Count() const;
		void Sort(); 
		~MyLinkedList(); // destructor
};
 
#endif

J essaie d ecrire mon constructeur de copie, mais je bug un peu.
Je copmrends bien que du fait que le membre de ma classe (il y a que m_start) est un pointeur, je dois faire une copie et creer un nvo ptr sinon , si j ecris par exemple:
m_start= other>m_start;
les 2 ptrs vont pointer au meme endroit et ca pose probleme...

Je n arrive pas a ecrire cette fonction copie que je pourrais utiliser ds mon copy constructor:
m_start=copie(other.m_start);

Pouvez vous m aider?

Merci d avance

Judith

[thetux]

Je propose quelque chose comme ça :

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
 
// On commence par copier l'élément sans les éléments qui suivent
node* const copy = new node; // on pointe toujours vers la copie
copy->str = m_start->str;
copy->next = NULL;
 
// On ajoute les éléments qui suivent
node * n = copy; // l'élément courant
const node * ref = m_start->next; // la référence (const par sécurité, pour éviter qu'on modifie la valeur lors du processus de copie)
 
 
while (ref)
{
    // Si ref existe on crée un nouveau noeud que l'on nomme comme ref
    node* next = new node;
    next->str = ref->str;
    // On indique à l'élément courant que son successeur est le noeud qu'on vient de créer
    n->next = next;
    // On itère
    next = n;
    ref = ref->next;
}
 
return copy;

[koala01]

Salut,

Le fait est que, lorsque tu copie un élément de la liste, tu dois le lier à... une copie de l'élément suivant spécialement pour l'occasion.

Autrement, tu te trouvera confronté au problème qu'un élément est référencé comme étant le suivant de deux éléments bien distincts, ce qui aura pour conséquence une double libération de la mémoire de cet élément: lors de la destruction de la liste d'origine et lors de la destruction de la copie de la liste.

La première chose est donc de veiller à copier correctement l'élément:

La valeur qu'il représente peut (si elle est copiable) être copiée, mais il faut veiller à ce que la référence (le pointeur en fait) soit initialisé à... rien

Ce ne sera que lorsque tu effectuera une copie de l'élément suivant pour l'accrocher à la copie de l'élément actuellement en cours de copie qu'il faudra définir la référence en question

Autrement dit, ta classe node devrait ressembler à:

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
class node 
{
    public:
        /* il est impossible de créer un noeud sans donner la valeur
         * qu'il représente
         * mais, par défaut, le noeud n'a pas de frère suivant
         */
        node(std::string const & str):str(str), next(0){}
        /* lorsque l'on copie le noeud, on ne copie que la valeur, mais pas
         * la référence vers le noeud suivant (le constructeur par copie
         * n'est pas trivial, et il faut donc le définir nous même
         */
        node(node const & n):str(n.str),next(0){}
        /* noud utilisons l'idiome copy and swap pour l'opérateur
         * d'affectation
         */
       node& operator=(node const & n)
       {
            node temp(n);
            std::swap(str,temp.str)
            std::swap(next,temp.next);
            return *this;
       }
       /* fournissons un opérateur qui permet de passer au noeud suivant
        *
        * dans sa version non constante
        */
       node * operator ++(){return next;}
       /* et dans sa version constante */
       node const * operator ++() const{return next;}
       /* donnons au noeud une sémantique de pointeur vers la valeur
        * qu'il représente
        * 
        * dans sa version non constante
        */
       std::string& operator*(){return str;}
       std::string& operator->(){return str;}
       /* et dans sa version constante */
       std::string const & operator*() const{return str;}
       std::string const & oeprator->()const{return str;}
       /* comparer l'égalité (ou l'inégalité) de deux noeuds revient à
        * effectuer une comparaison d'(in)égalité sur la valeur que chacun
        * des noeuds représente
        */
        bool operator==(node const * n) const{return str==n->str;}
        bool operator!=(node const * n) const{return !(this==n);}
        bool operator< (node const * n) const{return str<n->str;}
        bool operator> (node const * n) const{return str>n->str;}
        bool operator<=(node const * n) const{return !(this>n);}
        bool operator>=(node const * n) const{return !(this<n);}
    private:
	std::string str;
	node *next;
        /* pour permettre à la liste de modifier facilement la référence
         * vers le noeud suivant 
         */
        friend classe liste;
};

Maintenant que tu as la certitude que tes nœuds seront correctement copiés et affectés et qu'ils ont une sémantique de pointeur vers la valeur qu'ils représentent, tu peux envisager sereinement la création de ta 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
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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
class liste
{
    public:
        /* une liste peut être créée par défaut et sera vide */
        liste():first(0),last(0);
        /* une liste peut être créée avec un noeud unique */
        liste(noeud * n):first(new noeud(n)),last(first){}
        /* une liste peut etre créée au départ d'un écart entre [f, e)
         */
        list(node * f, node * e)
        {
            node *temp=f;
            /* pour chaque noeud apparaissant dans l'écart, nous insérons
             * une copie en fin de liste
             */
            while(temp!=e)
            {
                push_back(*temp);
                ++temp;
            }
        }
        /* le destructeur de la liste  doit détruire tous les noeuds qu'elle
         * constient
         */
        ~liste()
        {
             clear();
        }
        /* nous pouvons copier une liste */
        liste(liste const & rhs)
        {
            for(node* it=rhs.begin();it!=rhs.end(); ++it)
                push_back(*it);
        }
        /* et assigner une liste à une autre (la liste de destination
         * étant une copie de la liste d'origine)
         */
        liste& operator = (liste const & rhs)
        {
            liste temp(rhs);
            std::swap(first,temp->first);
            std::swap(last,temp->last);
            return *this;
        }
        /* il est intéressant de savoir si la liste est vide */
        bool empty() const{return first!=0;}
        /* ainsi que de savoir le nombre d'éléments qu'elle contient */
        size_t size() const
        {
             node * temp=first;
             size_t ret=0;
             while(temp)
             {
                 ++temp;
                 ++ret;
             }
             return ret;
        }
        /* on peut ajouter une valeur en début de liste */
        void push_front(std::string const & s)
        {
            node * temp=new node(s);
            temp->next=first;
            /* c'est peut être le premier noeud ajouté */
            if(!last)
                last=temp;
        }
        /* ou ajouter une valeur en fin de liste */
        void push_back(std::string const & s)
        {
            node * temp=new node(s);
            /* s'il y a déjà un dernier noeud, nous relions le noeud
             * fraichement créé au dernier
             */
            if(last)
                last->next = temp;
            /* le noeud fraichment créé devient le dernier */
            last = temp;
            /* mais c'est aussi peut être le premier noeud ajouté */
            if(!first)
                first = temp;
        }
        /* on peut retirer le premier noeud de la liste
         * 
         * cette opération se fait en temps constant (si nous avions eu
         * une liste doublement chainée, nous aurions pu envisager de
         * supprimer également le dernier noeud de la liste en temps
         * constant... comme ce n'est pas le cas, nous nous abstenons ;) )
         */
        void pop()
        {
            node* temp=++first;
            delete first;
            first=temp;
           /*c'était peut etre le seul élément de la liste */
           if(!first)
               last=0;
        }
        /* il est intéressant de fournir l'acces au premier 
         * élément de la liste et à ce qui suit le dernier élément de la
         * liste
         *
         * de manière non constante
         */
        node* begin(){return first;}
        node* end(){return 0;}
        /* et de manière constante */
        node const * begin() const{return first;}
        node const * end() const{return 0;}
        /* enfin, nous pouvons souhaiter vider l'ensemble de la liste */
        void clear()
        {
             while(first)
             {
                 node * temp=++first;
                 delete first;
                 first=temp;
             }
        }
    private:
        /* le premier élément de la liste */
        node * first;
        /* et le dernier (qui nous permet d'ajouter un dernier noeud
         * en temps constant )
         */
        node * last;
};

De cette manière, tu évitera une grosse majorité des problèmes

NOTA: les commentaires que j'ai placés dans le code sont sans doute plus importants que le code lui-même