Heapsort

#include<stdio.h>
#include<conio.h>
#define max 50

struct elem
{
 int info;
}ar[max],tr[max],item;

int noe,i,ptr,par,ind,left,right;

void inp_dat()
{
 do
 {
 printf("\n\n Enter the no. of elements : ");
 scanf("%d",&noe);
 }while(noe<=0 || noe>=max);
 printf("\n\n Enter the '%d' elements of array in unsorted order : ",noe);
 for(i=1;i<=noe;i++)
  scanf("%d",&ar[i].info);
 printf("\n\n The '%d' elements of array in unsorted order :",noe);
 for(i=1;i<=noe;i++)
  printf(" %d",ar[i].info);
}

void ins_heap(int n)
{
 tr[n] = ar[n];
 if(n != 1)
 {
 ptr = n;
 par = ptr/2;
 while(ptr>1 && tr[par].info < tr[ptr].info)
 {
  item = tr[par];
  tr[par] = tr[ptr];
  tr[ptr] = item;
  ptr = par;
  par = ptr/2;
 }
 }
}

void del_heap(int n)
{
 item = tr[1];
 tr[1] = tr[n];
 tr[n] = item;
 par = 1; left = 2; right = 3;
 ind = 0;
 while(par < n && ind == 0)
 {
  if(tr[left].info > tr[par].info && tr[left].info > tr[right].info && left<n)
  {
  item = tr[left];
  tr[left] = tr[par];
  tr[par] = item;
  par = left;
  }
  else if(tr[right].info > tr[par].info && tr[left].info < tr[right].info  && right<n)
  {
  item = tr[right];
  tr[right] = tr[par];
  tr[par] = item;
  par = right;
  }
  else
   ind = 1;
  left = 2*par;
  right = 2*par+1;
 }
 ar[n] = tr[n];
}

void hp_srt()
{
 for(i=1;i<=noe;i++)
  ins_heap(i);
 i = noe;
 while(i>=1)
 {
 del_heap(i);
 i--;
 }
 printf("\n\n The '%d' elements of array in sorted order :",noe);
 for(i=1;i<=noe;i++)
  printf(" %d",ar[i].info);
}

void main()
{
clrscr();
inp_dat();
hp_srt();
getch();
}

Depth-First Search (DFS) Algorithm

#include<stdio.h>

#include<conio.h>
#include<iostream.h>
#include"graph01.cpp"          /* Refer this Source Code */
#define max 50

struct stack
{
 int top;
 struct node *ver[max];
}stk;

void DFS()
{
 printf("\n Enter the starting Node : ");
 cin>>item;
 stk.top = 1;
 find_node();
 if(loc != NULL)
 {
  loc->status = 2;
  stk.ver[stk.top] = loc;
 }
 else
  printf("\n\n Node not found !!\n\n");
 printf("\n\n The DFS Traversal Is : ");
 while(stk.top != 0)
 {
  loc = stk.ver[stk.top--];
  printf(" %c",loc->info);
  loc->status = 3;
  //qu.front++;
  ptre = loc->adj;
  while(ptre!=NULL)
  {
   if(ptre->dest->status == 1)
   {
    ptre->dest->status = 2;
    stk.ver[++stk.top] = ptre->dest;
   }
  ptre = ptre->link;
  }
 }
}

void main()
{
clrscr();
create_node();
create_vertices();
DFS();
getch();
}

Breadth-First Search (BFS) Algorithm

#include<stdio.h>

#include<conio.h>
#include<iostream.h>
#include"graph01.cpp"          /* Refer this Source Code */
#define max 50

struct queue
{
 int front;
 int rear;
 struct node *ver[max];
}qu;

char string[max];

void BFS()
{
 printf("\n Enter the starting Node : ");
 cin>>item;
 qu.front = qu.rear = 1;
 find_node();
 if(loc != NULL)
 {
  loc->status = 2;
  qu.ver[qu.front] = loc;
 }
 else
  printf("\n\n Node not found !!\n\n");
 printf("\n\n The BFS Traversal Is : ");
 while(qu.front != 0)
 {
  loc = qu.ver[qu.front];
  printf(" %c",loc->info);
  loc->status = 3;
  qu.front++;
  ptre = loc->adj;
  while(ptre!=NULL)
  {
   if(ptre->dest->status == 1)
   {
    ptre->dest->status = 2;
    qu.rear += 1;
    qu.ver[qu.rear] = ptre->dest;
   }
  ptre = ptre->link;
  }
  if(qu.front > qu.rear)
   qu.front = 0;
 }
}

void main()
{
clrscr();
create_node();
create_vertices();
BFS();
getch();
}

Breadth and Depth First Search (BFS and DFS) Algorithms (Complex)

#include<stdio.h>
#include<conio.h>
#include<malloc.h>

struct node
{
char info;
int status;
struct node *next;
struct adjlist *adj;
}*start,*temp,*temp1,*q,*svar;



char queue[100];
int front=-1;
int rear=-1;

struct adjlist
{
char dest;
int status;
struct adjlist *link;
}*edge1,*p,*r;

struct node *findnode(struct node *,char);
void input(char);
void inputedge(char,char);


void dfsinitial(struct node *);
void dfssearch(struct node *);
void bfsinitial(struct node *);
void bfssearch(struct node *);
void queueinsert(char);
char queuedelete();
void backs();


void main()
{

int ch,choice=1;
char n,n1,n2;
clrscr();
do
{
printf("1. Input \n");
printf("2. input edge\n");
printf("3. bfs  search\n");





printf("Enter your choice\n");
scanf("%d",&ch);
fflush(stdin);

switch(ch)
{
case 1: printf("Enter the node\n");
scanf("%c",&n);
input(n);
 break;

case 2: printf("Enter the nodes between whom you want an edge\n");
scanf("%c\t%c",&n1,&n2);
inputedge(n1,n2);
break;




case 3: printf("The bfs search is as follows\n");
 bfsinitial(start);
 backs();
 break;
default: printf("Wrong choice\n");
}
printf("\nDo you want to enter more??\n");
scanf("%d",&choice);
}while(choice==1);
getch();

}


void backs()
{
printf("\b");
}

void input(char item)      //TO ADD NODES
{
struct node *ptr;
ptr=(struct node *)malloc(sizeof(struct node));

if(ptr==NULL)
{
printf("Memory full\n");
}

if(start==NULL)
{
ptr->info=item;
ptr->next=NULL;
ptr->adj=NULL;
start=ptr;
}

else
{
ptr->info=item;
ptr->next=start;
ptr->adj=NULL;
start=ptr;
}
ptr->status=1;

}

void inputedge(char item1,char item2)                 // TO ADD AN EDGE
{
temp=findnode(start,item1);
temp1=findnode(start,item2);
if(temp==NULL || temp1==NULL)
{
printf("Node not present\n");
}
edge1=(struct adjlist *)malloc(sizeof(struct adjlist));
edge1->dest=temp1->info;
if(temp->adj==NULL)
{


edge1->link=NULL;
temp->adj=edge1;
}
else
{
edge1->link=temp->adj;
temp->adj=edge1;
}
edge1->status=1;
}

struct node *findnode(struct node *graph,char item)  // TO FIND A NODE
{
while(graph!=NULL && graph->info!=item)
{
graph=graph->next;
}
if(item==graph->info)
{
return graph;
}
return 0;
}








void bfsinitial(struct node *start)
{

char a;
q=start;
queueinsert(q->info);
q->status=2;
a=queuedelete();
printf("%c",a);


bfssearch(q);
}

void bfssearch(struct node *yum)
{
char b,d;
r=yum->adj;
if(r->status==1)
{

while(r!=NULL && (r->status==1))
{

d=r->dest;
queueinsert(d);
r->status=2;
r=r->link;

}


b=queuedelete();
printf("%c",b);

svar=findnode(start,b);

bfssearch(svar);
}

}

void queueinsert(char s)
{
 if(front==-1 && rear==-1)
 {
 front=0;
 rear=0;
  queue[rear]=s;
 }
 else
 {
 rear++;
 queue[rear]=s;
 }

 }

 char queuedelete()
 {
 char rtn;
 rtn=queue[front];
 if(front==-1 && rear==-1)
 {
 printf("The queue is empty\n");
 }
 else if(front==rear)
 {
 front=-1;
 rear=-1;
 }

 else
 {
front++;
 }
 return rtn;
 }

Breadth and Depth First Search (BFS and DFS) Algorithms (Simple)

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
#include"graph01.cpp"      /* Refer this Source Code */
#define max 50

struct queue
{
 int front;
 int rear;
 struct node *ver[max];
}qu;

struct stack
{
 int top;
 struct node *ver[max];
}stk;


void BFS()
{
 qu.front = qu.rear = 1;
 if(loc != NULL)
 {
  loc->status = 2;
  qu.ver[qu.front] = loc;
 }
 else
  printf("\n\n Node not found !!\n\n");
 printf("\n\n The BFS Traversal Is : ");
 while(qu.front != 0)
 {
  loc = qu.ver[qu.front];
  printf(" %c",loc->info);
  loc->status = 3;
  qu.front++;
  ptre = loc->adj;
  while(ptre!=NULL)
  {
   if(ptre->dest->status == 1)
   {
    ptre->dest->status = 2;
    qu.rear += 1;
    qu.ver[qu.rear] = ptre->dest;
   }
  ptre = ptre->link;
  }
  if(qu.front > qu.rear)
   qu.front = 0;
 }
}

void DFS()
{
 stk.top = 1;
 if(loc != NULL)
 {
  loc->status = 2;
  stk.ver[stk.top] = loc;
 }
 else
  printf("\n\n Node not found !!\n\n");
 printf("\n\n The DFS Traversal Is : ");
 while(stk.top != 0)
 {
  loc = stk.ver[stk.top--];
  printf(" %c",loc->info);
  loc->status = 3;
  ptre = loc->adj;
  while(ptre!=NULL)
  {
   if(ptre->dest->status == 1)
   {
    ptre->dest->status = 2;
    stk.ver[++stk.top] = ptre->dest;
   }
  ptre = ptre->link;
  }
 }
}

void main()
{
clrscr();
create_node();
create_vertices();
printf("\n\n Enter the starting node : ");
cin>>item;
find_node();
int_stats();
BFS();
find_node();
int_stats();
DFS();
getch();
}

Basic Operations of Pointer Nodes

#include<stdio.h>
#include<conio.h>

 struct node
  {
   int info;
   node *next;
  }*start,*nptr,*save,*ptr,*end;

 node *create(int);
 int new_node_input();
 void insert_node(node *,int);
 void display_node(node *);
 void del_node(node *,int);

 void main()
 {
 clrscr();
 int choice,inf;
 start = end = NULL;
 inf = new_node_input();
 nptr = create(inf);
 insert_node(nptr,1);
 display_node(start);
 do
 {
 printf("\n\n\t\t What Would Like To Do Now ? \n");
 printf("\n 1. Inserting Node From the Beginning ");
 printf("\n 2. Inserting Node From the End ");
 printf("\n 3. Deleting Node From the Beginning");
 printf("\n 4. Deleting Node From the End");
 printf("\n\t\t ..... Hit Other Keys To Exit .....");
 printf("\n\n Enter your choice : ");
 scanf("%d",&choice);
 switch(choice)
  {
  case 1 :
  case 2 : inf = new_node_input();
  nptr = create(inf);
  insert_node(nptr,choice);
  break;

  case 3 :
  case 4 : del_node(nptr,choice);
  break;

  default : break;
  }
 display_node(start);
 }while((choice>=1)&&(choice<=4));
 printf("\n\n\t\t !!!! Thanks Fro Using The Program !!!!");
 getch();
 }

 int new_node_input()
 {
  int number;
  printf("\n Enter The Information For The New Node : ");
  scanf("%d",&number);
  return number;
 }

 node *create(int number)
 {
  ptr = new node;
  ptr->info = number;
  ptr->next = NULL;
  return ptr;
 }

 void insert_node(node *np,int choice)
 {
  printf("\n\n\t\tInsertion has been done \n\n");
  getch();
  if(start == NULL)
   start = end = np;
  else
  {
   if(choice == 1)
   {
   save = start;
   start = np;
   np->next = save;
   }
   else
   {
   end->next = np;
   end  = np;
   }
  }
 }

 void display_node(node *np)
 {
  printf("\n\n Now The List Is : \n\t");
  while(np != NULL)
  {
   printf("%d ->",np->info);
   np = np->next;
  }
 }

 void del_node(node *np,int choice)
 {
  printf("\n\n\t\tDeletion has been done \n\n");
  getch();
  if(start == NULL)
   printf("\n\nUNDERFLOW !!!\n\n");
  else
  {
   if (choice == 3)
   {
    np = start;
    start = start->next;
   }
   else
   {
    np = end;
    end = NULL;
   }
   delete np;
  }
 }

Basic Operations of Arrays

#include<stdio.h>
#include<conio.h>
#define max 20

struct data
 {
   int rno;
   int marks;
 }dt[max];

 struct data input_data();
 void disp_data(struct data[],int);
 void disp_sdata(struct data);
 int disp_sbm(int);
 void add_ele(struct data[],int&,int);
 void del_ele(struct data[],int&,int);
 void Ssort(struct data[],int);
 void Bsort(struct data[],int);
 void Lsearch(struct data[],int,int);
 void Bsearch(struct data[],int,int);
 void trav(struct data[],int,int);

void main()
 {
  clrscr();
  int i,num,cho,sbch,item,ssbch;
  do
  {
  printf("Enter the no. of students :- ");
  scanf("%d",&num);
  }while( num <= 0 ||  num >= max );
  for(i=0;i<num;i++)
   {
    printf("\n\n Enter the data of the student #%d: \n",i+1);
    dt[i] = input_data();
   }
  clrscr();
  disp_data(dt,num);
  getch();
  do
  {
  clrscr();
  printf("\n\n\t\t\t   Menu Selection\n");
  printf("\n 1. Insertion of an Element ");
  printf("\n 2. Deletion of an Element ");
  printf("\n 3. Sorting of an Array ");
  printf("\n 4. Searching of an Element ");
  printf("\n 5. Traversing of all Elements ");
  printf("\n\t\t Hit Other Keys To Exit .....");
  printf("\n\n Enter your choice :- ");
  scanf("%d",&cho);
  switch(cho)
   {
    case 1: sbch = disp_sbm(1);
   switch(sbch)
    {
      case 1:
      case 2:
      case 3: add_ele(dt,num,sbch);
      break;
     default : break;
    }
   break;
    case 2: sbch = disp_sbm(2);
   switch(sbch)
    {
      case 1:
      case 2:
      case 3: del_ele(dt,num,sbch);
      break;
     default : break;
    }
   break;
    case 3: sbch = disp_sbm(3);
   switch(sbch)
    {
      case 1: Ssort(dt,num);
      break;
      case 2: Bsort(dt,num);
      break;
     default : break;
    }
   break;
    case 4: sbch = disp_sbm(4);
   printf("Enter the roll no. to be searched : ");
   scanf("%d",&item);
   switch(sbch)
    {
      case 1: Lsearch(dt,num,item);
      break;
      case 2: Bsearch(dt,num,item);
      break;
      default: break;
    }
   break;
    case 5: sbch = disp_sbm(5);
   switch(sbch)
    {
      case 1:
      case 2: trav(dt,num,sbch);
      break;
      default: break;
    }
   break;
   }
  if(cho>=1 && cho<=5)
   disp_data(dt,num);
  }while(cho>=1 && cho<=5);
  printf("\n\n\t\t !!!! Thanks Fro Using The Program !!!!");
  getch();
 }

struct data input_data()
 {
   struct data s;
   printf("\n\t Enter the Roll no. of the student :- ");
   scanf("%d",&s.rno);
   printf("\n\t Enter the marks of the student :- ");
   scanf("%d",&s.marks);
   return s;
 }

void disp_data(struct data s[],int noe)
 {
  int i;
  clrscr();
  printf("\n\n\t The current status of the current data \n");
  for(i=0;i<noe;i++)
  {
   printf("\n\n Data of the Student #%d: \n",i+1);
   printf("\n\t Roll no.:- %d",s[i].rno);
   printf("\n\t Marks :- %d",s[i].marks);
  }
  getch();
 }

void disp_sdata(struct data s)
 {
    printf("\n\n Data of the Student \n");
    printf("\n\t Roll no.:- %d",s.rno);
    printf("\n\t Marks :- %d",s.marks);
 }

 int disp_sbm(int choice)
  {
    int sb_choice;
    if(choice == 1 || choice ==2)
    {
     if(choice == 1)
      printf(" \n\n\t Select the position to insert an element ");
     else
      printf(" \n\n\t Select the position to delete an element ");
    printf("\n 1. At the beginning ");
    printf("\n 2. At the end ");
    printf("\n 3. At a desired position ");
    }
    else if(choice==3)
    {
     printf(" \n\n\t Select the option of sorting the array ");
     printf("\n 1. Selection Sort ");
     printf("\n 2. Bubble Sort  ");
    }
    else if(choice==4)
    {
     printf(" \n\n\t Select the option of searching an element ");
     printf("\n 1. Linear Search ");
     printf("\n 2. Binary Search  ");
    }
    else
    {
     printf(" \n\n\t Select the option of traversing of all element ");
     printf("\n 1. Addition of every Element ");
     printf("\n 2. Subtraction of every Element ");
    }
    printf("\n\n Choose your option : ");
    scanf("%d",&sb_choice);
    return sb_choice;
  }
 void add_ele(struct data x[],int &noe,int choice)
  {
   int i,loc=0;
   struct data temp;
   if(noe == max)
    printf("\n Warning : OVERFLOW !!! ");
   else
    {
      if(choice == 3)
       {
do
{
 printf("\n Enter the location you want insert the element");
 scanf("%d",&loc);
}while( loc>noe || loc<=0 );
loc -= 1;
       }
      printf("Enter the details of the element");
      temp = input_data();
      if(choice == 1 || choice == 3)
       {
for(i=noe;i>loc;i--)
 x[i] = x[i-1];
x[loc] = temp;
       }
      else
       {
x[noe] = temp;
       }
       noe += 1;
      printf("\n\n\t\t The element has been inserted ");
      getch();
    }
  }

 void del_ele(struct data x[],int &noe,int choice)
  {
   int i,loc=0;
   if(noe == 0)
    printf("\n Warning : UNDERFLOW !!! ");
   else
    {
      if(choice == 3)
       {
do
{
 printf("\n Enter the location you want delete the element");
 scanf("%d",&loc);
}while( loc>noe || loc<=0 );
loc -= 1;
       }
      if(choice == 1 || choice == 3)
       {
for(i=loc;i<noe-1;i++)
 x[i] = x[i+1];
       }
       noe -= 1;
      printf("\n\n\t\t The element has been deleted ");
      getch();
    }
  }
 void Ssort(struct data x[],int noe)
  {
   int i,j,flag,small,posn;
   struct data temp;
   for(i=0;i<noe;i++)
   {
    flag = 0;
    small = x[i].rno;
    for(j=i+1;j<noe;j++)
    {
     if( x[j].rno < small )
      { small = x[j].rno;  flag = 1; posn = j; }
    }
    if(flag==1)
     {
     temp = x[i];
     x[i] = x[posn];
     x[posn] = temp;
     }
   }
   printf("\n\n\t\t Sorting has been done ... \n\n");
  }
 void Bsort(struct data x[],int noe)
  {
   int i,j;
   struct data temp;
   for(i=0;i<noe;i++)
   {
    for(j=0;j<noe-1-i;j++)
    {
     if( x[j].rno > x[j+1].rno )
     {
     temp = x[j];
     x[j] = x[j+1];
     x[j+1] = temp;
     }
    }
   }
   printf("\n\n\t\t Sorting has been done ... \n\n");
  }

 void Lsearch(struct data x[],int noe,int ele)
  {
    int flag=0,i,noc=0,posn;
    for(i=0;i<noe;i++)
     {
      noc++;
      if(ele == x[i].rno)
       {  flag = 1;  posn = i;  break;  }
     }
    if(flag==0)
     printf("\n\nThe data not found ");
    else
     {
      printf("\n\nThe data has been found at position #%d",posn+1);
      printf("\n& The no. of comparisions were made : %d",noc);
      disp_sdata(x[posn]);
      }
    getch();
  }

void Bsearch(struct data x[],int noe,int ele)
   {
     int flag=0,i,noc=0,posn,beg,last,mid;
     beg = 0; last = noe - 1;
     Ssort(x,noe);
     while(beg<=last)
      {
       mid = (beg+last)/2;
       noc++;
       if(ele == x[mid].rno)
{
flag = 1;
posn = mid;
break;
}
       else if(ele > x[mid].rno)
beg = mid + 1;
       else
last = mid - 1;
      }
     if(flag==0)
      printf("\n\nThe data not found ");
     else
      {
      printf("\n\nThe data has been found at position #%d",posn+1);
      printf("\n& The no. of comparisions were made : %d",noc);
      disp_sdata(x[posn]);
      }
      getch();
   }
 void trav(struct data x[],int noe,int choice)
  {
   int i,ele;
   if(choice == 1)
    printf("\n Enter any number to be added to the data : ");
   else
    printf("\n Enter any number to be subtracted from the data : ");
   scanf("%d",&ele);
   for(i=0;i<noe;i++)
    {
     if(choice == 1)
       x[i].marks += ele;
     else
       x[i].marks -= ele;
    }
   printf("\n\n\t Traversing of all the elements of the data has been done \n\n");
   getch();
  }