This chapter defined and identified various operations on a circular linked list.
-
Write the definitions of the class circularLinkedList and its member functions. (You may assume that the elements of the circular linked list are in ascending order.)
-
Write a program to test various operations of the class defined in the step above. Your program should accept a sorted list as input and output the following:
- The length of the list.
- The list after deleting a number.
- A message indicating if a number is contained in the list.
An example of the program is shown below:
Enter number ending with -999 1 2 3 4 5 6 7 8 9 10 -999 List 1: 1 2 3 4 5 6 7 8 9 10 Length List 1: 10 Enter the number to be searched: 4 4 found in the list Enter the number to be deleted: 4 After deleting the node, List 1: 1 2 3 5 6 7 8 9 10 Length List 1: 9
Your program should use the value -999 to denote the end of the input list.
Given program:
circularLinkedList.h
#ifndef H_circularLinkedList #define H_circularLinkedList #include
#include using namespace std; template struct node Type Type info; nodeType *link; template class circularLinkedlist public: const circularLinkedList& operator= (const circularLinkedList&); //overloads the assignment operator. void initializelist(); //Initializes the list to an empty state. //Postcondition: first = nullptr, last = nullptr, // count = 0 bool isEmptyList(); //Function to determine whether the list is empty. //Postcondition: Returns true if the list is empty; // otherwise, returns false. void print() const; int length(); //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(); //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, then the program terminates; otherwise, the first element of the list is returned. Type back(); //Function to return the last element of the Type back(); //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, then 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 found in the list; otherwise, it returns false. // void insertNode(const Type& newitem); 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, and last points to the last circularLinkedList(); //Default constructor //Initializes the list to an empty state. //Postcondition: first = nullptr, last = nullptr, count = 0 // circularLinkedList(const circularLinkedList& otherList // Copy constructor circularLinkedList(); //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 circularLinkedlist& otherlist); //Function to make a copy of otherList. //Postcondition: A copy of otherList is created and assigned to this list. }; template bool circularLinkedList:: isEmptyList() return (first == nullptr); template circularLinkedList::circularLinkedList() // default constructor first = nullptr; count = 0; template void circularLinkedList::destroylist() nodeType *temp; nodeType *current = nullptr; if (first != nullptr) if (first != nullptr) current = first->link; first->link = nullptr; while (current != nullptr) temp = current; current = current->link; delete temp; first = nullptr; //initialize last to nullptr; first has already //been set to nullptr by the while loop count = 0; template void circularLinkedList:: initializelist() destroyList(); //if the list has any nodes, delete them template int circularLinkedList:: length() return count; // end length } template Type circularLinkedList:: front() assert(first != nullptr); return first->link->info; //return the info of the first node }//end front template Type circularLinkedList::back() assert(first != nullptr); return first->info; //return the info of the first node }//end back template bool circularLinkedList:: Search(const Type& searchItem) nodeType *current; //pointer to traverse the list bool found = false; if (first != nullptr) current = first->link; while (current != first && ! found) if (current->info >= searchItem) found = true; else current = current->link; found = (current->info == searchItem); return found; }//end search template void circularLinkedList::insertNode(const Type& newitem) nodeType *current; //pointer to traverse the list nodeType *trailCurrent; //pointer just before current nodeType *trailCurrent; //pointer just before current nodeType *newNode; //pointer to create a node bool found; newNode = new nodeType; //create the node newNode->info = newitem; newNode->link = nullptr; //store newitem in the node //set the link field of the node //to nullptr if (first == nullptr) // Case 1 first = newNode; first->link = newNode; count++; else if (newitem >= first->info) newNode->link = first->link; first->link = newNode; first = newNode; else trailCurrent = first; current = first->link; found = false; while (current != first && !found) if (current->info >= newitem) found = true; else { trailCurrent = current; current = current->link; trailCurrent->link = newNode; newNode->link = current; count++; }//end else }//end insertNode template void circularLinkedList::deleteNode(const Type& deleteItem) void circularLinkedList:: deleteNode(const Type& deleteItem nodeType *current; //pointer to traverse the list nodeType *trailCurrent; //pointer just before current bool found; if (first == nullptr) // Case 1; list is empty. cerr link; while (current != first && !found) if (current->info >= deleteItem) found = true; else trailCurrent = current; current = current->link; if (current == first) if (first->info == deleteItem) if (first == first->link) first = nullptr; else trailCurrent->link = current->link; first = trailCurrent; delete current; count--; else cout info == deleteItem) { trailCurrent->link = current->link; count--; delete current; else cout void circularLinkedList: :print() const nodeType *current; //pointer to traverse the list current = first->link; while (current != first) //while more data to print cout info link; cout info circularLinkedList:: circularLinkedList() // destructor destroyList(); }//end destructor template void circularLinkedList::copylist (const circularLinkedList& otherList) nodeType *newNode; nodeType *current; node Type *tempFirst; if (first != nullptr) destroyList(); if (otherlist. first == nullptr) first = nullptr; count = 0; else current = otherList.first->link; //current points to the count = otherList.count; //copy the first node tempFirst = new nodeType; //create the node tempFirst->info = current->info; //copy the info last = tempFirst; //make last point to the //first node current = current->link; //make current point to the /ext node //copy the remaining list while (current != otherList.first) //create a node newNode = new nodeType; newNode->info = current->info; last->link = newNode; last = newNode; current = current->link; }//end while if (tempFirst == last) else { //create a node newNode = new nodeType; newNode->info = current->info; last->link = newNode; first = newNode; first->link = tempFirst; }//end else }//end copylist //copy constructor template circularLinkedList::circularLinkedList (const circularLinkedList& otherList) first = nullptr; copyList(otherList); }//end copy constructor //overload the assignment operator first = huriper copylist(otherList); }//end copy constructor //overload the assignment operator 7 template const circularLinkedList& circularLinkedList:: operator= (const circularLinkedList& otherList) if (this != &otherList) //avoid self-copy copylist(otherList); }//end else return *this; 5 #endif #ifndef H_circularLinkedList #define H_circularLinkedList #include #include using namespace std; template struct node Type Type info; nodeType *link; template class circularLinkedlist public: const circularLinkedList& operator= (const circularLinkedList&); //overloads the assignment operator. void initializelist(); //Initializes the list to an empty state. //Postcondition: first = nullptr, last = nullptr, // count = 0 bool isEmptyList(); //Function to determine whether the list is empty. //Postcondition: Returns true if the list is empty; // otherwise, returns false. void print() const; int length(); //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(); //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, then the program terminates; otherwise, the first element of the list is returned. Type back(); //Function to return the last element of the Type back(); //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, then 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 found in the list; otherwise, it returns false. // void insertNode(const Type& newitem); 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, and last points to the last circularLinkedList(); //Default constructor //Initializes the list to an empty state. //Postcondition: first = nullptr, last = nullptr, count = 0 // circularLinkedList(const circularLinkedList& otherList // Copy constructor circularLinkedList(); //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 circularLinkedlist& otherlist); //Function to make a copy of otherList. //Postcondition: A copy of otherList is created and assigned to this list. }; template bool circularLinkedList:: isEmptyList() return (first == nullptr); template circularLinkedList::circularLinkedList() // default constructor first = nullptr; count = 0; template void circularLinkedList::destroylist() nodeType *temp; nodeType *current = nullptr; if (first != nullptr) if (first != nullptr) current = first->link; first->link = nullptr; while (current != nullptr) temp = current; current = current->link; delete temp; first = nullptr; //initialize last to nullptr; first has already //been set to nullptr by the while loop count = 0; template void circularLinkedList:: initializelist() destroyList(); //if the list has any nodes, delete them template int circularLinkedList:: length() return count; // end length } template Type circularLinkedList:: front() assert(first != nullptr); return first->link->info; //return the info of the first node }//end front template Type circularLinkedList::back() assert(first != nullptr); return first->info; //return the info of the first node }//end back template bool circularLinkedList:: Search(const Type& searchItem) nodeType *current; //pointer to traverse the list bool found = false; if (first != nullptr) current = first->link; while (current != first && ! found) if (current->info >= searchItem) found = true; else current = current->link; found = (current->info == searchItem); return found; }//end search template void circularLinkedList::insertNode(const Type& newitem) nodeType *current; //pointer to traverse the list nodeType *trailCurrent; //pointer just before current nodeType *trailCurrent; //pointer just before current nodeType *newNode; //pointer to create a node bool found; newNode = new nodeType; //create the node newNode->info = newitem; newNode->link = nullptr; //store newitem in the node //set the link field of the node //to nullptr if (first == nullptr) // Case 1 first = newNode; first->link = newNode; count++; else if (newitem >= first->info) newNode->link = first->link; first->link = newNode; first = newNode; else trailCurrent = first; current = first->link; found = false; while (current != first && !found) if (current->info >= newitem) found = true; else { trailCurrent = current; current = current->link; trailCurrent->link = newNode; newNode->link = current; count++; }//end else }//end insertNode template void circularLinkedList::deleteNode(const Type& deleteItem) void circularLinkedList:: deleteNode(const Type& deleteItem nodeType *current; //pointer to traverse the list nodeType *trailCurrent; //pointer just before current bool found; if (first == nullptr) // Case 1; list is empty. cerr link; while (current != first && !found) if (current->info >= deleteItem) found = true; else trailCurrent = current; current = current->link; if (current == first) if (first->info == deleteItem) if (first == first->link) first = nullptr; else trailCurrent->link = current->link; first = trailCurrent; delete current; count--; else cout info == deleteItem) { trailCurrent->link = current->link; count--; delete current; else cout void circularLinkedList: :print() const nodeType *current; //pointer to traverse the list current = first->link; while (current != first) //while more data to print cout info link; cout info circularLinkedList:: circularLinkedList() // destructor destroyList(); }//end destructor template void circularLinkedList::copylist (const circularLinkedList& otherList) nodeType *newNode; nodeType *current; node Type *tempFirst; if (first != nullptr) destroyList(); if (otherlist. first == nullptr) first = nullptr; count = 0; else current = otherList.first->link; //current points to the count = otherList.count; //copy the first node tempFirst = new nodeType; //create the node tempFirst->info = current->info; //copy the info last = tempFirst; //make last point to the //first node current = current->link; //make current point to the /ext node //copy the remaining list while (current != otherList.first) //create a node newNode = new nodeType; newNode->info = current->info; last->link = newNode; last = newNode; current = current->link; }//end while if (tempFirst == last) else { //create a node newNode = new nodeType; newNode->info = current->info; last->link = newNode; first = newNode; first->link = tempFirst; }//end else }//end copylist //copy constructor template circularLinkedList::circularLinkedList (const circularLinkedList& otherList) first = nullptr; copyList(otherList); }//end copy constructor //overload the assignment operator first = huriper copylist(otherList); }//end copy constructor //overload the assignment operator 7 template const circularLinkedList& circularLinkedList:: operator= (const circularLinkedList& otherList) if (this != &otherList) //avoid self-copy copylist(otherList); }//end else return *this; 5 #endif
