Quick sort

#include<stdio.h>

#include<conio.h>

void main()

{

 int a[20],n,i; void quick(int a[],int lb,int ub);

 clrscr();

 printf("\n Enter size of array: ");

 scanf("%d",&n);

 printf("\n Enter the elements: ");

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

  scanf("%d",&a[i]);

 quick(a,0,n-1);

 printf("\n Elements after sorting:");

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

  printf("%d\t",a[i]);

 getch();

}

void quick(int a[],int lb,int ub)

{

 int i,j,temp,pivot;

 if(lb<ub)

 {

  i=lb+1;

  j=ub;

  pivot=a[lb];

  while(1)

  {

   while((a[i]<pivot)&&(i<=ub))

    i++;

   while((a[j]>pivot)&&(j>lb))

    j--;

   if(i<j)

   {

    temp=a[i];

    a[i]=a[j];

    a[j]=temp;

    i++;j--;

   }

   else

    break;

  }

  a[lb]=a[j];

  a[j]=pivot;

  quick(a,lb,j-1);

  quick(a,j+1,ub);

 }

}

Merge sort

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

void main()

{

 int a[20],n,i; void mergesort(int a[],int n);

 clrscr();

 printf("\n Enter size of array:");

 scanf("%d",&n);

 printf("\n Enter the elements:");

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

  scanf("%d",&a[i]);

  mergesort(a,n);

 printf("\n Elements After Sorting:");

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

  printf("%d\t",a[i]);

 getch();

}

int leftend,tmppos,numelem,i;

void msort(int a[],int tmparray[],int left,int right);

void merge(int a[],int tmparray[],int lpos,int rpos,int rightend);

void mergesort(int a[],int n)

{

 int *tmparray;

 tmparray=malloc(n * sizeof(int));

 if(tmparray!=NULL)

 {

  msort(a,tmparray,0,n-1);

  free(tmparray);

 }

}

void msort(int a[20],int tmparray[],int left,int right)

{

 int center;

 if(left<right)

 {

  center=(left+right)/2;

  msort(a,tmparray,left,center);

  msort(a,tmparray,center+1,right);

  merge(a,tmparray,left,center+1,right);

 }

}

void merge(int a[20],int tmparray[],int lpos,int rpos,int rightend)

{

 leftend=rpos-1;

 tmppos=lpos;

 numelem=rightend-lpos+1;

 while(lpos<=leftend && rpos<=rightend)

 {

  if(a[lpos]<=a[rpos])

   tmparray[tmppos++]=a[lpos++];

  else

   tmparray[tmppos++]=a[rpos++];

 }

 while(lpos<=leftend)

  tmparray[tmppos++]=a[lpos++];

  while(rpos<=rightend)

   tmparray[tmppos++]=a[rpos++];

   for(i=0;i<numelem;i++,rightend--)

    a[rightend]=tmparray[rightend];

}

Counting number of lines in a file

#include<stdio.h>

#include<conio.h>

#include<process.h>

void main()

{

 FILE *fp;

 char x;

 int count=0;

 clrscr();

 fp=fopen("f:/ds/f1.txt","r");

 if(fp==NULL)

 {

 printf("Error!!!!");

 exit(0);

 }

 x=fgetc(fp);

 while(x!=EOF)

 {

 if(x=='\n')

 {

 ++count;

  }

 x=fgetc(fp);

 }

 printf("no of lines are : %d",count);

 fclose(fp);

 getch();

 }

Insertion sort

#include<stdio.h>

#include<conio.h>

int i;

void insert(int b[20],int m)

{

 int j,p,temp;

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

 {

  temp=b[p];

  for(j=p;j>0 && b[j-1]>temp;j--)

   b[j]=b[j-1];

  b[j]=temp;

 }

}

void main()

{

 int a[20],n;

 clrscr();

 printf("\n Enter size of array ");

 scanf("%d",&n);

 printf("\n Enter the elements:");

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

  scanf("%d",&a[i]);

 insert(a,n);

 printf("\n Elements after sorting :");

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

  printf("%d\t",a[i]);

 getch();

}

DOUBLY LINKED LIST

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

struct node

{

struct node *prev;

int data;

struct node *next;

};

void main()

{

struct node *head,*tp,*temp;

int ch,key,value;

clrscr();

head = NULL;

printf("\n1.Insert @ first\t 2.Insert @ last\t 3.Insert @ middle\n");

printf("4.Deletion\t 5.Display");

do

{

printf("\n\nEnter your choice:");

scanf("%d",&ch);

switch(ch)

{

case 1: {

            printf("\nenter a no to insert @ first:");

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

            scanf("%d",&value);

            temp->prev=NULL;

            temp->data=value;

            temp->next=NULL;

            if(head==NULL)

            head=temp;

            else

            {

            temp->next=head;

            head->prev=temp;

            head=temp;

            }}

            break;

case 2: {

            printf("\nenter a no to insert @ last:");

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

            scanf("%d",&value);

            temp->prev=NULL;

            temp->data=value;

            temp->next=NULL;

            if(head==NULL)

            head=temp;

            else

            {

             tp=head;

             while(tp->next!=NULL)

             {

             tp=tp->next;

             }

             tp->next=temp;

             temp->prev=tp;

            }}

            break;

case 3: {

            printf("\nEnter a no to find:");

            scanf("%d",&key);

            printf("\nenter a no to insert @ middle:");

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

            scanf("%d",&value);

            temp->prev=NULL;

            temp->data=value;

            temp->next=NULL;

            if(head==NULL)

            head=temp;

            else

            {

            tp=head;

            while(tp!=NULL && tp->data!=key)

            tp=tp->next;

            if(tp!=NULL)

            {

             temp->next=tp->next;

             temp->prev=tp;

             tp->next->prev=temp;

             tp->next=temp;

             }

             else

             printf("\nElement not found...");

             }}

             break;

case 4: {

            printf("\nEnter a no to delete:");

            scanf("%d",&key);

            if(head==NULL)

            printf("\nlist is empty");

            else

            {

            tp=head;

            while(tp!=NULL && tp->data!=key)

            {

            tp=tp->next;

            }

            if(tp!=NULL)

            {

            if(tp==head)

            {

            head=head->next;

            head->prev=NULL;

            free(tp);

            }

            else

            {

            if(tp->next!=NULL)

            {

            temp->prev->next=tp->next;

            temp->next->prev=tp->prev;

            free(tp);

            }

            else

            {

            tp->prev->next=NULL;

            free(tp);

            }

            }}

            else

            printf("\nelement not found");

            }          }break;

case 5: {

            if(head!=NULL)

            tp=head;

            while(tp!=NULL)

            {

            printf("%d\t",tp->data);

            tp=tp->next;

            }

            }break;

default:printf("\nenter correct choice");

            break;

}

}while(ch<=5);

getch();

}

CIRCULAR LINKED LIST

#include<stdio.h>

#include<conio.h>

#include<alloc.h>

struct node

{

int data;

struct node *next;

};

void main()

{

struct node *head,*temp,*tp,*tmp;

int value,ch,key;

clrscr();

head=NULL;

printf("1.Insert at first\n2.insert at last\n");

printf("3.insert in middle\n4.delete\n5.display\n");

do

{

printf("\nEnter choice:");

scanf("%d",&ch);

switch(ch)

{

case 1:

            tp=head;

            printf("\nEnter no:");

            scanf("%d",&value);

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

            temp->data=value;

            temp->next=NULL;

            if(head==NULL)

            {

            head=temp;

            head->next=head;

            }

            else

            {

            temp->next=head;

            head->next=temp;

            head=temp;

            }

            break;

case 2:

            printf("\nEnter no:");

            scanf("%d",&value);

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

            temp->data=value;

            temp->next=NULL;

            if(head==NULL)

            {

            head=temp;

            head->next=head;

            }

            else

            {

            tp=head;

            while(tp->next!=head)

            tp=tp->next;

            temp->next=head;

            tp->next=temp;

            }

            break;

case 3:

            printf("\nEnter no:");

            scanf("%d",&value);

            printf("\nEnter target:");

            scanf("%d",&key);

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

            temp->data=value;

            temp->next=NULL;

            if(head==NULL)

            {

            head=temp;

            head->next=head;

            }

            else

            {

            tp=head;

            while(tp->data!=key && tp!=NULL)

            tp=tp->next;

            if(tp!=NULL)

            {

            temp->next=tp->next;

            tp->next=temp;

            }

            else

            printf("\nTarget not found");

            }

            break;

case 4:

            printf("\nEnter target:");

            scanf("%d",&key);

            if(head==NULL)

            printf("\nList is empty");

            else

            {

            tp=head;

            while(tp->data!=key && tp!=NULL)

            {

            temp=tp;

            tp=tp->next;

            }

            if(tp!=NULL)

            {

            if(tp==head)

            {

            while(tp->next!=head)

            tp=tp->next;

            head=head->next;

            free(tp);

            tp->next=head;

            }

            else

            {

            temp->next=tp->next;

            free(tp);

            }

            }

            else

            printf("\nTarget not found");

            }

            break;

case 5:

            tp=head;

            while(tp->next!=head)

            {

            printf("%d\t",tp->data);

            tp=tp->next;

            }

            printf("%d",tp->data);

            break;

            }

            }while(ch<6);

getch();

}

IMPLEMENTATION OF PRIMS ALGORITHM

#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

void distance(int destination);

int n;

int load[100][100];

char mst[100];

int m[100];

int whoto[100];

void distance(int destination)

{

int i;

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

if((load[destination][i]!=0)&&(m[i]>load[destination][i]))

{

m[i]=load[destination][i];

whoto[i]=destination;

}}

void main()

{

int i,j,total,minspan;

clrscr();

printf("enter the number of nodes:");

scanf("%d",&n);

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

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

{

printf("enter the weight from %d to %d",i,j);

scanf("%d",&load[i][j]);

}

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

m[i]=10000;

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

mst[i]=0;

printf("adding node %c\n",0+'a');

mst[0]=1;

distance(0);

total=0;

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

{

int min=-1;

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

if(!mst[i])

if((min==-1)||(m[min]>m[i]))

min=i;

printf("adding edges %c---%c\n",whoto[min]+'a',min+'a');

mst[min]=1;

total+=m[min];

distance(min);

}

printf("total distance:%d\n",total);

getch();

}

OUTPUT:

          enter the number of nodes:3

enter the weight from 0 to 0 5

enter the weight from 0 to 1 4

enter the weight from 0 to 2 3

enter the weight from 1 to 0 3

enter the weight from 1 to 1 7

enter the weight from 1 to 2 4

enter the weight from 2 to 0 1

enter the weight from 2 to 1 2

enter the weight from 2 to 2 4

adding node a

adding edges a---c

adding edges c---b

total distance:5

IMPLEMENTATION OF KRUSKAL’S ALGORITHM      

#include<stdio.h>

#define INFINITY 999

typedef struct graph

{

int v1;

int v2;

int cost;

}graph;

graph c[20];

int min(int);

int find(int v2,int p[]);

void combine(int i,int j,int p[]);

void main()

{

int t[10][10],v1,v2,cost,low,i,k,j,n,m;

int p[20],count=0,sum=0;

clrscr();

printf("\nenter the no of vertices:");

scanf("%d",&n);

printf("\n enter the no of edges:");

scanf("%d",&m);

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

{

printf("\nthe cost of the edge from");

scanf("%d",&c[k].v1);

printf("\t\t to ");

scanf("%d",&c[k].v2);

printf(" and the cost is");

scanf("%d",&c[k].cost);

}

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

p[i]=i;

k=0;

while(count!=(n-1))

{

low=min(m);

if(low==-1)

break;

v1=c[low].v1;

v2=c[low].v2;

i=find(v1,p);

j=find(v2,p);

if(i!=j)

{

t[k][0]=v1;

t[k][1]=v2;

k++;

count++;

sum=sum+c[low].cost;

combine(i,j,p);

}

c[low].cost=INFINITY;

}

printf("\nminimum spanning tree is:");

if(count==(n-1))

{

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

printf("\t%d->%d",t[i][0],t[i][1]);

printf("\n\nthe cost of the spanning tree is %d",sum);

}

getch();

}

int min(int n)

{int i,s,min;

s=INFINITY;

min=-1;

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

if(c[i].cost<s)

{

s=c[i].cost;

min=i;

}

return min;

}

int find(int v2,int p[])

{while(p[v2]!=v2)

{

v2=p[v2];

}

return v2;

}

void combine(int i,int j,int p[])

{if(i<j)

p[j]=i;

else

p[i]=j;

}

OUTPUT:

enter the no of vertices:6

enter the no of edges:9

the cost of the edge from 1 to 2

 the cost is5

the cost of the edge from 2 to 3

 the cost is5

the cost of the edge from 1 to 4

  the cost is3

the cost of the edge from  2 to 4

the cost is2

the cost of the edge from 2 to 5

the cost is6

the cost of the edge from 4 to 5

the cost is1

the cost of the edge from 3 to 5

the cost is1

the cost of the edge from 5  to 6

the cost is2

the cost of the edge from 3  to 6

 the cost is4

minimum spanning tree is:       4->5    3->5    2->4    5->6    1->4

the cost of the spanning tree is 9