CAUTION!!!

வணக்கம்!!!

Just Before now on I have Posted all of the Ten programs in the Data Structures Particles. So there will be nine Blog posts from now on: Numbered. All of them are in CPP. I have Compiled the Programs and Checked them. They are Error Free. But I don't Guarantee it. 


It is my Humble Opinion it will be of Great use to You. If U have any comments or suggestions or Errors.... Please put it up as Comments.


Dont Forget to Share it with your Friends.


Anyway ThankU for visiting my Blog :-)


நன்றி!!!


UPDATE:
Date: 26th November 2011
Time: 21:20::30


I admit that there were Lot of Errors in the Programs, which were posted before in this BLOG. I am deeply SORRY.


But now there is no Problem. I have Compiled all the PROGRAMS and all the Errors have been neatly Patched in the POSTS itself.


If U find any more errors kindly COMMENT upon!!! 


:-)))))))

10 All Pair Shortest Path

#include<iostream>

using namespace std;

int min(int a,int b);

int cost[10][10],a[10][10],i,j,k,c;

int main()

{

  int n,m;

  cout <<"enter no of vertices";

  cin >> n;

  cout <<"enter no of edges";

  cin >> m;

  cout<<"enter the\nEDGE Cost\n";

   for(k=1;k<=m;k++)

  {

  cin>>i>>j>>c;

  a[i][j]=cost[i][j]=c;

  }

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

 for(j=1;j<=n;j++)

{

if(a[i][j]== 0 && i !=j)

a[i][j]=31999;

}

for(k=1;k<=n;k++)

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

for(j=1;j<=n;j++)

a[i][j]=min(a[i][j],a[i][k]+a[k][j]);

cout <<"Resultant adj matrix\n";

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

 {

  for( j=1;j<=n;j++)

  {

  if(a[i][j] !=31999)

  cout << a[i][j] <<" ";

  }

cout <<"\n";

}

return 0;

}

int min(int a,int b)

{

if(a<b)

return a;

else

return b;

} 

9 Merge Sort

#include<iostream>

using namespace std ;


int merge(int[],int,int[],int,int[]) ;

int main()
{
int A[50], B[50], C[50], mn=0, m, n,i ;

cout<<"\nEnter the no. of elements of 1st array: ";
cin>> m ;

cout<<"\nEnter the 1st array: ";
 for(i=0 ; i<m ; i++)
 cin>> A[i] ;

cout<<"\nEnter the no. of elements of 2nd array: ";
cin>> n ;
 
mn=m+n ;

cout<<"\nEnter the 2nd array: ";
 for(i=0 ; i<n ; i++)
 cin>> B[i] ;
 
merge(A,m,B,n,C) ;
   
cout<<"\nThe merged array is: " ;
 for(i=0 ; i<mn ; i++)
 cout<<C[i]<<" " ;

return 0;


}

int merge(int A[],int m,int B[],int n,int C[])
{
int a, b, c;

 for(a=0, b=0, c=0; a<m && b<n; )
 {
 if(A[a]<=B[b])
 C[c++]=A[a++] ;
 else
 C[c++]= B[b++] ;
 }

 if(a<m)
 {
 while(a<m)
  C[c++] = A[a++] ;
 }
 else
 {
 while(b<n)
  C[c++] = B[b++] ;
 }

return 0;

}

7 Binary Transversal

Preorder Inorder Postorder (Using RECURSION)


#include<iostream>
#include<cmath>

using namespace std;

void getdata();
void inorder(int);
void preorder(int);
void postorder(int);

int t[50];
int n,i,l;

int main()
{
getdata();

cout<<"\nINORDER";
inorder(1);

cout<<"\nPREORDER";
preorder(1);

cout<<"\nPOSTORDER";
postorder(1);
cout<<"\n";

return 0;

}

void getdata()
 {
 cout<<"\nEnter the no.of levels of the binary tree:";
 cin>>l;

 n=(pow(2,l))-1;
 cout<<"\nThe maximum no.of the nodes for the given level of the binary tree is"<<" "<<n<<"\n";
 cout<<"\nEnter the nodes of the tree:";
 for(i=1;i<=n;i++)
 cin>>t[i];
 }

 void inorder(int i)
 {
  if(i<=n)
  {
  inorder(i*2);
  if(t[i]!=0)
  cout<<"\t"<<t[i];
  inorder(i*2+1);
  }
 }

 void preorder(int i)
 {
  if(i<=n)
  {
  if(t[i]!=0)
  cout<<"\t"<<t[i];
  preorder(i*2);
  preorder(i*2+1);
  }
 }

 void postorder(int i)
 {
  if(i<=n)
  {
  postorder(i*2);
  postorder(i*2+1);
  if(t[i]!=0)
  cout<<"\t"<<t[i];
  }
 }

8 Quick Sort

#include<iostream>
#include <stdlib.h>

using namespace std;

void exit(int status);
void qusort(int numbers[], int array_size);
void qsort(int numbers[], int left, int right);

int numbers[150];

int main()
{
   int i,n;
   cout<<"How many numbers you want to sort: ";
   cin>>n;
   cout<<"Enter "<<n<<" numbers.\n";
   for (i = 0; i<n; i++)
      cin>>numbers[i];
//perform quick sort on array
   qsort(numbers,0,n-1);

   cout<<"Numbers are sorted\n";
   for (i = 0; i<n; i++)
      cout<<numbers[i]<<"   ";
   return(0);
}

// Function to sort
void qsort(int numbers[], int left, int right)
{
   int pivot, l_hold, r_hold;
   l_hold = left;
   r_hold = right;
   pivot = numbers[left];
   while (left < right)
   {
      while ((numbers[right] >= pivot) && (left < right))
      right--;
      if (left != right)
      {
     numbers[left] = numbers[right];
     left++;
      }
      while ((numbers[left] <= pivot) && (left < right))
     left++;
      if (left != right)
      {
      numbers[right] = numbers[left];
      right--;
      }
   }
   numbers[left] = pivot;
   pivot = left;
   left = l_hold;
   right = r_hold;
   if (left < pivot)
      qsort(numbers, left, pivot-1);
   if (right > pivot)
      qsort(numbers, pivot+1, right);
}

6 Dijkstra's Algorithm

#include<iostream>
using namespace std;

int cost[20][20];

int main()
{
int i,j,c[10][10],dist[10],s[10];
int temp,tempcost,n,src,minm;

cout<<"\n\nEnter the no. of vertices:";
cin>>n;

cout<<"\nGive the cost:";

for(i=1;i<=n;i++)
 {
 for(j=1;j<=n;j++)
 {
  if(i==j)
  {
  c[i][j]=0;
  }
  else
  {
  cout<<"Enter the cost:"<<i<<"to"<<j<<"::";
  cin>>c[i][j];
  }
 }
}

cout<<"\nEnter the vertex number to find the shortest path for all paths:";
cin>>src;

cout<<"\nThe adjacency matrix given is:";
for(i=1;i<=n;i++)
{
 for(j=1;j<=n;j++)
 {
 cout<<c[i][j]<<"\t";
 }
 cout<<"\n";
}

for(i=1;i<=n;i++)
{
s[i]=0;
dist[i]=c[src][i];
}

s[src]=1;dist[src]=0;

for(i=1;i<=n;i++)
{
 for(j=1;j<=n;j++)
 {
  if(s[j]==0)
  {
  minm=dist[j];
  temp=j;
  break;
  }
 }
}

for(j=1;j<=n;j++)
{
 if(s[j]==0 && minm>dist[j])
 {
 minm=dist[j];
 temp=j;
 }
}

s[temp]=1;

for(j=1;j<=n;j++)
{
 if(s[j]==0)
 {
 tempcost=dist[temp]+c[temp][j];
  if(dist[j]>tempcost)
  {
  dist[j]=tempcost;
  }
 }
}

cout<<"\n\nThe vertices are:"<<"\n";
for(i=1;i<=n;i++)
cout<<"\t"<<i;

cout<<"\nThe distances are:"<<"\n";
for(i=1;i<=n;i++)
cout<<dist[i]<<"\t";

return 0;
}

5 Binary - Insertion Search & Deletion

#include<iostream>
#include<stdlib.h>

using namespace std;

struct node
{
int d;
struct node *left;
struct node *right;
};

struct node *root;


void init();
void empty();
int insert(int);
void search(int);
void remove(int);
 
void init()
{
root=(struct node *)malloc(sizeof(struct node));
root=NULL;
}

int insert(int x)
{
struct node *p,*previous,*current;
p=(struct node *)malloc(sizeof(struct node));
 if (p==NULL)
 {
 cout<<"\nOut of Memory";
 return 0;
 }
p->d=x;
p->left=NULL;
p->right=NULL;
 if(root==NULL)
 {
 root=p;
 return 1;
 }
previous=NULL;
current=root;

 while (current!=NULL)
 {
 previous=current;
  if (p->d<current->d)
  current=current->left;
  else
  current=current->right;
 }

 if(p->d<previous->d)
 previous->left=p;
 else
 previous->right=p;

return 1;
}

void remove(int x)
{
struct node *ptr=root, *parent = NULL, *t1, *t2, *temp;
 while(ptr!=NULL && ptr->d!=x)
 {
 parent=ptr;
 if(x<ptr->d)
  ptr=ptr->left;
 else
  ptr=ptr->right;
 }

 if(ptr==NULL)
 {
 cout<<"\nDelete Element Not found";
 return;
 }
 
 if(ptr->left==NULL)
  t1=ptr->right;
 else if(ptr->right==NULL)
  t1=ptr->left;
 else
 {
 t2=ptr;
 t1=ptr->right;
 temp=t1->left;
 
  while(temp!=NULL)
  {
  t2=t1;
  t1=temp;
  temp=t1->left;
  }
 
  if(t2!=ptr)
  {
  t2->left=t1->right;
  t1->right=ptr->right;
  }

  t1->left=ptr->left;
 }

 if(parent==NULL)
  root=t1;
 else
 {
  if(parent->left==ptr)
  parent->left=t1;
  else
  parent->right=t1;
 }

free(ptr);
}


void search(int sno)
{
struct node*t;
t=(struct node *)malloc(sizeof(struct node));
t=root;
 while(t!=NULL && t->d !=sno)
 {
  if(t->d>sno)
  { t=t->left; }
  else
  { t=t->right; }
 }

 if(t)
 cout<<"\nThe Search Element is Present";
 else
 cout<<"\nElement not Present";
}

int main()
{
int c,no,x;
init();

 do
 {
 cout<<"\n1.Insert";
 cout<<"\n2.Deletion";
 cout<<"\n3.Search";
 cout<<"\n4.Exit";
 cout<<"\nEnter Your Choice:\t";
 cin>>c;
 
  switch(c)
  {
  case 1:cout<<"\nEnter the Element to Insert:\t";
         cin>>no;
         x=insert(no);
          if(x==1)
          cout<<"\nsucessful Insertion";
          else
          cout<<"\nError in insertion";
         break;
  case 2:cout<<"\nEnter the Element to Delete:";
         cin>>x;
         remove(no);
         break;
  case 3:cout<<"\nEnter the Element to Search: \t";
         cin>>no;
         search(no);
         break;
  case 4: exit(0); break;
  default: cout<<"\nEnter Any No. Between 1-7"; break;
  }
 }while(c!=4);
return 0;
}