DATA STRUCTURE /C++ Replaced the circular linked list in the attached Josephus P
ID: 3834942 • Letter: D
Question
DATA STRUCTURE /C++
Replaced the circular linked list in the attached Josephus Problem solution with a queue.
this is the code to replace:
main source:
//This program tests various operation of a linked list
//34 62 21 90 66 53 88 24 10
#include <ctime>
#include <iostream>
#include <random>
#include "unorderedCircularLinkedList.h"
using namespace std;
void show(unorderedCircularLinkedList<unsigned>& ucl)
{
ucl.print();
cout << endl;
}
void load(unorderedCircularLinkedList<unsigned>& ucl, unsigned howmany = 41)
{
for (unsigned counter = 1; counter <= howmany; counter++)
ucl.insertLast(counter);
}
unorderedCircularLinkedList<unsigned> kill(const unorderedCircularLinkedList<unsigned>& victims, unsigned killinterval = 3)
{
unorderedCircularLinkedList<unsigned> survivors = victims;
unsigned killcount = 1;
circularLinkedListIterator<unsigned> it = survivors.begin();
while (survivors.length() >= killinterval)
{
if (killcount == killinterval)
{
circularLinkedListIterator<unsigned> dit = it;
++it;
killcount = 1;
survivors.deleteNode(*dit);
}
else
{
++it;
++killcount;
}
}
return survivors;
}
int main()
{
unorderedCircularLinkedList<unsigned> victims;
load(victims);
show(victims);
unorderedCircularLinkedList<unsigned> survivors = kill(victims);
show(survivors);
system("pause");
return 0;
}
Base class:
#pragma once
#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 circularLinkedListIterator
{
public:
circularLinkedListIterator();
//Default constructor
//Postcondition: current = NULL;
circularLinkedListIterator(nodeType<Type> *ptr);
//Constructor with a parameter.
//Postcondition: current = ptr;
Type operator*();
//Function to overload the dereferencing operator *.
//Postcondition: Returns the info contained in the node.
circularLinkedListIterator<Type> operator++();
//Overload the preincrement operator.
//Postcondition: The iterator is advanced to the next node.
bool operator==(const circularLinkedListIterator<Type>& right) const;
//Overload the equality operator.
//Postcondition: Returns true if this iterator is equal to
// the iterator specified by right, otherwise it returns
// false.
bool operator!=(const circularLinkedListIterator<Type>& right) const;
//Overload the not equal to operator.
//Postcondition: Returns true if this iterator is not equal to
// the iterator specified by right, otherwise it returns
// false.
private:
nodeType<Type> *current; //pointer to point to the current
//node in the linked list
};
template <class Type>
circularLinkedListIterator<Type>::circularLinkedListIterator()
{
current = NULL;
}
template <class Type>
circularLinkedListIterator<Type>::
circularLinkedListIterator(nodeType<Type> *ptr)
{
current = ptr;
}
template <class Type>
Type circularLinkedListIterator<Type>::operator*()
{
return current->info;
}
template <class Type>
circularLinkedListIterator<Type> circularLinkedListIterator<Type>::operator++()
{
current = current->link;
return *this;
}
template <class Type>
bool circularLinkedListIterator<Type>::operator==
(const circularLinkedListIterator<Type>& right) const
{
return (current == right.current);
}
template <class Type>
bool circularLinkedListIterator<Type>::operator!=
(const circularLinkedListIterator<Type>& right) const
{ return (current != right.current);
}
//***********************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement the basic
// properties of a linked list. This is an abstract class.
// We cannot instantiate an object of this class.
//***********************************************************
template <class Type>
class circularLinkedListType
{
public:
const circularLinkedListType<Type>& operator=
(const circularLinkedListType<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.
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.
circularLinkedListIterator<Type> begin();
//Function to return an iterator at the beginning of the
//linked list.
//Postcondition: Returns an iterator such that current is set
// to first.
circularLinkedListIterator<Type> end();
//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 NULL.
circularLinkedListType();
//default constructor
//Initializes the list to an empty state.
//Postcondition: first = NULL, last = NULL, count = 0;
circularLinkedListType(const circularLinkedListType<Type>& otherList);
//copy constructor
~circularLinkedListType();
//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 circularLinkedListType<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 circularLinkedListType<Type>::isEmptyList() const
{
return first == NULL;
}
template <class Type>
circularLinkedListType<Type>::circularLinkedListType() //default constructor
{
first = NULL;
last = NULL;
count = 0;
}
template <class Type>
void circularLinkedListType<Type>::destroyList()
{
nodeType<Type> *temp; //pointer to deallocate the memory
//occupied by the node
while (first != last) //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
}
delete first;
first = NULL;
last = NULL;
count = 0;
}
template <class Type>
void circularLinkedListType<Type>::initializeList()
{
destroyList(); //if the list has any nodes, delete them
}
template <class Type>
void circularLinkedListType<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 != last) //while more data to print
{
cout << current->info << ' ';
current = current->link;
}
cout << current->info;
}//end print
template <class Type>
int circularLinkedListType<Type>::length() const
{
return count;
} //end length
template <class Type>
Type circularLinkedListType<Type>::front() const
{
assert(first != NULL);
return first->info; //return the info of the first node
}//end front
template <class Type>
Type circularLinkedListType<Type>::back() const
{
assert(last != NULL);
return last->info; //return the info of the last node
}//end back
template <class Type>
circularLinkedListIterator<Type> circularLinkedListType<Type>::begin()
{
circularLinkedListIterator<Type> temp(first);
return temp;
}
template <class Type>
circularLinkedListIterator<Type> circularLinkedListType<Type>::end()
{
circularLinkedListIterator<Type> temp(last);
return temp;
}
template <class Type>
void circularLinkedListType<Type>::copyList
(const circularLinkedListType<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 = first; //set the link field of the node to itself
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 != otherList.first)
{
newNode = new nodeType<Type>; //create a node
newNode->info = current->info; //copy the info
newNode->link = first; //set the link of newNode to first
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>
circularLinkedListType<Type>::~circularLinkedListType() //destructor
{
destroyList();
}//end destructor
template <class Type>
circularLinkedListType<Type>::circularLinkedListType
(const circularLinkedListType<Type>& otherList)
{
first = NULL;
copyList(otherList);
}//end copy constructor
//overload the assignment operator
template <class Type>
const circularLinkedListType<Type>& circularLinkedListType<Type>::operator=
(const circularLinkedListType<Type>& otherList)
{
if (this != &otherList) //avoid self-copy
{
copyList(otherList);
}//end else
return *this;
}
Derived Class:
#pragma once
//***********************************************************
// Author: D.S. Malik
//
// This class specifies the members to implement the basic
// properties of an unordered circularlinked list. This class is
// derived from the class circularLinkedListType.
//***********************************************************
#include "circularLinkedList.h"
using namespace std;
template <class Type>
class unorderedCircularLinkedList: public circularLinkedListType<Type>
{
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, 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, 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.
};
template <class Type>
bool unorderedCircularLinkedList<Type>::search(const Type& searchItem) const
{
nodeType<Type> *current; //pointer to traverse the list
bool found = first != NULL && last->info == searchItem;
current = first; //set current to point to the first node in the list
while (current != last && !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 unorderedCircularLinkedList<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
if (first == NULL)
{
first = newNode;
last = first;
last->link = first;
}
else
{
last->link = newNode; //make last point to new node
newNode->link = first; //make new node point to first
first = newNode; //make first point to new node
}
count++; //increment count
}//end insertFirst
template <class Type>
void unorderedCircularLinkedList<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
if (first == NULL) //if the list is empty, newNode is both the first and last node
{
first = newNode;
last = first;
last->link = first;
}
else //the list is not empty, insert newNode after last
{
newNode->link = last->link;
last->link = newNode; //insert newNode after last
last = newNode;
}
count++;
}//end insertLast
template <class Type>
void unorderedCircularLinkedList<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;
count--;
if (first->link == first) //the list has only one node
{
first = NULL;
last = NULL;
}
else if (first->link == last) //the list has two nodes
{
first = first->link;
first->link = first;
last = first;
}
else
{
first = first->link;
last->link = first;
}
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 != first && !found)
if (current->info != deleteItem)
{
trailCurrent = current;
current = current-> link;
}
else
found = true;
if (found) //Case 3; if found, delete the node
{
trailCurrent->link = current->link;
if (current == last)
last = trailCurrent;
count--;
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
Explanation / Answer
try with the following code :
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *next;
}*last;
/*
* Class Declaration
*/
class circularlinkedlist
{
public:
void create_node(int value);
void add_begin(int value);
void add_after(int value, int position);
void delete_element(int value);
void search_element(int value);
void display_list();
void update();
void sort();
circularlinkedlist()
{
last = NULL;
}
};
/*
* Main :contains menu
*/
int main()
{
int choice, element, position;
circularlinkedlist cl;
while (1)
{
cout<<endl<<"---------------------------"<<endl;
cout<<endl<<"Circular singly linked list"<<endl;
cout<<endl<<"---------------------------"<<endl;
cout<<"1.Create Node"<<endl;
cout<<"2.Add at beginning"<<endl;
cout<<"3.Add after"<<endl;
cout<<"4.Delete"<<endl;
cout<<"5.Search"<<endl;
cout<<"6.Display"<<endl;
cout<<"7.Update"<<endl;
cout<<"8.Sort"<<endl;
cout<<"9.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the element: ";
cin>>element;
cl.create_node(element);
cout<<endl;
break;
case 2:
cout<<"Enter the element: ";
cin>>element;
cl.add_begin(element);
cout<<endl;
break;
case 3:
cout<<"Enter the element: ";
cin>>element;
cout<<"Insert element after position: ";
cin>>position;
cl.add_after(element, position);
cout<<endl;
break;
case 4:
if (last == NULL)
{
cout<<"List is empty, nothing to delete"<<endl;
break;
}
cout<<"Enter the element for deletion: ";
cin>>element;
cl.delete_element(element);
cout<<endl;
break;
case 5:
if (last == NULL)
{
cout<<"List Empty!! Can't search"<<endl;
break;
}
cout<<"Enter the element to be searched: ";
cin>>element;
cl.search_element(element);
cout<<endl;
break;
case 6:
cl.display_list();
break;
case 7:
cl.update();
break;
case 8:
cl.sort();
break;
case 9:
exit(1);
break;
default:
cout<<"Wrong choice"<<endl;
}
}
return 0;
}
/*
* Create Circular Link List
*/
void circularlinkedlist::create_node(int value)
{
struct node *temp;
temp = new(struct node);
temp->info = value;
if (last == NULL)
{
last = temp;
temp->next = last;
}
else
{
temp->next = last->next;
last->next = temp;
last = temp;
}
}
/*
* Insertion of element at beginning
*/
void circularlinkedlist::add_begin(int value)
{
if (last == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp;
temp = new(struct node);
temp->info = value;
temp->next = last->next;
last->next = temp;
}
/*
* Insertion of element at a particular place
*/
void circularlinkedlist::add_after(int value, int pos)
{
if (last == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp, *s;
s = last->next;
for (int i = 0;i < pos-1;i++)
{
s = s->next;
if (s == last->next)
{
cout<<"There are less than ";
cout<<pos<<" in the list"<<endl;
return;
}
}
temp = new(struct node);
temp->next = s->next;
temp->info = value;
s->next = temp;
/*Element inserted at the end*/
if (s == last)
{
last=temp;
}
}
/*
* Deletion of element from the list
*/
void circularlinkedlist::delete_element(int value)
{
struct node *temp, *s;
s = last->next;
/* If List has only one element*/
if (last->next == last && last->info == value)
{
temp = last;
last = NULL;
free(temp);
return;
}
if (s->info == value) /*First Element Deletion*/
{
temp = s;
last->next = s->next;
free(temp);
return;
}
while (s->next != last)
{
/*Deletion of Element in between*/
if (s->next->info == value)
{
temp = s->next;
s->next = temp->next;
free(temp);
cout<<"Element "<<value;
cout<<" deleted from the list"<<endl;
return;
}
s = s->next;
}
/*Deletion of last element*/
if (s->next->info == value)
{
temp = s->next;
s->next = last->next;
free(temp);
last = s;
return;
}
cout<<"Element "<<value<<" not found in the list"<<endl;
}
/*
* Search element in the list
*/
void circularlinkedlist::search_element(int value)
{
struct node *s;
int counter = 0;
s = last->next;
while (s != last)
{
counter++;
if (s->info == value)
{
cout<<"Element "<<value;
cout<<" found at position "<<counter<<endl;
return;
}
s = s->next;
}
if (s->info == value)
{
counter++;
cout<<"Element "<<value;
cout<<" found at position "<<counter<<endl;
return;
}
cout<<"Element "<<value<<" not found in the list"<<endl;
}
/*
* Display Circular Link List
*/
void circularlinkedlist::display_list()
{
struct node *s;
if (last == NULL)
{
cout<<"List is empty, nothing to display"<<endl;
return;
}
s = last->next;
cout<<"Circular Link List: "<<endl;
while (s != last)
{
cout<<s->info<<"->";
s = s->next;
}
cout<<s->info<<endl;
}
/*
* Update Circular Link List
*/
void circularlinkedlist::update()
{
int value, pos, i;
if (last == NULL)
{
cout<<"List is empty, nothing to update"<<endl;
return;
}
cout<<"Enter the node position to be updated: ";
cin>>pos;
cout<<"Enter the new value: ";
cin>>value;
struct node *s;
s = last->next;
for (i = 0;i < pos - 1;i++)
{
if (s == last)
{
cout<<"There are less than "<<pos<<" elements.";
cout<<endl;
return;
}
s = s->next;
}
s->info = value;
cout<<"Node Updated"<<endl;
}
/*
* Sort Circular Link List
*/
void circularlinkedlist::sort()
{
struct node *s, *ptr;
int temp;
if (last == NULL)
{
cout<<"List is empty, nothing to sort"<<endl;
return;
}
s = last->next;
while (s != last)
{
ptr = s->next;
while (ptr != last->next)
{
if (ptr != last->next)
{
if (s->info > ptr->info)
{
temp = s->info;
s->info = ptr->info;
ptr->info = temp;
}
}
else
{
break;
}
ptr = ptr->next;
}
s = s->next;
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.