Question: Hello, I would like some help in fixing errors in my code and implementing this assignment correctly, please. All classes are implemented and the only
Hello, I would like some help in fixing errors in my code and implementing this assignment correctly, please. All classes are implemented and the only thing I need help with is main.cpp. TIA!!
---------------------------------------------------------------------
---------------------------------------------------------------------
linkedList.h
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include
#include
using namespace std;
//Definition of the node
template
struct nodeType
{
Type info;
nodeType
};
template
class linkedListIterator
{
public:
linkedListIterator();
//Default constructor
//Postcondition: current = nullptr;
linkedListIterator(nodeType
//Constructor with a parameter.
//Postcondition: current = ptr;
Type operator*();
//Function to overload the dereferencing operator *.
//Postcondition: Returns the info contained in the node.
linkedListIterator
//Overload the pre-increment operator.
//Postcondition: The iterator is advanced to the next
// node.
bool operator==(const linkedListIterator
//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
//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
/ode in the linked list
};
template
linkedListIterator
{
current = nullptr;
}
template
linkedListIterator
linkedListIterator(nodeType
{
current = ptr;
}
template
Type linkedListIterator
{
return current->info;
}
template
linkedListIterator
{
current = current->link;
return *this;
}
template
bool linkedListIterator
(const linkedListIterator
{
return (current == right.current);
}
template
bool linkedListIterator
(const linkedListIterator
{ return (current != right.current);
}
//***************** class linkedListType ****************
template
class linkedListType
{
public:
const linkedListType
(const linkedListType
//Overload the assignment operator.
void initializeList();
//Initialize the list to an empty state.
//Postcondition: first = nullptr, last = nullptr, 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
//Function to return an iterator at the begining of the
//linked list.
//Postcondition: Returns an iterator such that current is
// set to first.
linkedListIterator
//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
//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
nodeType
private:
void copyList(const linkedListType
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and
// assigned to this list.
};
template
bool linkedListType
{
return(first == nullptr);
}
template
linkedListType
{
first = nullptr;
last = nullptr;
count = 0;
}
template
void linkedListType
{
nodeType
//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
{
destroyList(); //if the list has any nodes, delete them
}
template
void linkedListType
{
nodeType
current = first; //set current so that it points to
//the first node
while (current != nullptr) //while more data to print
{
cout info
current = current->link;
}
}//end print
template
int linkedListType
{
return count;
} //end length
template
Type linkedListType
{
assert(first != nullptr);
return first->info; //return the info of the first node
}//end front
template
Type linkedListType
{
assert(last != nullptr);
return last->info; //return the info of the last node
}//end back
template
linkedListIterator
{
linkedListIterator
return temp;
}
template
linkedListIterator
{
linkedListIterator
return temp;
}
template
void linkedListType
(const linkedListType
{
nodeType
nodeType
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
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
assert(newNode != nullptr);
newNode->info = current->info; //copy the info
newNode->link = nullptr; //set the link of
/ewNode 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
{
destroyList();
}//end destructor
template
linkedListType
(const linkedListType
{
first = nullptr;
copyList(otherList);
}//end copy constructor
//overload the assignment operator
template
const linkedListType
(const linkedListType
{
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
void divideList(nodeType
nodeType
nodeType
nodeType
};
template
bool unorderedLinkedList
search(const Type& searchItem) const
{
nodeType
bool found = false;
current = this->first; //set current to point to the first
/ode 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
{
nodeType
newNode = new nodeType
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
{
nodeType
newNode = new nodeType
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
{
nodeType
nodeType
bool found;
if (this->first == nullptr) //Case 1; the list is empty.
cout
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) /ode 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
}//end else
}//end else
}//end deleteNode
template
void unorderedLinkedList
divideList(nodeType
nodeType
{
nodeType
nodeType
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
/ode 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
mergeList(nodeType
nodeType
{
nodeType
//the merged list
nodeType
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 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 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
nodeType
{
nodeType
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
{
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
loc = 0;
while (loc
if (found) return loc; else return -1; } //end seqSearch
template
bool found = false;
while (first
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
template
for (loc = 0; loc
template
temp = list[first]; list[first] = list[second]; list[second] = temp; } //end swap
template
minIndex = first;
for (loc = first + 1; loc
return minIndex; } //end minLocation
template do { list[location] = list[location - 1]; location--; } while(location > 0 && list[location - 1] > temp); list[location] = temp; } } //end insertionSort template template if (first template int index, smallIndex; swap(list, first, (first + last) / 2); pivot = list[first]; smallIndex = first; for (index = first + 1; index swap(list, first, smallIndex); return smallIndex; } //end partition template 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 elemType temp = list[low]; //copy the root node of //the subtree largeIndex = 2 * low + 1; //index of the left child while (largeIndex 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 #endif /* SEARCHSORTALGORITHMS_H */ ---------------------------------------------------------------------------- ---------------------------------------------------------------------------- main.cpp #include using namespace std; int main() { int array = [10000]; //assign 10,000 elements in array int list1[array]; for(int i = 0; i exit(EXIT_SUCCESS); }
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
Study Help