C Implementation Of Radix sort

/*Radix sort using counting sort*/

#include <stdio.h>
#include <conio.h>
#define max 10
void print(int arr[max],int len)
{
    int i;
    for(i=0;i<len;i++)
        printf("%d\t",arr[i]);
    printf("\n");
}
void counting_sort_modified(int source_array[max],int destination_array_order[max],int upper_bound,int src_array_length)
{
    int temp_buffer[max],i;
    for(i=0;i<=upper_bound;i++)
    {
        temp_buffer[i]=0;
    }
    for(i=0;i<src_array_length;i++)
    {
        temp_buffer[source_array[i]]=temp_buffer[source_array[i]]+1;
    }
    for(i=1;i<=upper_bound;i++)
    {
        temp_buffer[i]=temp_buffer[i]+temp_buffer[i-1];
    }
    for(i=src_array_length-1;i>=0;i--)
    {
        destination_array_order[temp_buffer[source_array[i]]-1]=i;//source_array[i]; Returns the array of positions of sorted elements.
        temp_buffer[source_array[i]]=temp_buffer[source_array[i]]-1;
    }
}
void array_copy(int src[max],int dest[max],int length)
{
    int iterator=0;
    while(iterator < length)
    {
        dest[iterator]=src[iterator];
        iterator++;
    }
}
void radix_sort(int source_array[max],int src_array_length)
{
    int destination_array[max],stuffed_array[max],iterator,divisor=0,flag;
    do
    {
        flag=iterator=0;
        while(iterator < src_array_length)
        {
            stuffed_array[iterator]=(int)(source_array[iterator]/pow(10,divisor))%10;
            if(stuffed_array[iterator])
            {
                flag=1;
            }
            iterator++;
        }
        if(flag)
        {
            counting_sort_modified(stuffed_array,destination_array,9,src_array_length);
            iterator=0;
            while(iterator < src_array_length)
            {
                stuffed_array[iterator]=source_array[destination_array[iterator]];
                iterator++;
            }
            array_copy(stuffed_array,source_array,src_array_length);
        }
        divisor++;
    }while(flag);
}
int main()
{
    int arr[]={183,265,149,43,123,627};
    print(arr,6);
    radix_sort(arr,6);
    print(arr,6);
    getche();
    return 1;
}

Read more »

N Queen Problem Implementation

/*N queen problem*/
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define max 100

void display(int array[max],int size)
{
    int ctr=0;
    printf("Next set of possible coordinates:\n");
    while(ctr<size)
    {
        printf("(%d,%d)\t",ctr+1,array[ctr]+1);
        ctr++;
    }
    printf("\n");
}

int isAValidPosition(int position[max],int row,int column)
{
    int ctr=0;
    while(ctr<row)
    {
        if( column==position[ctr] || abs(ctr-row)==abs(column-position[ctr]))
        return 0;
        ctr++;
    }
    return 1;
}

void nQueen(int position[max],int n,int row)
{
    int i;
    if(row>=n)
    {
        display(position,n);
    }
    else
    {
        for(i=0;i<n;i++)
        {
            if(isAValidPosition(position,row,i))
            {
                position[row]=i;
                nQueen(position,n,row+1);
            }
        }
    }
}

int main()
{
    int positions[max];
    nQueen(positions,4,0);
    /*First parameter is the array containing the valid coordinates.
    Second parameter is the value of n; currently its 4 queen
    Third parameter is the starting row, which is always 0.*/
    system("pause");
}

Read more »

Binary Search Tree

/*Binary Search Tree along with a search module to find at which level a particular value resides.*/
#include<stdio.h>
#include<conio.h>
struct Tree
{
    int data,level;
    struct Tree *left;
    struct Tree *right;
};
typedef struct Tree node;
node*create_node(int value)
{
    node*p=(node*)malloc(sizeof(node));
    p->data=value;
    p->left=p->right=NULL;
    return p;
}
void create_tree(int value,node*root)
{
        if(value < root->data)
        {
            if(root->left==NULL)
                root->left=create_node(value);
            else
                create_tree(value,root->left);
        }
        else
        {
            if(root->right==NULL)
                root->right=create_node(value);
            else
                create_tree(value,root->right);
        }        
}
void inorder(node*root)
{
    if(root!=NULL)
    {
        inorder(root->left);
        printf("Data=%d\t",root->data);
        printf("Level=%d\n",root->level);
        inorder(root->right);
    }
}
void level_stamper(node*root,int levl)
{
    if(root!=NULL)
    {
        level_stamper(root->left,levl+1);
        root->level=levl;
        level_stamper(root->right,levl+1);
    }
}
node *find_node(node *root,int value)
{
    static node *ret_addr=NULL;
    if(root!=NULL)
    {
        find_node(root->left,value);
        if(root->data==value)
        ret_addr=root;
        find_node(root->right,value);
    }
    return ret_addr;
}
int main()
{
    node*srch;
    node*root=create_node(10);
    create_tree(14,root);
    create_tree(12,root);
    create_tree(15,root);    
    create_tree(8,root);    
    create_tree(9,root);
    level_stamper(root,0);    
    inorder(root);
    if((srch=find_node(root,9)))
    printf("Found at level %d\n",srch->level);
    else
    printf("Not Found\n");
    getche();
    return 1;
}

Read more »

Priority Queue

/*Priority Queue based on a explicit priority value "priority"*/

#include<stdio.h>

#include<conio.h>

typedef struct List

{

    char name;

    int priority;

    struct List *next;

}ProcessList;

ProcessList*getnode(char n,int pri)

{

    ProcessList*p=(ProcessList*)malloc(sizeof(ProcessList));

    p->name=n;

    p->priority=pri;

    p->next=NULL;

    return p;

}

ProcessList*new_process(ProcessList*head,char n,int p)

{

    ProcessList *t=head,*prev=NULL,*newnode;

    if(head==NULL)

        head=getnode(n,p);

    else

    {

        while(t!=NULL && t->priority>p)

        {

            prev=t;

            t=t->next;

        }

        newnode=getnode(n,p);

        if(prev==NULL)

        {

            newnode->next=head;

            head=newnode;

        }

        else

        {

            newnode->next=prev->next;

            prev->next=newnode;

        }

    }

    return head;

}

ProcessList next_process(ProcessList**head)

{

    ProcessList*p;

    if((*head)==NULL)

    {

        printf("No processes in the list\n");

        return;

    }

    else

    {

        p=(*head);

        (*head)=(*head)->next;

        return(*p);

    }

}

void info_printer(ProcessList pl)

{

    printf("\nProcess Name:: %c\tProcess Priority:: %d",pl.name,pl.priority);

}

int main()

{

    ProcessList*head=NULL;

    head=new_process(head,'a',10);

    head=new_process(head,'b',6);

    head=new_process(head,'c',11);

    head=new_process(head,'d',8);

    head=new_process(head,'e',6);

    head=new_process(head,'f',4);

    while(head!=NULL)

    info_printer(next_process(&head));

    getche();

}

Read more »

Insertion at a specified position in a doubly linked list

/*Insertion At a specified position in Doubly Linked List */
#include<stdio.h>
#include<conio.h>
struct linklist
{
    int data;
    struct linklist *next;
    struct linklist *prev;
};
typedef struct linklist node;

node *create_node(int val,node *nxt,node *prv)
{
    node *p;
    p=(node*)malloc(sizeof(node));
    p->data=val;
    p->next=nxt;
    p->prev=prv;
    return p;
} 

int get_length(node *head)/*Returns the number of elements in the list*/
{
    int count=0;
    if(head!=NULL)
    {
        while(head!=NULL)
        {
            head=head->next;
            count++;
        }
    }
    return count;
}

node *get_ith_node(node *head,int i)
{
    if(i<=get_length(head))
    {
        while(i>1)
        {
            head=head->next;
            i--;
        }
        return head;
    }
    else
        return NULL;
}

node *inposition(node *head,int val,int pos)/*At specified location*/
{
    int no_of_elements;
    node *p,*nxt;
    if(head==NULL)
    {
        if(pos==1)
            head=create_node(val,NULL,NULL);
        else
            printf("No linked list exists\n");
    }
    else
    {
        no_of_elements=get_length(head);
        if(pos<=no_of_elements+1)
        {
            p=get_ith_node(head,pos-1);
            if(pos==1)
            {
                head=create_node(val,head,NULL);
                head->next->prev=head;
            }
            else
            {
                nxt=p->next;
                p->next=create_node(val,p->next,p);
                if(nxt!=NULL)/*If the insertion is performed at the end of the doubly list, nxt will be NULL*/
                nxt->prev=p->next;
            }
        }
        else
            printf("Desired number of nodes do not exists\n");
    }
    return head;
}

node *del_from_pos(node *head,int pos)/*Deletion From specified Position*/
{
    node *p,*start=head;
    int no_of_elements;
    if(head!=NULL)
    {
        if(pos==1)
        {
            head=head->next;
            if(head!=NULL)/*If only 1 node exists*/
            head->prev=NULL;
            free(start);
        }
        else
        {
            no_of_elements=get_length(head);
            if(pos<=no_of_elements)
            {
                p=get_ith_node(head,pos-1);
                start=p->next;
                p->next=start->next;
                if(start->next!=NULL)/*If the deletion is performed at the end of the doubly list, start->next will be NULL*/
                start->next->prev=p;
                free(start);
            }
            else
                printf("Desired number of nodes do not exists\n");
        }
    }
    return head;
}

void print_r(node *head)/*Prints the reversed contents of the linked list*/
{
    node *t_head=head;
    printf("\nReversed_Contents\n");
    if(head!=NULL)
    {
        while(t_head!=NULL)
        {
            printf("%d \t",t_head->data);
            t_head=t_head->prev;
        }
        printf("\n");
    }
    else
        printf("The list is Empty \n");
}

void print(node *head)/*Prints the contents of the linked list*/
{
    node *t_head=head;
    printf("\nContents\n");
    if(head!=NULL)
    {
        while(t_head!=NULL)
        {
            printf("%d \t",t_head->data);
            head=t_head;
            t_head=t_head->next;
        }
        printf("\n");
    }
    else
        printf("The list is Empty \n");
    print_r(head);
}

int main()
{
    node *head=NULL;
    head=inposition(head,10,1);
    head=inposition(head,8,2);
    head=inposition(head,9,2);
    head=inposition(head,7,4);
    print(head);
    head=del_from_pos(head,4);
    print(head);
    head=del_from_pos(head,2);
    print(head);
    head=del_from_pos(head,1);
    print(head);
    head=del_from_pos(head,1);
    print(head);
    getche();
}

Read more »

Doubly Linked List

/*
  Name: Doubly Linked List
  Description: Includes insertion deletion modules
*/
#include<stdio.h>
#include<conio.h>
struct linklist
{
    int data;
    struct linklist *next;
    struct linklist *prev;
};
typedef struct linklist node;

void print(node *);
void print_r(node *);

node *create_node(int value,node *nxt,node *prv)
{
    node *p;
    p=(node*)malloc(sizeof(node));
    p->data=value;
    p->next=nxt;
    p->prev=prv;
    return p;
}

void create_list_e(int val,node **head)//Adding contents at the end
{
    node *start;
    if(*head==NULL)
        (*head)=create_node(val,NULL,NULL);
    else
    {
        start=(*head);
        while(start->next!=NULL)
            start=start->next;
        start->next=create_node(val,NULL,start);
    }
}

void create_list_b(int val,node **head)//Adding contents at the beginning
{
    if(*head==NULL)
        (*head)=create_node(val,NULL,NULL);
    else
    {
        (*head)->prev=create_node(val,*head,NULL);
        (*head)=(*head)->prev;
    }
}

void print(node *head)/*Prints the contents of the linked list*/
{
    node *t_head=head;
    printf("\nContents\n");
    while(t_head!=NULL)
    {
        printf("%d \t",t_head->data);
        head=t_head;
        t_head=t_head->next;
    }
    printf("\n");
    print_r(head);
}

void print_r(node *head)/*Prints the reversed contents of the linked list*/
{
    node *t_head=head;
    printf("\nR_Contents\n");
    while(t_head!=NULL)
    {
        printf("%d \t",t_head->data);
        t_head=t_head->prev;
    }
    printf("\n");
}

void del_beg(node **head)/*Deleting from beginning*/
{
    node *start;
    if(*head==NULL)
        printf("The list is empty\n");
    else
    {
        printf("%d \t",(*head)->data);
        start=*head;
        (*head)=(*head)->next;
        if(*head!=NULL)
            (*head)->prev=NULL;
        free(start);
    }
}

void del_end(node **head)/*Deleting from end*/
{
    node *start=*head;
    if(*head==NULL)
          printf("The list is empty\n");
    else
    {
        while(start->next!=NULL)
            start=start->next;
        if(start->prev!=NULL)    
            start->prev->next=NULL;
        else
            (*head)=NULL;
        free(start);
    }
}

int main()
{
    node *head=NULL;
    create_list_e(1,&head);
    create_list_e(2,&head);
    create_list_b(0,&head);
    create_list_b(-1,&head);
    print(head);
    del_beg(&head);
    print(head);
    del_end(&head);
    print(head);
    getche();
}

Read more »

Double Ended Queue

/*Output Restricted Deque*/
/*Input From both ends And Output from Front*/
#include<stdio.h>
#include<conio.h>
#define max 5
typedef struct Dq
{
    int list[max];
    int rear,front;
}DQ;
void enquing_front(DQ*q,int item)
{
    int i;
    if(q->front==0 && q->rear==max-1)
    {
        printf("The deque is full\n");
        getche();
        exit(0);
    }
    if(q->front==-1)
        q->rear=q->front=0;
    else if(q->front>0)
        q->front--;
    else
    {
        for(i=q->rear;i>=0;i--)
        {
            q->list[i+1]=q->list[i];
        }
        q->rear++;
    }
    q->list[q->front]=item;
}
void enquing_end(DQ*q,int item)
{
    int i;
    if(q->front==0 && q->rear==max-1)
    {
        printf("The deque is full\n");
        getche();
        exit(0);
    }
    if(q->front==-1)
       q->rear=q->front=0;
    else if(q->rear==max-1)
    {
        for(i=q->front;i<=q->rear;i++)
        {
            q->list[i-1]=q->list[i];
        }
        q->front--;
    }
    else
        q->rear++;
    q->list[q->rear]=item;
}
int dequing(DQ*q)
{
    int val;
    if(q->front==-1)
    {
        printf("The deque is Empty\n");
        getche();
        exit(0);
    }
    val=q->list[q->front];
    if(q->front==q->rear)
    {
        q->front=q->rear=-1;
        return val;
    }
    q->front++;
    return val;
}
int main()
{
    DQ queue;
    queue.front=queue.rear=-1;
    enquing_end(&queue,1);
    enquing_end(&queue,2);
    enquing_front(&queue,0);
    enquing_front(&queue,-1);
    enquing_end(&queue,3);
    printf("%d\n",dequing(&queue));
    enquing_end(&queue,4);
    printf("%d\n",dequing(&queue));
    printf("%d\n",dequing(&queue));
    printf("%d\n",dequing(&queue));
    printf("%d\n",dequing(&queue));
    printf("%d\n",dequing(&queue));
    getche();
}

Read more »

Circular linked list insertion and deletion at specified position

/*The Following Piece Of Code Adds an element at specified position in
  a circular linked list.
AND
  Removes an element from the specified Position.

AN INTERESTING THING: NO NEED TO MAKE SEPERATE PIECE OF CODE FOR INSERTION AND DELETION
FROM THE BEGINNING AND AT THE END,AS THESE ARE SPECIAL CASE OF ADDING
AND REMOVING FROM SPECIFIED POSITION, THINK HOW!!!!!!!!
*/
#include<stdio.h>
#include<conio.h>
struct linklist
{
    int data;
    struct linklist *next;
};
typedef struct linklist node;

/*---------------Set Of Helping Functions----------------*/

node *create_node(int val,node *address)
{
    node *p;
    p=(node*)malloc(sizeof(node));
    p->data=val;
    p->next=address;
    return p;
} 

int get_length(node *head)/*Returns the number of elements in the list*/
{
    node *t_head=head;
    int count=0;
    if(head!=NULL)
    {
        count++;
        t_head=t_head->next;
        while(t_head!=head)
        {
            t_head=t_head->next;
            count++;
        }
    }
    return count;
}

node *get_ith_node(node *head,int i)
{
    if(i<=get_length(head))
    {
        while(i>1)
        {
            head=head->next;
            i--;
        }
        return head;
    }
    else
        return NULL;
}

/*---------------------------------------------------------------------------*/
/*Module for Insertion At a specified Position*/

node *inposition_c(node *head,int val,int pos)
{
    int no_of_elements;
    node *p,*prev;
    if(head==NULL)
    {
        if(pos==1)
        {
            head=create_node(val,NULL);
            head->next=head;
        }
        else
            printf("No linked list exists\n");
    }
    else
    {
        no_of_elements=get_length(head);
        if(pos<=no_of_elements+1)   /*Can you think why position <= no_of_elements + 1?? Suppose there are 3 elements in the list, then a node can be added at 4th position*/
        {
            prev=get_ith_node(head,pos-1);/*Getting the node previous to the target node*/
            if(pos==1)
            {
                p=get_ith_node(head,no_of_elements); /*Extracting the last node*/
                head=create_node(val,head); /*Creating a new node at the beginning*/
                p->next=head; /*Making the last node to point to the new head*/
            }
            else
                prev->next=create_node(val,prev->next);    
        }
        else
            printf("Desired number of nodes do not exists\n");
    }
    return head;
}

/*Module for Deletion From a specified Position*/

node *del_from_pos_c(node *head,int pos)
{
    node *prev,*start=head;
    int no_of_elements;
    if(head!=NULL)
    {
        no_of_elements=get_length(head);
        if(pos==1)
        {
            if(no_of_elements==1)
                head=NULL;
            else
            {
                prev=get_ith_node(head,no_of_elements);/*Using prev as temporary variable, to point to the last node*/
                head=head->next; /*Advancing the head*/
                prev->next=head; /*Making the last node point to the advanced head*/
            }
            free(start);/*Node Tu Aazaad Hai*/
        }
        else
        {
            if(pos<=no_of_elements)
            {
                prev=get_ith_node(head,pos-1); /*Extracting the node previous to the target node*/
                start=prev->next; /*Making the start point to the target node*/
                prev->next=start->next; /*Adjusting the pointer*/
            }
            else
                printf("Desired number of nodes do not exists\n");
            free(start);/*Node Tu Aazaad Hai*/
        }
    }
    return head;
}

/*Module for Printing the list contents*/

void print(node *head)
{
    node *t_head=head;
    if(head!=NULL)
    {
        printf("\nContents\n");
        printf("%d\n",t_head->data);
        t_head=t_head->next;
        while(t_head!=head)
        {
            printf("%d\n",t_head->data);
            t_head=t_head->next;
        }
    }
    else
        printf("The list is empty\n");
}

int main()
{
    node *head=NULL;
    //clrscr();
    head=inposition_c(head,-2,1);
    head=inposition_c(head,-10,3);
    head=inposition_c(head,-12,1);
    head=inposition_c(head,0,3);
    head=inposition_c(head,19,2);
    print(head);
    head=del_from_pos_c(head,3);
    print(head);
    head=del_from_pos_c(head,1);
    print(head);
    head=del_from_pos_c(head,2);
    print(head);
    head=del_from_pos_c(head,1);
    print(head);
    getch();
}

Read more »

Singly Circular Linked List

/*
  Name: Singly Circular Linked List
  Description: Includes insertion deletion modules
*/

#include<stdio.h>
#include<conio.h>
struct linklist
{
    int data;
    struct linklist *next;
};
typedef struct linklist node;

node *create_node(int val)
{
    node *p;
    p=(node*)malloc(sizeof(node));
    p->data=val;
    return p;
} 

void create_list_b(int val,node **head,node **tail)//Adding contents at the beginning
{
    node *p=create_node(val);
    if(*head==NULL)
        (*head)=(*tail)=p;
    else
    {
        p->next=(*head);
        (*head)=p;
    }
    (*tail)->next=(*head);
}

void create_list_e(int val,node **head,node **tail)//Adding contents at the End
{
    node *p=create_node(val);
    if(*head==NULL)
    {
        (*head)=(*tail)=p;
        (*tail)->next=(*head);
    }
    else
    {
        p->next=(*tail)->next;
        (*tail)->next=p;
        (*tail)=p;   
    }
}

void print(node *head,node *tail)
{
    if(head==NULL)
        printf("No elements in the list\n");
    else
    {
        while(head!=tail)
        {
            printf("%d \t",head->data);
            head=head->next;
        }
        printf("%d\n",head->data);
    }
}

void del_end(node **head,node **tail)
{
    node *start;
    if(*head==NULL)
        printf("Underflow\n");
    else
    {
        printf("Deleting : %d\n",(*tail)->data);
        if((*head)==(*tail))
        {
            free((*head));
            *head=*tail=NULL;
        }
        else
        {
            start=*head;
            while(start->next!=(*tail))
                start=start->next;
            start->next=(*tail)->next;
            free((*tail));
            (*tail)=start;
        }   
    }
}

void del_beg(node **head,node **tail)
{
    node *start;
    if(*head==NULL)
        printf("Underflow\n");
    else
    {
        printf("Deleting : %d\n",(*head)->data);
        if((*head)==(*tail))
        {
            free((*head));
            *head=*tail=NULL;
        }
        else
        {
            start=*head;
            (*head)=(*head)->next;
            free(start);
            (*tail)->next=(*head);
        }
    }
}

int main()
{
    node *head=NULL,*tail=NULL;
    create_list_b(3,&head,&tail);
    create_list_b(2,&head,&tail);
    create_list_b(1,&head,&tail);
    create_list_e(0,&head,&tail);
    create_list_e(4,&head,&tail);
    print(head,tail);
    del_end(&head,&tail);
    print(head,tail);
    del_end(&head,&tail);
    print(head,tail);
    del_beg(&head,&tail);
    print(head,tail);
    del_beg(&head,&tail);
    print(head,tail);
    getche();
}

Read more »