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;
}

4 Queue - Linked List

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

using namespace std;

struct node
{
int data;
struct node *link;
};
struct node *cur,*first,*last;

void insert();
void delte();
void display();

void insert()
{
 if(first==NULL)
 {
 cout<<"\nENTER THE FIRST ELEMENT: ";
 cur=(struct node *)malloc(sizeof(struct node));
 cin>>cur->data;
 cur->link=NULL;
 first=cur;
 last=cur;
 }
 else
 {
 cout<<"\nENTER THE NEXT ELEMENT: ";
 cur=(struct node *)malloc(sizeof(struct node));
 cin>>cur->data;
 cur->link=NULL;
 last->link=cur;
 last=cur;
 }
}

void delte()
{
 if(first==NULL)
 {
 cout<<"\t\nQUEUE IS EMPTY\n";
 }
 else
 {
 cur=first;
 first=first->link;
 cur->link=NULL;
 cout<<"\n DELETED ELEMENT IS:";
 cout<<cur->data;
 free(cur);
 }
}

void display()
{
 if(first==NULL)
 cout<<"\nQueue Empty";
 else
 {
 cur=first;
 cout<<"\n";
  while(cur!=NULL)
  {
  cout<<"\t"<<cur->data;
  cur=cur->link;
  }
 }
}

int main()
{
 int ch;
 do
 {
 cout<<"\n 1.INSERT \n 2.DELETE  \n 3.Display \n 4.EXIT ";
 cout<<"\nENTER YOUR CHOICE : ";
 cin>>ch;

  switch(ch)
  {
  case 1: insert(); break;
  case 2: delte(); break;
  case 3: display(); break;
  case 4: exit(0);
  default:cout<<"\nInvalid Choice";
  }
 }while(ch!=4);
return 0;
}

3 Stack - Linked List

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

using namespace std;

void push();
void pop();
void display();


struct node
{
int info;
struct node *link;
} *top=NULL;

int main()
{
int choice;

 do
 {
 cout<<"\n\n1.Push\n";
 cout<<"2.Pop\n";
 cout<<"3.Display\n";
 cout<<"4.Quit\n";
 cout<<"Enter your choice : ";
 cin>>choice;

  switch(choice)
  {
  case 1:push();break;
  case 2:pop();break;
  case 3:display();break;
  case 4:exit(1);
  default :cout<<"Wrong choice\n";
  }
 }while(choice!=4);
return 0;
}

void push()
{
struct node *tmp;
int pushed_item;

tmp = (struct node *)malloc(sizeof(struct node));

cout<<"Value to Push:";
cin>>pushed_item;

tmp->info=pushed_item;
tmp->link=top;
top=tmp;
}

void pop()
{
struct node *tmp;
 if(top == NULL)
 cout<<"Stack is empty\n";
 else
 {
 tmp=top;
 cout<<"Popped item is "<<tmp->info;
 top=top->link;
 free(tmp);
 }
}

void display()
{
struct node *ptr;
ptr=top;
 if(top==NULL)
 cout<<"Stack is empty\n";
 else
 {
 cout<<"Stack elements :\n";
  while(ptr!= NULL)
  {
  cout<<"\n"<<ptr->info;
  ptr = ptr->link;
  }
 }
}

2 Queue - Array

# include<iostream>

# define MAX 5



using namespace std;

int qu[MAX];

int r = -1;

int f = -1;

void insert();
void del();
void disply();



int main()

{

int choice;


 do

 {

 cout<<"1.Insert\n";

 cout<<"2.Delete\n";

 cout<<"3.Display\n";

 cout<<"4.Quit\n";

 cout<<"Enter your choice : ";

 cin>>choice;



  switch(choice)

  {

  case 1 :insert();break;

  case 2 :del();break;

  case 3:display();break;

  case 4:exit(1);

  default:
cout<<"Wrong choice\n";

  }

 }while(choice!=4);

return 0;
}



void insert()

{

int added_item;


 if (r==MAX-1)

 cout<<"Queue Overflow\n";

 else

 {

  if (f==-1)
  f=0;

  cout<<"Input the element for adding in queue : ";

  cin>>added_item;

  r=r+1;

  qu[r] = added_item ;

 }

}



void del()

{

 if (f == -1 || f > r)

 {

 cout<<Queue Underflow\n";

 return ;

 }

 else

 {

 cout<<"Element deleted from queue is :"
 cout<<"\n"<<qu[f];

 f=f+1;

 }

}



void display()

{

int i;

 if (f ==-1 )

 cout<<Queue is empty\n";

 else

 {

 cout<<"Queue is :\n";

 for(i=f;i<= r;i++)

 cout<<qu[i]<<"\n";

 }

}

1 Stack - Array

#include<iostream>

#define MAX 5



using namespace std;

int top = -1;

int stack[MAX];



void push();
void pop();
void display();


int main()

{

int choice;


 do

 {

 cout<<"\n\n1.Push\n";

 cout<<"2.Pop\n";

 cout<<"3.Display\n";

 cout<<"4.Quit\n";

 cout<<"Enter your choice : ";

 cin>>choice;



  switch(choice)

  {

  case 1 :push();
break;

  case 2:pop();
break;

  case 3:display();
break;

  case 4:exit(1);


  default:cout<<"Wrong choice\n";

  }
 }while(choice!=4);
return 0;
}



void push()

{

int p;


if(top == (MAX-1))

cout<<"Stack Overflow\n";

 else

 {

 cout<<"Enter the item to be pushed in stack : ";

 cin>>p;
 top=top+1;

 stack[top] = p;

 }

}



void pop()

{

 if(top == -1)

 cout<<Stack Underflow\n";

 else

 {

 cout<<"Popped element is : "
 cin>>stack[top];

 top=top-1;

 }

}



void display()

{

int i;

 if(top == -1)

 cout<<"Stack is empty\n";

 else

 {

 cout<<"Stack elements :\n";

 for(i = top; i >=0; i--)

 cout<<"\n"
 cout<<stack[i];

 }

}

Binary Tree

Here the Program given Below Does all of the Following Functions In BINARY TREE:

1. Inserting a Element
2. Deleting a Element
3. Preorder
4. Inorder
5. Postorder
6. Searching an Element

(NOTE: the Inorder, PreOrder,PostOrder are in recursion ONLY!!!)

Thanks to தமிழரசு for the book DATA  STRUCTURES USING C - P.RadhGanesan from where this Program is written

#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 print(int);
void preorder(struct node *);
void inorder(struct node *);
void postorder(struct node *);
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 inorder(struct node *p)
{
 if(p!=NULL)
 {
 inorder(p->left);
 cout<<"\t"<<p->d;
 inorder(p->right);
 }
}

void preorder(struct node *p)
{
 if(p!=NULL)
 {
 cout<<"\t"<<p->d;
 preorder(p->left);
 preorder(p->right);
 }
}

void postorder(struct node *p)
{
 if(p!=NULL)
 {
 postorder(p->left);
 postorder(p->right);
 cout<<"\t"<<p->d;
 }
}

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 print(int x)
{
if(x==1)
 preorder(root);
else if(x==2)
 inorder(root);
else
 postorder(root);
}


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.PreOrder";

cout<<"\n3.InOrder";
cout<<"\n4.PostOrder";
cout<<"\n5.Deletion";
cout<<"\n6.Search";
cout<<"\n7.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:if(root!=NULL)
       {
       cout<<"\nPreOrder is:";
       print(1);
       cout<<"\n";
       }
       else
       cout<<"\nNo Element to Display";
       break;
case 3:if(root!=NULL)
       {
       cout<<"\nInOrder is:";
       print(2);
       cout<<"\n";
       }
       else
       cout<<"\nNo Element to Display";
       break;
case 4:if(root!=NULL)
       {
       cout<<"\nPostOrder is:";
       print(3);
       cout<<"\n";
       }
       else
       cout<<"\nNo Element to Display";
       break;
case 5:cout<<"\nEnter the Element to Delete:";
       cin>>x;
       remove(no);
       break;
case 6: cout<<"\nEnter the Element to Search: \t";

        cin>>no;

        search(no);

        break;

case 7: exit(0); break;

default: cout<<"\nEnter Any No. Between 1-7"; break;

}


}while(c!=7);


return 0;

}