C++ program to implement circular queue

C++ program to implement circular queue: A data structure program in C++ , which implements circular queue.Circular queue is a type of queue in data structure in which the last node contains the reference of first node.

C++ program to implement circular queue

#include<iostream.h>

#include<conio.h>#include<process.h>
class queue
  {int data[10];
   int front,rear;
   public:
   queue()
     {front=-1;
      rear=-1;
     }
   void add();
   void remove();
   void display();
  };
void queue::add()
  {if((rear+1==front)||(rear==9&&front==0))
     {cout<<"Overflow ";
     }
   else
     {if((rear==-1) &&(front==-1))
    {rear=0;
     front=0;
    }
      else if(rear==9)
    {rear=0;
    }
      else
    {rear++;
    }
      cout<<"Enter the element ";
      cin>>data[rear];
     }
  }
void queue::remove()
  {if(front==-1&&rear==-1)
     {cout<<"Underflow ";
     }
   else
     {if(front==9)
       {front=0;
       }
      else if(front==rear)
       {front=-1;
    rear=-1;
       }
      else
       {front++;
       }
     }
  }
void queue::display()
  {int i=0,n=9;
   if(rear==-1)
     {cout<<"No elements.."<<endl;
     }
   else
   { if(rear>front)
     {for(i=0;i<front;i++)
    {cout<<"_";
    }
      for(i=front;i<=rear;i++)
    {cout<<data[i];
    }
      for(i=rear+1;i<n;i++)
    {cout<<"_";
    }
     }
   else
     {for(i=0;i<=rear;i++)
    {cout<<data[i];
    }
      for(i=rear+1;i<front;i++)
    {cout<<"_";
    }
      for(i=front;i<n;i++)
    {cout<<data[i];
    }
    } }
  }
void main()
  {clrscr();
   int ch;
   queue queue;
   X:
   cout<<"\nEnter your choice\n1.Insert\n2.Delete\n3.Display\n4.Exit\n";
   cin>>ch;
   switch(ch)
     {case 1:queue.add();
         goto X;
      case 2:queue.remove();
         goto X;
      case 3:queue.display();
         goto X;
      case 4:exit(0);
     }
   getch();
  }

Publisher: Anand - 03:20

C++ program to implement bubble sort and selection sort

C++ program to implement bubble sort  and selection sort: A simple data structure program which implement the sorting technique .Sorting techniques are bubble sort and selection sort.

C++ program to implement bubble sort  and selection sort

#include<iostream.h>
#include<conio.h>
#include<process.h>
void main()
{
clrscr();
int ch;
int i,j,x,k,z,l,m,n,o,p,a[50],small;
q :
cout<<"Enter the choice 1:Selection  2:Bubble 3:Exchange Selection  4:Insertion 5:Exit"<<endl;
cin>>ch;
switch(ch)
{
case 1:
cout<<"Enter the limit "<<endl;
cin>>n;
cout<<endl;
cout<<"Enter the elements"<<endl;

for(i=0;i<n;i++)
   {
   cin>>a[i];
   cout<<endl;
   }

for(j=0;j<n;j++)
   {
   small=a[j];
   p=j;
 for(i=j;i<n;i++)
    {
    if(small>a[i])
    {
    small=a[i];
    p=i;
    }
    }
    for(k=p;k>j;k--)
   {
   a[k]=a[k-1];
   }
   a[j]=small;
   }
cout<<"Result"<<endl;
  for(z=0;z<n;z++)
  {
  cout<<a[z];
  cout<<endl;
  }
  goto q;
  case 2:
cout<<"Enter the limit"<<endl;
cin>>n;
cout<<"Enter the elements"<<endl;
  for(i=0;i<n;i++)
  cin>>a[i];
for(j=0;j<n;j++)
  {
  for(i=0;i<n-1;i++)
   {
   if (a[i]>a[i+1])
   {
   x=a[i+1];
   a[i+1]=a[i];
   a[i]=x;
   }
  }
  }
cout<<"Result"<<endl;
  for (i=0;i<n;i++)
   {
   cout<<a[i];
   cout<<endl;
   }
 break;
 case 3 :
cout<<"Enter the limit "<<endl;
cin>>n;
cout<<endl;
cout<<"Enter the elements"<<endl;

for(i=0;i<n;i++)
   {
   cin>>a[i];
   cout<<endl;
   }

for(j=0;j<n;j++)
   {
   small=a[j];
   p=j;
 for(i=j;i<n;i++)
    {
    if(small>a[i])
    {
    small=a[i];
    p=i;
    }
    }
   a[p]=a[j];
   a[j]=small;
   }
cout<<"Result"<<endl;
  for(z=0;z<n;z++)
  {
  cout<<a[z];
  cout<<endl;
  }
  goto q;

case 4 :
 int m=-32767;
  cout<<"enter the no. of elements"<<endl;
  cin>>n;
  cout<<"enter the array"<<endl;
  for(i=1;i<=n;i++)
  {cin>>a[i];}
  a[0]=m;
  for(i=1;i<=n;i++)
  {for(j=0;j<i;j++)
  {if(a[i]<a[j])
  {p=a[i];
  for(k=i-1;k>=j;k--)
  {a[k+1]=a[k];}
  a[j]=p;}}}
  for(i=1;i<=n;i++)
  {cout<<a[i];}
  goto q;

case 5:
exit(0);
default:
cout<<"Wrong choice";
goto q;

}
getch();
}

Publisher: Anand - 02:56

C program to find the value of a collection of coins

Here is simple C program to find the value of a collection of coins is given,which takes number of number of quarters, dimes, nickels, and pennies from user and compute the value of collection of coins manually.

C program to find the value of a collection of coins

#include <stdio.h>

void main ()
{
   // Local data ...
   int pennies;              // input: count of pennies
   int nickels;              // input: count of nickels
   int dimes;                // input: count of dimes
   int quarters;             // input: count of quarters
   int temp, left;           // temporaries for various
                             // computations 

   // Read in the count of quarters, dimes, nickels and pennies.
   printf("Enter the number of quarters, dimes, nickels, and pennies: ");
   scanf("%d %d %d %d", &quarters, &dimes, &nickels, &pennies);

   // Compute the total value in cents.
   left = 25 * quarters + 10 * dimes + 5 * nickels + pennies;

   // Find and display the value in dollars
   printf("Your collection is worth\n "); 
   temp = left / 100;
   printf("\t%d dollar", temp);
   if (temp==1) 
      printf(", ");
   else
      printf("s, ");
   left = left % 100;

   // Find and display the value left in quarters
   temp = left / 25;
   printf("%d quarter", temp);
   if (temp==1) 
      printf(", ");
   else
      printf("s, ");
   left = left % 25;

   // Find and display the value left in dimes
   temp = left / 10;
   printf("%d dime", temp);
   // Here, just for fun, instead of using a conditional statement, 
   // I use a conditional expression and string concatenation
   printf ((temp==1) ? ", " : "s, ");
   left = left % 10;

   // Find and display the value left in nickels
   temp = left / 5;
   printf("%d nickel", temp);
   if (temp==1) 
      printf(", and ");
   else
      printf("s, and ");
   left = left % 5;

   // Find and display the value left in pennies
   printf("%d penn", left);
   if (left==1) 
      printf("y\n");
   else
      printf("ies\n");
}

Output

Publisher: Anand - 21:16

C Program to implement Linear and Binary Search

Linear and binary searching is a similar type of searching because it search only in sorted elements list or array.

C Program to implement Linear and Binary Search

#include <stdio.h>
#include <conio.h>
void main()
{
 int arr[20], i, n, element, opt, pos, flag=0, beg, mid, end;
 clrscr();
 printf("How many elements? ");
 scanf("%d",&n);
 printf("nEnter %d sorted elements  : ",n);
 for (i=0; i<n; i++)
 scanf("%d",&arr[i]);
 printf("nThe entered array is :n");
  for (i=0; i<n; i++)
 {
  printf("%dt",arr[i]);
 }
 for (i=1; i<n; i++)
 {
  if (arr[i-1]>arr[i])
  {
   printf("nThe array entered isn't sorted!");
   printf("nExiting");
   getch();
   exit();
  }
 }
 printf("nnt **MAIN MENU**");
 printf("n1. Search using Linear Search");
 printf("n2. Search using Binary Search");
 printf("n Enter an option : ");
 scanf("%d",&opt);
 printf("nEnter the element to search : ");
 scanf("%d",&element);

 if (opt==1)
 {
  for (i=0; i<n; i++)
   {
    if (element==arr[i])
    {
     pos=i+1;
     flag=1;
     printf("The element is at postion %d",pos);
    }
   }
 }

 else if (opt==2)
 {
  beg=0;
  end=n;
  for (mid=(beg+end)/2;beg<=end;mid=(beg+end)/2)
  {
   if (arr[mid]==element)
   {
    printf("nThe element is at position %d",mid+1);
    flag=1;
    break;
   }
   if (arr[mid]>element)
    end=mid-1;
   else
    beg=mid+1;
  }

 if (flag==0)
     {
  printf("nn##Element not in array##");
     }
 }

 else printf("nn ERROR!! INVALID INPUT");
 getch();

}





Output:

Publisher: Anand - 20:20

C program to Reverse a linked list

Linked list is a data structure, which consist of nodes. Nodes contain information i.e data field and linked field. You can perform various c program to implement insertion deletion and counting of nodes in linked list. Reverse linked list c code need some technique.For implementing this c program to reverse linked list we need to take 3 node pointer.

Example of C program to Reverse a linked list

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct node
{
 int no;
 struct node *next;
};
struct node *head=NULL,*temp,*LLt;
void addrecord();
void main()
{
 int ch;
 clrscr();
 while (1)
 {
  printf("n add element (number) TO LISTn 0 TO EXIT / END");
  scanf("%d", &ch)
  if (ch==0)
  {
   exit(0);
  }
  else
  {
   AddElement(ch,*LLt );
  } 
  printf("the reverse of linked list is %d " reverse(*LLt));
} 
 
void AddElement(ch,*LLt )
{
 struct node *temp;
 temp=(struct node*)malloc(sizeof(struct node));
 temp->no=ch; 
 if (LLt==NULL)
 {
  LLt=temp;
  temp->next=NULL; 
 }
 else
 { 
  LLt->next=temp;
  temp->next=NULL; 
 }
}
node *reverse(node *first)
{
 node *temp = NULL; 
 if(first->next != NULL)
 {
  temp = reverse(first->next);
  temp->next = first;
  return first;
 }
 else
  return first;
}

Publisher: Anand - 14:11

C Program to implement Radix Sort

The idea of Radix Sort is to do digit by digit sort starting from least significant digit to most significant digit. Radix sort uses counting sort as a subroutine to sort.

Example of C Program to implement Radix Sort

#include <stdio.h>
#define MAX 100
#define SHOWPASS
void print(int *a, int n) 
{
  int i;
  for (i = 0; i < n; i++)
   printf("%dt", a[i]);
}
 
void radix_sort(int *a, int n)
{
  int i, b[MAX], m = 0, exp = 1;
  for (i = 0; i < n; i++) {
  if (a[i] > m)
  m = a[i];
 }
 while (m / exp > 0)
 {
  int box[10] = { 0 };
  for (i = 0; i < n; i++)
   box[a[i] / exp % 10]++;
  for (i = 1; i < 10; i++)
   box[i] += box[i - 1];
   for (i = n - 1; i >= 0; i--)
   b[--box[a[i] / exp % 10]] = a[i];
   for (i = 0; i < n; i++)
   a[i] = b[i];
   exp *= 10;
  
#ifdef SHOWPASS
   printf("nnPASS   : ");
   print(a, n);
#endif
 }
}
 
int main() 
{
  int arr[MAX];
  int i, num;
  
  printf("nEnter total elements (num < %d) : ", MAX);
  scanf("%d", &num);
  printf("nEnter %d Elements : ", num);
  for (i = 0; i < num; i++)
  scanf("%d", &arr[i]);
  printf("nARRAY  : ");
  print(&arr[0], num);
  radix_sort(&arr[0], num);
  printf("nnSORTED  : ");
  print(&arr[0], num);
  
  return 0;
}

Publisher: Anand - 14:08

C Program To implement Queue using Linked list

Queue is a linear data structure, in which the first data element inserted from one end called REAR (also called tail),and the deletion of exisiting element takes place from the other end called FRONT(also called head). This make queue is FIFO data structure,which means that element inserted first will also be removed first

Example of C Program To implement Queue using Linked list

#include<stdio.h>
struct node
{
 int info;
 struct node *link;
}*front = NULL, *rear = NULL;

void insert();
void delet();
void display();
int item;

main()
{
 int ch;
 do
 {
  printf("nn1.tInsertn2.tDeleten3.tDisplayn4.tExitn");
  printf("nEnter your choice: ");
  scanf("%d", &ch);
  switch(ch)
  {
   case 1:
   insert();
   break;
   
   case 2:
   delet();
   break
   
   case 3:
   display();
   break;
   
   case 4:
   exit(0);
   
   default:
   printf("nnInvalid choice. Please try again...n");
  }
 } while(1);
 getch();
}

void insert()
{
 printf("nnEnter ITEM: ");
 scanf("%d", &item);
 if(rear == NULL)
 {
  rear = (struct node *)malloc(sizeof(struct node));
  rear->info = item;
  rear->link = NULL;
  front = rear;
 }
 else
 {
  rear->link = (struct node *)malloc(sizeof(struct node));
  rear = rear->link;
  rear->info = item;
  rear->link = NULL;
 }
}

void delet()
{
 struct node *ptr;
 if(front == NULL)
 printf("nnQueue is empty.n");
 else
 {
  ptr = front;
  item = front->info;
  front = front->link;
  free(ptr);
  printf("nItem deleted: %dn", item);
  if(front == NULL)
  rear = NULL;
 }
}

void display()
{
 struct node *ptr = front;
 if(rear == NULL)
 printf("nnQueue is empty.n");
 else
 {
  printf("nn");
  while(ptr != NULL)
  {
   printf("%dt",ptr->info);
   ptr = ptr->link;
  }
 }
}

Publisher: Anand - 14:05

C program to implement Quick Sort

Quick sort algorithm is based on divide and conquer strategy. In a quick sort we take the one element called as pivot,then we list all the smaller elements than pivot, and greater than pivot. after partitioning we have pivot in the final position. After recursively sorting the partition array, we get the sorted elements

Example of C program to implement Quick Sort

#include <stdio.h>
void quick_sort(int [], int, int);
int partition(int [], int, int);
main()
{
 int a[50], n, i;
 printf("nEnter size of an array: ");
 scanf("%d", &n);
 printf("nEnter elements of an array:n");
 for(i=0; i<n; i++)
 scanf("%d", &a[i]);
 quick_sort(a, 0, n-1);
 printf("nnAfter sorting:n");
 for(i=0; i<n; i++)
 printf("n%d", a[i]);
 getch();
}

void quick_sort(int a[], int beg, int end)
{
 int x;
 if (beg < end)
 {
  x = partition(a, beg, end);
  quick_sort(a, beg, x-1);
  quick_sort(a, x+1, end);
 }
}

int partition(int a[], int beg, int end)
{
 int loc = beg, temp;
 while (1)
 {
 while (a[loc]<=a[end] && loc!=end) /* Scan from right to left */
 end--;
 if (loc == end)
  return loc;
 temp = a[loc];
 a[loc] = a[end];
 a[end] = temp;
 loc = end;
 while (a[loc]>=a[beg] && loc!=beg) /* Scan from left to right */
  beg++;
 if (loc == beg)
  return loc;
 temp = a[loc];
 a[loc] = a[beg];
 a[beg] = temp;
 loc = beg;
 }
}

Publisher: Anand - 14:03

C Program to perform Insertion and Deletion operation in Queue

Queue is a linear data structure, in which the first data element inserted from one end called REAR (also called tail),and the deletion of exisiting element takes place from the other end called FRONT(also called head). This make queue is FIFO data structure,which means that element inserted first will also be removed first.We can perform various operation on queue ,here we provide a simple C program which perform insertion and deletion operation.

Example of C Program to perform Insertion and Deletion operation in Queue

#include < stdio.h>
#include < conio.h>
#include < malloc.h> 
#define SIZE 5
void menu();
void display();
int underflow();
int overflow();
void enqueue(int);
void dequeue();
int queue[SIZE];
int front=-1;
int rear=-1;
void main()
{
    clrscr();
    menu();
}
void menu()
{
    int choice,item;
    printf("MENU");
    printf("n1. Insert into the queue");
    printf("n2. Delete from queue");
    printf("n3. Display");
    printf("n4. Exit");
    printf("nEnter your choice: ");
    scanf("%d",&choice);
    switch(choice)
    {
        case 1:
            clrscr();
            if(overflow()==0)
            {
                printf("nEnter the item tobe inserted: ");
                scanf("%d",&item);
                enqueue(item);
                clrscr();
                printf("nAfter inserting queue is:n");
            }
            display();
            getch();
            clrscr();
            menu();
            break;
        
case 2:
            clrscr();
            if(underflow()==1)
            {
                dequeue();
                if(underflow()==1)
                {
                    printf("nAfter deletion queue is:n");
                    display();
                }
            }
            getch();
            clrscr();
            menu();
            break;
        case 3:
            clrscr();
            if(underflow()==1)
            {
                printf("The queue is:n");
                display();
            }
            getch();
            clrscr();
            menu();
            break;
        case 4:
            exit(1);
        default:
            clrscr();
            printf("Your choice is wrongnn");
            menu();
    }
}
int underflow()
{
    if((front==-1)&&(rear==-1))
    {
        printf("nQueue is empty");
        return(0);
    }
    else
    {
        return(1);
    }
}

int overflow()
{
    if(rear==SIZE-1)
    {
        printf("nQueue is fulln");
        return(1);
    }
    else
    {
        return(0);
    }
}
void enqueue(int item)
{
    if((front==-1)&&(rear==-1))
    {
        front=0;
        rear=0;
    }
    else
    {
        rear=rear+1;
    }
    queue[rear]=item;
}
void dequeue()
{
    if(front==rear)
    {
        front=-1;
        rear=-1;
    }
    else
    {
        front=front+1;
    }
}
void display()
{
    int i;
    for(i=front;i<=rear;i++)
    {
        printf("nElement %d : %d",i+1,queue[i]);
    }
}

Output

Publisher: Anand - 13:59

C Program to implement Prims algorithm

Prim’s algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph. This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.Here we provide a C program which finds a minimum spanning tree for a connected weighted graph.

Example of C Program to implement Prims algorithm

#include<stdio.h>
#include<conio.h>
int a,b,u,v,n,i,j,ne=1;
int visited[10]={0},min,mincost=0,cost[10][10];

void main()
{
  clrscr();
  printf("n Enter the number of nodes: ");
  scanf("%d",&n);
  printf("n Enter the adjacency matrix: sn");
  for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
  {
   scanf("%d",&cost[i][j]);
   if(cost[i][j]==0)
   cost[i][j]=999;
  }
  visited[1]=1;
  printf("n");
  while(ne<n)
  {
    for(i=1,min=999;i<=n;i++)
    for(j=1;j<=n;j++)
    if(cost[i][j]<min)
    if(visited[i]!=0)
    {
     min=cost[i][j];
     a=u=i;
     b=v=j;
    }
    if(visited[u]==0 || visited[v]==0)
    {
     printf("n Edge %d:(%d %d) cost:%d",ne++,a,b,min);
     mincost+=min;
     visited[b]=1;
    }
    cost[a][b]=cost[b][a]=999;
  }
  printf("n Minimun cost=%d",mincost);
  getch();
}

Output

Publisher: Anand - 13:54

C program to implement Merge Sort

There  is a C program to implement Merge Sort is given below. Merge sort is based on the divide conquer strategy. Array is divided in to two halves.if the array length is n, then it is divided into n/2,n/4,n/8…. and each part is sorted independently, then conquered into the sorted array. The efficiency of merge sort is O(n log n).

The program which is written bellow also compute the time complexity of sorting.

Example of C program to implement Merge Sort 

#include<stdio.h>
#include<conio.h>
#include<time.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

void main(){
   
    int merge[MAX],i,n;
 clock_t top, bottom;
    printf("Enter the total number of elements: ");
    scanf("%d",&n);

    printf("Enter the elements which to be sort: ");
    for(i=0;i<n;i++){
         scanf("%d",&merge[i]);
    }
 top = clock();
    partition(merge,0,n-1);
 delay(100);
 bottom = clock();
    printf("After merge sorting elements are: ");
    for(i=0;i<n;i++){
         printf("%d ",merge[i]);
    }
 printf("nnThe time complexity is : %f", (bottom-top)/CLK_TCK);
 getch();
}

void partition(int arr[],int low,int high){

    int mid;

    if(low<high){
         mid=(low+high)/2;
         partition(arr,low,mid);
         partition(arr,mid+1,high);
         mergeSort(arr,low,mid,high);
    }
}

void mergeSort(int arr[],int low,int mid,int high){

    int i,m,k,l,temp[MAX];

    l=low;
    i=low;
    m=mid+1;

    while((l<=mid)&&(m<=high)){

         if(arr[l]<=arr[m]){
             temp[i]=arr[l];
             l++;
         }
         else{
             temp[i]=arr[m];
             m++;
         }
         i++;
    }

    if(l>mid){
         for(k=m;k<=high;k++){
             temp[i]=arr[k];
             i++;
         }
    }
    else{
         for(k=l;k<=mid;k++){
             temp[i]=arr[k];
             i++;
         }
    }
   
    for(k=low;k<=high;k++){
         arr[k]=temp[k];
    }
}


Output

Publisher: Anand - 13:51

C program to sort elements using Bubble sort

 There is a C program to sort elements using Bubble sort is given below,bubble sort, sometimes referred to as sinking sort, is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order.C programming code  for bubble sort to sort numbers or arrange them in ascending order. You can easily modify it to print numbers in descending order.

In the bubble sort, as elements are sorted they gradually “bubble” (or rise) to their proper location in the array, like bubbles rising in a glass of soda.  The bubble sort repeatedly compares adjacent elements of an array.  The first and second elements are compared and swapped if out of order.  Then the second and third elements are compared and swapped if out of order.  This sorting process continues until the last two elements of the array are compared and swapped if out of order. 

C program to sort elements using Bubble sort

#include <stdio.h>
void bubble_sort();
int a[50], n;
main()
{
 int i;
 printf("nEnter size of an array: ");
 scanf("%d", &n);
 printf("nEnter elements of an array:n");
 for(i=0; i<n; i++)
 scanf("%d", &a[i]);
 bubble_sort();
 printf("nnAfter sorting:n");
 for(i=0; i<n; i++)
 printf("n%d", a[i]);
 getch();
}

void bubble_sort()
{

 int j, k, temp;
 for(j=0; j<n; j++)
 for(k=0; k<(n-1)-j; k++)
 if(a[k] > a[k+1])
 {
   temp = a[k];
   a[k] = a[k+1];
   a[k+1] = temp;
 }
}

Output

Enter size of an array:10
Enter elements of an array:23 43 56 34 12 34 55 65 76 21
After sorting:12 21 23 34 34 43 55 56 65 76

Publisher: Anand - 13:47

C program to implement Kruskal algorithm

Kruskal’s algorithm is a greedy algorithm that finds the minimum spanning tree of a graph. Graph should be weighted, connected, and undirected. Minimum spanning tree is a spanning tree with weight less than or equal to the weight of every other spanning tree. 

Example of C program to implement Kruskal algorithm.

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

int i,j,k,a,b,u,v,n,ne=1;
int min,mincost=0,cost[9][9],parent[9];
int find(int);
int uni(int,int);

void main()
{
 clrscr();
 printf("nntImplementation of Kruskal's algorithmnn");
 printf("nEnter the no. of verticesn");
 scanf("%d",&n);
 printf("nEnter the cost adjacency matrixn");
 for(i=1;i<=n;i++)
 {
  for(j=1;j<=n;j++)
  {
   scanf("%d",&cost[i][j]);
   if(cost[i][j]==0)
   cost[i][j]=999;
  }
 }
 printf("nThe edges of Minimum Cost Spanning Tree arenn");
 while(ne<n)
 {
  for(i=1,min=999;i<=n;i++)
  {
   for(j=1;j<=n;j++)
   {
    if(cost[i][j]<min)
    {
     min=cost[i][j];
     a=u=i;
     b=v=j;
    }
   }
  }
  u=find(u);
  v=find(v);
  if(uni(u,v))
  {
   printf("n%d edge (%d,%d) =%dn",ne++,a,b,min);
   mincost +=min;
  }
  cost[a][b]=cost[b][a]=999;
 }
 printf("ntMinimum cost = %dn",mincost);
 getch();
}

int find(int i)
{
 while(parent[i])
 i=parent[i];
 return i;
}

int uni(int i,int j)
{
 if(i!=j)
 {
 parent[j]=i;
 return 1;
 }
 return 0;
}

Publisher: Anand - 13:45

C program to implement Insertion Sort

Here a C  program  to implement  insertion  sort is given, insertion sorting technique is the elementary sorting technique. Insertion sort sorts one element at a time, It is just like manual sorting by humans. Insertion sort is better for small set of elements. Insertion sort is slower than heap sort, shell sort, quick sort,and merge sort.

Every repetition of insertion sort removes an element from the input data, inserting it into the correct position in the already-sorted list, until no input elements remain. The choice of which element to remove from the input is arbitrary, and can be made using almost any choice algorithm.

C  program  to implement  Insertion  Sort

#include <stdio.h>
void insertion_sort();
int a[50],n;

main()
{
 int i;
 printf("nEnter size of an array: ");
 scanf("%d", &n);
 printf("nEnter elements of an array:n");
 for(i=0; i<n; i++)
 scanf("%d", &a[i]);
 insertion_sort();
 printf("nnAfter sorting:n");
 for(i=0; i<n; i++)
 printf("n%d", a[i]);
 getch();
}

void insertion_sort()
{
 int j, k, temp;
 for(j=1; j<n; j++)
 {
  temp = a[j];
  k = j-1;
  while (k>=0 && a[k]>temp)
  {
   a[k+1] = a[k];
   k--;
  }
  a[k+1] = temp;
 } 
}

Output

Enter size of an array:10
Enter elements of an array:23 43 56 34 12 34 55 65 76 21
After sorting:12 21 23 34 34 43 55 56 65 76

Publisher: Anand - 13:42

C Program to Implement Heap Sort

 Heap sort algorithm starts by building a heap from the given elements,and then heap removes its largest element from the end of partially sorted array. After removing the largest element, it reconstructs the heap, removes the largest remaining item, and places it in the next open position from the end of the partially sorted array. This is repeated until there are no items left in the heap and the sorted array is full. Elementary implementations require two arrays - one to hold the heap and the other to hold the sorted elements. 

C Program to Implement Heap Sort 

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

int main()
{
      int TREE[10],N,i,j,K,p,c,temp;
      printf("nn Enter no of elements..");
      scanf("%d",&N);
      printf("nn Enter the nos..");
      for(i=1;i<=N;i++)
      scanf("%d",&TREE[i]);
      for(i=2;i<=N;i++)
      {
          K=i;
          do
          {
              if(TREE[K]>TREE[K/2])                          
              {
                  temp=TREE[K];
                  TREE[K]=TREE[K/2];
                  TREE[K/2]=temp;
              }
              p=K/2;
              K=p;
          }
          while(K!=0);
      }
      printf("nnn On inserting values are arranged as n");
      for(i=1;i<=N;i++)                                
      printf("%dt",TREE[i]);
      for(j=N;j>0;j--)
      {
          temp=TREE[1];
          TREE[1]=TREE[j];
          TREE[j]=temp;
          p=0;
          do
          {                                              
               c=2*p+2;
               if((TREE[c][/c]<TREE[c language="+1"][/c]) && c<j-1)
               c++;
               if(TREE[p]<TREE[c][/c] && c<j)
               {
                    temp=TREE[p];
                    TREE[p]=TREE[c][/c];
                    TREE[c][/c]=temp;
               }
           p=c;
           }
           while(c<(j+1));
      }
      printf("nnn The sorted nos are..");
      for(i=1;i<=N;i++)                         
      printf("%dt",TREE[i]);
      getch();
}

Output

Enter size of an array:10
Enter elements of an array:23 43 56 34 12 34 55 65 76 21
After sorting:12 21 23 34 34 43 55 56 65 76

Publisher: Anand - 13:40

C program to implement Selection Sort

Write a C program to sort given N elements using SELECTION sort method using functions :
a) To find maximum of elements
b) To swap two elements
Selection sort is comparison based sorting technique, It finds the minimum value in list and swaps that value to the first position and so on. Selection sort is inefficient on larger data. 

Example of C program to implement Selection Sort

 
#include <stdio.h>
#include <conio.h>
 
void main()
{
 int array[10];
 int i, j, N, temp;
 
 int findmax(int b[10], int k);      /* function declaration */
 void exchang(int b[10], int k);
 
 clrscr();
 
 printf("Enter the value of Nn");
 scanf("%d",&N);
 
 printf("Enter the elements one by onen");
 for(i=0; i<N ; i++)
 {
  scanf("%d",&array[i]);
 
 }
 
 printf("Input array elementsn");
 for(i=0; i<N ; i++)
 {
  printf("%dn",array[i]);
 }
 
 /* Selection sorting begins */
 exchang(array,N);
 
 printf("Sorted array is...n");
 for(i=0; i< N ; i++)
 {
  printf("%dn",array[i]);
 }
 
}   /* End of main*/
 
/* function to find the maximum value */
int findmax(int b[10], int k)
{
 int max=0,j;
 for(j = 1; j <= k; j++)
 {
  if ( b[j] > b[max])
  {
   max = j;
  }
 }
 return(max);
}
 
 
void exchang(int b[10],int k)
{
 int  temp, big, j;
 for ( j=k-1; j>=1; j--)
 {
 
  big = findmax(b,j);
  temp = b[big];
  b[big] = b[j];
  b[j] = temp;
 }
 return;
}

Publisher: Anand - 13:37

C program to implement Topology Sort

Topological sort is the ordering vertices of a directed, acyclic graph(DAG), so that if there is an arc from vertex i to vertex j, then i appears before j in the linear ordering.

C program to implement topology sort

#include<stdio.h>
#define MAX 200
int n,adj[MAX][MAX];
int front = -1,rear = -1,queue[MAX];
void main()
{
 int i,j = 0,k;
 int topsort[MAX],indeg[MAX];
 create_graph();
 printf(“The adjacency matrix is:n”);
 display();
 for(i=1;i<+n;i++)
 {
  indeg[i]=indegree(i);
  if(indeg[i]==0)
   insert_queue(i);
 }
 while(front<=rear)
 {
  k=delete_queue();
  topsort[j++]=k;
  for(i=1;i<=n;i++)
  {
   if(adj[k][i]==1)
   {
    adj[k][i]=0;
    indeg[i]=indeg[i]-1;
    if(indeg[i]==0)
     insert_queue(i);
   }
  }
 }
 printf("Nodes after topological sorting are:n");
 for(i=0;i<=n;i++)
  printf("%d",topsort[i]);
 printf("n");
}
create_graph()
{
 int i,max_edges,origin,destin;
 printf("n Enter number of vertices:");
 scamf("%d",&n);
 max_edges = n * (n - 1);
 for(i = 1;i <= max_edges;i++)
 {
  printf("n Enter edge %d (00 to quit):",i);
  scanf("%d%d",&origin,&destin);
  if((origin == 0) && (destin == 0))
  {
   printf("Invalid edge!!n");
   i–;
  }
  else
   adj[origin][destin] = 1;
 }return;
}
display()
{
 int i,j;
 for(i = 0;i <= n;i++)
 {
  for(j = 1;jrear)
  {
   printf(“Queue Underflow”);
   return;
  }
  else
  {
   del_item = queue[front];
   front = front + 1;
   return del_item;
  }
 }
 int indegree(int node)
 {
  int i,in_deg = 0;
  for(i = 1;i <= n;i++)
   if(adj[i][node] == 1)
    in_deg++;
  returnin_deg;
 }

Publisher: Anand - 13:33

C program for String Sorting

C Program to sort the string, using shell sort technique. Shell sort is the one of the oldest sorting technique, quite well for all types of arrays in c. The shell sort is a “diminishing increment sort”, better known as a “comb sort” to the unwashed programming masses. The algorithm makes multiple passes through the list, and each time sorts a number of equally sized sets using the insertion sort . The size of the set to be sorted gets larger with each pass through the list, until the set consists of the entire list. This sets the insertion sort up for an almost-best case run each iteration with a complexity that approaches O(n) .

C program for String Sorting

#include <string.h>
#include <stdio.h>
#include <stdlib.h>
void shell_sort(char *chars, int c) 
 { 
 register int i, j, space, k;
 char x, a[5];
 
 a[0]=9; a[1]=5; a[2]=3; a[3]=2; a[4]=1;
 
 for(k=0; k < 5; k++) {
  space = a[k];
  for(i=space; i < c; ++i) {
   x = chars[i];
   for(j=i-space; (x < chars[j]) && (j >= 0); j=j-space)
    chars[j+space] = chars[j];
   chars[j+space] = x;
  }
 }
}
 
int main() {
 char string[300];
 printf("Enter a string:");
 gets(string);
 shell_sort(string, strlen(string));
 printf("The sorted string is: %s.n", string);
 return 0;
}

Publisher: Anand - 13:29

C program to implement Doubly Linked List

Doubly-linked list is a more sophisticated form of linked list data structure. Each node of the list contain two references (or links) – one to the previous node and other to the next node. The previous link of the first node and the next link of the last node points to NULL. In comparison to singly-linked list, doubly-linked list requires handling of more pointers but less information is required as one can use the previous links to observe the preceding element. It has a dynamic size, which can be determined only at run time.

Example program to implement Doubly Linked List

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

struct node
{
	struct node *prev;
	int info;
	struct node *next;
}*start;

main()
{
	int choice,n,m,po,i;
	start=NULL;
	while(1)
	{
		printf("1.Create Listn");
		printf("2.Add at beginingn");
		printf("3.Add aftern");
		printf("4.Deleten");
		printf("5.Displayn");
		printf("6.Countn");
		printf("7.Reversen");
		printf("8.exitn");
		printf("Enter your choice : ");
		scanf("%d",&choice);
		switch(choice)
		{
		 case 1:
			printf("How many nodes you want : ");
			scanf("%d",&n);
			for(i=0;i<n;i++)
			{
				printf("Enter the element : ");
				scanf("%d",&m);
				create_list(m);
			}
			break;
		 case 2:
			printf("Enter the element : ");
			scanf("%d",&m);
			addatbeg(m);
			break;
		 case 3:
			printf("Enter the element : ");
			scanf("%d",&m);
			printf("Enter the position after which this element is inserted : ");
			scanf("%d",&po);
			addafter(m,po);
			break;
		 case 4:
			printf("Enter the element for deletion : ");
			scanf("%d",&m);
			del(m);
			break;
		 case 5:
			display();
			break;
		 case 6:
			count();
			break;
		 case 7:
			rev();
			break;
		 case 8:
			exit();
		 default:
			printf("Wrong choicen");
	}/*End of switch*/
   }/*End of while*/
}/*End of main()*/

create_list(int num)
{
	struct node *q,*tmp;
	tmp= malloc(sizeof(struct node));
	tmp->info=num;
	tmp->next=NULL;
	if(start==NULL)
	{
		tmp->prev=NULL;
		start->prev=tmp;
		start=tmp;
	}
	else
	{
		q=start;
		while(q->next!=NULL)
			q=q->next;
		q->next=tmp;
		tmp->prev=q;
	}
}/*End of create_list()*/

addatbeg(int num)
{
	struct node *tmp;
	tmp=malloc(sizeof(struct node));
	tmp->prev=NULL;
	tmp->info=num;
	tmp->next=start;
	start->prev=tmp;
	start=tmp;
}/*End of addatbeg()*/

addafter(int num,int c)
{
	struct node *tmp,*q;
	int i;
	q=start;
	for(i=0;i<c-1;i++)
	{
		q=q->next;
		if(q==NULL)
		{
			printf("There are less than %d elementsn",c);
			return;
		}
	}
	tmp=malloc(sizeof(struct node) );
	tmp->info=num;
	q->next->prev=tmp;
	tmp->next=q->next;
	tmp->prev=q;
	q->next=tmp;
}/*End of addafter() */

del(int num)
{
	struct node *tmp,*q;
	if(start->info==num)
	{
		tmp=start;
		start=start->next;  /*first element deleted*/
		start->prev = NULL;
		free(tmp);
		return;
	}
	q=start;
	while(q->next->next!=NULL)
	{
		if(q->next->info==num)     /*Element deleted in between*/
		{
			tmp=q->next;
			q->next=tmp->next;
			tmp->next->prev=q;
			free(tmp);
			return;
		}
		q=q->next;
	}
	if(q->next->info==num)    /*last element deleted*/
	{ 	tmp=q->next;
		free(tmp);
		q->next=NULL;
		return;
	}
	printf("Element %d not foundn",num);
}/*End of del()*/

display()
{
	struct node *q;
	if(start==NULL)
	{
		printf("List is emptyn");
		return;
	}
	q=start;
	printf("List is :n");
	while(q!=NULL)
	{
		printf("%d ", q->info);
		q=q->next;
	}
	printf("n");
}/*End of display() */

count()
{ 	struct node *q=start;
	int cnt=0;
	while(q!=NULL)
	{
		q=q->next;
		cnt++;
	}
	printf("Number of elements are %dn",cnt);
}/*End of count()*/

rev()
{
	struct node *p1,*p2;
	p1=start;
	p2=p1->next;
	p1->next=NULL;
	p1->prev=p2;
	while(p2!=NULL)
	{
		p2->prev=p2->next;
		p2->next=p1;
		p1=p2;
		p2=p2->prev; /*next of p2 changed to prev */
	}
	start=p1;
}/*End of rev()*/

Publisher: Anand - 13:26