C Codes: 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();
}

Saturday 14 September 2013