C++

Forum

 
Cannot find where the memory leak is

mlholder (77)
Hi all,

I'am slowly working on a program that takes adds, subtracts and multiplies polynomials. I'm trying to implement the polynomial as a singly linked list. However, I keep getting a memory leak and I'am sure that I am deleting the allocated memory as needed. I'am hoping someone with more experience than I can look at the code and provide any hints as to where and why this is happening. Also, why is it that when I click the Preview button, it never shows me what I'm about to post? Thank you for any and all help and for your time.

File: Node.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
 
#ifndef NODE_H
#define NODE_H

class Node
{
	public:
		Node();
		Node(int);
		Node(int, int);
		Node(int, int, Node*);
		~Node();
		int getCoefficient() const;
		int getExponent() const;
		Node* getNext() const;
		void setCoefficient(int);
		void setExponent(int);
		void setNext(Node*);

	private:
		int coefficient;
		int exponent;
		Node *next;
		friend class LinkedList;
};

#endif


File: Node.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
 
#include <iostream>
#include "Node.h"

Node::Node()
{

}

Node::Node(int coef) : coefficient(coef), exponent(0), next(nullptr)
{

}

Node::Node(int coef, int expo) : coefficient(coef), exponent(expo), next(nullptr)
{

}

Node::Node(int coef, int expo, Node *ptr) : coefficient(coef), exponent(expo), next(ptr)
{

}

Node::~Node()
{
	//delete next;
}

int Node::getCoefficient() const
{
	return (coefficient);
}

int Node::getExponent() const
{
	return (exponent);
}

Node* Node::getNext() const
{
	return (next);
}

void Node::setCoefficient(int coef)
{
	coefficient = coef;
}

void Node::setExponent(int expo)
{
	exponent = expo;
}

void Node::setNext(Node *ptr)
{
	next = ptr;
}


File: Linked List.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
 
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
#include "Node.h"

class LinkedList
{
	public:
		LinkedList();
		LinkedList(const LinkedList&);
		~LinkedList();
		bool empty() const;
		friend std::ostream& operator<<(std::ostream&, const LinkedList&);

		friend std::istream& operator>>(std::istream&, LinkedList&);
		void insertHead(int);
		void insertHead(int, int);
		void append(int);
		void append(int, int);
		void remove(Node*);

	private:
		Node *head;
};

#endif


File: Linked List.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
 
 #include <iostream>
#include <cstdlib>
#include <cctype>
#include <string>
#include "Node.h"
#include "Linked List.h"

LinkedList::LinkedList() : head(nullptr)
{

}

LinkedList::LinkedList(const LinkedList &list)
{
	head = nullptr;
	Node *iterator = list.head;

	while(iterator != nullptr)
	{
		append(iterator->getCoefficient(), iterator->getExponent());
		iterator = iterator->getNext();
	}
}

LinkedList::~LinkedList()
{
	while(!empty())
	{
		Node *temp = head;
		head = head->getNext();
		delete temp;
	}

	delete head;

	_CrtDumpMemoryLeaks();
}

bool LinkedList::empty() const
{
	return (head == nullptr);
}

std::ostream& operator<<(std::ostream &ostr, const LinkedList &list)
{
	for(Node *iterator = list.head; iterator != NULL; iterator = iterator->getNext())
	{
		//Output the first term
		if(iterator == list.head)
		{
			if(iterator->getExponent() == 0)
				ostr << iterator->getCoefficient();
			else if(iterator->getExponent() == 1)
				ostr << iterator->getCoefficient() << 'x';
			else
				ostr << iterator->getCoefficient() << "x^" << iterator->getExponent();
		}

		else //Output all other terms
		{
			if(iterator->getExponent() == 0)
			{
				if(iterator->getCoefficient() < 0)
					ostr << " - " << -(iterator->getCoefficient());
				else
					ostr << " + " << iterator->getCoefficient();
			}
			else if(iterator->getExponent() == 1)
			{
				if(iterator->getCoefficient() < -1)
					ostr << " - " << -(iterator->getCoefficient()) << 'x';
				else if(iterator->getCoefficient() == -1)
					ostr << " - x";
				else if(iterator->getCoefficient() == 1)
					ostr << " + x";
				else
					ostr << " + " << iterator->getCoefficient() << 'x';
			}
			else
			{
				if(iterator->getCoefficient() < -1)
					ostr << " - " << -(iterator->getCoefficient()) << "x^" << iterator->getExponent();
				else if(iterator->getCoefficient() == -1)
					ostr << " - x^" << iterator->getExponent();
				else if(iterator->getCoefficient() == 1)
					ostr << " + x^" << iterator->getExponent();
				else
					ostr << " + " << iterator->getCoefficient() << "x^" << iterator->getExponent();
			}
		}
	}

	return (ostr);
}

std::istream& operator>>(std::istream &istr, LinkedList &list)
{
	using namespace std;

	bool term(false), negate(false), foundCoef(false);
	int coef, expo;
	string expression;

	getline(cin, expression);

	for(int index = 0; index < expression.length(); index++)
	{
		//Coefficients
		if(isdigit(expression[index]))
		{
			foundCoef = true;
			int tempIndex = index;
			while(isdigit(expression[index]))
			{
				index++;
				if(index == expression.length())
				{
					coef = atoi(expression.substr(tempIndex, index - tempIndex).c_str());
					if(negate)
						coef = -coef;
					list.append(coef);
					return (istr);
				}
			}

			coef = atoi(expression.substr(tempIndex, index - tempIndex).c_str());
			if(negate)
			{
				coef = -coef;
				negate = false;
			}

			index--;
		}

		//Variables
		else if(isalpha(expression[index]))
		{
			if(!foundCoef)
				coef = 1;
			expo = 1;

			if(index == expression.length() - 1)
			{
				if(negate)
					coef = -coef;
				list.append(coef, expo);
				return (istr);
			}
		}

		//Exponents
		else if(expression[index] == '^')
		{
			index++;
			int tempIndex = index;
			while(isdigit(expression[index]))
			{
				index++;
				if(index == expression.length())
				{
					expo = atoi(expression.substr(tempIndex, index - tempIndex).c_str());
					if(negate)
						coef = -coef;
					list.append(coef, expo);
					return (istr);
				}
			}

			expo = atoi(expression.substr(tempIndex, index - tempIndex).c_str());
			index--;
		}

		//Term Dividers and Negative Signs
		else if( (expression[index] == '+') || (expression[index] == '-') )
		{
			if(expression[index] == '-')
			{
				negate = true;
				if(index > 0)
					term = true;
			}
			else
			{
				term = true;
			}

			if(term)
			{
				term = false;
				foundCoef = false;
				list.append(coef, expo);
			}
		}
	}

	return (istr);
}

void LinkedList::insertHead(int coef)
{
	Node *temp = new Node(coef);

	if(!empty())
		temp->setNext(head->getNext());

	head = temp;
}

void LinkedList::insertHead(int coef, int expo)
{
	Node *temp = new Node(coef, expo);

	if(!empty())
		temp->setNext(head->getNext());

	head = temp;
}

void LinkedList::append(int coef)
{
	Node *temp = new Node(coef);

	if(empty())
		insertHead(coef);
	else
	{
		Node *iterator = head;
		while(iterator->getNext() != nullptr)
			iterator = iterator->getNext();
		iterator->setNext(temp);
	}
}

void LinkedList::append(int coef, int expo)
{
	Node *temp = new Node(coef, expo);

	if(empty())
		insertHead(coef, expo);
	else
	{
		Node *iterator = head;
		while(iterator->getNext() != nullptr)
			iterator = iterator->getNext();
		iterator->setNext(temp);
	}
}

void LinkedList::remove(Node *ptr)
{
	if(empty())
		return;
	else
	{
		if(ptr == head)
			head = head->getNext();
		else
		{
			Node *iterator = head;
			while(iterator->getNext() != ptr)
				iterator = iterator->getNext();
			iterator->setNext(ptr->getNext());
		}

		delete ptr;
	}
}


File: Polynomial Operations.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
#include <iostream>
#include "Linked List.h"

#define CRTDBG_MAP_ALLOC
#include <stdlib.h>
#include <crtdbg.h>

int main()
{
	using namespace std;

	char ch;
	LinkedList list;

	cout << "Enter a polynomial expression.\n";
	cin >> list;
	cout << endl;

	cout << list << endl;

	cin.get(ch);
	return 0;
}
Last edited on
helios (17574)
Your insertion is incorrect. You do
1
2
3
4
 
temp = new Node;
if (!this->empty())
    temp->next = this->head->next;
this->head = temp;
This code leaks the head node. The correct insertion is
1
2
3
4
 
temp = new Node;
//Assumption this->head == nullptr iff this->empty()
temp->next = this->head;
this->head = temp;
mlholder (77)
Thank you helios. I coded the insertion functions off the top of my head and didn't look back, thus assuming they were correct. Do you happen to know why, when I try to preview my posts, the only thing it shows is a blank post with my user name?
mlholder (77)
Ok, so after changing my head insertion functions, the debugger is still complaining about a memory leak. Any ideas?

1
2
3
4
5
6
7
8
9
 
void LinkedList::insertHead(int coef)
{
	Node *temp = new Node(coef);

	if(!empty())
		temp->setNext(head);

	head = temp;
}


The constructor for the node is

1
2
3
4
 
Node::Node(int coef) : coefficient(coef), exponent(0), next(nullptr)
{

}
mlholder (77)
After changing my insertion functions and also looking at the append functions, the memory leak was occuring due to calling new twice, once in the append function and once in the insertHead functions. Therefore the memory leak was coming from my append functions. I am posting this for anyone who is currently learning linked lists.
Topic archived. No new replies allowed.