C++ EXERCISE. I did almost one week trying to this without success. Please i rea
ID: 664815 • Letter: C
Question
C++ EXERCISE.
I did almost one week trying to this without success. Please i really need your help !!!!
First, program must contain two classes and one main( all are given ) except the function divideMid() that i have to define and add to the class linkedList.h .
classes name: linkedList.h , unorderedLinkedList.h (unorderedLinkedList is derived from linkedList)
main name : Ch16_mainProgram.cpp (Given)
EXERCISE:
(Splitting a linked list, at a given node, into two sublists)
a. Add the following operation to the class linkedList:
void divideMid( linkedListType <Type> &secondList );
//Divide the list at the node with the info item into two
//sublists.
//Postcondition: first and last point to the first and
// last nodes of the first sublist.
// secondList.first and secondList.last
// point to the first and last nodes of the
// second sublist.
Consider the following statements:
unorderedLinkedList<int> List;
unorderedLinkedList<int> Sublist;
Suppose myList points to the list with the elements 34 65 18 39 27 89 12
(in this order). The statement:
myList.divideMid(sublist);
divides List into two sublists: List points to the list with the
elements 34 65, and Sublist points to the sublist with the elements
18 39 27 89 12.
GIVEN MAIN PROGRAM TO TEST CLASSES
// Test Data: 22 34 56 4 19 2 89 90 0 14 32 88 125 56 11 43 55 -999
#include <iostream>
#include "unorderedLinkedList.h"
using namespace std;
int main()
{
unorderedLinkedList<int> 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;
}
Output :
Classes Are Given:
template <class Type>
class linkedList
{
virtual void insertLast( const Type& newItem) = 0 ; // function to insert Item at the end of the list
int length() ; // return the number of nodes of the list
void print() ; // function to output all data contained in the list
void destroyList() ; // function to delete all nodes of the list
linkedList(); // default constructor
~linkedList(); // destructor
protected:
int count ; // counter to count list elements
linkedList<Type> *first ; // pointer to first node of the list
linkedList<Type> *last ; // pointer to the last node of the list
};
template < class Type >
class unorderedLinkedList :
public linkedList < Type >
{
public:
void insertLast(const Type& newItem) ;
};
node :
template <class Type>
struct nodeType
{
int info;
nodeType <Type> *link;
};
Function definion Are ALSO GIVEN :
template <class Type>
void unorderedLinkedList<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 item in the node
newNode->info = NULL ; // set the field of the newNode to NULL
if (first == NULL) //if the first list is empty, newNode is both the first and last node
{
first = last ;
last = first ;
count++ ; //increment count
}
else // the last is not empty, insert newNode after last
{
last-> = newNode ; //insert newNode after last
last = newNode ; //make last point to the actual
//last node in the list
count++ ;
}
}//end insertLast
template <class Type>
int linkedList<Type>::length()
{
return count;
} // end length
template <class Type>
void linkedList<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>
void linkedList<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 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>
linkedList<Type>::linkedList() // default constructor
{
first = NULL;
last = NULL;
count = 0;
}
template <class Type>
linkedList<Type>::~linkedList() // destructor
{
destroyList();
}//end destructor
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();
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.