//INSTRUCTION //Look for ** to complete all of them //----- Globally setting up
ID: 3861351 • 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
Explanation / 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.