Hello, can I get some help with my code? I don't know why it does not work.

This is my code:

linkedList.h

#ifndef LINKEDLIST_H

#define LINKEDLIST_H

#include

#include

using namespace std;

//Definition of the node

template

struct nodeType

{

Type info;

nodeType *link;

};

template

class linkedListIterator

{

public:

linkedListIterator();

//Default constructor

//Postcondition: current = nullptrptr;

linkedListIterator(nodeType *ptr);

//Constructor with a parameter.

//Postcondition: current = ptr;

Type operator*();

//Function to overload the dereferencing operator *.

//Postcondition: Returns the info conatined in the node.

linkedListIterator operator++();

//Overload the pre-increment operator.

//Postcondition: The iterator is advanced to the next

// node.

bool operator==(const linkedListIterator& right) const;

//Overload the equality operator.

//Postcondition: Returns true if this iterator is equal to

// the iterator specified by right,

// otherwise it returns the value false.

bool operator!=(const linkedListIterator& right) const;

//Overload the not equal to operator.

//Postcondition: Returns true if this iterator is not

// equal to the iterator specified by

// right; otherwise it returns the value

// false.

private:

nodeType *current; //pointer to point to the current

//node in the linked list

};

template

linkedListIterator::linkedListIterator()

{

current = nullptrptr;

}

template

linkedListIterator::

linkedListIterator(nodeType *ptr)

{

current = ptr;

}

template

Type linkedListIterator::operator*()

{

return current->info;

}

template

linkedListIterator linkedListIterator::operator++()

{

current = current->link;

return *this;

}

template

bool linkedListIterator::operator==

(const linkedListIterator& right) const

{

return (current == right.current);

}

template

bool linkedListIterator::operator!=

(const linkedListIterator& right) const

{ return (current != right.current);

}

//***************** class linkedListType ****************

template

class linkedListType

{

public:

const linkedListType& operator=

(const linkedListType&);

//Overload the assignment operator.

void initializeList();

//Initialize the list to an empty state.

//Postcondition: first = nullptrptr, last = nullptrptr, count = 0;

bool isEmptyList() const;

//Function to determine whether the list is empty.

//Postcondition: Returns true if the list is empty,

// otherwise it returns false.

void print() const;

//Function to output the data contained in each node.

//Postcondition: none

int length() const;

//Function to return the number of nodes in the list.

//Postcondition: The value of count is returned.

void destroyList();

//Function to delete all the nodes from the list.

//Postcondition: first = nullptr, last = nullptr, count = 0;

Type front() const;

//Function to return the first element of the list.

//Precondition: The list must exist and must not be

// empty.

//Postcondition: If the list is empty, the program

// terminates; otherwise, the first

// element of the list is returned.

Type back() const;

//Function to return the last element of the list.

//Precondition: The list must exist and must not be

// empty.

//Postcondition: If the list is empty, the program

// terminates; otherwise, the last

// element of the list is returned.

virtual bool search(const Type& searchItem) const = 0;

//Function to determine whether searchItem is in the list.

//Postcondition: Returns true if searchItem is in the

// list, otherwise the value false is

// returned.

virtual void insertFirst(const Type& newItem) = 0;

//Function to insert newItem at the beginning of the list.

//Postcondition: first points to the new list, newItem is

// inserted at the beginning of the list,

// last points to the last node in the list,

// and count is incremented by 1.

virtual void insertLast(const Type& newItem) = 0;

//Function to insert newItem at the end of the list.

//Postcondition: first points to the new list, newItem

// is inserted at the end of the list,

// last points to the last node in the list,

// and count is incremented by 1.

virtual void deleteNode(const Type& deleteItem) = 0;

//Function to delete deleteItem from the list.

//Postcondition: If found, the node containing

// deleteItem is deleted from the list.

// first points to the first node, last

// points to the last node of the updated

// list, and count is decremented by 1.

linkedListIterator begin();

//Function to return an iterator at the begining of the

//linked list.

//Postcondition: Returns an iterator such that current is

// set to first.

linkedListIterator end();

//Function to return an iterator one element past the

//last element of the linked list.

//Postcondition: Returns an iterator such that current is

// set to nullptr.

linkedListType();

//default constructor

//Initializes the list to an empty state.

//Postcondition: first = nullptr, last = nullptr, count = 0;

linkedListType(const linkedListType& otherList);

//copy constructor

~linkedListType();

//destructor

//Deletes all the nodes from the list.

//Postcondition: The list object is destroyed.

protected:

int count; //variable to store the number of

//elements in the list

nodeType *first; //pointer to the first node of the list

nodeType *last; //pointer to the last node of the list

private:

void copyList(const linkedListType& otherList);

//Function to make a copy of otherList.

//Postcondition: A copy of otherList is created and

// assigned to this list.

};

template

bool linkedListType::isEmptyList() const

{

return(first == nullptr);

}

template

linkedListType::linkedListType() //default constructor

{

first = nullptr;

last = nullptr;

count = 0;

}

template

void linkedListType::destroyList()

{

nodeType *temp; //pointer to deallocate the memory

//occupied by the node

while (first != nullptr) //while there are nodes in the list

{

temp = first; //set temp to the current node

first = first->link; //advance first to the next node

delete temp; //deallocate the memory occupied by temp

}

last = nullptr; //initialize last to nullptr; first has already

//been set to nullptr by the while loop

count = 0;

}

template

void linkedListType::initializeList()

{

destroyList(); //if the list has any nodes, delete them

}

template

void linkedListType::print() const

{

nodeType *current; //pointer to traverse the list

current = first; //set current so that it points to

//the first node

while (current != nullptr) //while more data to print

{

cout << current->info << " ";

current = current->link;

}

}//end print

template

int linkedListType::length() const

{

return count;

} //end length

template

Type linkedListType::front() const

{

assert(first != nullptr);

return first->info; //return the info of the first node

}//end front

template

Type linkedListType::back() const

{

assert(last != nullptr);

return last->info; //return the info of the last node

}//end back

template

linkedListIterator linkedListType::begin()

{

linkedListIterator temp(first);

return temp;

}

template

linkedListIterator linkedListType::end()

{

linkedListIterator temp(nullptr);

return temp;

}

template

void linkedListType::copyList

(const linkedListType& otherList)

{

nodeType *newNode; //pointer to create a node

nodeType *current; //pointer to traverse the list

if (first != nullptr) //if the list is nonempty, make it empty

destroyList();

if (otherList.first == nullptr) //otherList is empty

{

first = nullptr;

last = nullptr;

count = 0;

}

else

{

current = otherList.first; //current points to the

//list to be copied

count = otherList.count;

//copy the first node

first = new nodeType; //create the node

assert(first != nullptr);

first->info = current->info; //copy the info

first->link = nullptr; //set the link field of

//the node to nullptr

last = first; //make last point to the

//first node

current = current->link; //make current point to

//the next node

//copy the remaining list

while (current != nullptr)

{

newNode = new nodeType; //create a node

assert(newNode != nullptr);

newNode->info = current->info; //copy the info

newNode->link = nullptr; //set the link of

//newNode to nullptr

last->link = newNode; //attach newNode after last

last = newNode; //make last point to

//the actual last node

current = current->link; //make current point

//to the next node

}//end while

}//end else

}//end copyList

template

linkedListType::~linkedListType() //destructor

{

destroyList();

}//end destructor

template

linkedListType::linkedListType

(const linkedListType& otherList)

{

first = nullptr;

copyList(otherList);

}//end copy constructor

//overload the assignment operator

template

const linkedListType& linkedListType::operator=

(const linkedListType& otherList)

{

if (this != &otherList) //avoid self-copy

{

copyList(otherList);

}//end else

return *this;

}

#endif /* LINKEDLIST_H */

----------------------------------------------------------

unorderedLinkedList.h:

#ifndef UNORDEREDLINKEDLIST_H

#define UNORDEREDLINKEDLIST_H

#include "linkedList.h"

using namespace std;

template

class unorderedLinkedList: public linkedListType

{

public:

bool search(const Type& searchItem) const;

//Function to determine whether searchItem is in the list.

//Postcondition: Returns true if searchItem is in the

// list, otherwise the value false is

// returned.

void insertFirst(const Type& newItem);

//Function to insert newItem at the beginning of the list.

//Postcondition: first points to the new list, newItem is

// inserted at the beginning of the list,

// last points to the last node in the

// list, and count is incremented by 1.

void insertLast(const Type& newItem);

//Function to insert newItem at the end of the list.

//Postcondition: first points to the new list, newItem

// is inserted at the end of the list,

// last points to the last node in the

// list, and count is incremented by 1.

void deleteNode(const Type& deleteItem);

//Function to delete deleteItem from the list.

//Postcondition: If found, the node containing

// deleteItem is deleted from the list.

// first points to the first node, last

// points to the last node of the updated

// list, and count is decremented by 1.

void mergeSort();

private:

void recMergeSort(nodeType* &head);

void divideList(nodeType* first1,

nodeType* &first2);

nodeType* mergeList(nodeType* first1,

nodeType* first2);

};

template

bool unorderedLinkedList::

search(const Type& searchItem) const

{

nodeType *current; //pointer to traverse the list

bool found = false;

current = this->first; //set current to point to the first

//node in the list

while (current != nullptr && !found) //search the list

if (current->info == searchItem) //searchItem is found

found = true;

else

current = current->link; //make current point to

//the next node

return found;

}//end search

template

void unorderedLinkedList::insertFirst(const Type& newItem)

{

nodeType *newNode; //pointer to create the new node

newNode = new nodeType; //create the new node

assert(newNode != nullptr); //if unable to allocate memory,

//terminate the program

newNode->info = newItem; //store the new item in the node

newNode->link = this->first; //insert newNode before first

this->first = newNode; //make first point to the

//actual first node

this->count++; //increment count

if (this->last == nullptr) //if the list was empty, newNode is also

//the last node in the list

this->last = newNode;

}//end insertFirst

template

void unorderedLinkedList::insertLast(const Type& newItem)

{

nodeType *newNode; //pointer to create the new node

newNode = new nodeType; //create the new node

assert(newNode != nullptr); //if unable to allocate memory,

//terminate the program

newNode->info = newItem; //store the new item in the node

newNode->link = nullptr; //set the link field of newNode

//to nullptr

if (this->first == nullptr) //if the list is empty, newNode is

//both the first and last node

{

this->first = newNode;

this->last = newNode;

this->count++; //increment count

}

else //the list is not empty, insert newNode after last

{

this->last->link = newNode; //insert newNode after last

this->last = newNode; //make last point to the actual

//last node in the list

this->count++; //increment count

}

}//end insertLast

template

void unorderedLinkedList::deleteNode(const Type& deleteItem)

{

nodeType *current; //pointer to traverse the list

nodeType *trailCurrent; //pointer just before current

bool found;

if (this->first == nullptr) //Case 1; the list is empty.

cout << "Cannot delete from an empty list."

<< endl;

else

{

if (this->first->info == deleteItem) //Case 2

{

current = this->first;

this->first = this->first->link;

this->count--;

if (this->first == nullptr) //the list has only one node

this->last = nullptr;

delete current;

}

else //search the list for the node with the given info

{

found = false;

trailCurrent = this->first; //set trailCurrent to point

//to the first node

current = this->first->link; //set current to point to

//the second node

while (current != nullptr && !found)

{

if (current->info != deleteItem)

{

trailCurrent = current;

current = current-> link;

}

else

found = true;

}//end while

if (found) //Case 3; if found, delete the node

{

trailCurrent->link = current->link;

this->count--;

if (this->last == current) //node to be deleted

//was the last node

this->last = trailCurrent; //update the value

//of last

delete current; //delete the node from the list

}

else

cout << "The item to be deleted is not in "

<< "the list." << endl;

}//end else

}//end else

}//end deleteNode

template

void unorderedLinkedList::

divideList(nodeType* first1,

nodeType* &first2)

{

nodeType* middle;

nodeType* current;

if (first1 == nullptr) //list is empty

first2 = nullptr;

else if (first1->link == nullptr) //list has only one node

first2->link = nullptr;

else

{

middle = first1;

current = first1->link;

if (current != nullptr) //list has more than two nodes

current = current->link;

while (current != nullptr)

{

middle = middle->link;

current = current->link;

if (current != nullptr)

current = current->link;

} //end while

first2 = middle->link; //first2 points to the first

//node of the second sublist

middle->link = nullptr; //set the link of the last node

//of the first sublist to nullptr

} //end else

} //end divideList

template

nodeType* unorderedLinkedList::

mergeList(nodeType* first1,

nodeType* first2)

{

nodeType *lastSmall; //pointer to the last node of

//the merged list

nodeType *newHead; //pointer to the merged list

if (first1 == nullptr) //the first sublist is empty

return first2;

else if (first2 == nullptr) //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 != nullptr && first2 != nullptr)

{

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 == nullptr) //first sublist exhausted first

lastSmall->link = first2;

else //second sublist exhausted first

lastSmall->link = first1;

return newHead;

}

}//end mergeList

template

void unorderedLinkedList::recMergeSort(

nodeType* &head)

{

nodeType *otherHead;

if (head != nullptr) //if the list is not empty

if (head->link != nullptr) //if the list has more than

//one node

{

divideList(head, otherHead);

recMergeSort(head);

recMergeSort(otherHead);

head = mergeList(head, otherHead);

}

} //end recMergeSort

template

void unorderedLinkedList::mergeSort()

{

recMergeSort(this->first);

if (this->first == nullptr)

this->last = nullptr;

else

{

this->last = this->first;

while (this->last->link != nullptr)

this->last = this->last->link;

}

} //end mergeSort

#endif /* UNORDEREDLINKEDLIST_H */

-----------------------------------------------------------

searchSortAlgorithms.h:

#ifndef SEARCHSORTALGORITHMS_H #define SEARCHSORTALGORITHMS_H

template int seqSearch(const elemType list[], int length, const elemType& item) { int loc; bool found = false;

loc = 0;

while (loc < length && !found) if (list[loc] == item) found = true; else loc++;

if (found) return loc; else return -1; } //end seqSearch

template int binarySearch(const elemType list[], int length, const elemType& item) { 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 void bubbleSort(elemType list[], int length) { for (int iteration = 1; iteration < length; iteration++) { for (int index = 0; index < length - iteration; index++) { if (list[index] > list[index + 1]) { elemType temp = list[index]; list[index] = list[index + 1]; list[index + 1] = temp; } } } } //end bubbleSort

template void selectionSort(elemType list[], int length) { int loc, minIndex;

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

template void swap(elemType list[], int first, int second) { elemType temp;

temp = list[first]; list[first] = list[second]; list[second] = temp; } //end swap

template int minLocation(elemType list[], int first, int last) { int loc, minIndex;

minIndex = first;

for (loc = first + 1; loc <= last; loc++) if (list[loc] < list[minIndex]) minIndex = loc;

return minIndex; } //end minLocation

template void insertionSort(elemType list[], int length) { for (int firstOutOfOrder = 1; firstOutOfOrder < length; firstOutOfOrder++) if (list[firstOutOfOrder] < list[firstOutOfOrder - 1]) { elemType temp = list[firstOutOfOrder]; int location = firstOutOfOrder;

do { list[location] = list[location - 1]; location--; } while(location > 0 && list[location - 1] > temp);

list[location] = temp; } } //end insertionSort

template void quickSort(elemType list[], int length) { recQuickSort(list, 0, length - 1); } //end quickSort

template void recQuickSort(elemType list[], int first, int last) { int pivotLocation;

if (first < last) { pivotLocation = partition(list, first, last); recQuickSort(list, first, pivotLocation - 1); recQuickSort(list, pivotLocation + 1, last); } } //end recQuickSort

template int partition(elemType list[], int first, int last) { elemType pivot;

int index, smallIndex;

swap(list, first, (first + last) / 2);

pivot = list[first]; smallIndex = first;

for (index = first + 1; index <= last; index++) if (list[index] < pivot) { smallIndex++; swap(list, smallIndex, index); }

swap(list, first, smallIndex);

return smallIndex; } //end partition

template void heapSort(elemType list[], int length) { buildHeap(list, length);

for (int lastOutOfOrder = length - 1; lastOutOfOrder >= 0; lastOutOfOrder--) { elemType temp = list[lastOutOfOrder]; list[lastOutOfOrder] = list[0]; list[0] = temp; heapify(list, 0, lastOutOfOrder - 1); }//end for }//end heapSort

template void heapify(elemType list[], int low, int high) { int largeIndex;

elemType temp = list[low]; //copy the root node of //the subtree

largeIndex = 2 * low + 1; //index of the left child

while (largeIndex <= high) { if (largeIndex < high) if (list[largeIndex] < list[largeIndex + 1]) largeIndex = largeIndex + 1; //index of the //largest child

if (temp > list[largeIndex]) //subtree //is already in a heap break; else { list[low] = list[largeIndex]; //move the larger //child to the root low = largeIndex; //go to the subtree to //restore the heap largeIndex = 2 * low + 1; } }//end while

list[low] = temp; //insert temp into the tree, //that is, list }//end heapify

template void buildHeap(elemType list[], int length) { for (int index = length / 2 - 1; index >= 0; index--) heapify(list, index, length - 1); }

#endif /* SEARCHSORTALGORITHMS_H */

------------------------------------------------

main.cpp

#include #include #include #include #include "searchSortAlgorithms.h" #include "unorderedLinkedList.h"

using namespace std;

int main() { int array = [10000]; //assign 10,000 elements in array int list1[array]; for(int i = 0; i < array; i++){ //randomize in list1 list1[i] = rand()% 10 + 1; } //copy list1 into other lists int list2 = list1; int list3 = list1; int list4 = list1; int list5 = list1; //initialize t1 clock_t t1; t1 = clock(); list1 = bubbleSort(list1,array);//bubble sort t1 = clock() - t1; double time_1 = ((double)t1)/CLOCKS_PER_SEC; cout << "Bubble sorting time: " << time_1 << endl; //initialize t2 clock_t t2; t2 = clock(); list2 = selectionSort(list2,array);//selection sort t2 = clock() - t2; double time_2 = ((double)t2)/CLOCKS_PER_SEC; cout << "Selection sorting time: " << time_2 << endl; //initialize t3 clock_t t3; t3 = clock(); list3 = insertionSort(list3,array);//insertion sort t3 = clock() - t3; double time_3 = ((double)t3)/CLOCKS_PER_SEC; cout << "Insertion sorting time: " << time_3 << endl; //initialize t4 clock_t t4; t4 = clock(); list4 = quickSort(list4,array);//quick sort t4 = clock() - t4; double time_4 = ((double)t4)/CLOCKS_PER_SEC; cout << "Quick sorting time: " << time_4 << endl; //initialize t5 clock_t t5; t5 = clock(); list5 = mergeSort(list5,array);//merge sort t5 = clock() - t5; double time_5 = ((double)t5)/CLOCKS_PER_SEC; cout << "Merge sorting time: " << time_5 << endl;

exit(EXIT_SUCCESS); }