Tuesday, October 4, 2011

C program to evaluate factorials upto 100 (100!)


Well, this program can be extended to find values of factorial of numbers more than 100. It uses an array of size equal to maximum no. of digits of factorial value(100 in this case). (We can only find factorial of upto 13 with unsigned long, after that we are left with no choice, hence the program solves this problem)

#include<stdio.h>
int fact[160];
main()
{
    int n,carry,i,size;;
    carry=0;
    size=159;
    fact[0]=1;
    scanf("%d",&n);
    while(n>0)
    {
        i=0;
        do
        {
            fact[i]*=n;
            fact[i]+=carry;
            carry=fact[i]/10;
            fact[i]=fact[i]%10;
        }while(i++ != 158);

        n--;
    }

    for(i=159;i>=0;i--)
    {
        if(fact[i]==0)
        size--;
        else
        break;
    }
    for(i=size;i>=0;i--)
    printf("%d",fact[i]);
    printf("\n");


}

Sunday, October 2, 2011

Data Alignment and performance optimization: C source code, concept


/*Check out the following code. This code is an example of data alignment in C. Read out more at http://www.codeguru.com/forum/showthread.php?t=276622  */
#include<stdio.h>

struct stud1
{
    double fee;
    char branch_code;
    float marks;
    int b1;
    int b2;

};

struct stud2
{

    char branch_code;
    double fee;
    float marks;
    int b1;
    int b2;

};

struct stud3
{

    char branch_code;
    float marks;
    int b1;
    int b2;
    double fee;

};
main()
{
    printf("%d %d %d",sizeof(struct stud1),sizeof(struct stud2),sizeof(struct stud3));
}
//Compile it, and check the output. If you are surprised, have a look at http://www.codeguru.com/forum/showthread.php?t=276622

Thursday, September 29, 2011

Common Input-Output Mistakes and Concepts in C


1.       printf(“sanjay”+2);   //prints njay only.
2.       Always use fflush(stdin) after any scanf statement.
3.       Always use & operator in scanf statement.
4.       We cannot use %d for inputting values other than int in scanf(for eg. long, float).
5.       Global variables initialize to 0, local to some garbage value. Global ‘char’ also initializes to 0.
6.       int/int is int. float/int is float. Int/float is float. (‘/’ represents division operator).
7.       scanf(“%c%c”,&ch1,&ch2);    //keyboard input must be ‘AB’ and not ‘A B’.
scanf(“%c %c”,&ch1,&ch2);  //keyboard input must be ‘A B’.
scanf(“%c/%c”,&ch1,&ch2);  //keyboard input must be ‘A/B’.
8.       printf returns the no. of bytes printed by it.
9.       scanf returns the no. of variables passed to it.
10.   sprintf(str, “%d %d”,x,y); // where str is a string.
sprintf does not prints on screen like printf, but it stores the formatted output in str.
Similarly sscanf takes the formatted input from str rather than from the keyboard.

Wednesday, September 28, 2011

Transferring array between functions using pointers, getting the size of array without using strlen


#include<stdio.h>
#include<string.h>
#define elements_count (sizeof(arr)/sizeof(arr[0]))

int compute_size(int arr[])
{
    return elements_count;
}
main()
{
    int list[]={11,12,13,14,15,16};
    int x,size;
    size=compute_size(list);
    for(x=0;x<size;x++)
    printf("%d",list[x]);
}

Friday, September 23, 2011

Polynomial using Linked Lists: Insertion, printing, adding two polynomials


//Any issues will be discussed in comments. Program tested with gcc compiler.
//Polynomial using linked lists: insert new term, print polynomial, add two polynomials

#include<stdio.h>
typedef struct polyNode *polyPointer;
struct polyNode
{
    int coef;
    int expon;
    polyPointer link;
}polyNode;

void printPoly(polyPointer);
void insertTerm(int,int,polyPointer);
polyPointer addPoly(polyPointer,polyPointer);

main()
{
    polyPointer p1,p2,p3;
    p1=malloc(sizeof(polyNode));
    p1->link=NULL;

    p2=malloc(sizeof(polyNode));
    p2->link=NULL;

    insertTerm(2,2,p1);
    insertTerm(5,5,p1);
    insertTerm(7,4,p2);
    insertTerm(-3,0,p2);
    insertTerm(4,4,p2);
    p3=addPoly(p1,p2);
    printf("\n");
    printPoly(p3);
    printf("\n");
    printPoly(p2);
    printf("\n");
    printPoly(p1);
}

void insertTerm(int coef,int expon,polyPointer root)
{
    if(root->link)
    {
        while(root->link && root->link->expon>=expon)
        root=root->link;
    }

    if(root->expon==expon)
    {
        root->coef+=coef;
        return;
    }

    polyPointer temp;
    temp=malloc(sizeof(polyNode));
    temp->coef=coef;
    temp->expon=expon;

    temp->link=root->link;
    root->link=temp;
}

void printPoly(polyPointer root)
{
    printf("\n");
    while(root->link)
    {
        printf("(%dx^%d)+",root->link->coef,root->link->expon);
        root=root->link;
    }
}

polyPointer addPoly(polyPointer p1, polyPointer p2)
{
    polyPointer p3;
    p3=malloc(sizeof(struct polyNode));
    p3->link=NULL;

    while(p1->link && p2->link)
    {
        while(p2->link && (p1->link->expon >= p2->link->expon))
        {
            insertTerm(p2->link->coef,p2->link->expon,p3);
            p2=p2->link;
        }

        while(p2->link && p1->link && (p2->link->expon >= p1->link->expon))
        {
            insertTerm(p1->link->coef,p1->link->expon,p3);printf("1");
            p1=p1->link;
        }
    }

    while(p1->link)
    {
        insertTerm(p1->link->coef,p1->link->expon,p3);
        p1=p1->link;
    }

    while(p2->link)
    {
        insertTerm(p2->link->coef,p2->link->expon,p3);
        p2=p2->link;
    }

    return p3;
}

Linked List Complete C program with insertion, deletion, print, reversing of List


//Any Problems can be discussed in comments.
//operations: insertNode, deleteNode, printList, reverseList

#include<stdio.h>

typedef struct node *nodePointer;
struct node
{
    int data;
    struct node *link;
}node;
int length=0;

void insertNode(int,nodePointer);
void print(nodePointer);
void deleteNode(int,nodePointer);
nodePointer reverseList(nodePointer);

main()
{
    nodePointer root;
    root=malloc(sizeof(node));
    root->link=NULL;
    insertNode(34,root);
    insertNode(56,root);
    insertNode(45,root);
    print(root);
    printf("Length is %d\n",length);

    root=reverseList(root);
    print(root);
    printf("Length is %d\n",length);
    deleteNode(56,root);
    deleteNode(34,root);
    insertNode(53,root);
    print(root);
    printf("Length is %d\n",length);

}

void insertNode(int data,nodePointer root)
{
    int i;
    if(length>0)
    {
        while(root->link)
        root=root->link;
    }

    nodePointer temp;
    temp=malloc(sizeof(node));
    temp->data=data;
    root->link=temp;
    temp->link=NULL;
    length++;
}

void print(nodePointer root)
{
    printf("Root");
    while(root->link)
    {
        printf("->%d",root->link->data);
        root=root->link;
    }
    printf("\n");
}

void deleteNode(int data,nodePointer root)
{
    nodePointer temp;
    temp=root;
    while(root->link)
    {
        if(root->link->data==data)
        {
            temp=root->link->link;
            free(root->link);
            root->link=temp;
            length--;
            return;
        }
        else
        {
            temp=root;
            root=root->link;
        }
    }
}

nodePointer reverseList(nodePointer root)
{
    nodePointer middle,trail,temp;
    temp=root;

    middle=NULL;
    root=root->link;

    while(root)
    {
        trail=middle;
        middle=root;
        root=root->link;
        middle->link=trail;
    }
    temp->link=middle;

    return temp;
}

Thursday, August 4, 2011

Postfix Evaluation and Expression Solving

Infix Expression :

Any expression in the standard form like "2*3-4/5" is an Infix(Inorder) expression.

Postfix Expression :

The Postfix(Postorder) form of the above expression is "23*45/-".

Postfix Evaluation :

In normal algebra we use the infix notation like a+b*c. The corresponding postfix notation is abc*+. The algorithm for the conversion is as follows :

  • Scan the Postfix string from left to right.
  • Initialise an empty stack.
  • If the scannned character is an operand, add it to the stack. If the scanned character is an operator, there will be atleast two operands in the stack.
    • If the scanned character is an Operator, then we store the top most element of the stack(topStack) in a variable temp. Pop the stack. Now evaluate topStack(Operator)temp. Let the result of this operation be retVal. Pop the stack and Push retVal into the stack.
    Repeat this step till all the characters are scanned.
  • After all characters are scanned, we will have only one element in the stack. Return topStack.
Example :

Let us see how the above algorithm will be imlemented using an example.

Postfix String : 123*+4-

Initially the Stack is empty. Now, the first three characters scanned are 1,2 and 3, which are operands. Thus they will be pushed into the stack in that order.


Stack

Expression

Next character scanned is "*", which is an operator. Thus, we pop the top two elements from the stack and perform the "*" operation with the two operands. The second operand will be the first element that is popped.


Stack

Expression

The value of the expression(2*3) that has been evaluated(6) is pushed into the stack.


Stack

Expression

Next character scanned is "+", which is an operator. Thus, we pop the top two elements from the stack and perform the "+" operation with the two operands. The second operand will be the first element that is popped.


Stack

Expression

The value of the expression(1+6) that has been evaluated(7) is pushed into the stack.


Stack

Expression

Next character scanned is "4", which is added to the stack.


Stack

Expression

Next character scanned is "-", which is an operator. Thus, we pop the top two elements from the stack and perform the "-" operation with the two operands. The second operand will be the first element that is popped.


Stack

Expression

The value of the expression(7-4) that has been evaluated(3) is pushed into the stack.


Stack

Expression

Now, since all the characters are scanned, the remaining element in the stack (there will be only one element in the stack) will be returned.

End result :
  • Postfix String : 123*+4-
  • Result : 3

Monday, August 1, 2011

Create a file containing 26 alphabets(A to Z) in separate lines.

"
#include<stdio.h>
#include<conio.h>
#include<string.h>
void main()
{
 FILE *fp;
 int i;
 char *file="c:/sanjay.txt";
 fp=fopen(file,"w");
 if(!fp){
         printf("Issues with file creation, sorry !");
         }
 for(i=1;i<=26;i++)
 {
 
 fprintf(fp,"%c \n",(i+64));
}
fclose(fp);
 getch();
}
"

Sunday, July 31, 2011

Define a pointer to an integer; read a list of n numbers using dynamic memory allocation and find average of these numbers

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

void main()
{
 int *i,count=1,x=1,sum=0;
 //Enter 0 to terminate input
 i=(int *)malloc(sizeof(int));
 scanf("%d",i);
 sum+=*i;
 while(i[count-1]!=0)
 {
 i=(int *)realloc(i,sizeof(int));
 scanf("%d",&i[count]);
 sum+=i[count];
 count++;
}
count--;
printf("\nAverage is: %d",sum/count);
 getch();
}
 "

Concatenate two strings without using strcat: C source code

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

void main()
{
 char s1[30],s2[30],s3[30];
 char *x,*y;
 int i=0;
 scanf("%s %s",s1,s2);
 x=s1;
 //first method given in comments(this method uses the third string)
/* while(*x!='\0')
 {
  *(s3+i)=*x;
  x++;i++;
  }
  x=s2;
   while(*x!='\0')
 {
  *(s3+i)=*x;
  x++;i++;
  }
  *(s3+i)='\0';
  printf("%s",s3);
  */
  //second method(uses no external string)
 while(*x!='\0')
 {
  x++;
  }
  y=s2;
  while(*y!='\0')
  {
   *x=*y;
   x++;y++;
   }
   *x='\0';
   printf("%s",s1);
 getch();
}
"

Saturday, June 25, 2011

Given n Boolean variables x1,x2,...xn , we wish to print all possible combinations of truth values they can assume. For instance, if n=2, there are four possibilities: 'true,true','false,true','true,false' and 'false,false'. Write a C program to do this. Q#3,Page#17, 'Fundamentals of Data Structures in C (2nd Edition)' by 'Horowitz and Sahni'

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

void comb(char *,int,int);
char toggle(char);

void main()
{
 char list[4]={'t','t','t','t'};
 int i=0,n=3;
 comb(list,i-1,n);
 getch();
}

void comb(char *list,int i,int n)
{
 int j,k;
 if(i==n)
 {
  for(j=0;j<=n;j++)
  printf("%c",list[j]);
  printf("  ");
 }
 else
 {
  for(k=0;k<=1;k++)
  {
   comb(list,i+1,n);
   list[i+1]=toggle(list[i+1]);
  }
}
}

char toggle(char c)
{
 if(c=='t')
 return 'f';
 else
 return 't';
}