while loop seemingly refuses to stop

kanesoban (39)
Okay, here's the code:

1
2
3
4
5
6
 
		while (L.notEmpty)
		{
			cout << "( " << L.Next().x << " ; " << L.Next().y << " )" << '\n';
			L.removeAfter();
			std::cout << L.notEmpty << '\n';
		}


This is the last part of the main function. If this while loop ends, the program ends.

You don't need to know what L.Next and L.removeAfter does. The important part is, that the std::cout << L.notEmpty << '\n'; line writes "0". L.notEmpty is a type bool variable.
What should happen, is that the program ends, instead, after writing out the "0", it gives me a segfault, and i don't know why.
helios (17607)
notEmpty should be a function, not a variable.
I'm afraid I will have to see the code for removeAfter().
Zaita (2770)
notEmpty should be a function, not a variable.

Only because this satisfies encapsulation. Unless your thinking of another reason?


+1 for having to see the code, you haven't provided enough information here. But it looks like you've developed your own linked list? Why not just use the STL type?
helios (17607)
How about that notEmpty being a variable, it's not read only?
Also, it has to be updated every time a method changes the structure, instead of every time it's needed. Not to mention that this also creates duplicate code.
kanesoban (39)
I'm afraid I will have to see the code for removeAfter().
1
2
3
4
5
6
7
8
9
10
11
12
13
 
template <class T>
void ChainedList<T>::removeAfter()
{
	if ( Head == 0 )
		{
			notEmpty = 0;
			return;
		}
	Node<T> * nodeBeingRemoved = Head;
	Head = Head->Next;
	delete nodeBeingRemoved;
	if ( Head == 0 )
		notEmpty = 0;


The code is a bit rushed, i know.

Here is the Node type:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#ifndef NODE_H
#define NODE_H
		template <class T>
		class Node
			{
				public:
				Node()
					{
						Next = 0;
					}
				Node(T _Data)
					{
						Data = _Data;
						Next = 0;
					}
				T Data;
				Node<T> * Next;
			};

#endif


But it looks like you've developed your own linked list? Why not just use the STL type?


Because i just made the implementation (just like this program) for C++ programming practice.

helios (17607)
It seems to me that "removeAfter" is a misnomer, since you're deleting the head of the list.

Ah, here's your problem.
If I understand your code correctly, this is your implementation of ChainedList<T>::Next():
1
2
3
 
T ChainedList<T>::Next(){
	return *(this->Head->Next);
}
This wouldn't be a problem if it wasn't for the fact that when the list is of size 1, this->Head->Next==0. Dereferencing a null pointer causes segmentation faults if you're lucky and undefined behavior if you're unlucky.
What you should do is have a method like Head() that will return a copy of the data at the head of the list.a
kanesoban (39)
1
2
3
4
5
 
template <class T>
T ChainedList<T>::Next()
{
	return Head->Data;
}


Yeah, i know that it has a misleading name, but Next() doesn't do what it's name implies.
helios (17607)
In that case, I don't think I will be able to help without directly debugging. Could you post the entire code?
kanesoban (39)
Well ok, but it's about 500 LOC.

main.cpp:

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
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
 
#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>
#include "ChainedList.h"
#include "Pont.h"
#include "Node.h"

using namespace std;

//template <class T>
//void GrahamScan(Pont array[], ChainedList<T> &L, int n);




// 0 : a pontok egy vonalon vannak ; 0 < : balra fordul ; 0 > : jobbra fordul
double Whatdirection(Pont p1, Pont p2, Pont p3)
	{
		return (p2.x-p1.x) * (p3.y-p1.y) - (p2.y-p1.y) * (p3.x-p1.x);
	}


void GetTangents(Pont p1 , Pont p2 , Pont Pivot, double &p1tangent, double &p2tangent)
{


	if (p1.y - Pivot.y < 0 )
		p1tangent = -1 * (p1.y - Pivot.y);
	else
		p1tangent =  (p1.y - Pivot.y);

	if (p1.x - Pivot.x < 0 )
		p1tangent /= -1 * (p1.x - Pivot.x);
	else
		p1tangent /=  (p1.x - Pivot.x);


	if (p2.y - Pivot.y < 0 )
		p2tangent = -1 * (p2.y - Pivot.y);
	else
		p2tangent =  (p2.y - Pivot.y);

	if (p2.x - Pivot.x < 0 )
		p2tangent /= -1 * (p2.x - Pivot.x);
	else
		p2tangent /=  (p2.x - Pivot.x);


}



bool Smaller (Pont p1 , Pont p2 , Pont Pivot)
{
	cout << Pivot.x << '\n';
	double p1tangent,p2tangent;

//Speciális eset kategória #1: amikor az x koordináta megegyezik (90 fokot zár be az x tengellyel)

	if (Pivot.x == p2.x) // A p2 és a Pivot vonala 90 fokot zár be az x tengellyel
		{
			if (Pivot.x == p1.x) //mindkét ponttal 90 fokot zár be, tehát egyik sem "kisebb"
				return 0;
			else
				return 1; //a p1 valóban "kisebb" p2-nél
		}
	if (Pivot.x == p1.x)
		return 0;

// Normális eset(ek):
	GetTangents(p1 , p2 , Pivot, p1tangent, p2tangent);
	return p1tangent < p2tangent;
}




bool Greater (Pont p1 , Pont p2 , Pont Pivot)
{
	double p1tangent,p2tangent;

//Speciális eset kategória #1: amikor az x koordináta megegyezik (90 fokot zár be az x tengellyel)

	if (Pivot.x == p1.x) // A p1 és a Pivot vonala 90 fokot zár be az x tengellyel
		{
			if (Pivot.x == p2.x) //mindkét ponttal 90 fokot zár be, tehát egyik sem "kisebb"
				return 0;
			else
				return 1; //a p2 valóban "kisebb" p2-nél
		}
	if (Pivot.x == p2.x)
		return 0;

// Normális eset(ek):

	GetTangents(p1 , p2 , Pivot, p1tangent, p2tangent);

	return p1tangent > p2tangent;
}




void QuickSortPoints(Pont array[],int lower_border,int upper_border, char c) //az algoritmus növekvő, vagy csökkenő rendbe rendez a megkapott karaktertől függően (i = increase ; d = decrease)
{
	int i = lower_border,j = upper_border,n = (lower_border + upper_border) / 2;
	Pont x,helper;
	if (c == 'i')
		{
			if (upper_border <= 1) //nincs mit rendezni
				return;
		}
	else
	if (c == 'd')		
		{
			if (lower_border-1 == upper_border) //nincs mit rendezni
				return;
		}
	x = array[n];
	do{
		if (c == 'i')
		{
//Ebben keletkezik a szegmens hiba
			while (Smaller (array[i] , x , array[0]) && i < j) i++;
//Ebben keletkezik a szegmens hiba
			while (Greater (array[j] , x , array[0]) && i < j) j--;
		}
		else
		if (c == 'd')
		{
			while (Greater (array[i] , x , array[0]) && i < j) i++;
			while (Smaller (array[j] , x , array[0]) && i < j) j--;
		}

		if (i <= j)
		{
			helper = array[i];
			array[i] = array[j];
			array[j] = helper;
			i++;
			j--;
		}
			
	}while (i <= j);
		
	if (lower_border < j)
		QuickSortPoints(array,lower_border,j, c);
	if (i < upper_border)
		QuickSortPoints(array,i,upper_border, c);
}



	
void MaxSearch(Pont array[], int n)
	{
		Pont csere;
		for (int i=1 ; i < n ; i++)
			{
				if ( (array[i].y > array[0].y) || (array[i].y == array[0].y && array[i].x < array[0].x) )
					{
						csere = array[i];
						array[i] = array[0];
						array[0] = csere;
					}
					
			}
	}
	
template <class T>
void GrahamScan(Pont array[], ChainedList<T> &L, int n)
	{
		if (n <= 1) //ha egy vagy nulla pont van...
			{
				L.insertAfter(array[0]);
				return;
			}
// I. A leg alacsonyabban lévő pont kerül előre
		MaxSearch(array, n);
		int j,k;
		Pont csere;
//II. Előre rendezzük a P-től jobbra lévő pontokat (és így persze a tőle balra levők hátra kerülnek) Ez buborékrendezéshez hasonló algoritmus
		k = 0; //A k vált. mindig a legutóbbi olyan pont indexe, amit nem kell cserélni
		for ( int i = 1; i < n ;i++ )
		{
	
			j = 0;
			if ( array[i].x < array[0].x )
			{
				j = i+1;
				while (j < n) 
				{
					if ( array[j].x >= array[0].x )
					{
						csere = array[j];
						array[j] = array[i];
						array[i] = csere;
						break;
					}
					j++;
				} 


			}
			else
				k = i;
	
	
			if (j == n)
			{
				k = i-1;
				break;
			}
			else
				k = i;
		}

// III. és IV. rész: rendezés a P és adott pont által meghatározott vonal X tengellyel bezárt szöge szerint
		QuickSortPoints(array,1,k, 'i');
		QuickSortPoints(array,k+1,n-1, 'd');
//Itt kezdődik az igazi Graham scan
		//double direction;
		Pont p1 = array[0],p2 = array[1],p3;

		
		L.insertAfter(p1);
		L.insertAfter(p2);


		for (int i = 2 ; i < n ; i++ )
		{
			p3 = array[i];
			L.insertAfter(p3);

			while (Whatdirection(p1, p2, p3) <= 0)
			{
				L.removeAfter();
				L.insertAfter(p3);
				i++;
				p3 = array[i];
			}

			p1 = p2;
			p2 = p3;

		}	
	}
	
	
	int main(int argc, char *argv[])
	{
  
	
		int n;
		cin >> n;
		Pont array[n];
		for (int i = 0;i < n;i++)
		{
			cin >> array[i].x;
			cin >> array[i].y;
		}
		ChainedList<Pont> L;
		GrahamScan(array,L,n);
		
		while (L.notEmpty)
		{
			cout << "( " << L.Next().x << " ; " << L.Next().y << " )" << '\n';
			L.removeAfter();
			std::cout << L.notEmpty << '\n';
		}
	
	}





kanesoban (39)
ChainedList.h :

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
 
#ifndef CHAINEDLIST_H
#define CHAINEDLIST_H

#include "Node.h"

template <class T>
class ChainedList
{
	private:

		Node<T> * Head;

	public:

		//Node<T> * Pointer;
		//T Element;
		bool notEmpty;
		ChainedList();
		Node<T> getNode ( int n );
		void insertAfter ( Node<T> &node, Node<T> &newNode );
		void insertAfter ( Node<T> &newNode );
		void insertAfter ( T _Data );
		void removeAfter ( Node<T> &node );
		void removeAfter();
		T Next();
		~ChainedList();

};

template <class T>
ChainedList<T>::ChainedList()
{
	Head = 0;
	notEmpty = 0;
	//Pointer = Head;
}

template <class T>
Node<T> ChainedList<T>::getNode ( int n )
{
	Node<T> node;
	Node<T>* pointer = Head;
	Node<T>* last;
	last = pointer;

//Hibakezelés: out of range  !!!!!
	for ( int i = 1;i < n;i++ )
	{
		pointer = ( *last ).Next;
		last = pointer;
	}
	node = *pointer;
	return node;
}


template <class T>
void ChainedList<T>::insertAfter ( Node<T> &node, Node<T> &newNode ) // newNode beszúrása node után
{
	newNode.Next = node.Next; // newNode rákövetkező cellája node eddigi rákövetkező cellája lesz
	node.Next = &newNode;   // node rákövetkező cellája mostantól newNode
	notEmpty = 1;
}
template <class T>
void ChainedList<T>::insertAfter ( Node<T> &newNode ) // newNode beszúrása a lista elejére
{
	newNode.Next = Head;    // newNode után következik a teljes eddigi lista
	Head = &newNode; // newNode a lista új feje
	notEmpty = 1;
}

template <class T>
void ChainedList<T>::insertAfter ( T _Data )
{
	Node<T> * newNode = new Node<T>;
	newNode->Data = _Data;
	newNode->Next = Head;
	Head = newNode;
	notEmpty = 1;
}

template <class T>
void ChainedList<T>::removeAfter ( Node<T> &node ) // a node után következő cella eltávolítása
{
	if ( Head == 0 )
		{
			notEmpty = 0;
			return;
		}
	Node<T> * nodeBeingRemoved = node.Next; // ezt a cellát akarjuk eltávolítani
	node.Next = ( *node.Next ).Next; // node rákövetkező eleme mostantól az eddig kettővel utána álló lesz
	delete nodeBeingRemoved;     // a törölt cella memóriaterületének felszabadítása
	if ( Head == 0 )
		notEmpty = 0;
}

template <class T>
void ChainedList<T>::removeAfter() // a node után következő cella törlése
{
	if ( Head == 0 )
		{
			notEmpty = 0;
			return;
		}
	Node<T> * nodeBeingRemoved = Head; // ezt a cellát akarjuk törölni
	Head = Head->Next;
	delete nodeBeingRemoved;     // a törölt cella memóriaterületének felszabadítása
	if ( Head == 0 )
		notEmpty = 0;
//std::cout << "Valami" << '\n';
}

template <class T>
ChainedList<T>::~ChainedList()
{

	Node<T>* p1;
	Node<T>* p2;
	p1 = Head;
	do
	{
		p2 = ( *p1 ).Next;
		( *p1 ).Next = 0;
		p1 = p2;
	}
	while ( ( *p1 ).Next != 0 );


}

template <class T>
T ChainedList<T>::Next()
{
	return Head->Data;
}

#endif


kanesoban (39)
Node.h :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
 
#ifndef NODE_H
#define NODE_H
		template <class T>
		class Node
			{
				public:
				Node()
					{
						Next = 0;
					}
				Node(T _Data)
					{
						Data = _Data;
						Next = 0;
					}
				T Data;
				Node<T> * Next;
			};

#endif


kanesoban (39)
Pont.h :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
class Pont
{
	public:
		double x,y;

		Pont()
		{
			x = 0;
			y = 0;
		}

		Pont(double _x, double _y)
		{
			x = _x;
			y = _y;
		}

};

helios (17607)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 
template <class T>
ChainedList<T>::~ChainedList()
{

	Node<T>* p1;
	Node<T>* p2;
	//This line is the one causing problems. You never check if this->Head==0...
	p1 = Head;
	do
	{
		//...so when you try to dereference this pointer, all hell breaks loose.
		p2 = ( *p1 ).Next;
		( *p1 ).Next = 0;
		p1 = p2;
	}
	while ( ( *p1 ).Next != 0 );


}
Topic archived. No new replies allowed.