Data Structure Programs

Home  >>  Computer Science  >>  Data Structure Programs

Data Structure Programs

1
Dec,2015

0

ds-logo

 

HEADER LIST

#include<iostream.h>

#include<conio.h>

using namespace std;

struct Node

{

      int info;

      Node *next;

 };

struct Head

{

       int count;

       double average;

       Node *link;

       };

Head *start = new Head;

Node *nd, *ptr;

int sum=0, c=0, choice, marks;

 

void display()

{

    cout<<“Average marks ” << start->average <<endl;

    cout<<“Number of nodes ” <<start -> count <<endl;  

    ptr=start->link;

    while (ptr!=NULL)

    {

        cout<<ptr->info;

        ptr = ptr ->next; 

       if(ptr!=NULL) cout<<“–>”;   

     }

     cout<<“\n”;

}

 

void deletion()

{

     if(start->link== NULL) cout<<“No item to delete”;

     else{start ->link = start -> link -> next; }

}

void insert()

{

     nd = new Node();

     cout<<“Enter the Marks” <<endl;

     cin>> marks;

     c++;

     sum = sum + marks;

     start->count = c;

     start -> average = sum/c;

       

        nd -> info = marks;

        nd ->next = start -> link;

        start -> link = nd;

}

int main()

{

start->link = NULL;

start->average = 0.0;

start-> count = 0;

do{

       cout<<“\nEnter Your Choice”<< endl;

       cout<<“1. Insert\n”;

       cout<<“2. Delete\n”;

       cout<<“3. Display\n”;

       cout<<“4. Exit\n”;

       cin>>choice;

       switch(choice){

       case 1: cout<<“\nAdding the Node in the begining\n”;

       insert();

       break;

       case 2: cout<<“\nDeleting the Node from the begining\n”;

       deletion();

       break;

       case 3: cout<<“\nDisplaying the Header List\n”;

       display();

       break;

        default: exit(0);

        }    

   }

while(choice<4);

getch();

return 0;   

    }

BINARY SEARCH

#include<conio.h>

#include<iostream.h>

 

using namespace std;

int n,low,high,mid,srch,i;

int main()

{

cout<<“Enter the size of array: “;

cin>>n;

int a[n];

cout<<“Enter “<<n<<” elements in the array:\n”;

for(i=0;i<n;i++)

{

cin>>a[i];

}

cout<<“Elements in the array are: “<<endl;

for(i=0;i<n;i++)

{

cout<<a[i]<<” “;

}

cout<<“\nEnter the element you want to search: “;

cin>>srch;

low=0;

high=n-1;

while(low<=high)

{

mid=(low+high)/2;

if(srch<a[mid])

high=mid-1;

else if(srch>a[mid])

low=mid+1;

else

{

cout<<“Element is present at ” <<mid+1<< ” location”;

break;

}

}

 

if(low>high)

cout<<“Element is not found”;

getch();

return 0;

}

SPIRAL TRAVERSAL

#include<iostream>

#include<conio.h>
using namespace std;
void spiralTraversal(int **a, int n);
main()
{
int n;

cout<<“Enter n for nxn matrix:”;
cin>>n;
int a[n][n];
cout<<“Enter the matrix:”;
for(int i=0;i<n;i++)
{
for(int j=0;j<n;j++)
cin>>a[i][j];
}
cout<<“The matrix before the spiral:”;
for(int i=0;i<n;i++)
{ cout<<“\n”;
for(int j=0;j<n;j++)
cout<<a[i][j]<<“\t”;

}

//SPIRAL TRAVERSAL
cout<<“Matrix after traversal:”;

int rs=0, cs=0; // RowStart and Column Start
int re=n-1, ce=n-1; // RowEnd & columnEnd

while(rs<=re && cs<=ce)
{
int i=rs, j=cs;

for(j=cs; j<=ce; j++)
cout<<” “<<a[i][j];

for(i=rs+1, j–; i<=re; i++)
cout<<” “<<a[i][j];

for(j=ce-1, i–; j>=cs; j–)
cout<<” “<<a[i][j];

for(i=re-1, j++; i>=rs+1; i–)
cout<<” “<<a[i][j];

rs++; cs++; re–; ce–;
}
}

BINARY SEARCH TREE (BST)

#include<iostream>
#include<conio.h>
using namespace std;
struct node
{
node *left;
node *right;
int info;
}*root=NULL,*ptr,*np,*save;
int x, height=0, c=0;
void in()
{
np=new node;
cout<<“enter element: \t”;
cin>>x;
np->info=x;
np->left=NULL;
np->right=NULL;
if(root==NULL)
root=np;
else
{
ptr=root;
while(ptr!=NULL)
{
save=ptr;
if(x<ptr->info)
ptr=ptr->left;
else
ptr=ptr->right;
}
if(save->info<=x)
save->right=np;
else
save->left=np;
}
}
void preorder(node *root)
{
if(root==NULL)
return;
cout<<root->info;
preorder(root->left);
preorder(root->right);
}
void postorder(node *root)
{
if(root==NULL)
return;
preorder(root->left);
preorder(root->right);
cout<<root->info;
}
void inorder(node *root)
{
if(root==NULL)
return;
if(++c > height) height=c;
inorder(root->left);
c–;
cout<<root->info <<“\t”;
if(++c > height) height=c;
inorder(root->right);
c–;
}
int main()
{
int ch;
do{
cout<<“\n================================”<<endl;
cout<<“1. create”<<endl;
cout<<“2. preorder”<<endl;
cout<<“3. postorder”<<endl;
cout<<“4. Height and Inorder Traversal”<<endl;
cout<<“5. Exit”<<endl;
cout<<“================================”<<endl;
cout<<“Enter your choice: \t”;
cin>>ch;
switch(ch)
{
case 1:
{
in();
break;
}
case 2:
{
preorder(root);
break;
}
case 3:
{
postorder(root);
break;
}
case 4:
{
inorder(root);
cout<<“\nheight is: ” <<height;
break;
}
case 5:
{
exit(0);break; }
};
}while(ch!=5);
getch();
return 0;
}

Quick Sort

#include <iostream>

#include <conio.h>
using namespace std;
int j, n, pivot;
int *arr;
void show()
{
cout<< “\n Array : “;
for (int i=0;i<n;i++)
cout<<arr[i]<<” “;
cout<<endl;
}
void exch(int a[],int i,int j){
int s=a[i];
a[i]=a[j];
a[j]=s;
}
int partition(int a[],int l,int h){
int i=l;
int j=h;
pivot=l;
cout<<“\npivot element is: ” << a[pivot] <<endl;
while(i<j){
while( a[i]<=a[pivot]) i++;
while(a[j]>a[pivot])j–;
if(i<j) exch(a, i, j);
}
exch(a, j, pivot);
show();
return j;
}
void quick(int a[],int l,int h){
if (h<=l) return ;
j=partition(a,l,h);
quick(a,l,j-1);
quick(a,j+1,h);
}
int main(){
cout<<“Enter the size of array : “;
cin>>n;
arr = new int[n];
cout<<“\n *** Enter Array Elements *** \n”;
for (int i=0; i<n; i++) cin>> arr[i];
cout<<“Initial Array is” <<endl;
show();
quick(arr,0,n-1);
cout<<“\n *** Sorted Array *** \n”;
show();
getch();
return 0;
}

HEAP SORT

#include <iostream>

#include <conio.h>
using namespace std;
void max_heapify(int *a, int i, int n)
{
int j, temp;
temp = a[i];
j = 2*i;
while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void heapsort(int *a, int n)
{
int i, temp;
for (i = n; i >= 2; i–)
{
temp = a[i];
a[i] = a[1];
a[1] = temp;
max_heapify(a, 1, i – 1);
}
}
void build_maxheap(int *a, int n)
{
int i;
for(i = n/2; i >= 1; i–)
{
max_heapify(a, i, n);
}
}
int main()
{
int n, i, x;
cout<<“enter no of elements of array\n”;
cin>>n;
int a[20];
for (i = 1; i <= n; i++)
{
cout<<“enter element”<<(i)<<endl;
cin>>a[i];
}
build_maxheap(a,n);
heapsort(a, n);
cout<<“sorted output\n”;
for (i = 1; i <= n; i++)
{
cout<<a[i]<<endl;
}
getch();
}

SELECTION SORT

#include <conio.h>

#include<iostream>
using namespace std;
int n;
int arr[20];
void display()
{
for(int i=0; i<n; i++)
cout<<arr[i] <<“\t”;
}
void selection_sort(int x[],int length)
{
int min,i,j, temp;
for(j=0;j<length;j++)
{
min=j;
for(i =j+1; i<length; i++)
{
if (x[i]< x[min]){
min = i; }
}
if(min!=j){
temp = x[j];
x[j]=x[min];
x[min] = temp;
}
display();
cout<<“\n”;
}
}
int main()
{
cout<<“Enter the number of elements: \t”;
cin>>n;
cout<<“\n Enter the elements of the array\n”;
for(int i=0; i<n; i++)
cin>> arr[i];
selection_sort(arr, n);
getch();
return 0;
}

INSERTION SORT

 

#include <conio.h>
#include<iostream>
using namespace std;
int n;
int arr[20];
void display()
{
for(int i=0; i<n; i++)
cout<<arr[i] <<“\t”;
}
void insertion_sort (int arr[], int length)
{
int j, temp;
for (int i = 1; i < length; i++){
j = i-1;
int x=arr[i];
while (j >= 0 && arr[j] > x){
arr[j+1] = arr[j];
j–;
}
arr[j+1]=x;
display();
cout<<“\n”;
}
}
int main()
{
cout<<“Enter the number of elements: \t”;
cin>>n;
cout<<“\n Enter the elements of the array\n”;
for(int i=0; i<n; i++)
cin>> arr[i];
insertion_sort(arr, n);
getch();
}

MERGE SORT

#include<iostream.h>
#include<conio.h>
void merge_split(int a[],int first,int last);
void merge(int a[],int f1,int l1,int f2,int l2);
int a[25],b[25];
int main()
{
int i,n;
cout<<“Merge Sort”;
cout<<“\n\n*********”;
cout<<“\n\nEnter the limit : “;
cin>>n;
cout<<“\nEnter the elements\n”;
for(i=0;i<n;i++)
cin>>a[i];
merge_split(a,0,n-1);
cout<<“\n\nSorted list : “;
for(i=0;i<n;i++)
cout<< a[i] << ” “;
getch();
return 0;
}
void merge_split(int a[],int first,int last)
{
int mid;
if(first<last)
{
mid=(first+last)/2;
merge_split(a,first,mid);
merge_split(a,mid+1,last);
merge(a,first,mid,mid+1,last);
}
}
void merge(int a[],int f1,int l1,int f2,int l2)
{
int i,j,k=0;
i=f1;
j=f2;
while(i<=l1 && j<=l2)
{
if(a[i]<a[j])
b[k]=a[i++];
else
b[k]=a[j++];
k++;
}
while(i<=l1)
b[k++]=a[i++];
while(j<=l2)
b[k++]=a[j++];
i=f1;
j=0;
while(i<=l2 && j<k)
a[i++]=b[j++];
}

TOWER OF HANOI

#include<iostream>
#include<conio.h>
using namespace std;
void towers(int,char,char,char);
int main()
{
int n; //Declare the variables to be used
//Get the input for number of disks
cout<<“enter the no of disks : “;
cin>>n;
towers(n,’A’,’C’,’B’); //Call the function
getch();
return 0;

}

 

Leave a Reply

Your email address will not be published. Required fields are marked *