//INSTRUCTION //Look for ** to complete all of them //----- Globally setting up
ID: 3859582 • Letter: #
Question
//INSTRUCTION
//Look for ** to complete all of them
//----- Globally setting up the alias and struct ----------------
typedef ** el_t ; // elements will be **
//a list node is defined here as a struct Node
// I could have done class Node and add the data members under public
// but it would use too much space
struct Node
{
el_t Elem; // elem is the element stored
Node *Next; // next is the pointer to the next node
};
//---------------------------------------------------------
class llist
{
private:
Node *Front; // pointer to the front node
Node *Rear; // pointer to the rear node
int Count; // counter for the number of nodes
public:
// Exception handling classes
class Underflow{};
class OutOfRange{}; // thrown when the specified Node is out of range
llist (); // constructor to create a list object
~llist(); // destructor to destroy all nodes
//**
bool isEmpty();
//**
void displayAll();
//**
void addFront(el_t);
//**
void addRear(el_t);
//**
void deleteFront(el_t&);
//**
void deleteRear(el_t&);
//**
void deleteIth(int, el_t&);
//**
void addbeforeIth(int, el_t);
};
// end of llist.h
using namespace std;
#include
#include"llist.h"
Constructor
- initialize Front and Rear to be NULL and Count = 0.
- This does not create any node. The new list is empty.
Destructor
- while the list is not empty, call deleteFront repeatedly to delete all nodes.
- Please place a cout in this function "calling the llist desctructor."
bool llist::isEmpty()
- return true if Front and Rear are both pointing to NULL and Count is 0.
- (all 3 conditions must be checked)
void llist::displayAll()
- Special case: if the list is empty, display [ empty ] ).
- Regular:
displays each element of the list horizontally starting from Front in [ ].
void llist::addRear(el_t NewNum)
2 cases:
- Special case: if this is going to be the very first node, you must
create a new node and make Front and Rear point to it. Place NewNum and
Count is updated.
- Regular: adds a new node at the rear and puts NewNum in the Elem field
of this new node. Count is updated.
Regular case:
Rear->Next = new Node;
Rear = Rear->Next;
Rear->Elem = NewNum;
Rear->Next = NULL;
void llist::addFront(el_t NewNum)
2 cases:
- Special case: if this is going to be the very first node, you must
create a new node and make Front and Rear point to it. Place NewNum and
Count is updated.
- Regular: add a new node to the front of the list and
Count is updated.
Regular case:
Node *x;
x = new Node;
x->Next = Front;
Front = x;
Front->Elem = NewNum;
void llist::deleteFront(el_t& OldNum)
3 cases:
- Error case: if the List is empty, throw Underflow
- Special case: if currently only one Node,
give back the front node element through OldNum (pass by reference) and
make sure both Front and Rear become NULL. Count is updated.
- Regular: give back the front node element through OldNum (pass by reference)
and also removes the front node. Count is updated.
Regular case:
OldNum = Front->Elem;
Node *Second;
Second = Front->Next;
delete Front;
Front = Second;
void llist::deleteRear(el_t& OldNum)
3 cases:
- Error case: if empty, throw Underflow
- Special case: if currently only one node,
give back the rear node element through OldNum (pass by reference) and
make sure both Front and Rear become NULL. Count is updated.
- Regular: give back the rear node element through OldNum (pass by reference)
and also remove the rear node. Count is updated.
Regular case:
OldNum = Rear->Elem;
Node *p;
Make p go to the one right before rear (using while)
delete Rear;
Rear = p;
void llist::deleteIth(int I, el_t& OldNum)
4 cases:
- Error case:
If I is an illegal value (i.e. > Count or < 1) throw OutOfRange.
- Special cases: this should simply call deleteFront when I is 1 or
deleteRear when I is Count
- Regular: delete the Ith node (I starts out at 1). Count is updated.
and make sure you indicate the purposes of these local pointers>
void llist::addbeforeIth(int I, el_t newNum)
4 cases:
- Error case:
If I is an illegal value (i.e. > Count+1 or < 1) throw OutOfRange.
- Special cases: this should simply call addFront when I is 1 or addRear when
I is Count+1
- Regular: add right before the Ith node. Cout if updated.
and make sure you indicate the purposes of these local pointers>
// end of llist.cpp
using namespace std;
#include
#include "llist.h"
void caseOne()
{
cout << "CASE 1:------------------- " << endl;
llist L; // this is my list
int x; // to hold a removed element
//1 check empty and report the result
cout << 1 << endl;
**
//2 display the list
cout << 2 << endl;
**
//3 add 4 integers 1,2,3,4
cout << 3 << endl;
**
//4 display the list
cout << 4 << endl;
**
//5 remove from front twice (and display the elements removed)
cout << 5 << endl;
**
//6 display the list
cout << 6 << endl;
**
//7 check empty and report the result
cout << 7 << endl;
**
//8 remove from the rear twice (display the element removed)
cout << 8 << endl;
**
//9 check empty again and report the result
cout << 9 << endl;
**
}//end of case 1
void caseTwo()
{
cout << "Case 2: -----------------------" << endl;
llist L2; // another list
int x; // to hold the removed element
int c = 1; // displayed step number
// 1.add to front once (element 5)
cout << c << endl; c++;
**
// 2.add to front again (element 4)
cout << c << endl; c++;
**
// 3.delete Front
cout << c << endl; c++;
**
// 4.add to rear 3 times (elements 6,8,9)
cout << c << endl; c++;
**
// 5. display all
cout << c << endl; c++;
**
// 6.add before the 1st (element 4) . 4 5 6 8 9
cout << c << endl; c++;
**
// 7.add before the 4th (element 7) . 4 5 6 7 8 9
cout << c << endl; c++;
**
// 8.add before the 7th (element 10) . 4 5 6 7 8 9 10
cout << c << endl; c++;
**
// 9.add before the 9th (element 12) . error (out of range)
cout << c << endl; c++;
try{** }
catch(**){**}
// 10.add before the 0th (element 0) . error (out of range)
cout << c << endl; c++;
try{** }
catch(**){**}
// 11.displayAll
cout << c << endl; c++;
**
// 12.delete Ith I==1 (indicate the element removed) . 5 6 7 8 9 10
cout << c << endl; c++;
**
// 13.delete Ith I==6 (indicate the element removed) - 5 6 7 8 9
cout << c << endl; c++;
**
// 14.delete Ith I==3 (indicate the element removed) - 5 6 8 9
cout << c << endl; c++;
**
// 15.delete Ith I==5 . error (out of range)
cout << c << endl; c++;
try {** }
catch(**){** }
// 16.delete Ith I==0 . error (out of range)
cout << c << endl; c++;
try {**}
catch(**){**}
// 17.displayAll
cout << c << endl; c++;
**
// 18.delete from rear until it is empty (indicate the elements removed)
cout << c << endl; c++;
**
// 19.displayAll
cout << c << endl; c++;
**
}//end of case 2
void caseThree()
{
cout << "Case 3:-------------------- " << endl;
llist L3;
int x; // to hold the removed element
// 1.add before the 0th . error (out of range)
cout << 1 << endl;;
try {**}
catch (**){**}
//2.delete front . error (underflow)
cout 2 << endl;
try {**}
catch (**){**}
} //end of case 3
void caseFour()
{
cout << "Case 4:------------------------ " << endl;
llist L4;
int x; // to hold the removed element
// 1.delete 2nd . error (out of range)
cout << 1 << endl;
try {** }
catch (**){**}
// 2.delete rear . error (underflow)
cout << 2 << endl;
try {** }
catch (**){**}
} // end of case 4
//PURPOSE of the Program: **
//Algorithm/Design: 4 test cases are divided into 3 functions and **
int main()
{
int selection; // this will indicate what the user wants to do
do
{
cout << endl << "MENU: These are your options: " << endl << endl;
cout << " (1) Case 1 " << endl;
cout << " (2) Case 2 " << endl;
cout << " (3) Case 3 " << endl;
cout << " (4) Case 4 " << endl;
cout << " Enter ( 0 ) to quit " << endl;
cout << "===>";
cin >> selection;
switch(selection)
{
case 1: caseOne(); break;
case 2: caseTwo(); break;
case 3: caseThree(); break;
case 4: caseFour(); break;
}
}
while(selection !=0);
}// end of client.cpp
1. [30 points] implement a singularly linked list class. Complete llisth, Ilist.cpp, and client.cpp. The client/main ram is a menu based Case 1: 1. check empty and report the result 2. display the list L.displayAllO). 3. add 4 integers L-addRear(1) LaddRear(2). LaddRear(3). LaddReart4) 4. display the list L display All0: -1234 5. remove from front twice (and display the elements as they are removed) 6. display the list 34 7. check empty again and report the result 8. remove from the rear twice (display the elements removed) 9. check empty again and report the result Case 2: 1. add to front once (element 5) 2. add to front again (element 4) 3. delete Front this removes 4 4. add to rear 3 times (elements 6.8.9) 5. displayAll (4 elements) 5689 -45689 6. add before the 1st (element 4) 7. add before the 4th (element 7) -456789 8. add before the 7th (element 10) 4567 89 10 error (out of range 9. add before the 9th (element 12) 10. add before the 0th (element 0) error (out of range 11. display All 4567 89 10 12. delete ith l 1 (indicate the element removed) 56789 10 13. delete lth l -6 (indicate the element removed) 56789 14. delete lth l FE3 (indicate the element removed) 5689 error (out of range 5. delete lth l >5 16. delete lith l >0 error (out of range 17. display AII 5689 18. delete from rear until it is empty (indicate the elements removed) 19. displayAllExplanation / Answer
//INSTRUCTION
//Look for ** to complete all of them
//----- Globally setting up the alias and struct ----------------
typedef ** el_t ; // elements will be **
//a list node is defined here as a struct Node
// I could have done class Node and add the data members under public
// but it would use too much space
struct Node
{
el_t Elem; // elem is the element stored
Node *Next; // next is the pointer to the next node
};
//---------------------------------------------------------
class llist
{
private:
Node *Front; // pointer to the front node
Node *Rear; // pointer to the rear node
int Count; // counter for the number of nodes
public:
// Exception handling classes
class Underflow{};
class OutOfRange{}; // thrown when the specified Node is out of range
llist (); // constructor to create a list object
~llist(); // destructor to destroy all nodes
//**
bool isEmpty();
//**
void displayAll();
//**
void addFront(el_t);
//**
void addRear(el_t);
//**
void deleteFront(el_t&);
//**
void deleteRear(el_t&);
//**
void deleteIth(int, el_t&);
//**
void addbeforeIth(int, el_t);
};
//implementation
bool llist::isEmpty()//this method checks whether list is empty or not
{
if(Count==0)//count equals to zero means there are no nodes, hence list is empty
{
return true;//returning true if list is empty
}
else//means list is not empty
{
return false;//returning false if list is not empty
}
}
void llist::displayAll()
{
Node *temp = Front;//varaible to traverse list
if(temp==NULL)//means list is empty
{
//printing message
cout<<"List is empty... ";
}
else
{
while(temp!=NULL)//traversing list
{
cout<<temp->Elem<<" ";//printing elements of the list
temp=temp->Next;
}
cout<<" ";
}
}
void llist::addFront(el_t e)//adding node to the front of the list
{
Node *newNode;//for creating new node
newNode = new Node;
newNode->Elem = e;//assigning value
newNode->Next = Front;//linking to current list
Front = newNode;//changing Front node..because newNode is now our front node
count++;//increamenting count because new node added to list
}
void llist::addRear(el_t e)//adding at the end
{
Node *newNode;//for creating new node
newNode = new Node;
newNode->Elem = e;//assigning value
newNode->Next = Null;
Rear->Next = newNode;//linking to current list
Rear = newNode;//changing rear node..because newNode is now our rear node
Count++;//increamenting count because new node added to list
}
void llist::deleteFront()//deleting front element
{
Node *d = Front;//storing node to delete
Front = Front->Next;//Changing front node
free(d);//deleting previous front node
Count--;//decrementing Count because we have deleted a node
}
void llist::deleteRear()//deleting last node
{
Node *d = Rear;//storing node to delete
Node *temp = Front//to traverse the list
while(temp->Next != Rear)
{
temp=temp->Next;//finding previous node of Rear node
}
temp->Next = NULL;//de linking the Node
Rear =temp;//Changing Rear node
free(d);//deleting previous Rear node
Count--;//decrementing Count because we have deleted a node
}
void llist::addbeforeIth(int i,el_t e)//adding element before ith element
{
if(i>0 && i<=Count)//if i given in range
{
if(i==1)//means adding at the front of the list..
{
addFront(e);//
}
else
{
Node *temp = Front;//varaible to traverse list
i--;
while(i>0)//traversing list
{
temp=temp->Next;
i--;
}
Node *newNode;//for creating new node
newNode = new Node;
newNode->Elem = e;//assigning value
newNode->Next = temp->Next;//linking to list
temp->Next = newNode;//linking
Count++;//increamenting count because new node added to list
}
}
else//we i given out of range, of number of elements
{
cout<<"Can't add, such position not exist ";
}
}
void llist::deleteIth(int i,el_t e)
{
if(i>0 && i<=Count)//if i given in range
{
if(i==1)//means adding at the front of the list..
{
deleteFront(e);//
}
else if(i==Count)//means to delete last element
{
deleteRear(e);
}
else
{
Node *temp = Front;//varaible to traverse list
i--;
while(i>0)//traversing list
{
temp=temp->Next;
i--;
}
Node *d = temp->Next;//pointing node to delete
temp->Next = d->Next;//ldelinking node
free(d);//deleting node
Count--;//decrementing Count because we have deleted a node
}
}
else//we i given out of range, of number of elements
{
cout<<"Can't delete, such position not exist ";
}
}
// end of llist.h
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.