Implementing Knapsack Problem in C Programming

The knapsack problem or rucksack problem is a problem in combinatorial optimization: Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. It derives its name from the problem faced by someone who is constrained by a fixed-size knapsack and must fill it with the most valuable items.

In this post, I will demonstrate how to implement it using C programming language.

#include<stdio.h>
void swap(float *a,int x,int y)
{
 int temp=*(a+x);
 *(a+x)=*(a+y);
 *(a+y)=temp;
}
void swap1(int *a,int x,int y)
{
 int temp=*(a+x);
 *(a+x)=*(a+y);
 *(a+y)=temp;
}
main()
{
 printf("\nProgram to implement Knapsack problem : \n");
 int n,i,j,kn,kn2;  
 printf("\nEnter knapsack capacity : ");
 scanf("%d",&kn);
 kn2=kn;
 printf("\nEnter no. of elements : ");
 scanf("%d",&n);
 int index[n];
 float weight[n],profit[n],prowt[n],totwt=0,rem=0,rem2=0,rem3=0; 
 for(i=0;i<n;i++)
  index[i]=i;
 printf("\nEnter weight and profit for each element : \n");
 printf("\n\t\tWeight\tProfit\n");
 for(i=0;i<n;i++)
 {
  printf("Element %d : \t",index[i]);
  scanf("%f%f",&weight[i],&profit[i]);
  prowt[i]=profit[i]/weight[i];   
 }
 for(i=0;i<n;i++)
  for(j=0;j<n-1-i;j++)
   if(prowt[j]<prowt[j+1])
   {
    swap1(index,j,j+1);
    swap(prowt,j,j+1);
    swap(weight,j,j+1);
    swap(profit,j,j+1);
   }
 printf("\nDetails entered by user (after sorting): \n");
 printf("\n\t\tWeight\t\tProfit\t\tProfit per wt.\n");
 for(i=0;i<n;i++)
 {
  printf("Element %d : ",index[i]);
  printf("\t%5.4f\t\t%5.4f\t\t%5.4f\n",weight[i],profit[i],prowt[i]);
 }
 for(i=0;i<n;i++)
 {
  if(totwt + weight[i] < kn)
  {
   totwt=totwt+weight[i];
   kn2=kn2-weight[i];
   printf("\n\nElement %d inserted completely in the knapsack ...",index[i]);
   printf("\nTotal weight of Knapsack : %4.2f",totwt);
   printf("\nRemaining capacity : %d",kn2);
  }
  else
  {
   rem=weight[i]-kn2;
   rem2=rem/weight[i];    
   rem3=(float)(1-rem2)*100;
   totwt=totwt+kn2;
   printf("\n\nOnly %4.2f %% of element %d inserted in the knapsack ...",rem3,i);
   printf("\nTotal weight of Knapsack : %4.2f",totwt);
   printf("\n\n\t***** Knapsack is full *****\n");
   break;
  }
 } 
}   

The output of the program will be like this :

Program to implement Knapsack problem :

Enter knapsack capacity : 10

Enter no. of elements : 3

Enter weight and profit for each element :

                      Weight    Profit
Element 0 :     6             10
Element 1 :     1              9
Element 2 :     5              5

Details entered by user (after sorting):

                        Weight        Profit        Profit per wt.
Element 1 :     1.0000        9.0000        9.0000
Element 0 :     6.0000        10.0000      1.0000
Element 2 :     5.0000        5.0000        1.0000


Element 1 inserted completely in the knapsack ...
Total weight of Knapsack : 1.00
Remaining capacity : 9

Element 0 inserted completely in the knapsack ...
Total weight of Knapsack : 7.00
Remaining capacity : 3

Only 60.00 % of element 2 inserted in the knapsack ...
Total weight of Knapsack : 10.00

    ***** Knapsack is full *****

Read More...

Kruskal's Algorithm in C using array

#include<stdio.h>
int visited[10]={0};
void kruskal(int w[10][10],int n)
{
 int min,sum=0,ne=0,i,j,u,v,a,b; 
 while(ne<n-1)
 {
  min=999;
  for(i=1;i<=n;i++)
   for(j=1;j<=n;j++)
    if(w[i][j]<min)
    {
     min=w[i][j];
     u=a=i;
     v=b=j;
    }
  while(visited[u])
   u=visited[u];
  while(visited[v])
   v=visited[v];
  if(u!=v)
  {
   ne++;
   sum+=min;
   printf("\nEdge ( %d , %d ) --> %d",a,b,min);
   visited[v]=u;
  }
  w[a][b]=w[b][a]=999;
 }
 printf("\nCost of minimum spanning tree : %d\n",sum);
}
main()
{
 int w[10][10],n,i,j;
 printf("\nProgram to implement Kruskal's Algorithm : \n");
 printf("\nEnter no. of vertices : ");
 scanf("%d",&n);
 printf("\nEnter the adjacency matrix : \n");
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   scanf("%d",&w[i][j]);
 for(i=1;i<=n;i++)
  for(j=1;j<=n;j++)
   if(w[i][j]==0)
    w[i][j]=999;
 kruskal(w,n);
}

Output of the program :

Program to implement Kruskal's Algorithm :

Enter no. of vertices : 3

Enter the adjacency matrix :
0 1 1
1 0 1
1 1 0

Edge ( 1 , 2 ) --> 1
Edge ( 1 , 3 ) --> 1

Cost of minimum spanning tree :  2

Read More...

Prim's Algorithm in C

     /*  Program to implement Prim's algorithm  */  
      
    #include<stdio.h>  
    #include<stdlib.h>  
    struct node  
    {  
        int key;  
        int data;  
        struct node *par;  
    };  
    struct node *n[20];  
    struct edge  
    {  
        int wt;  
        struct node *src,*des;  
    };  
    struct edge *e[20][20];  
    void makeset(int i)  
    {  
         n[i]=(struct node *)malloc(sizeof(struct node));  
         n[i]->data=i;  
         n[i]->key=9999;  
         n[i]->par=NULL;  
    }  
    int main()  
    {  
        int tn,i,adm[20][20],q[20],s,j,w,temp,k;  
        printf("Enter the total no. of nodes ");  
        scanf("%d",&tn);  
        for(i=0;i<=tn;i++)  
        {  
            for(j=0;j<=tn;j++)  
            {  
                adm[i][j]=0;  
            }  
        }  
        printf("\nEnter the weights for the following edges ::\n");  
        for(i=1;i<=tn;i++)  
        {  
            makeset(i);  
            q[i]=i;  
            for(j=i+1;j<=tn;j++)  
            {  
                printf("%d  %d: ",i,j);  
                scanf("%d",&w);  
                if(w==0)  
                w=9999;  
                e[i][j]=(struct edge *)malloc(sizeof(struct edge));  
                e[i][j]->wt=w;           
                e[i][j]->src=n[i];      
                e[i][j]->des=n[j];      
                adm[i][j]=1;  
                adm[j][i]=1;  
            }  
        }  
        j=1;  
        while(j<=tn)  
        {  
            q[j]=0;  
            temp=j;  
            for(k=1;k<=tn;k++)  
            {  
                if(adm[temp][k]==1 && q[k]==k)  
                {  
                    if(e[temp][k]->wt<n[k]->key)  
                    {  
                        n[k]->par=n[temp];    
                        n[k]->key=e[temp][k]->wt;  
                    }  
                }  
            }  
        j++;  
        }  
        for(j=2;j<=tn;j++)  
        {  
            k=(n[j]->par)->data;  
            printf("output is %d : %d - %d\n",k,j,e[k][j]->wt);  
        }  
    } 

Read More...

Kruskal's Algorithm in C

        /* Program to implement Kruskal's Algorithm */
      
    #include<stdio.h>  
    #include<stdlib.h>       
    void makeset();  
    void graph(int);  
    void kruskal();  
    struct node *findset(struct node *);  
    void union1(struct node *,struct node *);  
      
    int j=0;  
    struct node //Declare the structure of a node  
    {  
        int data,rank;  
        struct node *next,*parent;  
    };       
    struct edge //Declare the structure of a edge  
    {  
        int len;  
        struct node *src,*destination;  
    };        
    struct node *head[10];  
    struct edge *e[40];       
    int main()  
    {  
        int n,i;  
        printf("\nEnter no.of vertices in the graph : ");  
        scanf("%d",&n);  
        for(i=1;i<=n;i++)  
        {  
            makeset(i); //initialise each vertex  
        }  
        graph(n);  
        kruskal();      
    }      
    void makeset(int a)  
    {  
        struct node *x;  
        x=(struct node*)malloc(sizeof(struct node));  
        x->data=a;  
        x->parent=x;  
        x->rank=0;  
        x->next=NULL;  
        head[a]=x;  
    }     
    void graph(int n)   //here input neighbours of each vertex & the weight of edges  
    {  
        int i,k,l,len;  
        int dest;  
        for(i=1;i<=n;i++)  
        {  
            printf("\nfor vertex %d Enter no. of edges ",i);  
            scanf("%d",&l);  
            for(k=1;k<=l;k++)  
            {  
            printf("Enter destination vertex for %dth edge for vertex %d ",k,i);  
            scanf("%d",&dest);  
            j++;  
            e[j]=(struct edge*)malloc(sizeof(struct edge));  
            e[j]->src=head[i];  
            e[j]->destination=head[dest];  
            printf("Enter length of edge : ");  
            scanf("%d",&len);  
            e[j]->len=len;  
            }  
        }  
    }      
    void kruskal()  //Apply actual concept of kruskal  
    {  
        int i,k,l,p;  
        struct edge *temp;  
        i=1;  
        while(i<j)   //sort the edges with increasing order of their weights  
        {       //using insertion sort  
            p=i;  
            k=i+1;  
            while(k<=j)  
            {  
                if(e[p]->len>e[k]->len)  
                {  
                    p=k;  
                }  
                k++;  
            }  
            if(p!=i)  
            {  
            temp=e[p];  
            e[p]=e[i];  
            e[i]=temp;  
            }  
            i++;  
        }  
        printf("\nMST includes the following edges that are :\n");  
        for(i=1;i<=j;i++)  
        {  
            if(findset(e[i]->src)!=findset(e[i]->destination))    //if representative  
            {                           //of src & dest. are different  
            union1((findset(e[i]->src)),(findset(e[i]->destination)));    //then make connection  
            printf("\n%d->%d",e[i]->src->data,e[i]->destination->data);  //b/w them  
            }  
        }  
    }       
    struct node *findset(struct node *a)    //return the represenative of node  
    {  
        if(a!=a->parent)  
        {  
            a->parent=findset(a->parent);  
        }  
        return a->parent;  
    }      
    void union1(struct node *x,struct node *y)  //join the two vertex if desired  
    {  
        if(x->rank>y->rank)  
            y->parent=x;  
        else  
            x->parent=y;  
        if(x->rank==y->rank)  
        y->rank=y->rank+1;  
    }  

Read More...

Testing symmetry of a matrix in C programming

/* Symmetry of matrix  */

#include<stdio.h>
#define r 10
#define c 10
int i, j;
float value;
float mat[r][c];
void display(int, int);
void display_o( float transp[r][c],int, int);
void input( float transp[r][c],int, int);
void transpose( float transp[r][c],int, int);
int Symmetry_Matrix(float transp[r][c], int , int );

/* Transpose function */

void transpose( float transp[r][c], int row, int col)
{
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < col; j++)
        {
            mat[i][j] = transp[j][i] ;
        }
    }
}

/* Output function */

void display(int row, int col)
{
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < col; j++)
        {
            printf("  %f", mat[i][j]);
        }
        printf("\n");
    }
}

/* Output function */

void display_o(float transp[r][c], int row, int col)
{
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < col; j++)
        {
            printf("  %f", transp[i][j]);
        }
        printf("\n");
    }
}

/* Input function */

void input( float transp[r][c], int row, int col)
{
    for(i = 0 ; i< row; i++)
    {
        for(j = 0 ;  j<col; j++)
        {
            printf("Input Value for : %d: %d: ", i+1,j+1);
            scanf(" %f", &value);
            transp[i][j] = value;
        }
    }
}

/* Test  for Symmetry */

int  Symmetry_Matrix(float transp[r][c], int row, int col)
{
    int status = 0;
    for(i = 0; i < row; i++)
    {
        for(j = 0; j<col; j++)
            if(mat[i][j] != transp[i][j])
                status = 1;
    }
    return(status);
}

/* main function */

void main()
{
    int status;
    int row, col;
    float transp[10][10];
    printf("\n Input number of rows:");
    scanf("%d", &row);
    printf("\n Input number of cols:");
    scanf("%d", &col);
    input(transp, row, col);
    printf("\n Entered Matrix is as follows:\n");
    display_o(transp, row, col);
    transpose(transp, col, row);
    printf(" \n Transpose of above matrix is as follows:\n");
    display(col,row);
    status = Symmetry_Matrix(transp, row, col);
    if(status)
        printf("\n Matrix is not symmetric ");
    else
        printf("\n Matrix is Symmetric ");
}

Read More...

Singularity of a matrix using Cramer's Rule in C

/* Testing singularity of a matrix  */

#include<stdio.h>
int i, j;
float mat[10][10];
float mat1[10][10];
void display( int, int);
void input( int, int);
float Singular_Matrix(int, int);

/* Output function */

void display( int row, int col)
{
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < col; j++)
        {
            printf("  %f", mat[i][j]);
        }
        printf("\n");
    }
}

/* Input function */
void input( int row, int col)
{
    for(i = 0 ; i< row; i++)
    {
        for(j = 0 ;  j<col; j++)
        {
            printf("Input Value for : %d: %d: ", i+1, j+1);
            scanf("%f", &mat[i][j]);
        }
    }
}

/* Find Determinant using Cramer's rule */

float Singular_Matrix( int row1, int col1)
{
    int i, j, k, l;
    float sum=0, psum=0, partial=0, nsum=0;
    if(row1 == col1)
    {
        printf("\n Number rows  = Number of cols");
        printf("\n Singular Test is possible\n");

        if(row1 < 3)
        {
            sum = mat[0][0]*mat[1][1] - mat[0][1]*mat[1][0];
            return(sum);
        }
        else
        {
            for(k = 0; k <row1; k++)
                for(j = 0; j < row1; j++)
                    mat1[k][j] = mat[k][j];

            for(k = 0; k <row1; k++)
                for(j = row1; j < (2*row1-1); j++)
                    mat1[k][j] = mat1[k][j-row1];

            for(l = 0; l <row1; l++)
            {
                partial = 1;
                for(i = 0; i <row1; i++)
                {
                    partial *= mat1[i][i+l];
                }
                psum += partial;
            }

            for(l = row1-1; l < ( 2*row1 -1); l++)
            {
                partial = 1;
                for(i =0; i < row1; i++)
                {
                    partial *=mat1[i][l-i];
                }
                nsum += partial;
            }
            sum = psum - nsum ;
            return(sum);
        }
    }

    else
        printf("\n Check about singularity is not possible");

    return 0;
}

/* main function */

void main()
{
    float Determinant;
    int r,c;
    printf("\n Input the number of rows:");
    scanf("%d", &r);
    printf(" Input the number of cols:");
    scanf("%d", &c);
    input(r, c);
    printf("\n Entered Two Dimensional array is as follows:\n");
    display(r, c);
    Determinant = Singular_Matrix(r, c);
    printf("\n Determinant is : %d", Determinant);

    if(Determinant == 0)
        printf("\n The Above matrix is Singular");
    else
        printf("\n Above matrix is not singular");
}

Read More...

Replace a sub-string in string in C Programming

/* Replace a sub-string in a string */

#include<stdio.h>
#include<string.h>  
int index_str1,index_str2,k;
int c[100];  
int str_rep(char *, char *, int *);
 
/* Function str that finds first location of the sub-string */
 
int str_rep(char *s1, char *s2, int c[])
{
    int count = 0;
    int l =0;
    int j, i = 0;
    char s3[]= "Los Angeles";
    for(index_str1 = 0;  s1[index_str1]; index_str1++)
        for(index_str2=index_str1, k = 0; s1[index_str2] == s2[k]&&s1[index_str1]; index_str2++, k++)
            if(!s2[k+1])
            {
                count ++;
                c[l++] = index_str1;
                for(j = index_str1; j < strlen(s3)+index_str1;  j++)
                    s1[j] = s3[i++];
                printf("\n %s ", s1);
            }
 
    return(count);
}
 
/* Function main */
 
void main()
{
    char *s;
    int c[100];
    char s1[]="Michael Jackson";
    char s2[] ="Jackson";
    int count;
    str_rep(s1, s2,c);
} 

Read More...

Using Divide & Conquer Rule in C

/* Divide and  Conquer */
/* Find minimum and maximum from a given series of numbers */


int min1, max1;
void div_con(int *, int, int *, int *);

void div_con( int list[], int n, int *min, int *max)
{
    if( n == 1)
        *min = *max = list[0];
    else
        if( n == 2)
        {
            if(list[0] < list[1])
            {
                *min = list[0];
                *max = list[1];
            }
            else
            {
                *min = list[1];
                *max = list[0];
            }
        }
        else
        {
            div_con(list, n/2, min,  max);
            div_con(list+ n/2, n - n/2, &min1, &max1);
            if( min1 < *min)
                *min = min1;
            if( max1 > *max)
                *max =  max1;
        }
}

/*  Function main */

void main()
{
    int i;
    int *min, *max;
    int list[size];
    int number;
    printf("\n Input the number of elements in the list :");
    scanf(" %d", &number);

    printf("\n Input the list elements:\n");
    for(i = 0; i < number; i++)
    {
        scanf("%d", &list[i]);
    };

    printf("\n Min and Max are :");
    div_con( list, number, min, max);
    printf("\n Mimimum = %d", *min);
    printf("\n Maximum = %d", *max);
}

Read More...

Merge Sort & External Sort in C

/* merge sort and external sort */
/* EXTMRG.C */
#include 
#include 
#include 

/****************************
 * implementation dependent *
 ****************************/

/* template for workfiles (8.3 format) */
#define FNAME "_sort%03d.dat"
#define LNAME 13

/* comparison operators */
#define compLT(x,y) (x < y)
#define compGT(x,y) (x > y)

/* define the record to be sorted here */
#define LRECL 100
typedef int keyType;
typedef struct recTypeTag {
    keyType key;                                /* sort key for record */
    #if LRECL
        char data[LRECL-sizeof(keyType)];       /* other fields */
    #endif
} recType;

/******************************
 * implementation independent *
 ******************************/

typedef enum {false, true} bool;

typedef struct tmpFileTag {
    FILE *fp;                   /* file pointer */
    char name[LNAME];           /* filename */
    recType rec;                /* last record read */
    int dummy;                  /* number of dummy runs */
    bool eof;                   /* end-of-file flag */
    bool eor;                   /* end-of-run flag */
    bool valid;                 /* true if rec is valid */
    int fib;                    /* ideal fibonacci number */
} tmpFileType;

static tmpFileType **file;      /* array of file info for tmp files */
static int nTmpFiles;           /* number of tmp files */
static char *ifName;            /* input filename */
static char *ofName;            /* output filename */

static int level;               /* level of runs */
static int nNodes;              /* number of nodes for selection tree */

void deleteTmpFiles(void) {
    int i;

    /* delete merge files and free resources */
    if (file) {
        for (i = 0; i < nTmpFiles; i++) {
            if (file[i]) {
                if (file[i]->fp) fclose(file[i]->fp);
                if (*file[i]->name) remove(file[i]->name);
                free (file[i]);
            }
        }
        free (file);
    }
}

void termTmpFiles(int rc) {

    /* cleanup files */
    remove(ofName);
    if (rc == 0) {
        int fileT;

        /* file[T] contains results */
        fileT = nTmpFiles - 1;
        fclose(file[fileT]->fp); file[fileT]->fp = NULL;
        if (rename(file[fileT]->name, ofName)) {
            perror("io1");
            deleteTmpFiles();
            exit(1);
        }
        *file[fileT]->name = 0;
    }
    deleteTmpFiles();
}

void cleanExit(int rc) {

    /* cleanup tmp files and exit */
    termTmpFiles(rc);
    exit(rc);
}

void *safeMalloc(size_t size) {
    void *p;

    /* safely allocate memory and initialize to zero */
    if ((p = calloc(1, size)) == NULL) {
        printf("error: malloc failed, size = %d\n", size);
        cleanExit(1);
    }
    return p;
}

void initTmpFiles(void) {
    int i;
    tmpFileType *fileInfo;

    /* initialize merge files */
    if (nTmpFiles < 3) nTmpFiles = 3;
    file = safeMalloc(nTmpFiles * sizeof(tmpFileType*));
    fileInfo = safeMalloc(nTmpFiles * sizeof(tmpFileType));
    for (i = 0; i < nTmpFiles; i++) {
        file[i] = fileInfo + i;
        sprintf(file[i]->name, FNAME, i);
        if ((file[i]->fp = fopen(file[i]->name, "w+b")) == NULL) {
            perror("io2");
            cleanExit(1);
        }
    }
}

recType *readRec(void) {

    typedef struct iNodeTag {   /* internal node */
        struct iNodeTag *parent;/* parent of internal node */
        struct eNodeTag *loser; /* external loser */
    } iNodeType;

    typedef struct eNodeTag {   /* external node */
        struct iNodeTag *parent;/* parent of external node */
        recType rec;            /* input record */
        int run;                /* run number */
        bool valid;             /* input record is valid */
    } eNodeType;

    typedef struct nodeTag {
        iNodeType i;            /* internal node */
        eNodeType e;            /* external node */
    } nodeType;

    static nodeType *node;      /* array of selection tree nodes */
    static eNodeType *win;      /* new winner */
    static FILE *ifp;           /* input file */
    static bool eof;            /* true if end-of-file, input */
    static int maxRun;          /* maximum run number */
    static int curRun;          /* current run number */
    iNodeType *p;               /* pointer to internal nodes */
    static bool lastKeyValid;   /* true if lastKey is valid */
    static keyType lastKey;     /* last key written */

    /* read next record using replacement selection */

    /* check for first call */
    if (node == NULL) {
        int i;

        if (nNodes < 2) nNodes = 2;
        node = safeMalloc(nNodes * sizeof(nodeType));
        for (i = 0; i < nNodes; i++) {
            node[i].i.loser = &node[i].e;
            node[i].i.parent = &node[i/2].i;
            node[i].e.parent = &node[(nNodes + i)/2].i;
            node[i].e.run = 0;
            node[i].e.valid = false;
        }
        win = &node[0].e;
        lastKeyValid = false;

        if ((ifp = fopen(ifName, "rb")) == NULL) {
            printf("error: file %s, unable to open\n", ifName);
            cleanExit(1);
        }
    }

    while (1) {

        /* replace previous winner with new record */
        if (!eof) {
            if (fread(&win->rec, sizeof(recType), 1, ifp) == 1) {
                if ((!lastKeyValid || compLT(win->rec.key, lastKey))
                && (++win->run > maxRun))
                    maxRun = win->run;
                win->valid = true;
            } else if (feof(ifp)) {
                fclose(ifp);
                eof = true;
                win->valid = false;
                win->run = maxRun + 1;
            } else {
                perror("io4");
                cleanExit(1);
            } 
        } else {
            win->valid = false;
            win->run = maxRun + 1;
        }

        /* adjust loser and winner pointers */
        p = win->parent;
        do {
            bool swap;
            swap = false;
            if (p->loser->run < win->run) {
                swap = true;
            } else if (p->loser->run == win->run) {
                if (p->loser->valid && win->valid) {
                    if (compLT(p->loser->rec.key, win->rec.key))
                        swap = true;
                } else {
                    swap = true;
                }
            }
            if (swap) {
                /* p should be winner */
                eNodeType *t;

                t = p->loser;
                p->loser = win;
                win = t;
            }
            p = p->parent;
        } while (p != &node[0].i);

        /* end of run? */
        if (win->run != curRun) {
            /* win->run = curRun + 1 */
            if (win->run > maxRun) {
                /* end of output */
                free(node);
                return NULL;
            }
            curRun = win->run;
        }

        /* output top of tree */
        if (win->run) {
            lastKey = win->rec.key;
            lastKeyValid = true;
            return &win->rec;
        }
    }
}

void makeRuns(void) {
    recType *win;       /* winner */
    int fileT;          /* last file */
    int fileP;          /* next to last file */
    int j;              /* selects file[j] */


    /* Make initial runs using replacement selection.
     * Runs are written using a Fibonacci distintbution.
     */

    /* initialize file structures */
    fileT = nTmpFiles - 1;
    fileP = fileT - 1;
    for (j = 0; j < fileT; j++) {
        file[j]->fib = 1;
        file[j]->dummy = 1;
    }
    file[fileT]->fib = 0;
    file[fileT]->dummy = 0;

    level = 1;
    j = 0;


    win = readRec();
    while (win) {
        bool anyrun;

        anyrun = false;
        for (j = 0; win && j <= fileP; j++) {
            bool run;

            run = false;
            if (file[j]->valid) {
                if (!compLT(win->key, file[j]->rec.key)) {
                    /* append to an existing run */
                    run = true;
                } else if (file[j]->dummy) {
                    /* start a new run */
                    file[j]->dummy--;
                    run = true;
                }
            } else {
                /* first run in file */
                file[j]->dummy--;
                run = true;
            }

            if (run) {
                anyrun = true;

                /* flush run */
                while(1) {
                    if (fwrite(win, sizeof(recType), 1, file[j]->fp) != 1) {
                        perror("io3");
                        cleanExit(1);
                    }
                    file[j]->rec.key = win->key;
                    file[j]->valid = true;
                    if ((win = readRec()) == NULL) break;
                    if (compLT(win->key, file[j]->rec.key)) break;
                }
            }
        }

        /* if no room for runs, up a level */
        if (!anyrun) {
            int t;
            level++;
            t = file[0]->fib;
            for (j = 0; j <= fileP; j++) {
                file[j]->dummy = t + file[j+1]->fib - file[j]->fib;
                file[j]->fib = t + file[j+1]->fib; 
            }
        }
    }
}

void rewindFile(int j) {
    /* rewind file[j] and read in first record */
    file[j]->eor = false;
    file[j]->eof = false;
    rewind(file[j]->fp);
    if (fread(&file[j]->rec, sizeof(recType), 1, file[j]->fp) != 1) {
        if (feof(file[j]->fp)) {
            file[j]->eor = true;
            file[j]->eof = true;
        } else {
            perror("io5");
            cleanExit(1);
        }
    }
}

void mergeSort(void) {
    int fileT;
    int fileP;
    int j;
    tmpFileType *tfile;

    /* polyphase merge sort */

    fileT = nTmpFiles - 1;
    fileP = fileT - 1;

    /* prime the files */
    for (j = 0; j < fileT; j++) {
        rewindFile(j);
    }

    /* each pass through loop merges one run */
    while (level) {
        while(1) {
            bool allDummies;
            bool anyRuns;

            /* scan for runs */
            allDummies = true;
            anyRuns = false;
            for (j = 0; j <= fileP; j++) {
                if (!file[j]->dummy) {
                    allDummies = false;
                    if (!file[j]->eof) anyRuns = true;
                }
            }

            if (anyRuns) {
                int k;
                keyType lastKey;

                /* merge 1 run file[0]..file[P] --> file[T] */

                while(1) {
                    /* each pass thru loop writes 1 record to file[fileT] */

                    /* find smallest key */
                    k = -1;
                    for (j = 0; j <= fileP; j++) {
                        if (file[j]->eor) continue;
                        if (file[j]->dummy) continue;
                        if (k < 0 || 
                        (k != j && compGT(file[k]->rec.key, file[j]->rec.key)))
                            k = j;
                    }
                    if (k < 0) break;

                    /* write record[k] to file[fileT] */
                    if (fwrite(&file[k]->rec, sizeof(recType), 1, 
                            file[fileT]->fp) != 1) {
                        perror("io6");
                        cleanExit(1);
                    }

                    /* replace record[k] */
                    lastKey = file[k]->rec.key;
                    if (fread(&file[k]->rec, sizeof(recType), 1,
                            file[k]->fp) == 1) {
                        /* check for end of run on file[s] */
                        if (compLT(file[k]->rec.key, lastKey))
                            file[k]->eor = true;
                    } else if (feof(file[k]->fp)) {
                        file[k]->eof = true;
                        file[k]->eor = true;
                    } else {
                        perror("io7");
                        cleanExit(1);
                    }
                }

                /* fixup dummies */
                for (j = 0; j <= fileP; j++) {
                    if (file[j]->dummy) file[j]->dummy--;
                    if (!file[j]->eof) file[j]->eor = false;
                }

            } else if (allDummies) {
                for (j = 0; j <= fileP; j++)
                    file[j]->dummy--;
                file[fileT]->dummy++;
            }

            /* end of run */
            if (file[fileP]->eof && !file[fileP]->dummy) {
                /* completed a fibonocci-level */
                level--;
                if (!level) {
                    /* we're done, file[fileT] contains data */
                    return;
                }

                /* fileP is exhausted, reopen as new */
                fclose(file[fileP]->fp);
                if ((file[fileP]->fp = fopen(file[fileP]->name, "w+b"))
                        == NULL) {
                    perror("io8");
                    cleanExit(1);
                }
                file[fileP]->eof = false;
                file[fileP]->eor = false;

                rewindFile(fileT);

                /* f[0],f[1]...,f[fileT] <-- f[fileT],f[0]...,f[T-1] */
                tfile = file[fileT];
                memmove(file + 1, file, fileT * sizeof(tmpFileType*));
                file[0] = tfile;

                /* start new runs */
                for (j = 0; j <= fileP; j++)
                    if (!file[j]->eof) file[j]->eor = false;
            }
        }

    }
}


void extSort(void) {
    initTmpFiles();
    makeRuns();
    mergeSort();
    termTmpFiles(0);
}

int main(int argc, char *argv[]) {

    /* command-line:
     *
     *   ext ifName ofName nTmpFiles nNodes
     *
     *   ext in.dat out.dat 5 2000
     *       reads in.dat, sorts using 5 files and 2000 nodes, output to out.dat
     */
    if (argc != 5) {
        printf("%s ifName ofName nTmpFiles nNodes\n", argv[0]);
        cleanExit(1);
    }

    ifName = argv[1];
    ofName = argv[2];
    nTmpFiles = atoi(argv[3]);
    nNodes = atoi(argv[4]);

    printf("extSort: nFiles=%d, nNodes=%d, lrecl=%d\n",
        nTmpFiles, nNodes, sizeof(recType));

    extSort();

    return 0;
}

Read More...

Minimum Cost of a Spanning Tree in C Programming

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
 
struct lledge
{
    int v1, v2 ;
    float cost ;
    struct lledge *next ;
} ;
 
int stree[5] ;
int count[5] ;
int mincost ;
 
struct lledge * kminstree ( struct lledge *, int ) ;
int getrval ( int ) ;
void combine ( int, int ) ;
void del ( struct lledge * ) ;
 
void main( )
{
    struct lledge *temp, *root ;
    int i ;
 
    clrscr( ) ;
 
    root = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;
 
    root -> v1 = 4 ;
    root -> v2 = 3 ;
    root -> cost = 1 ;
    temp = root -> next = ( struct lledge * ) malloc ( sizeof ( struct lledge ) ) ;
 
    temp -> v1 = 4 ;
    temp -> v2 = 2 ;
    temp -> cost = 2 ;
    temp -> next =(struct lledge*)malloc(sizeof(struct lledge)) ;
 
    temp = temp -> next ;
    temp -> v1 = 3 ;
    temp -> v2 = 2 ;
    temp -> cost = 3 ;
    temp -> next =(struct lledge*)malloc(sizeof(struct lledge));
 
    temp = temp -> next ;
    temp -> v1 = 4 ;
    temp -> v2 = 1 ;
    temp -> cost = 4 ;
    temp -> next = NULL ;
 
    root = kminstree ( root, 5 ) ;
 
    for ( i = 1 ; i <= 4 ; i++ )
        printf ( "\nstree[%d] -> %d", i, stree[i] ) ;
    printf ( "\nThe minimum cost of spanning tree is %d", mincost ) ;
    del ( root ) ;
 
    getch( ) ;
}
struct lledge * kminstree ( struct lledge *root, int n )
{
    struct lledge *temp = NULL ;
    struct lledge *p, *q ;
    int noofedges = 0 ;
    int i, p1, p2 ;
 
    for ( i = 0 ; i < n ; i++ )
        stree[i] = i ;
    for ( i = 0 ; i < n ; i++ )
        count[i] = 0 ;
 
    while ( ( noofedges < ( n - 1 ) ) && ( root != NULL ) )
    {
        p = root ;
 
        root = root -> next ;
 
        p1 = getrval ( p -> v1 ) ;
        p2 = getrval ( p -> v2 ) ;
 
        if ( p1 != p2 )
        {
            combine ( p -> v1, p -> v2 ) ;
            noofedges++ ;
            mincost += p -> cost ;
            if ( temp == NULL )
            {
                temp = p ;
                q = temp ;
            }
            else
            {
                q -> next = p ;
                q = q -> next ;
            }
            q -> next = NULL ;
        }
    }
    return temp ;
}
 
int getrval ( int i )
{
    int j, k, temp ;
    k = i ;
    while ( stree[k] != k )
        k = stree[k] ;
    j = i ;
    while ( j != k )
    {
        temp = stree[j] ;
        stree[j] = k ;
        j = temp ;
    }
    return k ;
}
 
void combine ( int i, int j )
{
    if ( count[i] < count[j] )
        stree[i] = j ;
    else
    {
        stree[j] = i ;
        if ( count[i] == count[j] )
            count[j]++ ;
    }
}
 
void del ( struct lledge *root )
{
    struct lledge *temp ;
 
    while ( root != NULL )
    {
        temp = root -> next ;
        free ( root ) ;
        root = temp ;
    }
}

Read More...

Peep Operations on Stack using arrays in C

# include
# include
# include

# define size  100

int top = -1;
int flag = 0;

int stack[100];
int data;

void push(int *, int);
int peep(int *);
void display(int *);

/* Definition of the push function */

void  push(int s[], int d)
{
    if(top ==(size-1))
        flag = 0;
    else
    {
        flag = 1;
        ++top;
        s[top] = d;

    }
}

/* Definition of the peep function */

int peep(int s[])
{
    int i;
    int peeped_element;
    printf("\n Input the information number to which you want access:");
    scanf("%d", &i);

    if(top - i + 1 < 0)
    {
        peeped_element = 0;
        flag = 0;
    }
    else
    {
        flag = 1;
        peeped_element = s[top-i +1];
    }
    return (peeped_element);
}

/* Definition of the display function */
void display(int s[])
{
    int i;
    if(top == -1)
    {
        printf("Stack is empty");
    }
    else
    {
        for(i = top; i>=0; --i)
            printf(" %d  ", s[i]);
    }
}

/* Function main */

void main()
{
    int  data;
    char choice;
    int q = 0;
    int top = -1;

    do
    {
        printf(" \nPush->i Peep->p Quit->q:");
        printf("\nInput the choice : ");
        do
        {
            choice = getchar();
            choice =tolower(choice);
        }while(strchr("ipq",choice)==NULL);
        printf("Your choice is: ", choice);

        switch(choice)
        {
        case 'i' :
            printf("\n Input the element to push:");
            scanf("%d", &data);
            push(stack, data);
            if(flag)
            {
                printf("\n After inserting ");
                display(stack);
                if(top == (size-1))
                    printf("\n Stack is full");
            }
            else
                printf("\n Stack overflow after pushing");
            break;

        case 'p' : 
            data = peep(stack);
            if(flag)
            {
                printf("\n Data is peeped: %d", data);
                printf("\n Stack is as follows:\n");

                display(stack);
            }
            else
                printf("\n Stack underflow");
            break;
        case 'q': 
            q = 1;
        }
    } while(!q);
}

Read More...

Use of Polish notations in C Programming

/* polish.c */

  # include<malloc.h>
  # include<string.h>
  # include<stdlib.h> 
  # define size 5 
          void push(char *, char , int *);
          char pop( char *, int *);
          int letter_match(char );
          void push(char *, int *, char );
          int match_number(char );
          int match_operator(char );
          int operator_precedence(char );
          void polish_fun(char *, char *, int *);
          void error(int, int );

/* Push function */

    void push( char s[], int *s_pointer, char ch)
       {
         if(*s_pointer == size)
           {
         printf("\n Stack overflow");
           }
           else
           {
         s[++(*s_pointer)] = ch ;
           }
     }

/* Pop function */

  char pop( char s[], int *s_pointer)
       {
     if(*s_pointer < 0)
      {
       printf("\n Stack underflow");
       return 0;
      }
      else
      {
       return(s[(*s_pointer) -- ]);
      }
      }

/* Definition of function */

  int letter_match(char ch)
        {
          return(((ch>='A')&&(ch<='Z')) || ((ch>='a')&&(ch <= 'z')));
        }

/* Definition of the function */

 int  match_number( char ch)
      {
         return((ch >='0') && (ch<='9'));
      }

/* Definition of the function */

  int match_operator(char ch)
      {
      int i;
        char operator[6];

          operator[0] = '+';
          operator[1] = '-';
          operator[2] = '*';
          operator[3] = '/';
          operator[4] = '%';

         for(i = 0; i < 5; i ++)
         {
            if(ch == operator[i])
              return(1);
             else
              return(0);
         }
       }

/* Definition of the function */

  int operator_precedence(char ch)
     {
       int preced;
       switch(ch)
      {
        case '(' : preced = 0; break;
        case '+' :
        case '-' : preced = 1; break;
        case '*' :
        case '/' : preced = 2; break;
        case '%' : preced = 3; break;
      }
      return(preced);
     }

/* Definition of the function */

   void polish_fun(char infix[], char suffix[], int *err)
       {
     char ch, last =')';
     char stack[size];
     int i = 0;
     int s_pointer = -1;
     int bracket = 1;
     int ifp,sfp = 0;

     push(stack, &s_pointer,'(');

       do
         {
           while(infix[i] ==' ')
           ++i;
           ifp = i;
           ch = infix[ifp];
   switch(ch)
   {
   case '(': if(letter_match(last)||match_number(last) || (last == ')'))
          {
         *err = 1;
         error(1,ifp+1);
          }
          ++bracket ;
          push(stack,&s_pointer,ch);
          break;
    case '+':
    case '-':
    case '*':
    case '/':
    case '%':

      if(match_operator(last)||(!letter_match(last)&& !match_number(last)&&(last!=')')))
     {
       *err = 1;
       error(2,ifp+1);
     }

     while(operator_precedence(stack[s_pointer] >=operator_precedence(ch))
       suffix[sfp++]=pop(stack,&s_pointer);
       push(stack,&s_pointer,ch);
       break;

    case ')':
      if(match_operator(last)
    { *err = 1;
       error(2,ifp+1);
    }

    if(last == '(')
       {
          *err = 1;
          error(2,ifp+1);
          error(1,ifp+1);
       }

    while(stack[s_pointer] != '(' && s_pointer > 0)
      suffix[sfp++] = pop(stack, &s_pointer);
      --s_pointer;
      --bracket;
      break;

    case  ' ': while(infix[ifp+1] == ' ' && !infix[ifp])
         ++ifp;
         break;
    default:
          if(letter_match(last)||math_number(last))
           {
          *err = 1;
          error(1,ifp+1);
          error(5,ifp+1);
           }

           if (letter_match(ch))
          suffix[sfp++] = infix[ifp];
          else
           if (match_number(ch))
             {
               while(match_number(infix[ifp]))
              suffix[sfp++] = infix[ifp++];
              --ifp;
              }

              else error(4,ifp+1);
           } /* end of switch */

    last = infix[ifp];
    ++ifp;
    i = ifp;
    } while(infix[ifp]);

    suffix[sfp] = 0;
    if(bracket)
      {
         *err =1;
         error(3,ifp-1);
       }
    }
    break;

/* Definition of the function */

    void input(char infix[])
       {
         int i = 0;
         printf("\nInput the infix expression: ");
         gets(infix);
         i = strlen(infix);
         printf("\n Entered expression is :");
         gets(infix);
         infix[i] = ')';
         infix[i+1] = '\0';
        }

 /* Definition of the function */

 void error(int n, int ifp)
    {
       switch(n)
       {
         case 1: printf("\n Error->1:Missing operator");
         case 2: printf("\n Error->2:Missing operand");
         case 3: printf("\n Error->3:Mismatched parentheses");
         case 4: printf("\n Error->4:Illegal character is expression");
         case 5: printf("\n Error->5:Multicharacter variable");
        }
     printf("\n Position of the cursor: %d", ifp);
     }

/* Definition of the function main */

    void main()
       {
         int err, ans;
         char infix[size],suffix[size];
         err = 0;
         input(infix);
         polish_fun(infix,suffix, &err);
         if(!err)
           {
         printf("\n The suffix form of the given, expression is: ");
         puts(suffix);
           }
       }

Read More...

Deleting a node from a Binary Tree in C Programming

/* Deleting in Binary Tree */
/* DELET_BT.C */

# include<stdio.h>
# include<malloc.h>

struct NODE
{
    int Info;
    struct NODE *Left_Child;
    struct NODE *Right_Child;
};

int depth;
void Output (struct NODE *, int );
struct NODE *Delet_Node (struct NODE *, int );
struct NODE *Create_Tree (int , struct NODE *);
struct NODE * DELE(struct NODE *, struct NODE *);

/* Output function */

void Output(struct NODE *T, int Level)
{
    int i;
    if (T)
    {
        Output(T->Right_Child, Level+1);
        printf("\n");
        for (i = 0; i < Level; i++)
            printf("  ");
        printf("%c", T->Info);
        Output(T->Left_Child, Level+1);
    }
}

/* Delete a node in the binary tree */

struct NODE * DELE(struct NODE *Node1, struct NODE *Node)
{
    struct NODE *DNode;
    if (Node1->Right_Child != NULL)
        Node1->Right_Child = DELE(Node1->Right_Child, Node);
    else
    {
        DNode = Node1;
        Node->Info = Node1->Info;
        Node1 = Node1->Left_Child;
        free(DNode);
    }
    return (Node1);
}

/* Deletion in binary tree */

struct NODE * Delet_Node (struct NODE *Node, int Info)
{
    struct NODE *Temp;

    if (Node == NULL)
    {
        printf("\n Information does not exist in the above tree");
        return (Node);
    }
    else
    {
        if (Info < Node->Info )
            Node->Left_Child = Delet_Node (Node->Left_Child, Info);
        else
            if (Info > Node->Info )

                Node->Left_Child = Delet_Node (Node->Right_Child, Info);
            else
            {
                Temp = Node;
                if (Temp->Right_Child == NULL)
                {
                    Node = Temp->Left_Child;
                    free(Temp);
                }
                else
                    if (Temp->Left_Child == NULL)
                    {
                        Node = Temp->Right_Child;
                        free(Temp);
                    }
                    else
                        Temp->Left_Child = DELE(Temp->Left_Child, Temp);
            }
    }
    return(Node);
}

/* Create binary tree */

struct NODE *  Create_Tree (int Info, struct NODE *Node)
{
    if (Node == NULL)
    {
        Node = (struct NODE *) malloc(sizeof(struct NODE));
        Node->Info = Info;
        Node->Left_Child = NULL;
        Node->Right_Child = NULL;
        return (Node);
    }

    /* Test for the left child */

    if (Info < Node->Info)

        Node->Left_Child = Create_Tree (Info, Node->Left_Child);

    else

        /* Test for the right child */

        if (Info >= Node->Info)

            Node->Right_Child = Create_Tree (Info, Node->Right_Child);
    return(Node);
}

/* Function main */

void main()
{
    int Number = 0;
    int Info ;
    char choice;
    int depth;
    struct NODE *T = (struct NODE *) malloc(sizeof(struct NODE));
    T = NULL;
    printf("\n Input choice 'b' to break:");
    choice = getchar();

    while(choice != 'b')
    {
        fflush(stdin);
        printf("\n Input information of the node: ");
        scanf("%c", &Info);
        T = Create_Tree(Info, T);
        Number++;
        fflush(stdin);
        printf("\n Input choice 'b' to break:");
        choice = getchar();
    }
    fflush(stdin);
    printf("\n Number of elements in the list is %d", Number);
    printf("\n Tree is \n");
    Output(T, 1);

    printf("\n Input the information to which want remove from the above tree: ");
    scanf("%c", &Info);

    T = Delet_Node(T, Info);
    printf("\n Tree after deletion of a node: ");
    Output(T, 1);
} 

Read More...

How to create a Tree in C Programming ?

/* Create TREE */

# include<stdio.h>
# include<malloc.h>
struct NODE
{
    int Info;
    struct NODE *Left_Child;
    struct NODE *Right_Child;
};
struct NODE *Create_Tree (int , struct NODE *);
void Output(struct NODE *, int );

/* Function to create a tree */

struct NODE * Create_Tree (int Info, struct NODE *Node)
{
    if (Node == NULL)
    {
        Node = (struct NODE *) malloc( sizeof(struct NODE ));
        Node->Info = Info;
        Node->Left_Child = NULL;
        Node->Right_Child = NULL;
        return (Node);
    }

    /* Test for the left child */
    if (Node->Info >= Info )
        Node->Left_Child = Create_Tree (Info, Node->Left_Child);
    else

        /* Set all the rest of the elements as right child */

        Node->Right_Child = Create_Tree (Info, Node->Right_Child);
    return(Node);
}

/* Output function */

void  Output(struct NODE *T, int Level)
{
    int i;
    if (T)
    {
        Output(T->Right_Child, Level+1);
        printf("\n ");
        for (i = 0; i < Level; i++)
            printf("   ");
        printf("%d", T->Info);
        printf("\n");
        Output(T->Left_Child, Level+1);
    }
}

/* Function main */

void main()
{
    int Info ;
    char choice;
    struct NODE *T = (struct NODE *) malloc(sizeof(struct NODE *));
    T = NULL;
    printf("\n Input choice 'b' to break:");
    choice = getchar();
    while(choice != 'b')
    {
        printf("\n Input information of the node: ");
        scanf("%d", &Info);
        T = Create_Tree (Info, T);
        printf("\n Tree is ");
        Output(T, 1);
        printf("\n Input choice 'b' to break:");
        choice = getchar();
    }
}

Read More...

Create a Red-Black Tree in C programming

/* red-black tree */

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


/* implementation dependend declarations */
typedef enum {
    STATUS_OK,
    STATUS_MEM_EXHAUSTED,
    STATUS_DUPLICATE_KEY,
    STATUS_KEY_NOT_FOUND
} statusEnum;

typedef int keyType;            /* type of key */

/* user data stored in tree */
typedef struct {
    int stuff;                  /* optional related data */
} recType;

#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/* implementation independent declarations */
/* Red-Black tree description */
typedef enum { BLACK, RED } nodeColor;

typedef struct nodeTag {
    struct nodeTag *left;       /* left child */
    struct nodeTag *right;      /* right child */
    struct nodeTag *parent;     /* parent */
    nodeColor color;            /* node color (BLACK, RED) */
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
} nodeType;

#define NIL &sentinel           /* all leafs are sentinels */
nodeType sentinel = { NIL, NIL, 0, BLACK, 0};

nodeType *root = NIL;               /* root of Red-Black tree */

void rotateLeft(nodeType *x) {

   /**************************
    *  rotate node x to left *
    **************************/

    nodeType *y = x->right;

    /* establish x->right link */
    x->right = y->left;
    if (y->left != NIL) y->left->parent = x;

    /* establish y->parent link */
    if (y != NIL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->left)
            x->parent->left = y;
        else
            x->parent->right = y;
    } else {
        root = y;
    }

    /* link x and y */
    y->left = x;
    if (x != NIL) x->parent = y;
}

void rotateRight(nodeType *x) {

   /****************************
    *  rotate node x to right  *
    ****************************/

    nodeType *y = x->left;

    /* establish x->left link */
    x->left = y->right;
    if (y->right != NIL) y->right->parent = x;

    /* establish y->parent link */
    if (y != NIL) y->parent = x->parent;
    if (x->parent) {
        if (x == x->parent->right)
            x->parent->right = y;
        else
            x->parent->left = y;
    } else {
        root = y;
    }

    /* link x and y */
    y->right = x;
    if (x != NIL) x->parent = y;
}

void insertFixup(nodeType *x) {

   /*************************************
    *  maintain Red-Black tree balance  *
    *  after inserting node x           *
    *************************************/

    /* check Red-Black properties */
    while (x != root && x->parent->color == RED) {
        /* we have a violation */
        if (x->parent == x->parent->parent->left) {
            nodeType *y = x->parent->parent->right;
            if (y->color == RED) {

                /* uncle is RED */
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                /* uncle is BLACK */
                if (x == x->parent->right) {
                    /* make x a left child */
                    x = x->parent;
                    rotateLeft(x);
                }

                /* recolor and rotate */
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateRight(x->parent->parent);
            }
        } else {

            /* mirror image of above code */
            nodeType *y = x->parent->parent->left;
            if (y->color == RED) {

                /* uncle is RED */
                x->parent->color = BLACK;
                y->color = BLACK;
                x->parent->parent->color = RED;
                x = x->parent->parent;
            } else {

                /* uncle is BLACK */
                if (x == x->parent->left) {
                    x = x->parent;
                    rotateRight(x);
                }
                x->parent->color = BLACK;
                x->parent->parent->color = RED;
                rotateLeft(x->parent->parent);
            }
        }
    }
    root->color = BLACK;
}

statusEnum insert(keyType key, recType *rec) {
    nodeType *current, *parent, *x;

   /***********************************************
    *  allocate node for data and insert in tree  *
    ***********************************************/

    /* find future parent */
    current = root;
    parent = 0;
    while (current != NIL) {
        if (compEQ(key, current->key)) 
            return STATUS_DUPLICATE_KEY;
        parent = current;
        current = compLT(key, current->key) ?
            current->left : current->right;
    }

    /* setup new node */
    if ((x = malloc (sizeof(*x))) == 0)
        return STATUS_MEM_EXHAUSTED;
    x->parent = parent;
    x->left = NIL;
    x->right = NIL;
    x->color = RED;
    x->key = key;
    x->rec = *rec;

    /* insert node in tree */
    if(parent) {
        if(compLT(key, parent->key))
            parent->left = x;
        else
            parent->right = x;
    } else {
        root = x;
    }

    insertFixup(x);

    return STATUS_OK;
}

void deleteFixup(nodeType *x) {

   /*************************************
    *  maintain Red-Black tree balance  *
    *  after deleting node x            *
    *************************************/

    while (x != root && x->color == BLACK) {
        if (x == x->parent->left) {
            nodeType *w = x->parent->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateLeft (x->parent);
                w = x->parent->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rotateRight (w);
                    w = x->parent->right;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->right->color = BLACK;
                rotateLeft (x->parent);
                x = root;
            }
        } else {
            nodeType *w = x->parent->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->parent->color = RED;
                rotateRight (x->parent);
                w = x->parent->left;
            }
            if (w->right->color == BLACK && w->left->color == BLACK) {
                w->color = RED;
                x = x->parent;
            } else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    rotateLeft (w);
                    w = x->parent->left;
                }
                w->color = x->parent->color;
                x->parent->color = BLACK;
                w->left->color = BLACK;
                rotateRight (x->parent);
                x = root;
            }
        }
    }
    x->color = BLACK;
}

statusEnum delete(keyType key) {
    nodeType *x, *y, *z;

   /*****************************
    *  delete node z from tree  *
    *****************************/

    /* find node in tree */
    z = root;
    while(z != NIL) {
        if(compEQ(key, z->key)) 
            break;
        else
            z = compLT(key, z->key) ? z->left : z->right;
    }
    if (z == NIL) return STATUS_KEY_NOT_FOUND;

    if (z->left == NIL || z->right == NIL) {
        /* y has a NIL node as a child */
        y = z;
    } else {
        /* find tree successor with a NIL node as a child */
        y = z->right;
        while (y->left != NIL) y = y->left;
    }

    /* x is y's only child */
    if (y->left != NIL)
        x = y->left;
    else
        x = y->right;

    /* remove y from the parent chain */
    x->parent = y->parent;
    if (y->parent)
        if (y == y->parent->left)
            y->parent->left = x;
        else
            y->parent->right = x;
    else
        root = x;

    if (y != z) {
        z->key = y->key;
        z->rec = y->rec;
    }


    if (y->color == BLACK)
        deleteFixup (x);

    free (y);
    return STATUS_OK;
}

statusEnum find(keyType key, recType *rec) {

   /*******************************
    *  find node containing data  *
    *******************************/

    nodeType *current = root;
    while(current != NIL) {
        if(compEQ(key, current->key)) {
            *rec = current->rec;
            return STATUS_OK;
        } else {
            current = compLT (key, current->key) ?
                current->left : current->right;
        }
    }
    return STATUS_KEY_NOT_FOUND;
}


void main(int argc, char **argv) {
    int maxnum, ct, n;
    recType rec;
    keyType key;
    statusEnum status;
    maxnum = atoi(argv[1]);
    printf("maxnum = %d\n", maxnum);
    for (ct = maxnum; ct; ct--) {
        key = rand() % 9 + 1;
        if ((status = find(key, &rec)) == STATUS_OK) {
            status = delete(key);
            if (status) printf("fail: status = %d\n", status);
        } else {
            status = insert(key, &rec);
            if (status) printf("fail: status = %d\n", status);
        }
    }
}

Read More...

How to implement Regula Falsi Method in C Programming ?

    #include<stdio.h>
    #include<math.h>
    float f(float x)
    {
        return (x*x*x)-(3*x)+1;
    }
    main()
    {
        printf("\nProgram to implement Regula-Falsi method : \n");
        float a,b,m;
        int i,c=1;
        printf("\nEnter the lower and upper approximation root : \n");
        scanf("%f%f",&a,&b);
        if(f(b)>f(a))
        {
            m=a;
            a=b;
            b=m;
        }
        if((f(a)>0 && f(b)>0)||(f(a)<0 && f(b)<0))
        {
            printf("\nNo root present...");
            return;
        }
        while((fabs(a-b)>0.001)&& c!=40)
        {
            c++;
            m=(a*f(b)-b*f(a))/(f(b)-f(a));
            if(f(m)>0)    b=m;
            else        a=m;
        }
        printf("\nRoot = %f\n",m);
    } 

Read More...

How to implement Bisection Method in C Programming ?

 #include<stdio.h>
    #include<math.h>
    float f(float x)
    {
        return (x*x*x)-(3*x)+1;
    }
    main()
    {
        printf("\nProgram to implement Bisection method : \n");
        float a,b,m;
        int i,c=1;
        printf("\nEnter the lower and upper approximation root : \n");
        scanf("%f%f",&a,&b);
        if(f(b)<f(a))
        {
            m=a;
            a=b;
            b=m;
        }
        if((f(a)>0 && f(b)>0)||(f(a)<0 && f(b)<0))
        {
            printf("\nNo root present...");
            return;
        }
        while((fabs(a-b)>0.001)&& c!=40)
        {
            c++;
            m=(a+b)/2;
            if(f(m)>0)    b=m;
            else        a=m;
        }
        printf("\nRoot = %f\n",a);
    } 

Read More...

How to implement Newton's Divided Difference Interpolation in C Programming ?

  #include<stdio.h>
    main()
    {
        int i,j,n,k;
        float X[10],Y[10],d[10][10],x,t,y=0,s=1;
        printf("\nNewton's Divided Interpolation : \n");
        printf("\nEnter the value of n : ");
        scanf("%d",&n);
        printf("\nEnter the value of X[i] and Y[i] : \n");
        printf("\nX[i]\tY[i]\n");
        for(i=0;i<n;i++)
            scanf("%f%f",&X[i],&Y[i]);
        printf("\nEnter the value of x  : ");
        scanf("%f",&x);
        for(j=0;j<n;j++)
            for(i=0;i<n-j;i++)
                d[i][j]=0;
        for(i=0;i<n;i++)
            d[i][0]=Y[i];
        for(j=0;j<n;j++)
            for(i=0;i<n-j;i++)
            {
                if(j==0)    continue;                
                d[i][j]=(d[i+1][j-1]-d[i][j-1])/(X[i+j]-X[i]);
            }        
        y=Y[0];
        for(k=1;k<n;k++)
        {
            s=s*(x-X[k-1]);
            t=s*d[0][k];
            y=y+t;
        }
        printf("\nAnswer = %f\n\n",y);
    }

Read More...

Implement Orthogonal Matrix in C Programming

# include<stdio.h>
# include<stdlib.h>
# define row 10
# define col 10
int i, j, k;
int row1, col1;
float mat1[row][col];
float mat2[row][col];
float mat_res[row][col];

/* function to multiply matrix with its transpose */

void mat_mult( float mat1[row][col], int row1, int col1,float mat_res[row][col])
{
    int flag ;
    if(col1 == row1)
    {
        printf("\n Multiplication is possible and Result is as follows\n");
        for(i = 0; i<row1; i++)
            for(j = 0; j<col1; j++)
            {
                mat_res[i][j] = 0;
                for(k = 0; k < col1; k ++)
                {
                    mat_res[i][j] += mat1[i][k] * mat2[k][j];
                }
            }
        display(mat_res,row1,col1);
    }
    else
    {
        printf("\n Multiplication is not possible");
        exit(0);
    }
    for(i = 0 ; i< row1; i++)
    {
        for(j = 0; j < col1; j++)
        {
            if(((int)mat_res[i][i] == 1) && ((int ) mat_res[i][j] == 0))
                flag = 1;
        }
    }
    if( flag == 1)
    {
        printf("\n Matrix X * Transpose of X = Identity Matrix");
        printf("\n The given Matrix is Orthogonal");
    }
    else
    {
        printf("\n Matrix X * Transpose of X != Identity Matrix");
        printf("\n The given Matrix is not Orthogonal");
    }
}
void display(float mat[row][col], int r, int c )
{
    printf("\n");
    for( i = 0; i < r; i++)
    {
        for( j = 0; j < c; j++)
        {
            printf("   %f", mat[i][j]);
        }
        printf("\n");
    }
}
void input(float mat[row][col], int r, int c)
{
    for( i = 0 ; i< r; i++)
    {
        for( j = 0 ;  j<c; j++)
        {
            printf("Input Value for: %d: %d: ", i+1, j+1);
            scanf("%f", &mat[i][j]);
        }
    }
}
void transpose( float transp[10][10],int row1, int col1)
{
    for( i = 0; i< row1; i++)
    {
        for( j = 0; j < col1; j++)
        {
            mat2[i][j] = transp[j][i] ;
        }
    }
    display(mat2,row1,col1);
}
main()
{
    printf("Program to chech whether a matrix is orthogonal or not : \n");
    int row1, col1;
    int row2, col2;
    printf("\n Input the row  of the matrix:");
    scanf("%d", &row1);
    printf(" Input the col  of the matrix:");
    scanf("%d", &col1);
    printf("\n Input data for matrix\n");
    input(mat1, row1, col1);
    printf("\n Entered Matrix First is as follows:\n");
    display(mat1,row1,col1);
    printf(" \n Transpose of above matrix is as follows:\n");
    transpose(mat1, col1, row1);
    mat_mult(mat1 ,row1 ,col1, mat_res);
}

Read More...

Checking of a Rank of a matrix in C Programming

# include<stdio.h> 
int R,C; 
int i, j; 
int mat[10][10]; 
void display( int, int); 
void input( int, int); 
int Rank_Mat(int , int); 
void swap(int, int, int); 
void swap( int row1,int row2, int col) 
{ 
    for( i = 0; i < col; i++) 
    { 
        int temp = mat[row1][i]; 
        mat[row1][i] = mat[row2][i]; 
        mat[row2][i] = temp; 
    } 
} 
int Rank_Mat(int row1, int col1) 
{ 
    int r, c; 
    for(r = 0; r< col1; r++) 
    { 
        display(R,C); 
        if( mat[r][r] )  
        for(c = 0; c < row1; c++) 
            if(c != r) 
            { 
                float ratio = mat[c][r]/ mat[r][r]; 
                for( i = 0; i < col1; i++) 
                    mat[c][i] -= ratio * mat[r][i]; 
            } 
            else 
                printf("\n"); 
        else 
        { 
            for(c =  r+1 ; c < row1;  c++) 
                if (mat[c][r]) 
                { 
                    swap(r,c,col1); 
                    break ; 
                } 
            if(c == row1) 
            { 
                -- col1; 
                for(c = 0; c < row1; c ++) 
                    mat[c][r] = mat[c][col1]; 
            } 
            --r; 
        } 
    } 
    return col1; 
} 
void display( int row, int col) 
{ 
    for(i = 0; i < row; i++) 
    { 
        for(j = 0; j < col; j++) 
        { 
            printf("  %d", mat[i][j]); 
        } 
        printf("\n"); 
    } 
} 
void input( int row, int col) 
{ 
    int value; 
    for(i = 0 ; i< row; i++) 
    { 
        for(j = 0 ;  j<col; j++) 
        { 
            printf("Input Value for: %d: %d: ", i+1, j+1); 
            scanf("%d",  &value); 
            mat[i][j] = value; 
        } 
    } 
} 
void main() 
{ 
    int rank; 
    printf("\n Input number of rows:"); 
    scanf("%d", &R); 
    printf("\n Input number of cols:"); 
    scanf("%d", &C); 
    input(R, C); 
    printf("\n Row is : %d", R); 
    printf("\n Column is : %d \n", C); 
    printf("\n Entered Two Dimensional array is as follows:\n"); 
    display(R,C); 
    printf("\n Row is : %d", R); 
    printf("\n Column is : %d\n", C); 
    rank = Rank_Mat(R, C); 
    printf("\n Rank of above matrix is : %d", rank); 
}

Read More...