C++ Do not change anything in the supplied Ch16_Ex5_MainProgram.cpp except to ad
ID: 3732433 • Letter: C
Question
C++
Do not change anything in the supplied Ch16_Ex5_MainProgram.cpp except to add documentation and your name.
Please use the file names listed below since your file will have the following components:
Ch16_Ex5_MainProgram.cpp - given file
//22 34 56 4 19 2 89 90 0 14 32 88 125 56 11 43 55 -999
#include
#include "unorderedLinkedList.h"
using namespace std;
int main()
{
unorderedLinkedList list, subList;
int num;
cout << "Enter numbers ending with -999" << endl;
cin >> num;
while (num != -999)
{
list.insertLast(num);
cin >> num;
}
cout << endl;
cout << "List: ";
list.print();
cout << endl;
cout << "Length of the list: " << list.length() << endl;
list.divideMid(subList);
cout << "Lists after splitting list" << endl;
cout << "list: ";
list.print();
cout << endl;
cout << "Length of the list: " << list.length() << endl;
cout << "sublist: ";
subList.print();
cout << endl;
cout << "Length of subList: " << subList.length() << endl;
system("pause");
return 0;
}
linkedList.h
unorderedLinkedList.h
Dividing a linked list into two sublists of almost equal sizes:Add the operation divideMid to the class linkedListType as follows:
void divideMid(linkedListType &sublist);
//This operation divides the given list into two sublists
//of (almost) equal sizes.
//Postcondition: first points to the first node and last
// points to the last node of the first
// sublist.
// sublist.first points to the first node
// and sublist.last points to the last node
// of the second sublist.
Consider the following statements:
unorderedLinkedList <int> myList;
unorderedLinkedList <int> subList;
Suppose myList points to the list with elements 34 65 27 89 12 (in this order). The statement:
myList.divideMid(subList);
divides myList into two sublists: myList points to the list with the elements 34 65 27, and subList points to the sublist with the elements 89 12.
Write the definition of the function template to implement the operation divideMid. Also, write a program to test your function.
Explanation / Answer
Please find my answer.
#include <iostream>
using namespace std;
template <class Type>
struct ndTyp
{
Type lstinfo;
ndTyp<Type> *lstlink;
};
// Template for linkedListIterator
template <class Type> class linkedListIterator
{
public:
// Method declaration
linkedListIterator();
linkedListIterator(ndTyp<Type> *p);
Type operator*();
linkedListIterator<Type> operator++();
bool operator==(const linkedListIterator<Type>& right) const;
bool operator!=(const linkedListIterator<Type>& right) const;
private:
ndTyp<Type> *ndcurrent;
};
// Template for linkedListType
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& searchItem) const = 0;
virtual void insertFirst(const Type& newItem) = 0;
virtual void insertLast(const Type& newItem) = 0;
void divideMid(linkedListType<Type> &sublist);
linkedListIterator<Type> begin();
linkedListIterator<Type> end();
linkedListType();
linkedListType(const linkedListType<Type>& otherList);
~linkedListType();
protected:
int count;
ndTyp<Type> *ndfirst;
ndTyp<Type> *ndlast;
private:
void copyList(const linkedListType<Type>& otherList);
};
template <class Type> class unorderedLinkedList: public linkedListType<Type>
{
public:
bool search(const Type& searchItem) const;
void insertFirst(const Type& newItem);
void insertLast(const Type& newItem);
void deleteNode(const Type& deleteItem);
};
// Default constructor
template <class Type> linkedListIterator<Type>::linkedListIterator()
{
ndcurrent = NULL;
}
// Constructor with arguments
template <class Type> linkedListIterator<Type>::linkedListIterator(ndTyp<Type> *p)
{
ndcurrent = p;
}
// Overload * operator
template <class Type> Type linkedListIterator<Type>::operator*()
{
return ndcurrent->lstinfo;
}
// Overload ++ operator
template <class Type> linkedListIterator<Type> linkedListIterator<Type>::operator++()
{
ndcurrent = ndcurrent->lstlink;
return *this;
}
// Overload == operator
template <class Type> bool linkedListIterator<Type>::operator==(const linkedListIterator<Type>& right) const
{
return (ndcurrent == right.ndcurrent);
}
// Overload != operator
template <class Type> bool linkedListIterator<Type>::operator!=(const linkedListIterator<Type>& right) const
{
return (ndcurrent != right.ndcurrent);
}
// Method to check whether the linked list is empty
template <class Type> bool linkedListType<Type>::isEmptyList() const
{
return (ndfirst == NULL);
}
// Default constructor
template <class Type> linkedListType<Type>::linkedListType()
{
ndfirst = NULL;
ndlast = NULL;
count = 0;
}
// Method to deallocate the memory occupied by nodes
template <class Type> void linkedListType<Type>::destroyList()
{
ndTyp<Type> *tempNode;
while (ndfirst != NULL)
{
tempNode = ndfirst;
ndfirst = ndfirst->lstlink;
delete tempNode;
}
ndlast = NULL;
count = 0;
}
// Method to reinitialize list to empty state, delete nodes
template <class Type> void linkedListType<Type>::initializeList()
{
destroyList();
}
// Method to print the list contents
template <class Type> void linkedListType<Type>::print() const
{
ndTyp<Type> *ndcurrent;
ndcurrent = ndfirst;
while (ndcurrent != NULL)
{
cout << ndcurrent->lstinfo << " ";
ndcurrent = ndcurrent->lstlink;
}
}
// Method to get the length of the list
template <class Type> int linkedListType<Type>::length() const
{
return count;
}
// Method to return the ndfirst node information
template <class Type> Type linkedListType<Type>::front() const
{
assert(ndfirst != NULL);
return ndfirst->lstinfo;
}
// Method to return the last node information
template <class Type> Type linkedListType<Type>::back() const
{
assert(ndlast != NULL);
return ndlast->lstinfo;
}
// Method to define iterators begin to use in loops
template <class Type> linkedListIterator<Type> linkedListType<Type>::begin()
{
linkedListIterator<Type> tempNode(ndfirst);
return tempNode;
}
// Method to define iterators end to use in loops
template <class Type> linkedListIterator<Type> linkedListType<Type>::end() //end iterator
{
linkedListIterator<Type> tempNode(NULL);
return tempNode;
}
// Method to make deep copy of list
template <class Type> void linkedListType<Type>::copyList(const linkedListType<Type>& otherList)
{
ndTyp<Type> *lstnewNode;
ndTyp<Type> *ndcurrent;
if (ndfirst != NULL)
destroyList();
if (otherList.ndfirst == NULL)
{
ndfirst = NULL;
ndlast = NULL;
count = 0;
}
else
{
ndcurrent = otherList.ndfirst;
count = otherList.count;
ndfirst = new ndTyp<Type>;
ndfirst->lstinfo = ndcurrent->lstinfo;
ndfirst->lstlink = NULL;
ndlast = ndfirst;
ndcurrent = ndcurrent->lstlink;
while (ndcurrent != NULL)
{
lstnewNode = new ndTyp<Type>;
lstnewNode->lstinfo = ndcurrent->lstinfo;
lstnewNode->lstlink = NULL;
ndlast->lstlink = lstnewNode;
ndlast = lstnewNode;
ndcurrent = ndcurrent->lstlink;
}
}
}
// Destructor to free the allocated memory
template <class Type> linkedListType<Type>::~linkedListType()
{
destroyList();
}
// Copy constructor
template<class Type> linkedListType<Type>::linkedListType(const linkedListType<Type>& otherList)
{
ndfirst = NULL;
copyList(otherList);
}
// Method for = operator overloading
template <class Type> const linkedListType<Type>& linkedListType<Type>::operator=(const linkedListType<Type>& otherList)
{
if (this != &otherList)
{
copyList(otherList);
}
return *this;
}
// Method to search a item
template <class Type> bool unorderedLinkedList<Type>::search(const Type& searchItem) const
{
ndTyp<Type> *ndcurrent;
bool found = false;
ndcurrent = ndfirst;
while (ndcurrent != NULL && !found)
if (ndcurrent->lstinfo == searchItem)
found = true;
else
ndcurrent = ndcurrent->lstlink;
return found;
}
// Method to insert the item in first location of list
template <class Type> void unorderedLinkedList<Type>::insertFirst(const Type& newItem)
{
ndTyp<Type> *lstnewNode;
lstnewNode = new ndTyp<Type>;
lstnewNode->lstinfo = newItem;
lstnewNode->lstlink = ndfirst;
ndfirst = lstnewNode;
count++;
if (ndlast == NULL)
ndlast = lstnewNode;
}
// Method to divide the list
template <class Type> void linkedListType<Type>::divideMid(linkedListType<Type> &sublist)
{
int lstmyItems, lstsubItems;
if ((count%2)!=0) lstmyItems = (count/2 + 1);
else lstmyItems = (count/2);
lstsubItems = (count - lstmyItems);
ndTyp<Type> *ndcurrent;
ndcurrent = ndfirst;
sublist.ndlast = ndlast;
for (int i=0; i<lstmyItems; i++)
{
ndlast = ndcurrent;
ndcurrent = ndcurrent -> lstlink;
}
ndlast->lstlink=NULL;
sublist.ndfirst = ndcurrent;
}
// Method to insert the item in first location of list
template <class Type> void unorderedLinkedList<Type>::insertLast(const Type& newItem)
{
ndTyp<Type> *lstnewNode;
lstnewNode = new ndTyp<Type>;
lstnewNode->lstinfo = newItem;
lstnewNode->lstlink = NULL;
if (ndfirst == NULL)
{
ndfirst = lstnewNode;
ndlast = lstnewNode;
count++;
}
else
{
ndlast->lstlink = lstnewNode;
ndlast = lstnewNode;
count++;
}
}
// Main method
int main()
{
// Code to creat a object for the class
unorderedLinkedList<int> list;
unorderedLinkedList<int> subList;
int num;
cout << "Enter numbers ending with -999" << endl;
cin >> num;
while (num != -999)
{
list.insertLast(num);
cin >> num;
}
cout << endl;
cout << "List: ";
list.print();
cout << endl;
cout << "Length of the list: " << list.length() << endl;
list.divideMid(subList);
// List after divide
cout << "Lists after splitting list" << endl;
cout << "list: ";
list.print();
cout << endl;
// Sub list
cout << "sublist: ";
subList.print();
cout << endl;
system("pause");
return 0;
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.