Issue with array-based mergesort

.h file
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
#include <iostream>
#include <cassert>

using namespace std;

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

template<class Type>
class arrayListType
{
public:
	void print() const;
	void insertAt(int location, const Type& insertItem);
	arrayListType(int size = 100);
	arrayListType(const arrayListType<Type>& otherList);
protected:
	Type *list;
	int length;
	int maxSize;
	nodeType<Type> *first; //pointer to the first node of the list
    nodeType<Type> *last;  //pointer to the last node of the list
};

template<class Type>
class orderedArrayListType: public arrayListType<Type>
{
public:
	int binarySearch(const Type& item) const;
	void selectionSort();
	orderedArrayListType(int size = 100);
	void mergeSort();
private:
	void divideList(nodeType<Type>* first1, nodeType<Type>* &first2);
	nodeType<Type>* mergeList(nodeType<Type>* first1, nodeType<Type>* first2);
	void recMergeSort(nodeType<Type>* &head);
};
template <class Type>
void arrayListType<Type>::print() const
{
	int i;

	for (i = 0; i < length; i++)
		cout << list[i] << " ";
	cout << endl;
}



template <class Type>
void arrayListType<Type>::insertAt(int location, const Type& insertItem)
{
	int  i;

	if (location < 0 || location >= maxSize)
		cout << "The position of the item to be inserted "
			 << "is out of range." << endl;
	else
		if (length >= maxSize)  //list is full
			cout << "Cannot insert in a full list" << endl;
		else
		{
			for (i = length; i > location; i--)
				list[i] = list[i - 1];	//move the elements down

			list[location] = insertItem;	//insert the item at the 
 										//specified position

			length++;	//increment the length
		}
} //end insertAt

template <class Type>
arrayListType<Type>::arrayListType(int size)
{
	if (size <= 0)
	{
		cout << "The array size must be positive. Creating "
 			 << "an array of size 100. " << endl;

 	   maxSize = 100;
 	}
 	else
 	   maxSize = size;

	length = 0;

	list = new Type[maxSize];
	assert(list != NULL);
}
//*************************************************************//
template<class Type>
int orderedArrayListType<Type>::binarySearch(const Type& item) const
{
	int first = 0;
	int last = length - 1;
	int mid;

	bool found = false;

	while (first <= last && !found)
	{
		mid = (first + last) / 2;

		if (list[mid] == item)
			found = true;
		else
			if (list[mid] > item)
				last = mid - 1;
			else
				first = mid + 1;
	}

	if (found)
		return mid;
	else 
		return -1;
}// end binarySearch

template<class Type>
void orderedArrayListType<Type>::selectionSort()
{
	int loc, minIndex;

	for (loc = 0; loc < length; loc++)
	{
		minIndex = minLocation(loc, length - 1);
		swap(loc, minIndex);
	}
}

template<class Type>
orderedArrayListType<Type>::orderedArrayListType(int size): arrayListType<Type>(size)
{
}

template<class Type>
void orderedArrayListType<Type>::mergeSort()
{
	recMergeSort(first);
}


template<class Type>
void orderedArrayListType<Type>::divideList(nodeType<Type>* first1, nodeType<Type>* &first2)
{
	nodeType<Type>* middle;
	nodeType<Type>* current;

	if (first1 == NULL)   //list is empty
		first2 = NULL;
	else
		if(first1->link == NULL)	//list has only one node
			first2 = NULL;
		else
		{
			middle = first1;
			current = first1->link;
			if (current != NULL)  	//list has more that two nodes
				current = current->link;

			while (current != NULL)
			{
				middle = middle->link;
				current = current->link;
				if (current != NULL)
					current = current->link;
			} //end while

			first2 = middle->link;  //first2 points to the first 
 								    //node of the second sublist
			middle->link = NULL;    //set the link of the last node 
    					              //of the first sublist to NULL
		} //end else
} //end divide

template<class Type>
nodeType<Type>* orderedArrayListType<Type>::mergeList (nodeType<Type>* first1, nodeType<Type>* first2)
{
	nodeType<Type> *lastSmall; //pointer to the last node of 
  					    //the merged list
	nodeType<Type> *newHead;   //pointer to the merged list

	if (first1 == NULL)   //the first sublist is empty
		return first2;
	else
		if (first2 == NULL)   //the second sublist is empty
			return first1;
		else
		{
			if (first1->info < first2->info) //compare the first nodes
			{
				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;
				}
			} //end while

			if (first1 == NULL)  	  //first sublist is exhausted first
				lastSmall->link = first2;
			else			  //second sublist is exhausted first
				lastSmall->link = first1;

	   return newHead;
	}	
}//end mergeList

template<class Type>
void orderedArrayListType<Type>::recMergeSort(nodeType<Type>* &head)
{
	nodeType<Type> *otherHead;

	if (head != NULL)  //if the list is not empty
	   if(head->link != NULL)  //if the list has more than one node
	   {
			divideList(head, otherHead);
			recMergeSort(head);
			recMergeSort(otherHead);
			head = mergeList(head, otherHead);
	   }
} //end recMergeSort 

.cpp file
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
#include <iostream>
#include "hw5resourcepart2.cpp"

using namespace std;

int main()
{
	orderedArrayListType<int> intList;

	int number, count;

	cout << "Please enter 5 numbers:" << endl;

	for (count = 0; count < 5; count++)
	{
		cin >> number;
		intList.insertAt(count, number);
	}

	cout << endl << "List: ";
	intList.print();
	cout << endl;

	intList.mergeSort();

	cout << endl << "After Sorting List: ";
	intList.print();
	cout << endl;

	system("pause");
	return 0;
}



My issue is when I go to compile it, I get an error code Unhandled exception at 0x00ec2680. 0xC0000005: Access violation reading location 0xccccccd0.. When I went to step through the program, the error pops up when I reach intList.mergeSort(); in the .cpp file and if(head->link) in void orderedArrayListType<Type>::recMergeSort(nodeType<Type>* &head). I feel like something is not putting a value into link which causes the error. Am I correct on this part? I feel like it's missing something like
1
2
3
newNode->info = newItem; 	   //store the new item in the node
   newNode->link = first;        //insert newNode before first
   first = newNode;
Topic archived. No new replies allowed.