add the operation divideMid to the class linkedListType as follows: void divedMi
ID: 3534101 • Letter: A
Question
add the operation divideMid to the class linkedListType as follows:
void divedMid(linkedLisType<Type> &sublist);
//This operation divides the given list into two sublists
// of (almost) equal sizes.
//Postcondition: first 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;
write the definition of the funtion template to implement the operation divideMid. Also write a program to test your function
*****************************************************************************************************************
#include <iostream>
#include <cassert>
using namespace std;
//Definition of the node
template <class Type>
struct nodeType
{
Type info;
nodeType<Type> *link;
};
//***********************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement an iterator
// to a linked list.
//***********************************************************
template <class Type>
class linkedListType
{
public:
const linkedListType<Type>& operator=
(const linkedListType<Type>&);
//Overload the assignment operator.
void initializeList();
//Initialize the list to an empty state.
//Postcondition: first = NULL, last = NULL, 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 = NULL, last = NULL, 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.
bool search(const Type& searchItem);
//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.
linkedListType();
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
linkedListType(const linkedListType<Type>& 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 list elements
//
nodeType<Type> *first; //pointer to the first node of the list
nodeType<Type> *last; //pointer to the last node of the list
private:
void copyList(const linkedListType<Type>& otherList);
//Function to make a copy of otherList.
//Postcondition: A copy of otherList is created and assigned
// to this list.
};
template <class Type>
bool linkedListType<Type>::isEmptyList() const
{
return (first == NULL);
}
template <class Type>
linkedListType<Type>::linkedListType() //default constructor
{
first = NULL;
last = NULL;
count = 0;
}
template <class Type>
void linkedListType<Type>::destroyList()
{
nodeType<Type> *temp; //pointer to deallocate the memory
//occupied by the node
while (first != NULL) //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 = NULL; //initialize last to NULL; first has already
//been set to NULL by the while loop
count = 0;
}
template <class Type>
void linkedListType<Type>::initializeList()
{
destroyList(); //if the list has any nodes, delete them
}
template <class Type>
void linkedListType<Type>::print() const
{
nodeType<Type> *current; //pointer to traverse the list
current = first; //set current so that it points to
//the first node
while (current != NULL) //while more data to print
{
cout << current->info << " ";
current = current->link;
}
}//end print
template <class Type>
int linkedListType<Type>::length() const
{
return count;
} //end length
template <class Type>
Type linkedListType<Type>::front() const
{
assert(first != NULL);
return first->info; //return the info of the first node
}//end front
template <class Type>
Type linkedListType<Type>::back() const
{
assert(last != NULL);
return last->info; //return the info of the last node
}//end back
template <class Type>
bool linkedListType<Type>::
search(const Type& searchItem)
{
nodeType<Type> *current; //pointer to traverse the list
bool found = false;
current = first; //set current to point to the first
//node in the list
while (current != NULL && !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 <class Type>
void linkedListType<Type>::insertFirst(const Type& newItem)
{
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = first; //insert newNode before first
first = newNode; //make first point to the
//actual first node
count++; //increment count
if (last == NULL) //if the list was empty, newNode is also
//the last node in the list
last = newNode;
}//end insertFirst
template <class Type>
void linkedListType<Type>::insertLast(const Type& newItem)
{
nodeType<Type> *newNode; //pointer to create the new node
newNode = new nodeType<Type>; //create the new node
newNode->info = newItem; //store the new item in the node
newNode->link = NULL; //set the link field of newNode
//to NULL
if (first == NULL) //if the list is empty, newNode is
//both the first and last node
{
first = newNode;
last = newNode;
count++; //increment count
}
else //the list is not empty, insert newNode after last
{
last->link = newNode; //insert newNode after last
last = newNode; //make last point to the actual
//last node in the list
count++; //increment count
}
}//end insertLast
template <class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem)
{
nodeType<Type> *current; //pointer to traverse the list
nodeType<Type> *trailCurrent; //pointer just before current
bool found;
if (first == NULL) //Case 1; the list is empty.
cout << "Cannot delete from an empty list."
<< endl;
else
{
if (first->info == deleteItem) //Case 2
{
current = first;
first = first->link;
count--;
if (first == NULL) //the list has only one node
last = NULL;
delete current;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = first; //set trailCurrent to point
//to the first node
current = first->link; //set current to point to
//the second node
while (current != NULL && !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;
count--;
if (last == current) //node to be deleted
//was the last node
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 <class Type>
void linkedListType<Type>::copyList
(const linkedListType<Type>& otherList)
{
nodeType<Type> *newNode; //pointer to create a node
nodeType<Type> *current; //pointer to traverse the list
if (first != NULL) //if the list is nonempty, make it empty
destroyList();
if (otherList.first == NULL) //otherList is empty
{
first = NULL;
last = NULL;
count = 0;
}
else
{
current = otherList.first; //current points to the
//list to be copied
count = otherList.count;
//copy the first node
first = new nodeType<Type>; //create the node
first->info = current->info; //copy the info
first->link = NULL; //set the link field of
//the node to NULL
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 != NULL)
{
newNode = new nodeType<Type>; //create a node
newNode->info = current->info; //copy the info
newNode->link = NULL; //set the link of
//newNode to NULL
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 <class Type>
linkedListType<Type>::~linkedListType() //destructor
{
destroyList();
}//end destructor
template <class Type>
linkedListType<Type>::linkedListType
(const linkedListType<Type>& otherList)
{
first = NULL;
copyList(otherList);
}//end copy constructor
//overload the assignment operator
template <class Type>
const linkedListType<Type>& linkedListType<Type>::operator=
(const linkedListType<Type>& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
//This program tests various operation of a linked list
//Line 3
int main() //Line 4
{ //Line 5
linkedListType<int> list1, list2; //Line 6
int num; //Line 7
cout << "Line 8: Enter integers ending "
<< "with -999" << endl; //Line 8
cin >> num; //Line 9
while (num != -999) //Line 10
{ //Line 11
list1.insertLast(num); //Line 12
cin >> num; //Line 13
} //Line 14
cout << endl; //Line 15
cout << "Line 16: list1: "; //Line 16
list1.print(); //Line 17
cout << endl; //Line 18
cout << "Line 19: Length of list1: "
<< list1.length() << endl; //Line 19
list2 = list1; //test the assignment operator Line 20
cout << "Line 21: list2: "; //Line 21
list2.print(); //Line 22
cout << endl; //Line 23
cout << "Line 24: Length of list2: "
<< list2.length() << endl; //Line 24
cout << "Line 25: Enter the number to be "
<< "deleted: "; //Line 25
cin >> num; //Line 26
cout << endl; //Line 27
list2.deleteNode(num); //Line 28
cout << "Line 29: After deleting " << num
<< " list2: " << endl; //Line 29
list2.print(); //Line 30
cout << endl; //Line 31
cout << "Line 32: Length of list2: "
<< list2.length() << endl; //Line 32
return 0; //Line 38
} //Line 39
Explanation / Answer
Code:
#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();
void deleteNode(const Type& deleteItem);
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);
};
// 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;
}
template <class Type>
void linkedListType<Type>::deleteNode(const Type& deleteItem)
{
ndTyp<Type> *current; //pointer to traverse the list
ndTyp<Type> *trailCurrent; //pointer just before current
bool found;
if (ndfirst == NULL) //Case 1; the list is empty.
cout << "Cannot delete from an empty list."
<< endl;
else
{
if (ndfirst->lstinfo == deleteItem) //Case 2
{
current = ndfirst;
ndfirst = ndfirst->lstlink;
count--;
if (ndfirst == NULL) //the list has only one node
ndlast = NULL;
delete current;
}
else //search the list for the node with the given info
{
found = false;
trailCurrent = ndfirst; //set trailCurrent to point
//to the ndfirst node
current = ndfirst->lstlink; //set current to point to
//the second node
while (current != NULL && !found)
{
if (current->lstinfo != deleteItem)
{
trailCurrent = current;
current = current-> lstlink;
}
else
found = true;
}//end while
if (found) //Case 3; if found, delete the node
{
trailCurrent->lstlink = current->lstlink;
count--;
if (ndlast == current) //node to be deleted
//was the last node
ndlast = 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
// 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()
{
unorderedLinkedList<int> list1, list2; //Line 6
int num; //Line 7
cout << "Line 8: Enter integers ending "
<< "with -999" << endl; //Line 8
cin >> num; //Line 9
while (num != -999) //Line 10
{ //Line 11
list1.insertLast(num); //Line 12
cin >> num; //Line 13
} //Line 14
cout << endl; //Line 15
cout << "Line 16: list1: "; //Line 16
list1.print(); //Line 17
cout << endl; //Line 18
cout << "Line 19: Length of list1: "<< list1.length() << endl; //Line 19
list2 = list1; //test the assignment operator Line 20
cout << "Line 21: list2: "; //Line 21
list2.print(); //Line 22
cout << endl; //Line 23
cout << "Line 25: Enter the number to be "<< "deleted: "<< endl; //Line 25
cin >> num; //Line 26
cout << endl; //Line 27
list2.deleteNode(num); //Line 28
cout << "Line 29: After deleting " << num << " list2: " << endl; //Line 29
list2.print(); //Line 30
cout << endl; //Line 31
cout << "Line 32: Length of list2: "<< list2.length() << endl; //Line 32
cout << "Line 24: Length of list2: "<< list2.length() << endl; //Line 24
list1.divideMid(list2);
// List after divide
cout << "Lists after splitting list" << endl;
cout << "list: "<< endl;
list1.print();
cout << "Lists2" << endl;
cout << "list: ";
list2.print();
cout<< endl;
system("pause");
return 0; //Line 38
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.