Merge Sort and Linked Lists

yoked88 (140)
I am getting an error trying to convert from nodeType<Type> to nodeType<Type>* in my recursiveSort function and I do not know why this is happening. Can anyone help?

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
 
#ifndef H_linkedListIterator
#define H_linkedListIterator
#include <iostream>

template <class Type>
struct nodeType
{
	Type info;
	nodeType<Type> *link;
};

template <class Type>
class linkedListIterator
{
public:
	linkedListIterator();
	linkedListIterator(nodeType<Type>*);
	Type operator*();
	linkedListIterator<Type> operator++();
	bool operator==(const linkedListIterator<Type>&) const;
	bool operator!=(const linkedListIterator<Type>&) const;
private:
	nodeType<Type> *current;
};

template <class Type>
linkedListIterator<Type>::linkedListIterator()
{
	current = NULL;
}

template <class Type>
linkedListIterator<Type>::linkedListIterator(nodeType<Type> *ptr)
{
	current = ptr;
}

template <class Type>
Type linkedListIterator<Type>::operator *()
{
	return current->info;
}

template <class Type>
linkedListIterator<Type> linkedListIterator<Type>::operator ++()
{
	current = current->link;
	return *this;
}

template <class Type>
bool linkedListIterator<Type>::operator ==(const linkedListIterator<Type>& other) const
{
	return (current == other.current);
}

template <class Type>
bool linkedListIterator<Type>::operator !=(const linkedListIterator<Type>& other) const
{
	return (current != other.current);
}

#endif 


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
 
#ifndef H_linkedListType
#define H_linkedListType
#include "linkedListIterator.h"
#include <iostream>
#include <cassert>

using namespace std;

template <class Type>
class linkedListType
{
public:
	const linkedListType<Type>& operator=(const linkedListType<Type>&); //
	void initializeList(); //
	bool isEmptyList() const; //
	void print() const; //
	int length() const; //
	void destroyList(); //
	Type front() const; //
	Type back() const; //
	virtual bool search(const Type&) const = 0;
	virtual void insertFirst(const Type&) = 0;
	virtual void insertLast(const Type&) = 0;
	virtual void deleteNode(const Type&) = 0;
	linkedListIterator<Type> begin(); //
	linkedListIterator<Type> end(); //
	linkedListType(); //
	linkedListType(const linkedListType<Type>&); //
	~linkedListType(); //
protected:
	int count;
	nodeType<Type> *first;
	nodeType<Type> *last;
private:
	void copyList(const linkedListType<Type>&); //
};

template <class Type>
bool linkedListType<Type>::isEmptyList() const
{
	return (first == NULL);
}

template <class Type>
linkedListType<Type>::linkedListType()
{
	first = NULL;
	last = NULL;
	count = 0;
}

template <class Type>
void linkedListType<Type>::destroyList()
{
	nodeType<Type> *temp;
	while(first != NULL)
	{
		temp = first;
		first = first->link;
		delete temp;
	}
	last = NULL;
	count = 0;
}

template <class Type>
void linkedListType<Type>::initializeList()
{
	destroyList();
}

template <class Type>
void linkedListType<Type>::print() const
{
	nodeType<Type> *current;
	current = first;
	while(current != NULL)
	{
		cout << current->info << " ";
		current = current->link;
	}
}

template <class Type>
int linkedListType<Type>::length() const
{
	return count;
}

template <class Type>
Type linkedListType<Type>::front() const
{
	assert(first != NULL);
    return first->info;
}

template <class Type>
Type linkedListType<Type>::back() const
{
	assert(last != NULL);
	return last->info;
}

template <class Type>
linkedListIterator<Type> linkedListType<Type>::begin()
{
	linkedListIterator<Type> temp(first);
	return temp;
}

template <class Type>
linkedListIterator<Type> linkedListType<Type>::end()
{
	linkedListIterator<Type> temp(NULL);
	return temp;
}

template <class Type>
void linkedListType<Type>::copyList(const linkedListType<Type>& other)
{
	nodeType<Type> *newNode, *current;
	if(first != NULL)
		destroyList();
	if(other.first == NULL)
	{
		first = NULL;
		last = NULL;
		count = 0;
	}
	else
	{
		current = other.first;
		count = other.count;
		first = new nodeType<Type>;
		first->info = current->info;
		first->link = NULL;
		last = first;
		current = current->link;
		while(current != NULL)
		{
			newNode = new nodeType<Type>;
			newNode->info = current->info;
			newNode->link = NULL;
			last->link = newNode;
			last = newNode;
			current = current->link;
		}
	}
}

template <class Type>
linkedListType<Type>::~linkedListType()
{
	destroyList();
}

template <class Type>
linkedListType<Type>::linkedListType(const linkedListType<Type>& other)
{
	first = NULL;
	copyList(other);
}

template <class Type>
const linkedListType<Type>& linkedListType<Type>::operator =(const linkedListType<Type>& other)
{
	if(this != &other)
	{
		copyList(other);
	}
	return *this;
}

#endif
Last edited on
yoked88 (140)
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
 
 
#ifndef H_unorderedLinkedList
#define H_unorderedLinkedList
#include "linkedListType.h"

using namespace std;

template <class Type>
class unorderedLinkedList: public linkedListType<Type>
{
public:
	bool search(const Type&) const;
	void insertFirst(const Type&);
	void insertLast(const Type&);
	void deleteNode(const Type&);
	void divideList(nodeType<Type>*,nodeType<Type>*&);
	nodeType<Type> mergeList(nodeType<Type>*,nodeType<Type>*);
	void recursiveSort(nodeType<Type>*&);
	void mergeSort();
};

template <class Type>
bool unorderedLinkedList<Type>::search(const Type& searchItem) const
{
	nodeType<Type> *current;
	bool found = false;
	current = first;
	while(current != NULL && !found)
		if(current->info == searchItem)
			found = true;
		else
			current = current->link;
	return found;
}

template <class Type>
void unorderedLinkedList<Type>::insertFirst(const Type& item)
{
	nodeType<Type> *newNode;
	newNode = new nodeType<Type>;
	newNode->info = item;
	newNode->link = first;
	first = newNode;
	count++;
	if(last == NULL)
		last = newNode;
}

template <class Type>
void unorderedLinkedList<Type>::insertLast(const Type& item)
{
	nodeType<Type> *newNode;
	newNode = new nodeType<Type>;
	newNode->info = item;
	newNode->link = NULL;
	if(first == NULL)
	{
		first = newNode;
		last = newNode;
		count++;
	}
	else
	{
		last->link = newNode;
		last = newNode;
		count++;
	}
}

template <class Type>
void unorderedLinkedList<Type>::deleteNode(const Type& item)
{
	nodeType<Type> *current, *trailCurrent;
	bool found;
	if(first == NULL)
		cout << "The list is empty." << endl;
	else
	{
		if(first->info == item)
		{
			current = first;
			first = first->link;
			count--;
			if(first == NULL)
				last = NULL;
			delete current;
		}
		else
		{
			found = false;
			trailCurrent = first;
			current = first->link;
			while(current != NULL && !found)
			{
				if(current->info != item)
				{
					trailCurrent = current;
					current = current->link;
				}
				else
					found = true;
			}
			if(found)
			{
				trailCurrent->link = current->link;
				count--;
				if(last == current)
					last = trailCurrent;
				delete current;
			}
			else
				cout << "Item not found in list." << endl;
		}
	}
}

template <class Type>
void unorderedLinkedList<Type>::divideList(nodeType<Type> * first1, nodeType<Type>* &first2)
{
	nodeType<Type> *middle, *current;
	if(first1 == NULL) //list is empty
		first2 = NULL;
	else if(first1->link == NULL)  //list only has one node
		first2 = NULL;
	else
	{
		middle = first1;
		current = first1->link;
		if(current != NULL) //list has more than two nodes
			current = current->link;
		while(current != NULL)
		{
			middle = middle->link;
			current = current->link;
			if(current != NULL)
				current = current->link;
		}
		first2 = middle->link; //points to first node of second sublist
		middle->link = NULL; //link of last node of first sublist set to null
	}
}

template <class Type>
nodeType<Type> unorderedLinkedList<Type>::mergeList(nodeType<Type>* first1, nodeType<Type>* first2)
{
	nodeType<Type> *lastSmall, *newHead;
	if(first1 == NULL)
		return first2;
	else if(first2 == NULL)
		return first1;
	else
	{
		if(first1->info < first2->info)
		{
			newHead = first1;
			first1 = first1->link;
			lastSmall = newHead;
		}
		else
		{
			newHead = first2;
			first2 = first2->link;
			lastSmall = newHead;
		}
		while(first1 != NULL && first2 != NULL)
		{
			if(first1->info < first2->info)
			{
				lastSmall->link = first1;
				lastSmall = lastSmall->link;
				first1 = first1->link;
			}
			else
			{
				lastSmall->link = first2;
				lastSmall = lastSmall->link;
				first2 = first2->link;
			}
		}
		if(first1 == NULL) //first sublist if processed first
			lastSmall->link = first2;
		else  //second sublist is processed first
			lastSmall->link = first1;
		return newHead;
	}
}

template <class Type>
void unorderedLinkedList<Type>::recursiveSort(nodeType<Type>* &head)
{
	nodeType<Type> *otherHead;
	if(head != NULL)
		if(head->link != NULL)
		{
			divideList(head,otherHead);
			recursiveSort(head);
			recursiveSort(otherHead);
			head = mergeList(head,otherHead);
		}
}

template <class Type>
void unorderedLinkedList<Type>::mergeSort()
{
	recursiveSort(first);
	if(first == NULL)
		last = NULL;
	else
	{
		last = first;
		while(last->link != NULL)
			last = last->link;
	}
}

#endif 


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
 
#include <iostream>
#include "unorderedLinkedList.h"

using namespace std;

int main()
{
	unorderedLinkedList<int> list1;
	list1.insertLast(65);
	list1.insertLast(18);
	list1.insertLast(85);
	list1.insertLast(95);
	list1.insertLast(25);
	list1.insertLast(20);
	list1.insertLast(45);
	list1.insertLast(75);
	list1.insertLast(30);
	cout << "list1 = ";
	list1.print();
	cout << endl;
	list1.mergeSort();
	cout << "list1 = ";
	list1.print();
	cout << endl;
	system("PAUSE");
	return 0;
}
yoked88 (140)
Would anyone mind compiling my code and letting me know what is happening? Any help is appreciated and thank you in advance.
long double main (999)
You have
nodeType<Type> mergeList(nodeType<Type>*,nodeType<Type>*);

but in your recursiveSort function, you do
head = mergeList(head,otherHead);

So you try to assign a value of type nodeType<Type> to head, which is a nodeType<Type>* variable.
yoked88 (140)
I'm still a bit confused because I pass head as a pointer and reference parameter, so shouldn't it be okay? For instance when I call didiveList, both parameters are pointers and it accepts head as a pointer actual parameter.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
 
template <class Type>
void unorderedLinkedList<Type>::recursiveSort(nodeType<Type>* &head)
{
	nodeType<Type> *otherHead;
	if(head != NULL)
		if(head->link != NULL)
		{
			divideList(head,otherHead);
			recursiveSort(head);
			recursiveSort(otherHead);
			head = mergeList(head,otherHead);
		}
}


It also lets me call recursiveSort function with head as a pointer variable, so I'm not really sure what is causing this error.


 error C2440: '=' : cannot convert from 'nodeType<Type>' to 'nodeType<Type> *'
yoked88 (140)
Can anyone help me fix this?
Smac89 (1727)
As @ long double main pointed out, your mergeList function needs to return a pointer and that is exactly what the error message is referring to.

Also remember to pass your pointers by ref if you wish to modify the underlying list
yoked88 (140)
This was one of those errors that made me feel stupid. I had a meeting at work this morning and while waiting for it to begin, I started looking over my code and had a major epiphany and realized that I didn't have the return type of my mergeList function as a pointer. Problem solved! Thanks to all who replied.
Topic archived. No new replies allowed.