Listes doublement chaînées

Version imprimable

Bonjour,

Pour mon plaisir perso, j'ai l'intention de créer une petite classe qui me permettra de manipuler aisément les listes doublement chaînées. Apparement le code ci-dessous fonctionne correctement. En revanche je ne comprends pas pourquoi je suis obligé de créer un pointeur de ma liste pour y insérer des éléments. Si je crée pas de pointeur, j'ai une "segmentation fault", sympa quoi ... De plus, j'aimerai que quelques personnes puissent me donner leur(s) avis sur le code même et les éventuelles erreurs. Merci d'avance :)

Fichier "node.h"

Code:

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
 
template<typename T> class CNode
{
    protected :
	T m_Value;
	CNode<T> * m_Previous, * m_Next;
 
    public :
	CNode( const T & Value = T(), CNode<T> * Previous = NULL, CNode<T> * Next = NULL ) : m_Value(Value), m_Previous(Previous), m_Next(Next) {}
 
	CNode( const CNode<T> & Node )
	{
		m_Value    = Node.m_Value;
		m_Previous = Node.m_Previous;
		m_Next     = Node.m_Next;
	}
 
	virtual ~CNode()
	{
		if( m_Previous )
			delete m_Previous;
 
		if( m_Next )
			delete m_Next;
	}
 
	CNode<T> & CNode<T>::operator = ( const CNode<T> & Node )
	{
		if( m_Previous )
			delete m_Previous;
 
		if( m_Next )
			delete m_Next;
 
		m_Value    = Node.m_Value;
		m_Previous = Node.m_Previous;
		m_Next     = Node.m_Next;
 
		return (*this);
	}
 
	const CNode<T> * Previous() const
	{
		return m_Previous;
	}
 
	CNode<T> *& Previous()
	{
		return m_Previous;
	}
 
	const CNode<T> * Next() const
	{
		return m_Next;
	}
 
	CNode<T> *& Next()
	{
		return m_Next;
	}
 
	const T & Value() const
	{
		return m_Value;
	}
 
	T & Value()
	{
		return m_Value;
	}
 
	bool IsAlone() const
	{
		return !(m_Previous && m_Next);
	}
};

Fichier "linked_list.h"

Code:

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
128
129
130
131
132
 
template<typename T> class CLinkedList
{
     private :
	unsigned int m_NbElements;
	CNode<T> * m_Head, * m_Tail;
 
     public :
	CLinkedList() : m_NbElements(0), m_Head(), m_Tail() {}
 
	~CLinkedList()
	{
		if( m_Head )
			delete m_Head;
 
		if( m_Tail )
			delete m_Tail;
	}
 
	bool IsEmpty() const
	{
		return (m_NbElements == 0);
	}
 
	CNode<T> * Head() const
	{
		return m_Head;
	}
 
	CNode<T> * Tail() const
	{
		return m_Tail;
	}
 
	void Empty()
	{
 
	}
 
	const unsigned int & NbElements() const
	{
		return m_NbElements;
	}
 
	void PushBack( const T & Value )
	{
		CNode<T> * Node = new CNode<T>(Value);
 
		if( !m_Head )
			m_Head = Node;
 
		Node->Previous() = m_Tail;
 
		if( m_Tail )
			m_Tail->Next() = Node;
 
		m_Tail = Node;
		++m_NbElements;
	}
 
	void PopBack()
	{
		if( m_NbElements > 0 )
		{
			if( m_NbElements == 1 )
				m_Head = NULL;
 
			CNode<T> * Node = new CNode<T>();
			Node            = m_Tail;
			m_Tail          = Node->Previous();
 
			if( m_Tail )
			{
				Node->Previous() = NULL;
				m_Tail->Next()   = NULL;
			}
 
			--m_NbElements;
			delete Node;
		}
	}
 
	void PushFront( const T & Value )
	{
		CNode<T> * Node = new CNode<T>(Value);
 
		if( !m_Tail )
			m_Tail = Node;
 
		Node->Next() = m_Head;
 
		if( m_Head )
			m_Head->Previous() = Node;
 
		m_Head = Node;
		++m_NbElements;
	}
 
	void PopFront()
	{
		if( m_NbElements > 0 )
		{
			if( m_NbElements == 1 )
				m_Tail = NULL;
 
			CNode<T> * Node = new CNode<T>();
			Node            = m_Head;
			m_Head          = Node->Next();
 
			if( m_Head )
			{
				Node->Next()       = NULL;
				m_Head->Previous() = NULL;
			}
 
			--m_NbElements;
			delete Node;
		}
	}
 
	unsigned int Find( const T & Value )
	{
		CNode<T> * Node = new CNode<T>();
		Node = m_Head;
		unsigned int Elements(0);
 
		for( Node = m_Head; Node; Node = Node->Next() )
			if( Node->Value() == Value )
				++Elements;
		return Elements;
	}
};

Nico.

10/10/2005, 19h01
Médinoc

Déjà, dans ton destructeur tu fais un delete previous et delete next... (donc, si elles ne sont pas allouées dynamiquement, c'est la segfault)

Delete next ne risque-t-il pas de rappeler le destructeur du premier maillon? et ainsi de suite?
En tout cas, il y a au moins un maillon qui est deleté deux fois, c'est le premier... Tu nous fais des effacements récursifs, là...

Bon j'ai tenté de refaire le destructeur de ma classe CList et de supprimer le contenu de mon destructeur de ma classe CNode. Pour l'instant tout fonctionne sans problèmes. Cependant j'ai deux questions à vous poser :

:arrow: Est-ce une bonne chose de laisser entièrement la charge de la destruction des noeuds chaînés à la classe CList ?

:arrow: Avec ce que j'ai codé (voir ci-dessous), je peux parcourir ma liste doublement chaînée à l'aide d'un noeud. Ce noeud pointe sur la tête de la liste accessible via la fonction 'Head()'. Je me suis aperçu qu'en faisant un delete de ce pointeur, la tête était aussi supprimée. Est-ce normal ? Ne devrais-je pas renvoyer dans ce cas une copie de la tête pour éviter que l'utilisateur ne détruise la tête de sa liste par mégarde ?

Voici le code modifié :

Code:

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
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
 
template<typename T> class CNode
{
    protected :
	T m_Value;
	CNode<T> * m_Previous, * m_Next;
 
    public :
	CNode( const T & Value = T(), CNode<T> * Previous = NULL, CNode<T> * Next = NULL ) : m_Value(Value), m_Previous(Previous), m_Next(Next) {}
 
	CNode( const CNode<T> & Node )
	{
		m_Value    = Node.m_Value;
		m_Previous = Node.m_Previous;
		m_Next     = Node.m_Next;
	}
 
	~CNode() {}
 
	CNode<T> & CNode<T>::operator = ( const CNode<T> & Node )
	{
		if( m_Previous )
			delete m_Previous;
 
		if( m_Next )
			delete m_Next;
 
		m_Value    = Node.m_Value;
		m_Previous = Node.m_Previous;
		m_Next     = Node.m_Next;
 
		return (*this);
	}
 
	const CNode<T> * Previous() const
	{
		return m_Previous;
	}
 
	CNode<T> *& Previous()
	{
		return m_Previous;
	}
 
	const CNode<T> * Next() const
	{
		return m_Next;
	}
 
	CNode<T> *& Next()
	{
		return m_Next;
	}
 
	const T & Value() const
	{
		return m_Value;
	}
 
	T & Value()
	{
		return m_Value;
	}
 
	bool IsAlone() const
	{
		return !(m_Previous && m_Next);
	}
};
 
template<typename T> class CLinkedList
{
     private :
	unsigned int m_NbElements;
	CNode<T> * m_Head, * m_Tail;
 
     public :
	CLinkedList() : m_NbElements(0), m_Head(), m_Tail() {}
 
	~CLinkedList()
	{
		if( m_Head )
		{
			while( m_NbElements )
				PopBack();
 
			m_Head = NULL;
			m_Tail = NULL;
		}
	}
 
	bool IsEmpty() const
	{
		return (m_NbElements == 0);
	}
 
	CNode<T> * Head() const
	{
		return m_Head;
	}
 
	CNode<T> * Tail() const
	{
		return m_Tail;
	}
 
	const unsigned int & NbElements() const
	{
		return m_NbElements;
	}
 
	void PushBack( const T & Value )
	{
		CNode<T> * Node = new CNode<T>(Value);
 
		if( !m_Head )
			m_Head = Node;
 
		Node->Previous() = m_Tail;
 
		if( m_Tail )
			m_Tail->Next() = Node;
 
		m_Tail = Node;
		++m_NbElements;
	}
 
	void PopBack()
	{
		if( m_NbElements > 0 )
		{
			if( m_NbElements == 1 )
				m_Head = NULL;
 
			CNode<T> * Node = m_Tail;
			m_Tail          = Node->Previous();
 
			if( m_Tail )
			{
				Node->Previous() = NULL;
				m_Tail->Next()   = NULL;
			}
 
			--m_NbElements;
			delete Node;
		}
	}
 
	void PushFront( const T & Value )
	{
		CNode<T> * Node = new CNode<T>(Value);
 
		if( !m_Tail )
			m_Tail = Node;
 
		Node->Next() = m_Head;
 
		if( m_Head )
			m_Head->Previous() = Node;
 
		m_Head = Node;
		++m_NbElements;
	}
 
	void PopFront()
	{
		if( m_NbElements > 0 )
		{
			if( m_NbElements == 1 )
				m_Tail = NULL;
 
			CNode<T> * Node = m_Head;
			m_Head          = Node->Next();
 
			if( m_Head )
			{
				Node->Next()       = NULL;
				m_Head->Previous() = NULL;
			}
 
			--m_NbElements;
			delete Node;
		}
	}
};
 
 
int main( int argc, char ** argv )
{
	CLinkedList<int> LinkedList;
	LinkedList.PushBack(10);
	LinkedList.PushBack(11);
	LinkedList.PushBack(12);
 
	CNode<int> * Node = LinkedList.Head();
 
	while( Node )
	{
		std::cout << Node->Value() << std::endl;
		Node = Node->Next();
	}
 
        // le fameux delete ...
	//delete Node;
 
	return EXIT_SUCCESS;
}

Merci à ceux qui pourront éclairer mon chemin :)

Nico.

En fait je crois avoir trouvé moi-même l'erreur : elle viendrait des fonctions de renvoi du noeud précédent et suivant. Elles renvoient une référence du noeud de tête. Par conséquent, lorsque je détruis mon noeud qui me sert à parcourir la liste dans la fonction 'main' cela détruit la tête d'origine de la liste ... En conclusion, j'ai préféré réecrire les fonctions Previous() et Next() comme ci-dessous :
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 void SetPrevious( CNode<T> * Previous ) { m_Previous = Previous; } CNode<T> * GetPrevious() const { return m_Previous; } void SetNext( CNode<T> * Next ) { m_Next = Next; } CNode<T> * GetNext() const { return m_Next; }
Voilà, si des personnes ont des précisions à apporter, qu'elles n'hésitent pas :)

Il y a des choses que je comprend pas dans la logique de ton code
Code:

1 2 3 4 5 6 CNode( const CNode<T> & Node ) { m_Value = Node.m_Value; m_Previous = Node.m_Previous; m_Next = Node.m_Next; }
Ce constructeur par copie, copie également les pointeurs. Ce n'est pas logique : sa position dans la liste n'(aur)a rien à voir avec celle de l'original. Il ne peut pas se placer "en parallèle" dans la liste avec l'original.
Code:

1 2 3 4 5 6 7 8 9 10 11 12 CNode<T> & CNode<T>::operator = ( const CNode<T> & Node ) { if( m_Previous ) delete m_Previous; if( m_Next ) delete m_Next; m_Value = Node.m_Value; m_Previous = Node.m_Previous; m_Next = Node.m_Next; return (*this); }
Pourquoi l'opérateur d'assignation détruit-il les noeuds précédent et suivant ? Pourquoi modifier m_Previous et m_Next ? Ne suffit-il pas d'affecter m_Value ?

Code:

~CNode() {}

On peut le garder vide, mais alors, il ne peut pas être utilisé directement sans passer par une méthode de CLinkedList : Si ce noeud est dans une liste, sa destruction directe détruit également le chaînage m_Previous et m_Next et la liste est détruite. Logiquement, tu ne dois pas permettre à l'utilisateur l'accès direct aux variables CNode.
Plus quelques autres remarques sur ta classe CLinkedList si ça t'interresse

19/11/2005, 12h17
jmv
Elle est pas mal ta classe :wink: mais j'ai quelques remarques à faire :
Tu utilise un pointeur sur CNode comme itérateur, tu ne pourras donc pas empécher l'utilisateur de ta classe d'accéder directement aux noeuds et de faire des delete par mégarde. Tu devrais faire une classe CIterator<T> pour permettre de parcourir ta liste (comme dans la STL).

sinon quelques remarques sur le code:

dans le constructeur tu devrais initialiser les pointeurs à 0 (c'est peut-être fait par défaut mais dans le doute...

Code:

CLinkedList() : m_NbElements(0), m_Head(0), m_Tail(0) {}

Dans le destructeur, beaucoup de chose inutile, si PopBack() fait bien son boulot, ça devrait suffire.
Code:

1 2 3 4 5 ~CLinkedList() { while( m_NbElements ) PopBack(); }
Tu déclare Head() const !!! alors qu'il renvoie un pointeur qui va permettre de modifier la liste. Mieux vaut écrire 2 versions:
Code:

1 2 3 4 5 6 7 8 CNode<T> * Head() { return m_Head; } const CNode<T> * Head() const { return m_Head; }
Même remarque pour Tail().

Et dans la classe CNode, je ne vois pas l'utilité du constructeur par copie et de l'operateur =, ceux par défaut ne suffisent pas ?