Heaps and priority queues: Complete C program with sorting and all other functions ( Cormen C implementation)

"
#include<stdio.h>

#define EXCHANGE(x,y,z) {z=x;x=y;y=z;}

void printheap(int *);
void max_heapify(int *,int);
void build_max_heap(int *);
void heapsort(int *);
int heap_extract_max(int *);
int heap_maximum(int *);
void heap_increase_key(int *,int ,int);
void max_heap_insert(int *,int);

int n=10;
main()
{
    int heap[]={0,16,14,10,8,7,9,3,2,4,1,0,0,0};
    // int n=9 is a global variable
    printheap(heap);
    heap_increase_key(heap,9,15);
    printheap(heap);
}

void printheap(int *heap)
{
    int i;
    for(i=1;i<=n;i++)
    printf("%d,",heap[i]);
    printf("\n");
}

void max_heapify(int *heap,int i)
{
    int left,right,largest;
    left=2*i;
    right=2*i + 1;

    if(heap[left]>heap[i] && left<=n)
    largest=left;
    else
    largest=i;

    if(heap[right]>heap[largest] && right<=n)
    largest=right;

    if(largest != i)
    {
        int temp;
        temp=heap[i];
        heap[i]=heap[largest];
        heap[largest]=temp;

        max_heapify(heap, largest);
    }
}

void build_max_heap(int *heap)
{
    int i;
    for(i=n/2;i>0;i--)
    {
        max_heapify(heap,i);
    }
}

void heapsort(int *heap)
{
    int i,temp,k=n;
    build_max_heap(heap);
    for(i=n;i>0;i--)
    {
        temp=heap[1];
        heap[1]=heap[i];
        heap[i]=temp;
        n--;
        max_heapify(heap,1);
    }
    n=k;
}

int heap_extract_max(int *heap)
{
    int temp;
    temp=heap[1];
    heap[1]=heap[n];
    n--;
    max_heapify(heap,1);
    return temp;
}

void max_heap_insert(int *heap,int key)
{
    n++;
    heap[n]=-100;
    heap_increase_key(heap,n,key);
}
int heap_maximum(int* heap)
{
    return heap[1];
}

void heap_increase_key(int *heap,int i, int key)
{
    int temp;
    heap[i]=key;
    while(heap[i/2]<key && i>1)
    {
        EXCHANGE(heap[i],heap[i/2],temp);
        i/=2;
    }
}

"

C program to evaluate factorials upto 100 (100!)

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

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

        n--;
    }

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


}

Data Alignment and performance optimization: C source code, concept

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

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

};

struct stud2
{

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

};

struct stud3
{

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

};
main()
{
    printf("%d %d %d",sizeof(struct stud1),sizeof(struct stud2),sizeof(struct stud3));
}

//Compile it, and check the output. If you are surprised, have a look at http://www.codeguru.com/forum/showthread.php?t=276622

Common Input-Output Mistakes and Concepts in C

1.       printf(“sanjay”+2);   //prints njay only.

2.       Always use fflush(stdin) after any scanf statement.

3.       Always use & operator in scanf statement.

4.       We cannot use %d for inputting values other than int in scanf(for eg. long, float).

5.       Global variables initialize to 0, local to some garbage value. Global ‘char’ also initializes to 0.

6.       int/int is int. float/int is float. Int/float is float. (‘/’ represents division operator).

7.       scanf(“%c%c”,&ch1,&ch2);    //keyboard input must be ‘AB’ and not ‘A B’.

scanf(“%c %c”,&ch1,&ch2);  //keyboard input must be ‘A B’.

scanf(“%c/%c”,&ch1,&ch2);  //keyboard input must be ‘A/B’.

8.       printf returns the no. of bytes printed by it.

9.       scanf returns the no. of variables passed to it.

10.   sprintf(str, “%d %d”,x,y); // where str is a string.

sprintf does not prints on screen like printf, but it stores the formatted output in str.

Similarly sscanf takes the formatted input from str rather than from the keyboard.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

    return p3;
}

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

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

#include<stdio.h>

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

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

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

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

}

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

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

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

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

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

    middle=NULL;
    root=root->link;

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

    return temp;
}