Binary Tree Traversals

Binary TreeThis program is for creating and traversing a binary tree in preorder,inorder,postorder using recursion and level order using iteration

sorting

Sorting Algorithmssorting techniques

ADT

ADT This is about abstract data types

garbage collection

garbage collectionthis is for garbage collection

Stack Implementation Using Single Linked List

/*
Author:B.Vinod Kumar
email: vinod_cse2008@yahoo.com

  This is a program for implementation of the stack using single linked list.
  The operations performed on a stack are

  1)push(): This is the function which is for insertion(pushing)of an element into stack
              
      It is similar to the insertion of an element at the end of a single linked list
     
            see  the function insert_end() in the program for operations of single linked list

  2)pop(): This is the function which is for deletion(popping up) of an element from the stack

           It is similar to the deletion of an element at the end of a single linked list

     see  the function delete_end() in the program for operations of single linked list

  3)stack_display():This is the function which is for displaying the elements of a stack

    
      It is similar to the forward traversal of a single linked list

      see  the function ftraverse() in the program for operations of single linked list

note:
Stack is a list of elements in which insertions and deletions are at the same end of the list called top.
The other end is known as Bottom.Insertion is also known as push,deletion is also known as pop

*/
#include<iostream.h>
#include<stdlib.h>
class stack
{
 int element;
 stack* next;
public:
 stack* push(stack*,int);
 stack* pop(stack*);
 void stack_display(stack*);
}*head,object;
stack* stack::push(stack* head,int key)
{
 stack* temp,*temp1;
 temp1=head;
 temp=new stack;
 temp->element=key;
 temp->next=NULL;
 if(head==NULL)
  head=temp;
 else
 {
 while(head->next!=NULL)
  head=head->next;
 head->next=temp;
 head=temp1;
 }
 return head;
}
stack* stack::pop(stack* head)
{
 stack* temp;
 if(head!=NULL)
 {
 temp=head;
 if(head->next==NULL)
 {
  cout<<"\nthe pooped element from the stack is: "<<head->element<<endl;
  return NULL;
 }
 while(head->next->next!=NULL)
 head=head->next;
 cout<<"the popped element from the stack is  "<<head->next->element;
 cout<<endl;
 head->next=head->next->next;
 head=temp;
 return head;
 }
 else
 {
  cout<<"\nit is impossible to pop an element from the stack as ";
  return head;
 }
}
void stack::stack_display(stack* head)
{
 if(head!=NULL)
 {
 while(head->next!=NULL)
 {
  cout<<head->element<<"->";
  head=head->next;
 }
 cout<<head->element;
 cout<<endl;
 }
 else
  cout<<"the stack is empty\n";
}  
void choice()
{
  int key,ch;
 cout<<"\nchoose the operation to be performed\n";
 cout<<"\n1.push\t2.pop\t3.exit\n\n";
 cin>>ch;
head=NULL;
while(1)
{
 switch(ch)
 {
 case 1:
  
 cout<<"——————————————————————————–\n";
  cout<<"\nenter the element to be pushed\n";
  cin>>key;
  head=object.push(head,key);
  cout<<"\nthe stack after push operation is \n";
  object.stack_display(head);
  
 cout<<"——————————————————————————–\n";
  break;

 case 2:
 cout<<"\n“““““““““““““““““““““““““““““““““““““““\n";
  head=object.pop(head);
  cout<<"\nthe stack after pop operation is :\n";
  object.stack_display(head);
  
 cout<<"\n“““““““““““““““““““““““““““““““““““““““\n";
  break;
 case 3:
  exit(1);
 default:
  cout<<"\nenter the correct choice\n";
  break;
 }
cout<<"\nchoose the operation to be performed\n";
 cout<<"\n1.push\t2.pop\t3.exit\n";
 cin>>ch;
}
}
void main()
{
choice();
}

Queue Using Single Linked List

/*
Author: B.Vinod Kumar
email: vinod_cse2008@yahoo.com

  This is a program for implementation of the queue using single linked list.
  The operations performed on a queue are

  1)enqueue(): This is the function which is for insertion(enqueueing)of an element into queue
              
      It is similar to the insertion of an element at the end of a single linked list
     
               see  the function inset_end() in the program for operations of single linked list

  2)dequeue(): This is the function which is for deletion(dequeueing) of an element from the queue

               It is similar to the deletion of an element at front of a single linked list

      see  the function delete_front() in the program for operations of single linked list

  3)queue_display():This is the function which is for displaying the elements of a queue

    
      It is similar to the forward traversal of a single linked list

      see  the function ftraverse() in the program for operations of single linked list

note:
Queue is a list of elements in which insertions are at one end of the list called rear end
and the deletions are at the other end of the list called FRONT end.
Insertion is also known as Enqueue,deletion is also known as Dequeue

*/
#include<iostream.h>
class queue
{
 int element;
 queue* next;
public:
 queue* enqueue(queue*,int);
 queue* dequeue(queue*);
 void queue_display(queue*);
}*head,*tail,object;

queue* queue::enqueue(queue* head,int key)
{
 queue* temp;
 temp=new queue;
 temp->element=key;
 temp->next=NULL;
 if(head==NULL)
  head=temp;
 else
  tail->next=temp;
 tail=temp;
 return head;
}
queue* queue::dequeue(queue* head)
{
queue* temp;
if(head==NULL)
{
 cout<<"\nit is impossible to dequeue an element as ";
 return NULL;
}
else if(head->next==NULL)
{
 cout<<"\nthe element dequeued from the queue is: "<<head->element<<endl;
 return NULL;
}
else
{
 cout<<"\nthe element dequeued from the queue is "<<head->element<<endl;
 temp=head->next;
 head=temp;
 cout<<"\nthe elements of queue after dequeueing are \n";
 return head;
}
}
void queue::queue_display(queue* head)
{
 if(head!=NULL)
 {
  while(head->next!=NULL)
  {
   cout<<head->element<<"->";
   head=head->next;
  }
  cout<<head->element;
  cout<<endl;
 }
 else
  cout<<"the queue is empty\n";
}
void choice()
{
 
 int key,ch;
 head=tail=NULL;
 cout<<"\nchoose the operation\n";
 cout<<"\n1.enqueue\t2.dequeue\t3.exit\n\n";
 cin>>ch;
 while(ch!=3)
 {
  switch(ch)
  {
  case 1:
  cout<<"\nenter the key to be inserted\n";
  cin>>key;
  head=object.enqueue(head,key);
  cout<<"\nthe elements of queue after inserting "<<key<<" are\n";
  object.queue_display(head);
  break;
  case 2:
   head=object.dequeue(head);   
   object.queue_display(head);
   break;
  case 3:
   break;
  default:
   cout<<"\nenter correct choice\n";
   break;
  }
  cout<<"\n——————————————————————————\n";
 cout<<"\nchoose the operation\n";
 cout<<"\n1.enqueue\t2.dequeue\t3.exit\n\n";
 cin>>ch;
 
  cout<<"\n——————————————————————————\n";
 }
}
void main()
{
 choice();
}

code for Dijkstra’s algorithm in c++

/*Author: Vinod Kumar.B

email: vinod_cse2008@yahoo.com

*/

#include<iostream.h>
class dijkstra
{
private:
 int graph[15][15];
 int set[15],predecessor[15],mark[15],pathestimate[15];
 int source;
 int num_of_vertices;
public:
 int minimum();
 void read();
 void initialize();
 void printpath(int);
 void algorithm();
 void output();
};
void dijkstra::read()
{
 cout<<”enter the number of vertices\n”;
 cin>>num_of_vertices;
 while(num_of_vertices<=0)

{
  cout<<”\nthis is meaningless,enter the number carefully\n”;

cin>>num_of_vertices;

}
 cout<<”enter the adjacent matrix:\n”;
 for(int i=1;i<=num_of_vertices;i++)
 {
  cout<<”\nenter the weights for the row\n”<<i;
  for(int j=1;j<=num_of_vertices;j++)
  {
   cin>>graph[i][j];
   while(graph[i][j]<0)
   {
    cout<<”\nu should enter the positive valued weights only\nenter the value again\n”;
    cin>>graph[i][j];
   }
  }
 }
cout<<”\nenter the source vertex\n”;
cin>>source;
}

void dijkstra::initialize()
{
 for(int i=1;i<=num_of_vertices;i++)
 {
  mark[i]=0;
  pathestimate[i]=999;
  predecessor[i]=0;
 }
 pathestimate=0;
}
void dijkstra::algorithm()
{
 initialize();
 int count=0;
 int i;
 int u;
while(count<num_of_vertices)
 {
  u=minimum();
  set[++count]=u;
  mark[u]=1;
  for(i=1;i<=num_of_vertices;i++)
  {
   if(graph[u][i]>0)
   {
    if(mark[i]!=1)
    {
    if(pathestimate[i]>pathestimate[u]+graph[u][i])
    {
     pathestimate[i]=pathestimate[u]+graph[u][i];
     predecessor[i]=u;
    }
    }
   }
  }
 }

}

void dijkstra::printpath(int i)
{
cout<<endl;
if(i==source)
{
cout<<source;
}
else if(predecessor[i]==0)
cout<<”no path from “<<source<<” to “<<i;
else
{
printpath(predecessor[i]);
cout<<”..”<<i;
}
}
void dijkstra::output()
{
 for(int i=1;i<=num_of_vertices;i++)
 {
 printpath(i);
 if(pathestimate[i]!=999)
  cout<<”->(“<<pathestimate[i]<<”)\n”;
 }
 cout<<endl;
}
int dijkstra::minimum()
{
int min=999;
 int i,t;
 for(i=1;i<=num_of_vertices;i++)
 {
  if(mark[i]!=1)
  {
   if(min>=pathestimate[i])
   {
   min=pathestimate[i];
   t=i;
   }
  }
 }
 return t;
}
void main()
{
 dijkstra s;
 s.read();
 s.algorithm();
 s.output();
}

shortest path problem

weight function for a weighted direct graph G=(V,E) ,W:E->R mapping from edges to real valued weights.
the weight of a path p=(v0,v1,v2,v3…….,vn) is given by the sum of its constituent edges.

the length of shorest path is given by l(u,v)=min(w(p)) if there is a path from
u to v; other wise l(u,v)=infinity

shortest path from vertex u to vertex v can be defined as that path p whose
w(p)=l(u,v);

the types of shortest path problems are:

1) single source shortest path problem: Ths is to find the shortest path from a given source vertex 's' to all other vertices in V

2)single destination shortest path prolem: This is to find the shortest paths to a vertex v from all other vertirces in V

3)single pair shortest path problem:This is to find the shortest path from a vertex u to a vertex v for a given pair of vertices (u,v) which belong to V

4)All-pairs shortest paths problem:This is to find the shortest paths from vertex u to vertex v for each pair of (u,v) which are in V

 

code for dijkstra’s algorithm in c

#include<stdio.h>
#include<stdlib.h> 
void main()
{
 int graph[15][15],s[15],pathestimate[15],mark[15];
 int num_of_vertices,source,i,j,u,predecessor[15];
 int count=0;
 int minimum(int a[],int m[],int k);
 void printpath(int,int,int[]);
 printf("\nenter the no.of vertices\n");
 scanf("%d",&num_of_vertices);
 if(num_of_vertices<=0)
 {
  printf("\nthis is meaningless\n");
   exit(1);
 }
 printf("\nenter the adjacent matrix\n");
    for(i=1;i<=num_of_vertices;i++)
 {
  printf("\nenter the elements of row %d\n",i);
  for(j=1;j<=num_of_vertices;j++)
  {
   scanf("%d",&graph[i][j]);
  }
 }
 printf("\nenter the source vertex\n");
 scanf("%d",&source);
 for(j=1;j<=num_of_vertices;j++)
 {
  mark[j]=0;
  pathestimate[j]=999;
  predecessor[j]=0;
 }
 pathestimate=0;
 
 while(count<num_of_vertices)
 {
  u=minimum(pathestimate,mark,num_of_vertices);
  s[++count]=u;
  mark[u]=1;
  for(i=1;i<=num_of_vertices;i++)
  {
   if(graph[u][i]>0)
   {
    if(mark[i]!=1)
    {
    if(pathestimate[i]>pathestimate[u]+graph[u][i])
    {
     pathestimate[i]=pathestimate[u]+graph[u][i];
     predecessor[i]=u;
    }
    }
   }
  }
 }
 for(i=1;i<=num_of_vertices;i++)
 {
 printpath(source,i,predecessor);
 if(pathestimate[i]!=999)
 printf("->(%d)\n",pathestimate[i]);
 }
}
int minimum(int a[],int m[],int k)
{
 int mi=999;
 int i,t;
 for(i=1;i<=k;i++)
 {
  if(m[i]!=1)
  {
  if(mi>=a[i])
  {
   mi=a[i];
   t=i;
  }
 }}
 return t;
}
void printpath(int x,int i,int p[])
{
 printf("\n");
if(i==x)
{
printf("%d",x);
}
else if(p[i]==0)
printf("no path from %d to %d",x,i);
else
{
printpath(x,p[i],p);
printf("..%d",i);
}
}

Hello world!

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!