Listes doublement chaînées

**nicolas66** · 10/10/2005, 18h04

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 :

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
 
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 :

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
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.

**Médinoc** · 10/10/2005, 19h01

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à...

**nicolas66** · 18/11/2005, 15h54

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 :

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

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 :

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
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.

**nicolas66** · 18/11/2005, 18h04

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 :

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
 
	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

**diogene** · 19/11/2005, 11h10

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

Code :

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

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 :

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

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 :

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

~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

**jmv** · 19/11/2005, 12h17

Elle est pas mal ta classe

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 :

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

   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 :

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

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 :

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

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 ?

Listes doublement chaînées

C++

Discussions similaires

Partager

Partager