Create a sequence data structure using dynamic arrays. Sequence is similar to th

Question

Create a sequence data structure using dynamic arrays. Sequence is similar to the bag but the order is important in it (1, 2, 3 is different than 2, 1, 3). Implement the erase_first and erase_last which respectively remove the first and the last occurrence of a value. Implement the erase_occurrence which removes the occurrence of a value (e.x. Erase the second occurrence of the value 4). Implement the erase_from function which accepts INDEX of an element and erases the element from that index (index starts from zero). Implement the insert, count and size functions that respectively insert to the end of the sequence, count number of occurrence of a value and returns number of elements in the sequence. Implement the insert_first function that insert an element as the first index. Implement the insert_at function which insert some element at a specific index. If you have 3 values then you may have 4 places to insert at, for example if you have 1, 2, 3 and you want to insert 4 in the sequence, then you may insert at index 0, 1, 2, 3 and the result will be 4, 1, 2, 3 or 1, 4, 2, 3 or 1, 2, 4, 3 or 1, 2, 3, 4 respectively. Implement the + operator that connects two sequences and create the third one, Overload the + operator such that it connects a sequence to a number and return the result. * Implement the += as a member function that it will add a sequence to this sequence and the overloaded version which adds a number to this sequence. * Implement the = operator this time try to return a sequence& instead of a sequence (This is the most accurate version of the = operator). Implement the == operator which checks the equality of two sequences. Overload ostream (e.x. cout s) operator so you may print a sequence or insert a sequence by console. In the main try to create a loop with 1,000,000,000 iterations. Try to create an instance of a sequence class in the loop and add one element to that. Run your program and check the memory usage. Add a destructor for to your sequence class and try the test again. What happens to the memory? Don't forget namespace and macro-guard.

Explanation / Answer

Hi there,

Sequence here is basically a Linked List. It is easily implemented using Nodes concept But here we are supposed to use Array.

Here is the code:

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;

class sequence
{
public:
       int elements,size;
       int *a;
       void inc_size();
void insert_first();
void insert();
void erase_first();
void erase_last();
void count();
void count_occurance();
sequence()
{
size = 10;   //taking defaultsize of an array to be 10, you can change as per your requirement
           elements = 0;
           int n[size];
           a = n;
}
};
/*
* Increase Size
*/

void sequence::inc_size()
{
   int i, newSize;
   newSize = size + 10;
   int n[newSize];
   for( i = 0; i < size; i++ )
   {
       n[i] = a[i];
   }  
   a = n;
   size = newSize;
}

/*
* Inserting element in beginning
*/
void sequence::insert_first()
{
   int value,i;
int n[size];
   cout<<"Enter the value to be inserted: ";
cin>>value;
if( size == elements )
   {
       inc_size();
   }
  
   n[0] = value;
   for( i = 0; i < element; i++ )
   {
       n[i+1] = a[i];
   }  
   element++;
   a = n;
   cout<<"Element Inserted at last"<<endl;
}

/*
* Inserting Node at last
*/
void sequence::insert()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
if( size == elements )
   {
       inc_size();
   }
   a[elements++] = value;
cout<<"Element Inserted at beginning"<<endl;
}

/*
* Count number of elements
*/
void sequence::count()
{
cout<<"Total number of elements are: "<<elements<<endl;
}

/*
* Delete first element
*/
void sequence::erase_first()
{
int value, i;
   int n[size];
if (element == 0)
{
cout<<"List is empty"<<endl;
return;
}
  
   value = a[element-1];
   for( i = 1; i < element; i++ )
   {
       n[i-1] = a[i];
   }
   element--;
   a = n;
   cout<<"Element Deleted is: "<<value<<endl;
}
/*
* Delete last element
*/
void sequence::erase_last()
{
int value;
if (element == 0)
{
cout<<"List is empty"<<endl;
return;
}
  
   value = a[element-1];
   cout<<"Element Deleted is: "<<value<<endl;
}

/*
* Count the number of occurance of a value
*/
void sequence::count_occurance()
{
int value, count = 0;
if (element == 0)
{
cout<<"List is empty"<<endl;
return;
}
   cout<<"Enter the data to be searched: ";
cin>>value;
   for( i = 0; i < element; i++ )
   {
       if( i == value)
           count++;
   }
  
   cout<<"Occurance of "<<value<<"is: "<<count<<endl;
}

void main()
{
   int choice;
   sequence s1 = new sequence();
do
{
cout<<endl<<"Main Menu"<<endl;
       cout<<"1.Insert Node at beginning"<<endl;
cout<<"2.Insert node at last"<<endl;
       cout<<"3.Delete the first element"<<endl;
       cout<<"4.Delete the last element"<<endl;
       cout<<"5.Count the number of elements"<<endl;
       cout<<"6.Count the number of occurance of a value"<<endl;
cout<<"0.Exit "<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Inserting Node at Beginning: "<<endl;
sl.insert_first();
cout<<endl;
break;
case 2:
cout<<"Inserting Node at Last: "<<endl;
sl.insert();
cout<<endl;
break;
case 3:
cout<<"Deleting Node at Beginning: "<<endl;
sl.erase_first();
break;
       case 4:
cout<<"Deleting Node at Last: "<<endl;
sl.erase_last();
break;
       case 5:
cout<<"Counting the number of elements in the list"<<endl;
sl.count();
cout<<endl;
break;
case 6:
cout<<"Count the number of occurance of a value: "<<endl;
sl.count_occurance();
cout<<endl;
break;
case 0:
cout<<"Exiting..."<<endl;
exit(1);
break;
default:
cout<<"Wrong choice"<<endl;
}
      
}while (choice != 0);
   getch();
   return 0;
  
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.