Friday 26 December 2014

recursion

Base conversion program from decimal


#include<stdio.h>
void convert(int dec,int base)
{
if(dec<base)
{
printf(" %d",dec);
return;
}
int n=dec%base;
convert(dec/base,base);
printf(" %d",n);
}
void main()
{
int dec,base;
printf("Enter the decimal number : ");
scanf("%d",&dec);
        printf("Enter the base : ");
        scanf("%d",&base);
        convert(dec,base);
}

         Printing Digits of a Number

function display prints digit in actual order while the function revdisplay prints the digit in reverse order
#include<stdio.h>
void display(int n)
{
if(n<10)
{
printf(" %d",n);
return;
}
int dig=n%10;
display(n/10);
    printf(" %d",dig);
}
void revdisplay(int n)
{
if(n==0)
{
return;
}
int dig=n%10;
    printf(" %d",dig);
revdisplay(n/10);
}
void main()
{
int num;
printf("Enter the number : ");
scanf("%d",&num);
printf("\nDigits of the number in actual order is : ");
display(num);
printf("\nDigits of the number in reverse order is : ");
revdisplay(num);
}

Posted by at No comments:

data structure

Evaluation of Postfix Expression

Algorithm to find the Value of an arithmetic expression P Written in Postfix
[1] Add a right parenthesis ‘)” at the end of P. [This act as delimiter]
[2] Scan P from left to right and repeat Steps 3 and 4 for each element of P until the delimiter “)” is encountered 
[3] If an operand is encountered, put it on STACK
[4] If an operator     is encountered, then
  (a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element
  (b) Evaluate B    A
  (c ) Place the result of (b) on STACK
[5] Set Value equal to the top element of STACK
[6] Exit 
example

Evaluation of Prefix Expression

Algorithm to find the Value of an arithmetic expression P Written in Prefix
[1] Scan P from right to left and repeat Steps 2 and 3 for each element of P 
[2] If an operand is encountered, put it on STACK
[3] If an operator  is encountered, then
  (a) Remove the two top elements of STACK, where A is the top element and B is the next-to-top element
  (b) Evaluate A OP B
  (c ) Place the result of (b) on STACK
[4] Set Value equal to the top element of STACK
[5] Exit 

                 Infix to Postfix

Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent postfix notation
[1] Push “(“ onto STACK and “)” to the end of Q
      [2] Scan Q from Left to Right and Repeat Steps 3 to 6         for each element of Q until the STACK is empty
[3] If an operand is encountered, add it to P
[4] If a left parenthesis is encountered, push it onto STACK
[5] If an operator     is encountered, then:
  (a) Repeatedly pop from STACK and to P each operator (on the top of STACK) which has same precedence as or higher precedence than    .
  (b)  Add     to STACK
[6] If  a right parenthesis is encountered, then
  (a) Repeatedly pop from the STACK and add to P each operator (on top of STACK) until a left parenthesis is encountered.
  (b)  Remove the left parenthesis. [Do not add it to P]
     [7] Exit 


                           Infix to Prefix 

Q is an arithmetic expression written in infix notation. This algorithm finds the equivalent prefix notation
[1] Push “)“ onto STACK and “(” to the begin of Q
      [2] Scan Q from right to left and Repeat Steps 3 to 6         for each element of Q until the STACK is empty
[3] If an operand is encountered, add it to P
[4] If a right parenthesis is encountered, push it onto STACK
[5] If an operator     is encountered, then:
  (a) Repeatedly pop from STACK and to P each operator (on the top of STACK) which has same precedence as or higher precedence than    .
  (b)  Add     to STACK
[6] If  a left parenthesis is encountered, then
  (a) Repeatedly pop from the STACK and add to P each operator (on top of STACK) until a right parenthesis is encountered.
  (b)  Remove the right parenthesis. [Do not add it to P]
     [7] now reverse the expression P we get the prefix expression

Read more »
Posted by at No comments:

Tuesday 23 December 2014

data structure programs

Linked list implementation and operations

Linked list operation


#include<stdio.h>

#include<string.h>

#include<stdlib.h>
typedef struct student
{
char name[20];
int roll;
struct student *link;
}student;
student *insbeg(student *head,char *name,int roll)
{
student *temp;
temp=(student *)malloc(sizeof(struct student));
temp->roll=roll;
temp->link=NULL;
strcpy(temp->name,name);
if(head==NULL)
{
head=temp;
   return head;
}
temp->link=head;
head=temp;
return head;
}
student *insatend(student *head,char *name,int roll)
{
student *temp,*p;
temp=(student *)malloc(sizeof(struct student));
temp->roll=roll;
temp->link=NULL;
strcpy(temp->name,name);
if(head==NULL)
{
head=temp;
   return head;
}
p=head;
while(p->link!=NULL)
p=p->link;
p->link=temp;
return head;
}
void search(student *head,char *name,int roll)
{
student *p=head;
int pos=1;
while(p)
{
  if(p->roll==roll && !strcmp(p->name,name))
  {
        printf("\nItemp found with Name %s  \tRoll %d ",p->name,p->roll);
        return ;
  }
  p=p->link;
  pos++;
    }
printf("\nItemp not found");
}
student *insempty(student *head,char *name,int roll)
{
student *temp;
temp=(student *)malloc(sizeof(struct student));
temp->roll=roll;
temp->link=NULL;
strcpy(temp->name,name);
if(head==NULL)
{
head=temp;
   return head;
}
printf("\nlist already contains some data");
return head;
}
void display(student *head)
{
student *p=head;
while(p!=NULL)
{
printf("\nName : %s \tRoll : %d ",p->name,p->roll);
p=p->link;
}
}
student *insertafter(student *head,char *name,int roll,char *nname,int nroll)
{ 
    student *temp,*p=head;
while(p)
{
  if(p->roll==roll && !strcmp(p->name,name))
  {
        printf("\nItemp found with Name %s  \tRoll %d ",p->name,p->roll);
        temp=(student *)malloc(sizeof(struct student));
        temp->roll=nroll;
        temp->link=NULL;
        strcpy(temp->name,nname);
        temp->link=p->link;
        p->link=temp;
        return head;
  }
  p=p->link;
    }
printf("\nItemp not found");
return head;
}
student *insertbefore(student *head,char *name,int roll,char *nname,int nroll)
{ 
    student *temp,*p=head,*q=head;
temp=(student *)malloc(sizeof(struct student));
temp->roll=nroll;
temp->link=NULL;
temp->link=NULL;
strcpy(temp->name,nname);
    if(p->roll==roll && !strcmp(p->name,name))
    {
    printf("\nItemp found with Name %s  \tRoll %d ",p->name,p->roll);
    temp->link=p;
   head=temp;
   return head;
}
while(p)
{
  if(p->roll==roll && !strcmp(p->name,name))
  {
       
        temp->link=p;
        q->link=temp;
        return head;
  }
  q=p;
  p=p->link;
    }
printf("\nItemp not found");
free(temp);
return head;
}
struct student *deletfirst(student *head)
{
student *temp=head;head=head->link;
free(temp);
return head;
}
student *deletbefore(student *head,char *name,int roll)
{
student *p=head,*q=head;
    if(p->roll==roll && !strcmp(p->name,name))
    {
    printf("\nItem is the first node so can't delete ");
   return head;
}
p=head->link;
if(p->roll==roll && !strcmp(p->name,name))
    {
    free(head);
    head=p;
    return head;
}
while(p)
{
  if(p->link->roll==roll && !strcmp(p->link->name,name))
  {
        
        q->link=p->link;
        free(p);
        return head;
  }
  q=p;
  p=p->link;
    }
printf("\nItemp not found");
return head;
}
student *deletafter(student *head,char *name,int roll)
{
student *p=head,*q;
while(p->link)
{
  if(p->roll==roll && !strcmp(p->name,name))
  {
      q=p->link;
        p->link=p->link->link;
        free(q);
        return head;
  }
  p=p->link;
    }
    if(p->roll==roll && !strcmp(p->name,name))
    {
    printf("\nthis is the last item so deletion can't be performed of a node after this");
    return head;
    }
printf("\nItemp not found");
return head;
}
student *deletkey(student *head,char *name,int roll)
{
student *p=head,*q;
    if(p->roll==roll && !strcmp(p->name,name))
    {
    head=p->link;
    free(p);
    return head;
    }
while(p)
{
  if(p->roll==roll && !strcmp(p->name,name))
  {
      q->link=p->link;
        free(p);
        return head;
  }
  q=p;
  p=p->link;
    }
printf("\nItemp not found");
return head;
}
void main()
{
int roll,ch,nroll;
char name[20],nname[20];
student *head=NULL,*p=head;
printf("\n1.insertion at begining\t2.insertion at end\n3.insertion in empty\t4.insertion in between\n5.display\t\t6.search item\t7.insert after item\t8.insert before item\t9.delet first node\t10.delet before\t11.delet after\t12.delet key\t13.exit");
while(1)
{
printf("\nEnter your choice : ");
        scanf("%d",&ch);
switch(ch)
{
   case 1: printf("Enter Name :");
            fflush(stdin);
       gets(name);
       printf("Enter Roll :");
       scanf("%d",&roll);
       head=insbeg(head,name,roll);
       break;
   case 2: printf("Enter Name :");
            fflush(stdin);
       gets(name);
       printf("Enter Roll :");
       scanf("%d",&roll);
       head=insatend(head,name,roll);
       break;
case 3: printf("Enter Name :");
            fflush(stdin);
       gets(name);
       printf("Enter Roll :");
       scanf("%d",&roll);
       head=insempty(head,name,roll);
       break;
case 5: printf("\nContent of list ");
       display(head);
       break;
   case 6: printf("Enter Name :");
            fflush(stdin);
       gets(name);
       printf("Enter Roll :");
       scanf("%d",&roll);
       search(head,name,roll);
       break;
case 7: printf("After whom \nEnter Name :");
            fflush(stdin);
       gets(name);
       printf("Enter Roll :");
       scanf("%d",&roll);
       printf("To who\tEnter Name :");
       fflush(stdin);
       gets(nname);
       printf("Enter Roll :");
       scanf("%d",&nroll);
       head=insertafter(head,name,roll,nname,nroll);
       break;
case 8: printf("Before whom \nEnter Name :");
            fflush(stdin);
       gets(name);
       printf("Enter Roll :");
       scanf("%d",&roll);
       printf("To who\tEnter Name :");
       fflush(stdin);
       gets(nname);
       printf("Enter Roll :");
       scanf("%d",&nroll);
       head=insertbefore(head,name,roll,nname,nroll);
       break;
case 9 :head=deletfirst(head);
       break;
case 10:printf("\nbefore whom");
       printf("\nEnter Name :");
            fflush(stdin);
       gets(name);
       printf("Enter Roll :");
       scanf("%d",&roll);
       head=deletbefore(head,name,roll);
       break;
case 11:printf("\nAfter whom");
       printf("\nEnter Name :");
            fflush(stdin);
       gets(name);
       printf("Enter Roll :");
       scanf("%d",&roll);
       head=deletafter(head,name,roll);
       break;
case 12:printf("\nTo whom");
       printf("\nEnter Name :");
           fflush(stdin);
       gets(name);
       printf("Enter Roll :");
       scanf("%d",&roll);
       head=deletkey(head,name,roll);
       break;
case 13: exit(1);
}
}
while(head)
{
p=head->link;
free(head);
head=p;
}
}

Read more »
Posted by at No comments:

Sunday 21 December 2014

programs


                                          Fibonacci series


        In mathematics, the Fibonacci numbers or Fibonacci sequence are the numbers in the                     following sequence:
       1 , 1 , 2 , 3 , 5 , 13 , 18 ,21 , 34 ,55 , 89 , .....
      or (oftern in modern usage)
0  1 , 1 , 2 , 3 , 5 , 13 , 18 ,21 , 34 ,55 , 89 , ....
.in mathematical terms any term of fibonacci series is given by
a(n) = a(n-1) + a(n-2)
  • Non recursive c program to print fibonacci series
#include<stdio.h>
void fib(int n)
{
int a=1,b=1,s,i;
if(n==1)
{
printf(" %d ",a);
return;
}
if(n==2)
    {
    printf(" %d %d ",a,b);
    return;
    }
    printf(" %ld %d ",a,b);
for(i=2;i<n;i++)
{
s=a+b;
a=b;
b=s;
printf("%d ",s);
    }
}
main()
{
int num;
printf("Enter the number of terms : ");
scanf("%d",&num);
fib(num);
}
recursive c program to print fibonacci series
#include<stdio.h>
int fib(int n)
{
if(n==0)
return 0;
if(n==1)
return 1;
return (fib(n-1)+fib(n-2));
}
main()
{
int i,num;
printf("Enter the number of terms : ");
scanf("%d",&num);
for(i=0;i<num;i++)
{
                       printf(" %d",fib(i));
             }
  }

Program for finding factorial of a large number


logic:- store the result in array with each element of array as a single digit
so we first multiply each element with num and then for each element we store them as the rightmost digit remains at it's location while the remaining part is added to the next element and the last element is again stored as single digit and the remaining is stored on next till remaining part becomes 0

#include<stdio.h>
void factorial(int num)
{
int temp,i,k=0,a[200]={0};
a[0]=num--;
while(num)
{
for(i=0;i<=k;i++)
a[i]*=num;
for(i=0;i<=k;i++)
{
temp=a[i]/10;
a[i]=a[i]%10;
a[i+1]=temp+a[i+1];
if(i==k)
{
temp=a[k+1];
while(temp>0)
{
k++;
a[k]=temp%10;
temp=temp/10;
}
i=k;
}
}
num--;
}
for(i=k;i>=0;i--)
printf("%d",a[i]);
}

main()
{
int num;
    printf("Enter the number : ");
    scanf("%d",&num);
    factorial(num);
}

Read more »
Posted by at 1 comment:
Subscribe to: Posts (Atom)