C Codes

Saturday, 14 September 2013

sort array with 0 1 and 2

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

typedef struct node node;

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

node *head=NULL;

void sort_zero_one_two(node *head)
{

}
main()
{
FILE *f=fopen("hinput.txt","r");
char c[5];

node *ptr,*temp,*given;
int count,i=0,flag=1;

while(fscanf(f,"%s",c)!=EOF)
{
ptr=(node*)malloc(sizeof(node));
ptr->info=atoi(c);

if(head==NULL)
{
head=ptr;
ptr->next=NULL;
temp=head;
given=head;
i+=1;
}
else
{
temp->next=ptr;
ptr->next=NULL;
temp=temp->next;

if(i!=count && flag)
{
given=given->next;
}
else
flag=0;
i+=1;
}
}

node *ptr0=NULL,*ptr1=NULL,*ptr2=NULL;
node *head1=NULL,*head2=NULL;
temp=head;
while(temp!=NULL)
{
if(temp->info==0)
{
if(ptr0==NULL)
{
head=temp;
ptr0=temp;
}
else
{ ptr0->next=temp;
ptr0=ptr0->next;
}
temp=temp->next;
ptr0->next=NULL;

}
else if(temp->info==1)
{
if(ptr1==NULL)
{
head1=temp;
ptr1=temp;
}
else
{ ptr1->next=temp;
ptr1=ptr1->next;
}
temp=temp->next;
ptr1->next=NULL;

}
else
{
if(ptr2==NULL)
{
head2=temp;
ptr2=temp;
}
else
{ ptr2->next=temp;
ptr2=ptr2->next;
}
temp=temp->next;
ptr2->next=NULL;

}
}
ptr0->next=head1;
ptr1->next=head2;
temp=head;
while(temp!=NULL)
{
printf("\n%d\n",temp->info);
temp=temp->next;
}

getch();
}

tree traversal inorder postorder preorder

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

typedef struct node node;

struct node
{
int info;
node *left;
node *right;
};

node *root=NULL;

void inorder(node *n)
{
if(n->left!=NULL) inorder(n->left);
printf("%d",n->info);
if(n->right!=NULL) inorder(n->right);
}

void postorder(node *n)
{
if(n->left!=NULL) inorder(n->left);
if(n->right!=NULL) inorder(n->right);
printf("%d",n->info);

}
void preorder(node *n)
{
printf("%d",n->info);
if(n->left!=NULL) inorder(n->left);
if(n->right!=NULL) inorder(n->right);
}
main()
{
FILE *f=fopen("hinput.txt","r");
char c[5];
node *ptr;
while(fscanf(f,"%s",c)!=EOF)
{
ptr=(node*)malloc(sizeof(node));
ptr->info=atoi(c);
if(root==NULL)
{
root=ptr;
root->left=NULL;
root->right=NULL;
}
else
{
node *temp=root;
while(1)
{
if(temp->info>=ptr->info)
{
if(temp->left==NULL)
{
temp->left=ptr;
ptr->left=NULL;
ptr->right=NULL;
break;
}
else temp=temp->left;
}
else
{
if(temp->right==NULL)
{
temp->right=ptr;
ptr->left=NULL;
ptr->right=NULL;
break;
}
else temp=temp->right;
}
}
}
}

printf("Preorder Traversal :"); preorder(root);

printf("\nInorder Traversal :"); inorder(root);

printf("\npostorder Traversal :"); postorder(root);

fclose(f);
getch();
}

subset sum problem

#include<stdio.h>

int memo[6][10];

int subset_sum(int *a,int sum,int n)
{
if(sum==0)
{
return 1;
}
if(n==0 && sum!=0)
{
return 0;
}
if(a[n-1]>sum)
return subset_sum(a,sum,n-1);

if(memo[n][sum]!=0) return memo[n][sum];
else
return memo[n][sum]= subset_sum(a,sum-a[n-1],n-1) || subset_sum(a,sum,n-1);
}
main()
{
int a[]={3,34,4,12,5,2,5,6};
int sum=35;
int i=0;
int j=0;
for(;i<6;i++)
{
for(;j<20;j++)
{
memo[i][j]=0;
}
}
printf("%d\n\n",subset_sum(a,sum,6));
getch();
}

subset sum display

#include<stdio.h>

int memo[6][10];

void display(int *sub,int n)
{
int i=0;
while(i<n)
{
printf("%d\n",sub[i]);
i++;
}
printf("\n end\n");
}

void subset_sum(int *a,int *sub,int sum,int n)
{
static int i=0;
if(sum==0)
{
display(sub,i);
return ;
}
if(n==0 && sum!=0)
{
return ;
}
if(a[n-1]>sum)
subset_sum(a,sub,sum,n-1);
sub[i]=a[n-1];
++i;
subset_sum(a,sub,sum-a[n-1],n-1);
i--;
subset_sum(a,sub,sum,n-1);
}
main()
{
int a[]={3,34,4,12,5,2,5,6};
int sub[10];
int sum=6;
int i=0;
int j=0;
for(;i<6;i++)
{
for(;j<20;j++)
{
memo[i][j]=0;
}
}
subset_sum(a,sub,sum,8);
getch();
}

reverse k nodes in linked list

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

typedef struct node node;

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

node *head=NULL;

node *reversekblock(node *root,int k,node **nexttemp,node **temphead)
{
if(root==NULL)
return NULL;
if(k<=0)
{
*nexttemp=root;
return NULL;
}
node *ptr=reversekblock(root,k-1,nexttemp,temphead);
if(ptr){ ptr->next=root;}
if(k==1){ *temphead=root;}
if(root==head){ root->next=(*nexttemp); head=*temphead;}
return root;
}

main()
{
FILE *f=fopen("hinput.txt","r");
char c[5];

node *ptr,*temp,*given;
int count,i=0,flag=1;

while(fscanf(f,"%s",c)!=EOF)
{
ptr=(node*)malloc(sizeof(node));
ptr->info=atoi(c);

if(head==NULL)
{
head=ptr;
ptr->next=NULL;
temp=head;
given=head;
i+=1;
}
else
{
temp->next=ptr;
ptr->next=NULL;
temp=temp->next;

if(i!=count && flag)
{
given=given->next;
}
else
flag=0;
i+=1;
}
}

node *tempn=reversekblock(head,3,NULL,NULL);
temp=head;
while(temp!=NULL)
{
printf("\n%d\n",temp->info);
temp=temp->next;
}
getch();
}

detect two interleaved strings

#include<stdio.h>
#include<conio.h>
main()
{
FILE *f=fopen("slinput.txt","r");
char a[20],b[20],c[40];

fscanf(f,"%s",a);
fscanf(f,"%s",b);
fscanf(f,"%s",c);

printf("%s %s %s\n",a,b,c);

int la=0,lb=0;

while(a[la]!='\0')la++;
while(b[lb]!='\0')lb++;

//system("pause");
int ai=0,bi=0,ci=0,flag=1;
for(;ci<la+lb-1;)
{
if(c[ci]==a[ai] && ai<la)
{ printf("a");
ai++;
ci++;
}
else if(c[ci]==b[bi] && bi<lb)
{ printf("b");
bi++;
ci++;
}
else
flag=0;
}
if(flag)
printf("Interleaved");
else
printf("Not Interleaved");
getch();
}

reverse doubly linked list

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

typedef struct node node;

struct node
{
int info;
node *pre;
node *next;
};

node *head=NULL;

node *reverse(node *ptr)
{

if(ptr->next->next==NULL)
{
head=ptr->next;
ptr->next->next=ptr;
}
else
{
reverse(ptr->next);
ptr->next->next=ptr;
}
return ptr;
}

main()
{
FILE *f=fopen("hinput.txt","r");
char c[5];
node *ptr,*temp;
while(fscanf(f,"%s",c)!=EOF)
{
ptr=(node*)malloc(sizeof(node));
ptr->info=atoi(c);

if(head==NULL)
{
head=ptr;
ptr->pre=NULL;
ptr->next=NULL;
temp=head;
}
else
{
ptr->pre=temp;
ptr->next=NULL;
temp->next=ptr;
temp=temp->next;
}
}
temp=head;
while(temp!=NULL)
{
printf("%d\n",temp->info);
temp=temp->next;
}

temp=reverse(head);
temp->next=NULL;
temp=head;
while(temp!=NULL)
{
printf("%d\n",temp->info);
temp=temp->next;
}

getch();
}

Sunday, 23 June 2013

Merge Sort C Code

Merge Sort

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

int c[10],k;

void merge(int *a,int u,int l,int n)
{int i;
k=u;
int st=u;
while(u<l && l<=n)
{
if(a[u]<=a[l])
{
c[k]=a[u];
u++;
k++;
}
else
{
c[k]=a[l];
k++;
l++;
}
}
while(u<l)
{
c[k]=a[u];
u++;
k++;
}
while(l<=n)
{
c[k]=a[l];
k++;
l++;
}
i=st;
while(i<=n)
{
a[i]=c[i];
i++;
}
}

void mergesort(int *a,int u,int l)
{
if(u<l)
{
int i=(u+l)/2;

mergesort(a,u,i-1);
mergesort(a,i,l);
merge(a,u,i+1,l);
}
}

int main()
{
int a[50];

FILE *f=fopen("hinput.txt","r");
char c[5];
int i=0;
while(fscanf(f,"%s",c)!=EOF)
a[i++]=atoi(c);
int n=i-1;
for(;i>=0;i--)
printf("a[%d]=%d\n",i,a[i]);

mergesort(a,0,n);

for(i=0;i<=n;i++)
printf("c[%d]=%d\n",i,c[i]);

fclose(f);
getch();
return 0;
}

Quick Sort C Code

Quick Sort

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

void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}

int par(int *a,int p,int r)
{
int i=p-1,j=p,pivot;
pivot=r;

while(j<pivot)
{
if(a[j]<=a[pivot])
{
swap(&a[j],&a[i+1]);
i++;
j++;
}
else
{
j++;
}
}
swap(&a[i+1],&a[pivot]);

return i+1;
}

void quicksort(int *a,int p,int r)
{
int q;
if(p<r)
{
q=par(a,p,r);
quicksort(a,p,q-1);
quicksort(a,q+1,r);
}
}

main()
{
FILE *f=fopen("hinput.txt","r");
char c[10];
int a[10],i=0;

while(fscanf(f,"%s",c)!=EOF)
{
a[i++]=atoi(c);
}
int n=i-1;

for(i-=1;i>=0;i--)
printf("a[%d]=%d\n",n-i,a[n-i]);
quicksort(a,0,n);
printf("\n#######\n Quick Sort\n#########\n");
for(i=0;i<=n;i++)
printf("a[%d]=%d\n",i,a[i]);

fclose(f);
getch();
}

Heap Sort

Heap Sort

#include<stdio.h>
#include<conio.h>
#define MAX 50
int n;
void swap(int *a,int *b)
{
int temp;
temp=*a;
*a=*b;
*b=temp;
}

void max_heapify(int *a,int x,int n)
{
int largest=x;
if(2*x<=n)
if(a[x]<a[2*x])
largest=2*x;
if((2*x+1)<=n)
if(a[largest]<a[2*x+1])
largest=2*x+1;
if(x!=largest)
{
swap(&a[x],&a[largest]);
max_heapify(a,largest,n);
}
}

void build(int *a,int n)
{
int i;
for(i=n/2;i>=0;i--)
max_heapify(a,i,n);
}

void heap_sort(int *a,int n)
{
int i;

build(a,n);
for(i=n;i>=2;i--)
{
swap(&a[n],&a[0]);
n--;
max_heapify(a,0,n);
}
}

main()
{
int a[MAX];
FILE *f=fopen("hinput.txt","r");

char c[5];
int i=0;
printf("Input\n");
while(fscanf(f,"%s",c)!=EOF)
{
a[i++]=atoi(c);
}
n=i-1;

for(i-=1;i>=0;i--)
printf("a[%d]=%d\n",n-i,a[n-i]);
heap_sort(a,n);
printf("\n#######\n Heap Sort\n#########\n");
for(i=0;i<=n;i++)
printf("a[%d]=%d\n",i,a[i]);

fclose(f);
getch();
}