Getting started with C

this is a blinking christmas tree.

2014-01-21T18:09:00.000+05:30

#include<stdio.h>
#include <time.h>
void sleep(time_t delay)
{
time_t timer0,timer1;
time(&timer0);
do{
time(&timer1);
}while((timer1-timer0)<delay);
}
int main()
{

int i=5,j,k,s=0;

printf("your christmas tree is here\n");
for(k=0;k<5;k++)
printf(" ");
sleep(1);
printf("@@\n");
for(j=0;j<10;j++)
{
for(k=i;k<10;k++)
printf(" ");
i++;
if(i>10)
{
for(k=0;k<3;k++)
printf(" ");
}
sleep(1);
printf("*");
for(k=0;k<2*s;k++)
{if(2*s<10){
sleep(1);
printf("*");
}
}
if(2*s>=10)
{for(k=0;k<4;k++)
{sleep(1);
printf("*");}
}
sleep(1);
printf("*");
s++;

printf("\n");
}
return 0;
}

program that prints inorder traversal of tree and count the leaf nodes.

2014-01-21T18:06:00.002+05:30

#include<stdio.h>
struct x{
int data;
struct x *right;
struct x *left;
};
typedef struct x node;
node* createTree(node * ,int );
node* createNode(int x);
void inorder(node** );
int countLeaf(node** );
int main()
{
int i,x,j,n;
node *root=NULL;
printf("how many nodes you want to create\n");
scanf("%d",&n);
if(n>0)
{
printf("enter the data for nodes\n");
for(i=0;i<n;i++)
{
scanf("%d",&x);
root=createTree(root,x);
}
}
inorder(&root);
j=countLeaf(&root);
printf("\nthe leaf nodes are %d\n",j);
return 0;

}
node* createNode(int x)
{
node* a;
a=(node*)malloc(sizeof(node));
a->data=x;
a->right=NULL;
a->left=NULL;
return a;
}
node* createTree(node* root,int x)
{
if(root==NULL)
{
root=createNode(x);
return root;
}
else if(root->data<x)
root->right=createTree(root->right,x);
else
root->left=createTree(root->left,x);
return root;
}
void inorder(node **root)
{
if(*root==NULL)
return;
else{
inorder(&((*root)->left));
printf("%d->",(*root)->data);
inorder(&((*root)->right));
}
}
int countLeaf(node **root)
{
static int count=0;
if(*root==NULL)
return count;
else if((*root)->left==NULL && (*root)->right==NULL)
{
count++;
return count;
}
else{
countLeaf(&((*root)->left));
countLeaf(&((*root)->right));
}
}

conversion of an infix expression to a prefix expression using stack.

2013-11-28T02:05:00.002+05:30

THE CODE:
#include<stdio.h>
#include<ctype.h>
#define max 50
struct x{
char data[max];
int top;
};
typedef struct x stack;
void infix_prefix(char [],char []);
void infix_postfix(char [],char []);
void push(stack *,char );
char pop(stack *);
int precedence(char );
int main()
{
char infix[max],prefix[max];
printf("\nenter an infix expression\n");
gets(infix);
infix_prefix(infix,prefix);
printf("\n prefix:\n %s ",prefix);
return 0;
}
void infix_prefix(char infix[],char prefix[])
{
int i,j;
char a[max],temp;
for(j=strlen(infix)-1,i=0;j>=0;j--,i++)
a[i]=infix[j];
a[i]='\0';
for(i=0;a[i]!='\0';i++)
{
if(a[i]=='(')
a[i]=')';
else if(a[i]==')')
a[i]='(';
}
infix_postfix(a,prefix);
for(i=0,j=strlen(prefix)-1;i<j;i++,j--)
{
temp=prefix[j];
prefix[j]=prefix[i];
prefix[i]=temp;
}
}

void infix_postfix(char infix[],char postfix[])
{
int i,j;
stack s;
char x,token;
s.top=-1;
j=0;
for(i=0;infix[i]!='\0';i++)
{
token=infix[i];
if(isalnum(token)){
postfix[j]=token;
j++;
}
else if(token=='(')
push(&s,'(');
else if(token==')')
{
while((x=pop(&s))!='('){
postfix[j]=x;
j++;
}
}
else
{
while( s.top!=-1 && precedence(token)<=precedence(s.data[s.top]))
{
x=pop(&s);
postfix[j++]=x;
}
push(&s,token);
}

}
while(s.top!=-1)
{
x=pop(&s);
postfix[j]=x;
j++;
}
postfix[j]='\0';
}
int precedence(char x)
{
if(x=='(')
return 0;
else if(x=='+'||x=='-')
return 1;
else if(x=='*'||x=='/'||x=='%')
return 2;
else
return 3;
}
void push(stack *s,char x)
{
s->top=s->top+1;
s->data[s->top]=x;
}
char pop(stack *s)
{
int x;
x=s->data[s->top];
s->top=s->top-1;
return x;
}

sorting using quicksort method(divide and conqour method ).

2013-10-24T10:23:00.001+05:30

THE NEED:
quicksort is the fastest sort in best average case of complexity O(n logn) in worst average case it is O(n²).
the method is to choose pivot, which in my program is the index such that all number in the left of array[pivot],should be less than array[pivot]. And all number in right should be greater than array[pivot].
Rest will be done by recursion.

CODE:
#include<stdio.h>
#define max 10
void quicksort(int a[],int ,int );
int choosepivot(int a[],int ,int );
int main()
{
int a[max],first=0,last,i,n;
printf("enter lenght of array you want to sort\n");
scanf("%d",&last);
printf("enter the array\n");
for(i=0;i<last;i++){
scanf("%d",&a[i]);
}
quicksort(a,first,last-1);
for(i=0;i<last;i++)
{
printf("%d ",a[i]);
}
}
void quicksort(int a[max],int first,int last)
{
int pivot;
if(first<last)
{
pivot=choosepivot(a,first,last);
quicksort(a,first,pivot-1);
quicksort(a,pivot+1,last);
}
}
int choosepivot(int a[max],int first,int last)
{
int j,temp;
int pivot=first;
j=last;
while(j>pivot)
{
if(a[pivot]<a[pivot+1]){
pivot++;
}
else if(a[j]<a[pivot]){
temp=a[pivot];
a[pivot]=a[j];
a[j]=temp;
}
else
j--;
}
return pivot;
}

APPROACH:

the function quicksort() sorts the array by dividing them on the basis of index(pivot) that's why this is called as divide and conquer approach.

the function choose pivot ,takes the pivot as first element of the array that is being called.And then check weather the next to it is greater than the number in a[pivot],if not pivot(index) will move to the next number else it will rotate the next number with the last and moves pivot to the next index.

at last the function returns the pivot .

2013-09-05T00:25:00.000+05:30

Vector & Matrix Algebra

#include<iostream.h>
#include<conio.h>
#include <cstdlib>
#include <math.h>
class vector
{
public:
int x,y,z;
void read()
{
cout<<"\n\nEnter the magnitude of i : ";
cin>>x;
cout<<"\n\nEnter the magnitude of j : ";
cin>>y;
cout<<"\n\nEnter the magnitude of k : ";
cin>>z;
}
vector operator -()
{
x=-x;
y=-y;
z=-z;
}
vector operator +(vector b)
{
vector c;
c.x=x+b.x;
c.y=y+b.y;
c.z=z+b.z;
return c;
}
vector operator *(vector b)
{
int prod;
vector c;
c.x=x*b.x;
c.y=y*b.y;
c.z=z*b.z;
prod=c.x+c.y+c.z;
cout<<"\nInner Product = ";
cout<<prod;
vector d;
d.x=(y*b.z)-(z*b.y);
d.y=(x*b.z)-(z*b.x);
d.z=(x*b.y)-(y*b.x);
return d;
}
void display()
{
cout<<x<<"i"<<"+"<<y<<"j"<<"+"<<z<<"k";
}
};

using namespace std;

void vecmat_mult()
{
int mat[10][10];
int vec[3];
int out[10];
int c,d,m,n,i,j;
cout<<"Enter the number of rows and columns of matrix"<<endl;
cin>>m;
cin>>n;
cout<<"Enter the elements of matrix"<<endl;
for ( c = 0 ; c < m ; c++ )
{
for ( d = 0 ; d < n ; d++ )
{
cout<<"Enter elements mat"<<c+1<<d+1<<" ";
cin>>mat[c][d];
}
}

cout<<"Enter Vector Component"<<endl;

for(i=0;i<3;i++)
{
cin>>vec[i];
}

for (i = 0; i < m; i++ )
{
out[i] = 0;
for ( int j = 0; j < n; j++ )
{
out[i] += mat[i][j] * vec[j];
}
}
cout<<"Result Product is\n\n";
for (i=0;i<m;i++)
{
cout<<out[i]<<" "<<endl;
}
}

void matrixmult()
{
int m1[10][10],i,j,k,m2[10][10],mult[10][10],r1,c1,r2,c2;
cout<<"Enter number of rows and columns of first matrix\n";
cin>>r1>>c1;
cout<<"Enter number of rows and columns of second matrix\n";
cin>>r2>>c2;
if(r2==c1)
{
cout<<"Enter rows and columns of First matrix \n";
for(i=0;i<r1;i++)
for(j=0;j<c1;j++)
cin>>m1[i][j];
cout<<"First Matrix is :\n";
for(i=0;i<r1;i++)
{
for(j=0;j<c1;j++)
cout<<m1[i][j]<<"\t";
cout<<"\n";
}
cout<<"Enter rows and columns of Second matrix \n";
for(i=0;i<r2;i++)
for(j=0;j<c2;j++)
cin>>m2[i][j];
cout<<"Second Matrix is:\n";
for(i=0;i<r2;i++)
{
for(j=0;j<c2;j++)
cout<<m2[i][j]<<"\t";
cout<<"\n";
}
cout<<"Multiplication of the Matrices:\n";
for(i=0;i<r1;i++)
{
for(j=0;j<c2;j++)
{
mult[i][j]=0;
for(k=0;k<r1;k++)
mult[i][j]+=m1[i][k]*m2[k][j];
cout<<mult[i][j]<<"\t";
}
cout<<"\n";
}
}
else
{
cout<<"Matrix multiplication cannot be done";
}
}
void matrixtranspose()
{
int a[10][10], trans[10][10], r, c, i, j;
cout<<"Enter rows and column of matrix: "<<endl;
cin>>r>>c;
cout<<"\nEnter elements of matrix:\n";
for(i=0; i<r; ++i)
{
for(j=0; j<c; ++j)
{
cout<<"Enter elements a"<<i+1<<j+1<<" ";
cin>>a[i][j];
}
}
/*Displaying the matrix a[][] */
cout<<"\nEntered Matrix: \n";
for(i=0;i<r; ++i)
{
for(j=0; j<c; ++j)
{
cout<<a[i][j]<<"\t";
if(j==c-1)
cout<<"\n\n";
}
}

/* Finding transpose of matrix a[]
[] and storing it in array trans[][]. */

for(i=0; i<r; ++i)
{
for(j=0;j<c; ++j)
{
trans[j][i]=a[i][j];
}
}
/* Displaying the transpose,i.e, Displaying array trans[][].*/

cout<<"\nTranspose of Matrix:\n";
for(i=0; i<c; ++i)
{
for(j=0; j<r; ++j)
{
printf("%d ",trans[i][j]); if(j==r-1) printf("\n\n");
}
}
}

int main()
{
vector v1,v2,v3;
int choice,cont;
do
{
cout<<"\n\tVECTORS & MaTRIX Algebra\n\n1.Vector Addition\n\n2.Vector Product\n\n3.Product Matrix-Vector\n\n4.Product Matrix-Matrix\n\n5.Transpose Matrix\n\n6.Exit";
cout<<"\n\nEnter your choice : ";
cin>>choice;
switch(choice)
{

case 1 : cout<<"\n\nEnter the First Vector : ";
v1.read();
cout<<"\n\nEnter the Second Vector : ";
v2.read();
v3=v1+v2;
cout<<"\n\nThe Sum of Vectors : ";
v3.display();
break;
case 2 : cout<<"\n\nEnter the First Vector : ";
v1.read();
cout<<"\n\nEnter the Second Vector : ";
v2.read();
v3=v1*v2;
cout<<"\n\nCross Product = ";
v3.display();
break;
case 3 : vecmat_mult();
break;

case 4 : matrixmult();
break;

case 5 : matrixtranspose();
break;

case 6 : exit(0);
default : cout<<"\n\nInvalid Choice";
}
cout<<"\n\n\nDo you want to continue?(1-YES,0-NO)\n";
cin>>cont;
}while(cont==1);
return 0;
}

Returning a structure in C

2012-01-10T23:05:00.002+05:30

The need:

   This program is basically solution of a problem I found on internet. Problem statement is:
There is a purse filled with some coins of gold, silver ans copper. A person draws coins one by one and notes down the type of coin each time. He writes g for gold, s for silver and c for copper coin. Thus a character string is formed. You have to write a function countCoins() which takes that string as parameter and returns count each type of coin. As we know that a function can return only single value, we have 2 options left to return all three counts with one function:
    1. store 3 answers in some contiguous location and return a pointer to that location.
    2. If possible, club all three variables to make a single variable and return that single variable. Yes it is possible, we can make a structure variable containing all three counts and return that structure variable.

The code:

----------------------------------------------------------

#include<stdio.h>
typedef struct
{
    int silver;
    int copper;
    int gold;
}CoinPurse;
CoinPurse countCoin(char *);

int main()
{
    int i;
    CoinPurse a,*b;
    char *coins="gscgcc";
    a=countCoin(coins);
    printf("Coppper coins are %d\n",a.copper);
    printf("Gold coins are %d\n",a.gold);
    printf("Silver coins are %d\n",a.silver);
    return 0;
}

CoinPurse countCoin(char *coins)
{
    CoinPurse x;
    x.copper=0;
    x.gold=0;
    x.silver=0;
    while(*coins)
    {
        switch(*coins)
        {
        case 'c':    x.copper++;
                    break;
        case 'g':    x.gold++;
                    break;
        case 's':    x.silver++;
                    break;
        default:    break;
        }
        coins++;
    }
    return x;
}

----------------------------------------------------------

Approach:
The approach is very simple. The structure CoinPurse contains counter for each type of coin. the function countCoin() takes a character string , examines each character and based on that increments the correct counter. after the string is finished, the structure containing the counts is returned by the function countCoin(). In this program i have given the character string *coins as "gscgcc" soit is clear that there are 2 gold, 1 silver and 3 copper coins which can be verified by the program output.

Counting total number of nodes in a tree

2012-01-08T01:45:00.003+05:30

The need:

This program counts the total number of nodes in a binary tree and prints that for the user. This count is also known as tree size.

The code:

----------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
struct tree_node
{
 int data;
 struct tree_node *left,*right,*parent;
};
typedef struct tree_node node;
node * new_node(int x);
node * insert_node(node *root, int x);
int count_nodes(node *root);

int main()
{
 node *root=NULL;
 int i,x,max;
 printf("how many numbers do you want to enter in tree?\n");
 scanf("%d",&max);
 printf("Enter %d numbers \n",max);
 for(i=0;i<max;i++)
 {
  scanf("%d",&x);
  root = insert_node(root, x);
 }
 printf("all numbers inserted into the tree\t press enter to count");
 fflush(stdin);
 getchar();
 printf("\nThere are total %d nodes in this tree\n",count_nodes(root));
    return 0;
}

node * insert_node(node *root, int x)
{
 if(!root)
 {
  root = new_node(x);
  return root;
 }
 if(root->data > x)
  root->left = insert_node(root->left,x);
 else
  root->right = insert_node(root->right,x);
 return root;
}

int count_nodes(node *root)
{
 if(!root)
 return 0;
 else
 return(count_nodes(root->left) + 1 + count_nodes(root->right));
}

node * new_node(int x)
{
 node *furnished;
 furnished = (node*)malloc(sizeof(node));
 furnished->data=x;
 furnished->left=NULL;
 furnished->right=NULL;
 furnished->parent=NULL;
 return furnished;
}

----------------------------------------------------------

Approach: The approach is simple. We have to go by recursion. if the root is null(means there is no tree) then number of nodes are 0. Otherwise if root is not null(the tree exists), the total number of nodes will be
(number of nodes in left subtree + number of nodes in right subtree + 1 )
Here recursive function count_nodes does the job very well.

Reversing order of words in a sentence using stack

2011-12-12T18:06:00.004+05:30

The need:

This is another way ( a layman's approach) to write previous program about this topic. I have written the approach there too.

The code:

----------------------------------------------------------

#include<stdio.h>
#include<string.h>
#include<stdlib.h>

struct linked_list
{
    char *chr;
    struct linked_list *next;
};
typedef struct linked_list node;
void push(node **p,char *x);
char *pop(node **p);

int main()
{
    char a[50],*temp,*dup;
    strcpy(a,"I dont know why useless programs are asked");
    node * head=NULL;
    temp=strtok(a," ");
    while(temp != NULL)
    {
        dup=strdup(temp);
        temp=strtok(NULL," ");
        push(&head,dup);
    }
    strcpy(a,"");
    while((temp=pop(&head))!=NULL)
    {
        strcat(a,temp);
        strcat(a," ");
    }
    a[strlen(a)-1]='\0';
    printf("%s\n",a);
    return 0;
}

void push(node **p,char *x)
{
    node *new_node;
    new_node=(node *)malloc(sizeof(node));
    new_node->chr=x;
    new_node->next=*p;
    *p=new_node;
}

char *pop(node **p)
{
    char *temp=NULL;
    node *tmp;
    if(*p==NULL)
        return (NULL);
    else
    {
        temp=(*p)->chr;
        tmp=*p;
        (*p)=(*p)->next;
        free(tmp);
        return (temp);
    }
}

----------------------------------------------------------

Approach:
In that case I have made use of my stack concepts and using almost no brain I have got it done. Have a look how simple is this. Steps are:
1. read word by word (strtok has been used to read words delimiter is space)
2. keep on pushing all words on a stack till last word.
3. Now pop each word and print. :-)
Remarks:
1. This is not the most efficient method to do this. For more efficient method have a look at previous program about this topic.
2. This program can also be used to reverse the order of words in a file. In that case steps are:

read word by word (using fscanf(FilePointer,"%s",&TempString)).
keep on pushing all words on a stack till last word.
Now pop each word and print to another file. :-)

Finding k'th root of a number

2011-12-11T00:13:00.003+05:30

The need:
The need is nothing but to find k'th root of a number.
The code:
----------------------------------------------------------------

#include<stdio.h>
#include<math.h>
main()
{
    printf ("*********a program to find k'th root of x ....\n\n");
    char c;
    float i,j,k,m;
    do
    {
    printf ("To get k'th root of x ....\n");
    printf ("type the values .....\n\n");
    printf ("x= "); 
    scanf("%f",&i);
    printf ("k=  ");
    scanf("%f",&k);
    j=pow(i,(1/k));
    printf("\n %dth root of%f = %f\n\n\n",(int)k,i,j);
    printf("do you want to try more? y/n \t");
    fflush(stdin);
    c=getchar();
    }while(c=='y');
}

----------------------------------------------------------------
The Approach:
The approach is very simple. Lets apply simple math
If y^k = x
then y = x^(1/k)
and the problem is solved because we have built-in pow() function for a power.

Variable number of arguments to a function

2011-12-10T15:11:00.005+05:30

Variable number of arguments:

   Till now we have seen various types of functions in C. Some them were built-in and some user defined. There are a lot of noticeable point about them. Intuitively We can say that all the functions should possess same characteristics whether it is user defined or built-in. We have also seen function returning some value, not returning any value, taking no argument and taking certain fixed number of arguments with certain data-types.
Some-times a question can come in your mind if it is possible for a function to accept any number of arguments in C language. Off course it is possible !!! In fact we have used such function many times. Don't remember??? Recall our most commonly used functions printf() and scanf(). How many arguments does printf() function take??
   Let me remind you when we pass arguments to a function while calling it, the arguments are separated by a comma(,). So printf() function takes variable number of arguments. First argument to printf() is a character string and after that some other arguments of various types may or may not come. This fact encourages us to create our own user defined function which would take variable number of arguments.
Problem and solution:
    There may be some problems while implementing variable arguments. One such problem is to determine how many arguments have been passed during a particular call. To overcome that problem there is a rule that at least one argument must be specified in the declaration of function. For more ease I will be giving that argument as a number equal to the count of following arguments so that I can easily know that how many arguments are being passed.
Sample program:
     This program is one of the simplest programs for illustrating the use of variable number of arguments. There is a function sum which can take may arguments and print the sum of those.
Have a look.
------------------------------------------------------------

#include <stdio.h>
#include <stdarg.h>
int sum(int num, ... );
int main( void )
{
    printf("This is program to show the use of variable numbers of arguments to a function\n");
    printf( "Sum of 1,2,3,4 is %d\n", sum(4,1,2,3,4) );
    printf( "Sum of 4,5,3 is %d\n", sum(3,4,5,3) );
    printf( "Sum of 7,3,4,9,1,5 is %d\n", sum(6,7,3,4,9,1,5) );
    return( 0 );
 }
int sum(int num, ... )
{
    int answer = 0;
    va_list argptr;
    va_start( argptr, num );
    while(num-- > 0)
    answer += va_arg( argptr, int );
    va_end( argptr );
    return( answer );
}

------------------------------------------------------------
Explanation:
Declaration of the function is clear as shown. Here argptr is a variable of type va_list. After va_start function is executed here, argptr will contain list of rest of the variables. After that each value of each argument can be accessed with the help of va_arg() function. When all the arguments are finished va_end() function should be put at the end. This va_end() is analogous to fclose() in file handling.

Remarks:
1. variable number of arguments means the function can take some random(but finite) number of arguments. This does not mean that the function can take infinite number of arguments. Maximum number of arguments to a function are limited and depend on the compiler.

Insertion sort in C

2011-12-10T13:40:00.002+05:30

The need:

This is a program to sort a given array of numbers using insertion sort. This program sorts numbers in increasing order. To read more about insert sort read wikipedia.

The code:

----------------------------------------------------------

#include<stdio.h>
void insert_sort(int a[],int size);
int main()
{
    int i,size;
    printf("program for sorting using insert sort\nHow many numbers do you want to sort\n");
    scanf("%d",&size);
    int arr[size];
    printf("enter numbers\n");
    for(i=0;i<size;i++)
    scanf("%d",&arr[i]);
    
    printf("the array before sort is\n");
    for(i=0;i<size;i++)
    printf("%d ",arr[i]);
    printf("\n");
    insert_sort(arr,size);
    printf("the array after sort is\n");
    for(i=0;i<size;i++)
    printf("%d ",arr[i]);
    printf("\n");
    return 0;
}

void insert_sort(int a[],int size)
{
    int i,j,k,temp;
    for(i=1;i<size;i++)
    {
        j=0;
        temp=a[i];
        while(temp>a[j]&&j<i)
        j++;
        for(k=i;k>j;k--)
            a[k]=a[k-1];
        a[k]=temp;
    }
}

---------------------------------------------------------- 

Approach:
The approach is to follow the existing algorithm. Read algorithm on wikipedia. The basic idea is traverse the array form start, temporarily store value of current element and search for the place to the left of that element where the value fits. When you find the place, shift the elements after that position by one to make the void to place temporarily stored element.

finding kth largest number out of n numbers

2011-12-09T13:12:00.003+05:30

The need:

This program gives the kth largest number from the given unsorted list of n numbers. I don't know what could be the application of that but some sites tell that it is asked as interview question sometimes.

The code:

----------------------------------------------------------

/*find kth largest number from a list of n numbers*/
#include<stdio.h>
#include<stdlib.h>
void getMaxToFront(int *p,int front, int end);
void swap(int *, int *);
int main()
{
    int i,*num,n,k;
    printf("This is a program to find kth largest number from a list of numbers\n");
    printf("how many are total numbers\n n = \t");
    scanf("%d",&n);
    if(1>n)
        exit(printf("n cannot be less than 1\n"));
    printf("for kth largest give value of k\n k = \t");
    scanf("%d",&k);
    if(k<1)
        exit(printf("k cannot be less than 1\n"));
    if(k>n)
        exit(printf("k must be less then n\n"));
    num=(int *)malloc(n*sizeof(int));
    printf("now enter %d integers\n",n);
    for(i=0;i<n;i++)
    scanf("%d",num+i);
    for(i=0;i<k;i++)
        getMaxToFront(num,i,n-1);
    printf("\n%d is %dth largest\n",*(num+k-1),k);
    getchar();
    return 0;
}

void getMaxToFront(int *p,int front, int end)
{              
    int i;
    for(i=front+1;i<=end;i++)
        if( *(p+front) < *(p+i) )
        swap(p+front,p+i);
}

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

----------------------------------------------------------

Approach:
first approach is simple. Pick the largest bring it to 1st position, then pick largest from the rest of list and bring on 2nd position and so on upto kth :-).

Remarks:

Analyze the case:

n=100, k=5;

The above program is fine with that. Just find out biggest 5 numbers and done.

Now have a look at this case:

n=100, k=95;

In this case you will not want to go from front to end because you will have to iterate the loop in main 95 time. Instead we'll find out 6th smallest and go end to front... :-)

so better modify the above program a little bit which is like below:

-------------------------------------------------------------

/*find kth largest number from a list of n numbers*/
#include<stdio.h>
#include<stdlib.h>
void getMaxToFront(int *p,int front, int end);
void getMinToEnd(int *p,int front, int end);
void swap(int *, int *);
int main()
{
    int i,*num,n,k;
    printf("This is a program to find kth largest number from a list of numbers\n");
    printf("how many are total numbers\n n = \t");
    scanf("%d",&n);
    if(1>n)
        exit(printf("n cannot be less than 1\n"));
    printf("for kth largest give value of k\n k = \t");
    scanf("%d",&k);
    if(k<1)
        exit(printf("k cannot be less than 1\n"));
    if(k>n)
        exit(printf("k must be less then n\n"));
    num=(int *)malloc(n*sizeof(int));
    printf("now enter %d integers\n",n);
    for(i=0;i<n;i++)
    scanf("%d",num+i);
    if(k<=n/2){
    printf("\nusing getMaxToFront\n");
    for(i=0;i<k;i++)
        getMaxToFront(num,i,n-1);
    }
    else{
    printf("\nusing getMinToEnd\n");
    for(i=n;i>=k;i--)
        getMinToEnd(num,0,i-1);
    }
    printf("\n%d is %dth largest\n",*(num+k-1),k);
    getchar();
    return 0;
}

void getMaxToFront(int *p,int front, int end)
{                //end is needed as an argument here because we need to use the length of list
    int i;
    for(i=front+1;i<=end;i++)
        if( *(p+front) < *(p+i) )
        swap(p+front,p+i);
}

void getMinToEnd(int *p,int front, int end)
{                //actually we could have skipped front as an argument here observe each time I am passing 0 as front
    int i;
    for(i=end;i>=front;i--)
        if( *(p+end) > *(p+i) )
        swap(p+end,p+i);
}

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

-------------------------------------------------------------

This program uses the method/function which gives less number of loop runs. 

Finding whether a number is armstrong number of not

2011-12-09T13:10:00.003+05:30

The need:

This one is trivial program at this point of time. Still putting on demand of Rahul Devra.For those who dont know what is Armstrong number (Narcissistic number) first have a look at Narcissistic number on wikipedia.

The code:

----------------------------------------------------------

/*Find whether entered number is armstrong number or not*/
#include<stdio.h>
#include<math.h>
int digit_count(int x);
int isArmstrong(int x);

int main()
{
    int flg=0,num;
    printf("This is a program to find whether a number is armstrong number\n");
    printf("enter a natural number\n");
    scanf("%d",&num);
    if(isArmstrong(num))
    printf("%d is an armstrong number\n",num);
    else
    printf("%d is not an armstrong number\n",num);
    getchar();
    return 0;
}

int digit_count(int x)
{
    int count=0;
    if(x==0)
    return 0;
    while(x/=10)
    count++;
    return count+1;
}

int isArmstrong(int x)
{
    int i,num_digit,sum=0,current_digit,holder;
    num_digit = digit_count(x);
    holder=x;
    for(i=0;i<num_digit;i++)
    {
        current_digit = x%10;
        sum+=pow(current_digit,num_digit);
        x/=10;
    }
    if(sum==holder)
    return 1;
    else
    return 0;
}

----------------------------------------------------------

Approach:
The approach is simple. Go by the definition, take digit by digit check for the condition for Armstrong number and that's it.

getting nth term of fibonacci series unlimited number of terms

2011-12-07T13:06:00.002+05:30

The need:

          The program for fibonacci series is very simple but those programs give you terms upto the limit of integer size. This is a program to print Fibonacci series upto 10000th term. I wrote this program when I noticed people coming on previous fibonacci program in search of 2011th term or so.

The code:
--------------------------------------------

#define MAX 2100 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 
void print(char x[]); 
void add(char x[], char y[], char z[]); 

int main() 
{ 
    int i=0,j,num; 
    char n_minus1[MAX]="1",n_minus2[MAX]="1",nth[MAX]=""; 
    printf("This is a program to print fibonacci sequence upto desired term.(max 10000)\n"); 
    printf("\nenter a natural number upto which do you want fibonacci series\n");
    scanf("%d",&num); 
    if(    num<1||num>10000) 
    { 
        printf("The desired term index was either invalid or greater than 10000\n"); 
        exit(0); 
    }
    printf("\noptions:\n1. print only %dth term\n2. print all terms\n",num);
    scanf("%d",&j);
    switch(j)
    {
        case 1: 
                if(num<2){
                printf("The first term is 1\n");
                break;
                }
                if(num<3){
                printf("The second term is 1\n");
                break;
                }
                for(i=2;i<num;i++)
                {
                  add(nth,n_minus1,n_minus2);
                  strcpy(n_minus2,n_minus1);
                  strcpy(n_minus1,nth);
                }
                printf("The %dth term is ",num);
                print(nth);
                break;
        case 2:    printf("\nFibonacci series upto %dth term\n\n",num);
                printf("term \tvalue\n",num);
                printf("%4d \t1\n",1);
                if(num<2)
                break;
                printf("%4d \t1\n",2);
                if(num<3)
                break;
                for(i=2;i<num;i++)
                {
                  add(nth,n_minus1,n_minus2);
                  printf("%4d\t",i+1);
                  print(nth);
                  strcpy(n_minus2,n_minus1);
                  strcpy(n_minus1,nth);
                }
                break;
        default: printf("Invalid choice...!!! \tExiting\n");
                exit(0);
    }
    printf("\n\nprgram finished successfully.\t press any key to continue\n");
    getchar(); 
    return 0; 
} 

void print(char x[]) 
{ 
    int i; 
    for(i=strlen(x)-1;i>=0;i--) 
    { 
        putchar(x[i]); 
        if(i%5==0) 
        putchar(' '); 
    } 
    putchar('\n'); 
    return; 
} 

void add(char x[],char y[],char z[]) 
{ 
    int i,ylen,zlen,equal;
    char c = 0,temp;
    ylen = strlen(y);
    zlen = strlen(z);
    equal = (ylen == zlen) ? 1 : 0; 
    for(i=0;i<zlen;i++) 
    { 
        x[i]=c + y[i] + z[i] - '0'; 
        if( x[i]-'0' > 9)
        {
            x[i]-=10;
            c=1;
        }
        else
        c=0; 
    }
    if(equal)
    {
        if(c!=0)
        {
            x[i]=c + '0';
            x[i+1]='\0';
        }
    }
    else
    {
        x[i]=c + y[i];
        x[i+1]='\0';
    } 
    return; 
}

--------------------------------------------

The approach:
This program creates a Fibonacci series upto the terms given by the user. The logic is same. Just go with the definition of Fibonacci that any term is the sum of its two preceding terms. Here nth always hold current term and n_minus1 and n_minus2 hold previous 2 terms(except for first 2 terms case). I have already told that integers are very small to work when we have more than 10digits in the scene so these 3 variables are taken as strings. add() is UDF defined by me which takes 3 arguments x,y,z. add puts sum of y and z into x. This add() is the only twist here to differentiate this program from program38 of this blog.

Remarks:
1. In this program is capable to give you upto 10000th term of fibonacci easily.

2. You can get upto more terms. all you have to do is to increase the value of max in #define statement. This is why I wrote unlimited in the title.

program to reverse the spelling of words in a sentence

2011-12-06T19:52:00.000+05:30

The need:

I don't know what could be the need of this program but I found this question on many sites and thats why I wrote this program.

The code:

----------------------------------------------------------

#include<stdio.h>
#include<string.h>

void reverse(char *str,int start, int end)
{
    char temp;
    int i,j;
    i=end-start;
    for(j=0;j<=i/2;j++)
    {       
        temp=*(str+start+j);
        *(str+start+j)=*(str+start+i-j);
        *(str+start+i-j)=temp;
    }
}

rev_word(char *str)
{
    int start=0,end=0,i=0;   
    while(*(str+i)!='\0')
    {
        if(*(str+i)==' ')
        {
            end=i-1;
            reverse(str, start, end);
            i++;
            start=i;
        }
        else
            i++;
    }
    end=i-1;
    reverse(str, start, end);
}

int main()
{
    char a[]="I dont know why useless programs are asked";
    printf("before\n%s\n",a);
    rev_word(a);
    printf("after\n%s\n",a);
    return 0;
}

----------------------------------------------------------

Approach:
The approach is simple. make a note of start and end points (indices) of each word and reverse with the help of those points. The UDF reverse() does the job here.

program to reverse the order of words in a sentence

2011-12-06T19:39:00.007+05:30

The need:

I don't know what could be the need of this program but I found this question on many sites and thats why I wrote this program.This program is extension of previous program.

The code:

----------------------------------------------------------

#include<stdio.h>
#include<string.h>

void reverse(char *str,int start, int end)
{
    char temp;
    int i,j;
    i=end-start;
    for(j=0;j<=i/2;j++)
    {      
        temp=*(str+start+j);
        *(str+start+j)=*(str+start+i-j);
        *(str+start+i-j)=temp;
    }
}

rev_word(char *str)
{
    int start=0,end=0,i=0;  
    while(*(str+i)!='\0')
    {
        if(*(str+i)==' ')
        {
            end=i-1;
            reverse(str, start, end);
            i++;
            start=i;
        }
        else
            i++;
    }
    end=i-1;
    reverse(str, start, end);
}

int main()
{
    char a[]="I dont know why useless programs are asked";
    printf("before\n%s\n",a);
    rev_word(a);
    reverse(a, 0, strlen(a)-1);
    printf("after\n%s\n",a);
    return 0;
}

----------------------------------------------------------

Approach:
The approach is simple. make a note of start and end points (indices) of each word and reverse with the help of those points. The UDF reverse() does the job here. After that reverse the whole sentence character by character. I have used my UDF here because its existing and I dont need to write or search for another function though one could also use strrev() built-in function to reverse the whole sentence character by character.
Remarks:
1. You can modify reverse() function here into ordinary string_reverse (same as built-in strrev) function. For that remove arguments start and end from the function definition and use 0 in place of start and (length of string-1) as end.
Other approach:
2. Here for doing the whole thing I have used only one extra character other than the provided string (off course I have also used counters etc. but that is different thing). If I was allowed to use as much space as I wanted, I would have not thought this much like I have thought here --> reversing the spelling of each word and then reversing the whole string. In that case I would have made use of my stack concepts and using almost no brain I could have got it done. Have a look how simple is this. Steps are:
1. read word by word (using scanf with %s)
2. keep on pushing all words on a stack till last word.
3. Now pop each word and print. :-)
For this approach have a look at next program on this topic.

Get the execution time of a C program

2011-11-23T11:38:00.003+05:30

The need:

Need is same as previous program which gives you precision of nanoseconds but that program would work only on linux. This program will work on windows also but will give you precision of milli seconds only. All you need to do is to place your test program code (the code whose execution time is to be measured) in between the comments which indicate the start and end of the program.

The code:

----------------------------------------------------------

/*This program should work on both windows and linux*/
#include<time.h> 
#include<stdio.h>
#include<stdlib.h> 
#define START if ( (start_time = clock()) == -1) {printf("Could not call clock");exit(1);} 
#define STOP if ( (stop_time = clock()) == -1) {printf("Could call clock");exit(1);} 
#define PRINT_TIME_DIFF printf( "Your program took %.3f seconds.\n", ((double)stop_time-start_time)/CLOCKS_PER_SEC); 
    
int main()
{ 
    clock_t start_time, stop_time;
    int i=0; 
    START
    //test program code begins
    
    //test program code ends 
    STOP 
    PRINT_TIME_DIFF
    return 0; 
}

----------------------------------------------------------

Approach:
The approach is simple. There is a built-in function clock() in <time.h> header file. In this program I have use macros to differentiate between your test code and the statement which would be used to print the time and other things. I thought this would simplify the look of the program a little bit.
Remarks:
1. This program should work on both windows and linux.
2. This program will give accuracy of (1/1000)th part of a second.

Getting running time of a C program

2011-11-22T16:53:00.006+05:30

The need:

Need is obvious.Whenever you are curious to find running time of a program or you are asked to do so, you can use this program. All you need to do is to place your program code(the code between the brackets of main() function ) in between the comments which indicate the start and end of the program.

The code:

----------------------------------------------------------

/*This program is intended to work on linux*/
#include <stdio.h> 
#include <time.h> 
void print_time_diff(struct timespec begin,struct timespec end);
int main ( void )
{
    struct timespec start, end;
    gettimeofday(&start, NULL);
    //program code begins
    //program code ends
    gettimeofday(&end, NULL);
    print_time_diff(start,end);
    return 0;
}

void print_time_diff(struct timespec begin,struct timespec end)
{
    unsigned int sec,nanosec;
    if (end.tv_nsec<begin.tv_nsec) {
        sec = end.tv_sec-begin.tv_sec-1;
        nanosec = 1000000000+end.tv_nsec-begin.tv_nsec;
    } else {
        sec = end.tv_sec-begin.tv_sec;
        nanosec = end.tv_nsec-begin.tv_nsec;
    }
    printf("your program took %d seconds and %u nanoseconds to run.\n",sec,nanosec);
}

----------------------------------------------------------
Approach:
   The approach is simple. There is a built-in structure timespec in <time.h> header file of linux.The built-in definition of structure is:
struct timespec
{
    __time_t tv_sec;        /* Seconds. */
    long int tv_nsec;        /* Nanoseconds. */
};
The program declares 2 struct variables start and end. built-in function gettimeofday() fills the struct variable passed to it with suitable values at that particular instance. This implies that start gets the value of time when your program (code to be measured) is just about to start and end gets the value of time as soon as your program finishes.
print_time_diff() is user defined function which prints the difference of the two times passed to it as arguments.
Remarks:
1. This program should not work on windows and operating systems other than linux.
2. The program which would work on windows will be posted shortly.

Heap sort in C

2011-11-22T15:10:00.004+05:30

The need:
Heap sort is a better than bubble, selection and insertion algorithm for sorting. To show how heap can be useful in real life implementation.

The code:

-----------------------------------------------------------

/*this program is an array implementation of heap*/ 
#include<stdio.h> 
#include<string.h> 
#include<stdlib.h> 

void print_array(int a[],int array_size); 
void heap_sort(int a[],int array_size); 
void heapify(int a[],int count); 
void adjust_down(int a[],int start, int end); 

main() 
{ 
    int i,arr[50],size=0; 
    arr[0]=0; 
    printf("how many elements do you want to enter\n");
    scanf("%d",&size); 
    if(size<1)
    {
        printf("You did not enter a valid count of elements.\n");
        printf("Rerun the program and try again\n");
        exit(0);
    }
    printf("enter array\n"); 
    for(i=1;i<=size;i++) 
        scanf("%d",&arr[i]);
    printf("the array before heap sort.\n"); 
    print_array(arr,size); 
    heap_sort(arr,size);
    printf("the array after heap sort.\n"); 
    print_array(arr,size);    
} 

void heap_sort(int a[],int array_size)
{
    int i,j,heap_end,temp;
    heap_end=array_size;
    heapify(a,array_size);
    while(heap_end>2)
    {
        temp=a[1];
        a[1]=a[heap_end];
        a[heap_end]=temp;
        heap_end--;
        adjust_down(a, 1, heap_end);
    }
}

void heapify(int a[],int count) 
{ 
    int start;
    start = count/2 + 1;
    while(start>0)
    {
        adjust_down(a, start, count);
        start--;
    } 
} 

void adjust_down(int a[],int start, int end)
{
    int root = start,temp,bigger_child;
    while(2*root <= end)
    {
        if(2*root+1 > end)
        {
            if(a[2*root]<a[root])
            {
                temp=a[root];
                a[root]=a[2*root];
                a[2*root]=temp;
            }
            root=2*root;
        }
        else
        {
            bigger_child = (a[2*root]>a[2*root+1])? 2*root : 2*root+1;
            if(a[root]<a[bigger_child])
            {
                temp=a[root];
                a[root]=a[bigger_child];
                a[bigger_child]=temp;
            }
            root=bigger_child;
        }
    }
}

void print_array(int x[],int size) 
{ 
    int i; 
    for(i=0;i<size;i++) 
        printf("%d\t",x[i+1]); 
    putchar('\n'); 
}

-----------------------------------------------------------

The approach:

The approach is simple. This program uses a max heap to sort the numbers in ascending order. You know that in a max heap root is largest element. This program works on the below logic:

1. first take an array from user. Notice that I have saved the elements from index one leaving index 0 empty. See remark1 below.

2. make that array to satisfy max heap property(max - heapify array).

3. Now swap last element of heap with the root. So that the biggest element comes last.

4. Now leave the last element and assume rest array as heap.

5. Adjust the new heap so satisfy max heap property.

6. Repeat step 3-5 till only root is left as rest part of heap.

7. You will be getting an increasingly sorted array.

you can refer to wikipedia for more theory and graphics about heap sort.

Remark:

1. This is the convention I follow when I implement heap on an array because this gets you left and right children as 2*current_node, and (2*current_node + 1). You can use other convention of starting with index 0. In that case left and right children will be evaluated (2*current_node+1), and (2*current_node + 2) which seems a little bigger expressions to me :P

Concept of Heap in C

2011-11-22T14:51:00.001+05:30

Heap is a concept which can be implemented on trees, priority queues and arrays. When we plot a heap on paper, we draw it as binary tree. We also analyse a heap as a binary tree. There are 2 types of heaps:
1. min heap: parent node is always less than both children.
2. max heap: parent node is always greater than both children.
In both the cases equality is permitted. No other property is required for a heap. We do not care about any other thing like which child is greater.

Heap can be utilized in
1. heapsort
2. a priority queue can be implemented with a heap
3. auto balancing binary tree

For general purposes this much on heap is enough. For more you can study in details on wikipedia.

Creating and traversing a binary search tree

2011-10-16T00:30:00.002+05:30

The need:

This program is written to show creation and various types of printing of a binary search tree. This program takes values and put them in a binary search tree and then prints the resulting tree in preorder, inorder and post order.
The BST(Binary Search tree): a binary search tree is a binary tree in which value of each node is greater or equal than that of its left child and less than that of its right child. Hence all nodes in the left sub-tree of a node are less than or equal to the value of that node and all nodes in the right sub-tree of a node are greater than the value of that node if it is a binary search tree. We'll use this property while inserting a node in the BST in insert() function.

The code:

----------------------------------------------------------

#define MAX 10
#define DEBUG if(!(root->left))    printf("inserted %d to the left of %d\n",x,root->data);
#include<stdio.h>
#include<stdlib.h>
struct tree_node
{
    int data;
    struct tree_node *left,*right,*parent;
};
typedef struct tree_node node;
node * new_node(int x);
node * insert_node(node *root, int x);
void print_preorder(node *root);
void print_inorder(node *root);
void print_postorder(node *root);

int main()
{
    node *root=NULL;
    int i;
    int arr[]={5,6,1,9,0,4,2,3,8,7};
    for(i=0;i<MAX;i++)
    root = insert_node(root, arr[i]);
    printf("\ntree pre order is\n");
    print_preorder(root);
    printf("\n\ntree in order is\n");
    print_inorder(root);
    printf("\n\ntree post order is\n");
    print_postorder(root);
    return 0;
}

node * insert_node(node *root, int x)
{
    if(!root)
    {
        root = new_node(x);
        return root;
    }
    if(root->data > x)
    {
//        DEBUG
        root->left = insert_node(root->left,x);
    }
    else
    {
//        DEBUG
        root->right = insert_node(root->right,x);
    }
    return root;
}

void print_preorder(node *root)
{
    if(!root)
    return;
    printf("%d ",root->data);
    print_preorder(root->left);
    print_preorder(root->right);
    return;
}

void print_inorder(node *root)
{
    if(!root)
    return;
    print_inorder(root->left);
    printf("%d ",root->data);
    print_inorder(root->right);
    return;
}

void print_postorder(node *root)
{
    if(!root)
    return;
    print_postorder(root->left);
    print_postorder(root->right);
    printf("%d ",root->data);
    return;
}

node * new_node(int x)
{
    node *furnished;
    furnished = (node*)malloc(sizeof(node));
    furnished->data=x;
    furnished->left=NULL;
    furnished->right=NULL;
    furnished->parent=NULL;
    return furnished;
}

----------------------------------------------------------

Approach:

This program is just to show the printing of a tree in pre-order, inorder and post order. For that first we have to make the tree. Here we dont have tree with 3 nodes necessarily. So we need to make a function to construct the tree. Here insert() function does the job. create_node() function creates a node with given data/value ans returns it address. we create first node, make it root. After that we create 2 more nodes and make them left and right children of root. Then there are 3 functions in_print(), pre_print() and post_print() which print the expression in infix, prefix and postfix form respectively.

Remarks:

1. We noticed that here in each function I have used recursion like I have already said in previous posts that recursion makes our life easier in trees.
2. Uncomment DEBUG to see where the nodes are being inserted.
3. Here I am taking node data from an array we can take data from user also.

Inorder, Preorder and Post-Order traversal of tree

2011-10-14T23:09:00.002+05:30

The need:

This program is written to show the program implementation of the concept explained in the previous post. This program is the implementation of 2 + 3 example given there.

The code:

----------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
struct tree
{
    char num;
    struct tree *left, *right, *parent;
};
typedef struct tree node;

void in_print(node *p);
void pre_print(node *p);
void post_print(node *p);
node * create_node(char c);
int main()
{
    int i;
    node *root=NULL;
    root = create_node('+');
    root->left = create_node('a');
    root->right = create_node('b');
    printf("Pre order print\t\t");
    pre_print(root);
    printf("\nIn order print\t\t");
    in_print(root);
    printf("\nPost order print\t");
    post_print(root);
    putchar('\n');
    return 0;
}

node * create_node(char c)
{
    node *new_node;
    new_node = (node *)malloc(sizeof(node));
    new_node->num = c;
    new_node->parent = NULL;
    new_node->left = NULL;
    new_node->right = NULL;
    return new_node;
}

void pre_print(node *p)
{
    if(p==NULL)
    return;
    else
    printf("%c ",p->num);
    pre_print(p->left);
    pre_print(p->right);
}

void in_print(node *p)
{
    if(p==NULL)
    return;
    else
    in_print(p->left);
    printf("%c ",p->num);
    in_print(p->right);
}

void post_print(node *p)
{
    if(p==NULL)
    return;
    else
    post_print(p->left);
    post_print(p->right);
    printf("%c ",p->num);
}

----------------------------------------------------------

Approach:
This program is just to show the printing of a tree in pre-order, inorder and post order. For that first we have to make the tree. Here I have not created a bigger tree. Here we have the simplest tree with 3 nodes only. So we need not make a function to construct the tree. Here simply I have created 3 nodes and put them to make a small tree. create_node() function creates a node with given data/value ans returns it address. we create first node, make it root. After that we create 2 more nodes and make them left and right children of root. Then there are 3 functions in_print(), pre_print() and post_print() which print the expression in infix, prefix and postfix form respectively.
Remarks:

1. Here this program is shown to print the simplest expression in prefix, infix and post-fix form but this program can be used to print any binary tree in pre-order, inorder and post order.

2. This program is the base of all the tree programs related to trees.

Inorder, Preorder and Post-Order traversal : An overview

2011-10-12T14:23:00.000+05:30

The Idea:
Lets first have a look at some mathematical side. The Infix, Prefix and Post-fix notations are exactly analogous to the In-order, Preorder and Post-order traversal of trees.
Have a look at the expresstion:
a + b
     This is a familiar expression to all of us. Here + is an operator with a and b as operands. This is one way to write sum of a and b. This way is called in-fix notation. In this way we write operator in between the operands. This is the only used method for writing expressions for human understanding. Thats why everybody is familiar to this method. But this is not the only way to be used for every purpose. there are 2 more ways.
     Prefix notation: In this way of writing expressions the operator comes first which is followed by the operators. The same expression can be written in Prefix notation as:
+ a b
     Postfix notation: In this way of writing expressions the operator comes last after both the operands have been written. The same expression can be written in Prefix notation as:
a b +

Analogy comes from here. Have a look at the above image.
Its a tree with + at parent node and 2 and 3 as child nodes. Now we have
Infix: 2 + 3
Prefix: + 2 3
postfix: 2 3 +
    We see that it is the position of operator which changes and decides which fix notation is this. The relative positions of operands are always same.
    This is about expressions writing. Now lets move to traversal of trees in data-structures topic. In the same manner as in the case of expressions in trees also left child will always be accessed before the right. It is the root which decides which type of traversal it is.
     InOrder Traversal: In this way of traversing tree the root is accessed first after that the children are accessed.
     PreOrder Traversal: In this way of traversing tree one child is accessed first and then the root is accessed after that the other child is accessed.
     PostOrder Traversal: In this way of traversing tree the root is accessed after both of the children are accessed.
   here this concept is explained with the basic tree consisting of only 3 nodes but this holds true for any tree(binary tree). Recursion will play very important role in tree traversal. We can store a mathematical expression in tree and then that can be printed in any order using inorder, preorder and postorder traversal giving infix, prefix and post-fix form of that expression respectively. Obviously this is not the only use of trees.

2011-10-11T12:39:00.000+05:30

Concept of trees in C:

The concept of trees is same to real world tree. In real word every tree has roots, and can have many branches. Each branch can have sub-branches. If you look at branches and sub-branches as a whole, the combination looks like a tree (lets call it a sub-tree). Same is the case of a tree in programming jargon. There is only one difference in plotting the trees. A real world tree has roots on the downside while in C programming, a tree is upside down which has roots on the top and sub-trees below that. Tree is a variation of linked lists.

Here in programming the most commonly used tree is a binary tree. Now lets come to data-structural jargon. A binary tree is a tree in a tree (data structure) in which each node (say current node) has addresses of 2 next possible nodes. The current node is called parent node and these next 2 nodes are called children of that node. We'll call them left child and right child. From the current node, if you want to come down, you have 2 options (either you can come on left child or the right child).

You people have seen that we can traverse a singly linked list in one direction and doubly linked list in two directions in the similar way in a tree you can reach max three nodes from a current node. So in a binary tree each node has only 2 address pointers, you can traverse only in the down direction. If you want to traverse the tree in both the directions (downward as well as upward), each node must be having address of its parent node also.

Here the node structure is a bit different. You can think of a binary tree as a continuation of linked lists from singly to doubly to binary tree. Let me explain further. In node of a singly connected linked list we have one single pointer pointing to next node and in node of a doubly connected linked list we have 2 pointers which can point to other 2 nodes (next and previous nodes). Similarly in a node of a binary tree we have 3 pointers which can point to 3 other nodes one to parent, one to left child, one to right child so that we can traverse easily in both the directions.

program to print a linked list in reverse order

2011-09-23T15:36:00.000+05:30

The need:

This program is a program to prints a linked list in reverse order without actually reversing it (For reversing a given linked list have a look on program78 of this blog). This program is written to show how recursion becomes more useful. First it asks user to enter numbers to be entered into linked list then creates a linked list, prints it in same as given and reversed order.

The code:

---------------------------------------------------------

#include<stdio.h>
#include<stdlib.h>
typedef struct linked_list
{
    int item;
    struct linked_list *next;
}node;

node *create_list();
void print_list(node *);
void print_list_in_reverse(node *);

int main()
{
    node *head=NULL;
    printf("This program creates a linked list and then prints it first in given order and then in reverse\n");
    printf("create a list by entering elements press -999 to end\n");
    head=create_list();
    printf("\nThe list is\n");
    print_list(head);
    printf("\nThe list in reverse order is");
    print_list_in_reverse(head);
    printf("\n");
    return 0;
}

node *create_list()
{
    int x;
    node *temp=NULL;
    scanf("%d",&x);
    if(x!=-999)
    {
        temp=(node*)malloc(sizeof(node));
        temp->item=x;
        temp->next=NULL;
        temp->next=create_list();
    }
    return temp;
}
void print_list(node *p)
{
    if(p)
    {
        printf("%d ",p->item);
        print_list(p->next);
    }
    else
    printf("\n");
}

void print_list_in_reverse(node *p)
{
    if(p)
    {
        print_list_in_reverse(p->next);
        printf("%d ",p->item);
    }
    else
    printf("\n");
}

---------------------------------------------------------

The need:

The approach is nothing but basics of recursion.
If we say the recursion in create_list function in normal English, we'll say "It will take a number form user if it is not -999, a new node is created, data is filled in it and address of this node is returned else NULL is returned." because temp is initialised to NULL each time in the starting of function.

If we say the recursion in print_list function in normal English, we'll say "It will print the data of a node and then go for doing the same to the next node after that if present".

If we say the recursion in print_list_in_reverse function in normal English, we'll say "It will print the data of a node when all the node after that are printed or if there is no node after that node".

Remarks:

1. We can print linked list as it is (in the given order) without using extra storage or extra thinking. We can just use loops but if we are asked to write a program to print the linked list without actually reversing it, we can not do it by just using loops. What we can do is next point.

2. For that we have to create a stack and push addresses of all the elements of linked list on it starting from head to end. Then pop addresses one by one and print the corresponding data. This requires extra storage and extra thinking.

3. So in this program recursion is the way to do the same without extra thinking and without explicitly using extra memory and functions.

4. I wrote explicitly with stress because recursion actually uses its own stack (System stack). Now I am not going into these details.