About  Contact


Data structure


Introduction: A data structure is actually a collection of data each data item belongs to same or different data type. Array in C++ is an example of structured data, discussed in the previous topic. Array is compiler defined data structure. There may be user defined data structure e.g structure, class will be discussed in subsequent topics. While we study data structure mainly we study how data is stored in the memory and what operation can done be done on them. In this topic we study array as data structure and the structure data type The following operation is generally done on array-
  • Traversal - reading the array element
  • Insertion in the array
    • Insertion at the begining
    • Insertion athe end
    • Insertion at any position of the Array
  • Deletion
    • From the begining
    • From the end
    • From any position
  • Searching
    • Linear search
    • Binary search
  • Sorting
    • Bubble sort
    • Selection sort
    • Insertion sort
  • Merging
  • Concatenation
Let us write a program for the first two operations (Insertion and deletion). We will write functions for each of the operations, in the "main()" we will have a menu so that the user can do any operation randomly.

Program-69

#include <iostream.h>
#include <conio.h>>
#include <windows.h>

using namespace std;

const int maxSize=10;


int insertBeg(int a[], int &fill, int e){
   int i, s=0;
   if(fill==maxSize-1){
      cout<<"Array is full";
      s=-1;
   }
   else{
      i=fill;
      while(i>=0){
         a[i+1]=a[i];
         i--;
      }
      a[0]=e;
      fill++;
   }
   return(s);	
}

int insertEnd(int a[], int &fill, int e){
  int i, s=0;
   if(fill==maxSize-1){
      cout<<"Array is full";
      s=-1;
   }
   else{
     fill++;
     a[fill]=e;
   }
   return(s);	
}

int insertPos(int a[], int &fill, int e, int pos){
   int i, s=0;
   if(fill==maxSize-1){
      cout<<"Array is full";
      s=-1;
   }
   else if(pos<0 && pos>fill){
      cout<<"Invalid position";
   }
   else{
      i=fill;
      while(i>=pos){
         a[i+1]=a[i];
         i--;
      }
    a[pos]=e;
    fill++;
   }
   return(s);
}

int delBeg(int a[], int &fill){
 int i, s=0;
 if(fill==-1){
   cout<<"The array is empty";
   s=-1;
 }
 else{
   for(i=0; i<=fill-1; i++){
     a[i]=a[i+1];
   }
   fill--;
 }
 return(s);
}
int delEnd(int a[], int &fill){
   int i, s=0;
   if(fill==-1){
     cout<<"The array is empty";
     s=-1;
   }
   else{
     fill--;
   }
   return(s);
}
int delPos(int a[], int &fill, int pos){
  int i, s=0;
  if(fill==-1){
     cout<<"The array is empty";
     s=-1;
  }
  else if(pos<0 && pos>fill){
     cout<<"Invalid Position";
  }
  else{
     for(i=pos; i<=fill-1; i++){
       a[i]=a[i+1];
     }
     fill--;
  }
  return(s);
}

int main(){
  int a[10], choice, e, fill=-1, i, p,k;
	
  do{
    system("cls");
    cout<<"1. Insert at the begining\n";
    cout<<"2. Insert at the end\n";
    cout<<"3. Insert at any position\n";
    cout<"4. Delete from the begining\n";
    cout<<"5. Delete from the end\n";
    cout<<"6. Delete from any position\n";
    cout<<"7. Display\n";
    cout<<"8. Exit\n\n\n\n\n";
    cout<<"Enter your option:";
    cin>>choice;
    switch(choice){
       case 1: cout<<"Enter the element to be inserted:";
            cin>>e;
            k=insertBeg(a,fill,e);
            if(k==0)
                cout<<"Element is inserted successfully";
            break;
       case 2: cout<<"Enter the element to be inserted:";
            cin>>e;
            k=insertEnd(a,fill,e);
            if(k==0)
                cout<<"Element is inserted successfully";
            break;
       case 3: cout<<"Enter the element to be inserted:";
            cin>>e;
            cout<<"Enter the position:";
            cin>>p;
            k=insertPos(a,fill,e,p);
            if(k==0)
                cout<<"Element is inserted successfully";
            break;
       case 4: 
            k=delBeg(a,fill);
            if(k==0)
                cout<<"Element is deleted successfully";
            break;
       case 5: 
            k=delEnd(a,fill);
            if(k==0)
                cout<<"Element is deleted successfully";
            break;
       case 6: cout<<"Enter the position:";
            cin>>p;
            k=delPos(a,fill,p);
            if(k==0)
                cout<<"Element is deleted successfully";
            break;
       case 7: 
            if(fill>=0){
                cout<<"The elements in the array are as below\n";
                for(i=0; i<=fill; i++){
                   cout<<"  ";
                }
            }
            else{
                cout<<"The array is empty";
            }
            break;
			
   }
   if(choice>8){
       cout<<"Wrong option System will Exit";
   }
   else if(choice==8){
      cout<<"System will Exit";
   }
   cout<<"\n\n\nHit any key to continue";
   getch();
  }while(choice<=7); 
}
This program is written in Dev C++, header file windows.h is included because system("cls") used in the program for clearing the screen. In this program the variable "fill" is used to mark the index number of last occupied cell, and its value is -1 when the array is empty. Remember that we can not enter any element in the array keeping any previous cell empty (i.e if the array has elemenst till index number 5, then we can not enter elemet at 7 keeping cell 6 empty). See that in every function this variable is passed as referenced. The return value of every function checks if the operation is successfull or not (0 success, -1 fail). Insertion and deletion at any point assumes that the position is between 0 to the last occupied cell. The maximum number of element that can be inserted is 10, defined as const . All the operations can be done randomly.