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...

Insertion at the end of a linked list using recursion in C Programming

 #include <stdio.h> 
    #include <malloc.h> 
    struct node 
    { 
            int data ; 
            struct node *link ; 
    }; 

    void addatend ( struct node **, int ) ; 
    void display ( struct node * ) ; 
    void main( ) 
    { 
            struct node *p ; 
            p = NULL ; 
            addatend ( &p, 1 ) ; 
            addatend ( &p, 2 ) ; 
            addatend ( &p, 3 ) ; 
            addatend ( &p, 4 ) ; 
            addatend ( &p, 5 ) ; 
            addatend ( &p, 6 ) ; 
            addatend ( &p, 10 ) ; 
           display ( p ) ; 
    } 
    void addatend ( struct node **s, int num ) 
    { 
            if ( *s == NULL ) 
            { 
                *s = malloc ( sizeof ( struct node ) ) ; 
                ( *s ) -> data = num ; 
                ( *s ) -> link = NULL ; 
            } 
           else 
               addatend ( &( ( *s ) -> link ), num ) ; 
    } 
    void display ( struct node *q ) 
    { 
            printf ( "\n" ) ; 
        while ( q != NULL ) 
            { 
                   printf ( "%d ", q -> data ) ; 
                q = q -> link ; 
            } 
    }

Read More...

Implement union within a structure in C Programming

   /* Program to implement union in structure  */

    #include<stdio.h>
    #include<malloc.h>
    #define new (nd *)malloc(sizeof(nd))
    struct link
    {
        char ch;
        union 
        {
            int a;
            char b[30];
            float c;
        };
        struct link *next;
    };
    typedef struct link nd;
    void create(nd *ptr)
    {
        int ch1;
        char ch2;
        do
        {
            printf("\nEnter data to insert : ");
            printf("\n[1] Enter integer  ");
            printf("\n[2] Enter character  ");
            printf("\n[3] Enter floating no. ");
            printf("\n\nEnter your choice : ");
            scanf("%d",&ch1);
            ptr->ch=ch1;
            switch(ch1)
            {            
                case 1:
                    printf("\nEnter data : "); 
                    scanf("%d",&ptr->a);
                    break;            
                case 2:            
                    printf("\nEnter data : ");
                    scanf("%s",&ptr->b);
                    break;
                case 3:
                    printf("\nEnter data : ");
                    scanf("%f",&ptr->c);
                    break;
            }
            printf("\nWant to continue ?(y/n) : ");
            scanf("%s",&ch2);
            if(ch2=='y'||ch2=='Y')
            {
                ptr->next=new;
                ptr=ptr->next;
            }
            
        }while(ch2=='y'||ch2=='Y');
    }
    void display(nd *h)
    {
        printf("\nList : ");
        nd *ptr=h;
        char ch;
        
        while(ptr!=NULL)
        {
            ch=ptr->ch;
            switch(ch)
            {
                case 1:
                    printf(" %d --> ",ptr->a);
                    break;
                case 2:
                    printf(" %s --> ",ptr->b);
                    break;
                case 3:
                    printf(" %f --> ",ptr->c);
                    break;
            }
            ptr=ptr->next;
        }
        printf("\b\b\b\b   ");
    }
    main()
        {
            printf("\nProgram to implement union within a structure : \n");
            nd *h;
            h=new;
            printf("\n");
            create(h);
            display(h);
            printf("\n\n");
        }

Read More...

Double linked list operations in C Programming

   /* Program to perform operations on a doubly linked list */
    
    #include<stdio.h>
    #include<malloc.h>
    #define new (nd *)malloc(sizeof(nd))
    struct dlist
    {
        struct dlist *prev;
        int info;
        struct dlist *next;
    };
    typedef    struct dlist nd;
    void create(nd **ptr)
    {
        char ch;
        nd *t=*ptr;
        do
        {
            printf("\nEnter data : ");
            scanf("%d",&t->info);
            printf("\nWant to continue ?(y/n) : ");
            scanf("%s",&ch);
            if(ch=='y'||ch=='Y')
            {
                t->next=new;
                t->next->prev=t;
                t=t->next;
            }
        }while(ch=='y'||ch=='Y');
        t->next=NULL;
    }
    void display(nd *ptr)
    {
        printf("\nLinked List :  ");
        while(ptr!=NULL)
        {
            printf(" %d --> ",ptr->info);
            ptr=ptr->next;
        }
        printf("\b\b\b\b   ");
        printf("\n");
    }
    void insert_front(nd **ptr)
    {
        nd *t=new;
        printf("\n\nEnter the data to insert at the front : ");
        scanf("%d",&t->info);
            t->next=*ptr;
            t->next->prev=t;            
            *ptr=t;                    
        printf("\nData inserted...\n");
    }
    void insert_end(nd **ptr)
    {
        nd *t=*ptr;
        nd *t1=new;
        printf("\n\nEnter data to insert at the end : ");
        scanf("%d",&t1->info);
        while(t->next!=NULL)
            t=t->next;
        t->next=t1;                    //  t -> traversing node variable
        t->next->prev=t;                //  t1 -> new node to be inserted
        t1->next=NULL;
    }
    void insert_pos(nd **ptr,int loc)
    {
        int i;
        nd *t=*ptr,*t1=new;
        printf("\n\nEnter data to insert at chosen position : ");
        scanf("%d",&t1->info);
        for(i=1;i<loc-1;i++)
            t=t->next;
        t1->next=t->next;
        t->next->prev=t1;
        t->next=t1;
        t1->prev=t;
    }
    void del(nd **ptr,int x)
    {
        if(*ptr==NULL)
            printf("\nList empty ...\n");
        nd *t=*ptr;
        nd *p=NULL;
        while(t!=NULL)
        {
            if(t->info==x)
            {
                if(t==*ptr)
                {
                    *ptr=t->next;
                    t->next->prev=*ptr;
                    free(t);
                    break;
                }
                else
                {
                    p->next=t->next;
                    p->next->prev=p;
                    free(t);
                    break;
                }
            }
            else
            {
                p=t;
                t=t->next;
            }
        }
            
    }                        
    void reverse(nd **ptr)
    {
        nd *c=*ptr,*p,*temp;
        p=temp=NULL;
        while(c!=NULL)
        {
            temp=p;
            p=c;
            c=c->next;
            p->next=temp;
            p->prev=c;
        }
        *ptr=p;
    }
    int count(nd *ptr)
    {
        int c=0;
        while(ptr!=NULL)
        {
            c++;
            ptr=ptr->next;
        }
        return c;
    }
    main()
    {
        nd *h=new;
        int ch,x,pos,c;
        printf("\nProgram to perform operations on a doubly linked list : ");
        int cnt;
       do
       {
        printf("\n[1] Create node              [2] Insert at front   [3] Insert at end    ");
        printf("\n[4] Insert at any position   [5] Delete node       [6] Reverse the list ");
        printf("\n[7] Display the list         [8] Count nodes       [9] Quit           \n");
        printf("\nEnter your choice : ");
        scanf("%d",&ch); 
        switch(ch)
        {
                case 1: 
                    create(&h);
                    printf("\nNode created ...\n");
                    display(h);
                    break;
                case 2: 
                    insert_front(&h);
                    printf("\nElement inserted ...\n");
                    display(h);
                    break;
                case 3:
                    insert_end(&h);
                    printf("\nElement inserted ...\n");
                    display(h);
                    break;
                case 4:
                    printf("\nEnter postion to insert : ");
                    scanf("%d",&pos);
                                        cnt=count(h);
                    if(pos==1)
                        insert_front(&h);
                                        else if(pos==cnt+1)
                                                insert_end(&h);
                                        else if(pos > cnt+1)
                                        {
                                                printf("\nwrong input ....\n");
                                                break;
                                        }
                    else
                        insert_pos(&h,pos);                    
                    printf("\nElement inserted ...\n");
                    display(h);
                    break;
                case 5:
                    c=count(h);
                    printf("\nEnter element to delete  : ");
                    scanf("%d",&x);
                    del(&h,x);
                    cnt=count(h);
                    if(cnt == c)
                        printf("\nElement not found...\n");
                    else
                        printf("\nElement deleted...\n");
                    display(h);
                    break;
                case 6:
                    reverse(&h);
                    printf("\nList reversed ...\n");
                    display(h);                    
                    break;
                case 7:
                    display(h);
                    break;
                case 8:
                    cnt=count(h);
                    printf("\nNumber of nodes : %d\n",cnt);
                    break;
                case 9:
                    break;
                default : 
                    printf("\nEnter correct choice : \n");
                    break;
            }
        }while(ch!=9);
    
        printf("\n\n");
    } 

Read More...

Polynomial Multiplication

/* Program to multiply two polynomials  */   

    #include
    #include
    #define new (nd *)malloc(sizeof(nd))
    struct poly
        {
            int coef;
            int pow;
            struct poly *next;
        };
    typedef struct poly nd;
    void swap(int *x,int *y)
    {
        int temp=*x;
        *x=*y;
        *y=temp;
    }
    create(nd **h1)
        {
            char ch;
            nd *t=*h1;
            do
            {
                printf("Enter coef : ");
                scanf("%d",&t->coef);
                printf("Enter power : ");
                scanf("%d",&t->pow);
                printf("Want to continue ? (y/n)  ");
                scanf("%s",&ch);
                printf("\n");
                if(ch=='y'||ch=='Y')
                    {
                        t->next=new;
                        t=t->next;
                    }
            }while(ch=='y'||ch=='Y');
            t->next=NULL;
        }
    display(nd **h1)
    {
    nd *t=*h1;
    while(t!=NULL)
    {   
        if(t->coef==0)
            printf("");
        else if((t->coef==1) && (t->pow==1))
            printf("x + ");
        else if((t->coef<0)&&(t->pow>0 && t->pow!=1))
        {
            printf("\b\b\b");
            printf(" %dx^%d + ",t->coef,t->pow);
        }
        else if(t->coef<0 && t->pow==0)
        {
            printf("\b\b\b");
            printf(" %d + ",t->coef);
        }
        else if((t->coef<0)&&(t->pow==1))
        {    printf("\b\b\b");
            printf(" %dx + ",t->coef);
        }
        else if((t->coef<0)&&(t->pow>1))
        {    printf("\b\b\b");
            printf(" -x^%d + ",t->pow);
        }
        else if((t->coef==-1)&&(t->pow==1))
        {
            printf("\b\b\b");
            printf("- x + ");
        }
        else if(t->coef==-1)
        {
            printf("\b\b\b");
            printf("-x^%d + ",t->pow);
        }
        else if((t->coef==1) && ((t->pow!=1)||(t->pow!=0)))
            printf("x^%d + ",t->pow);   
        else if(t->pow==0)
            printf("%d + ",t->coef);
        else if(t->pow==1)
            printf("%dx + ",t->coef);
        else if(t->coef==1 && t->coef==0)
            printf(" 1 + ");
        else
            printf("%dx^%d + ",t->coef,t->pow);
        t=t->next;
    }
    }
    void sort(nd **ptr)
    {
        nd *i,*j;
        for(i=*ptr;i->next!=NULL; i=i->next)
            for(j=i->next; j!=NULL; j=j->next)
                if(i->pow < j->pow)
                {
                    swap(&i->pow,&j->pow);
                    swap(&i->coef,&j->coef);
                }
    }
    void mul(nd **h1,nd **h2,nd **h3)
    {
        nd *t1=*h1,*t2=*h2,*t3=*h3;
        while(t1!=NULL)
        {   
            t2=*h2;
            while(t2!=NULL)
            {
                t3->coef=t1->coef * t2->coef;
                t3->pow=t1->pow + t2->pow;
                t2=t2->next;
                t3->next=new;
                t3=t3->next;
            }
            t1=t1->next;
        }   
        t3->next=NULL;
    }
    void search(nd **h3,nd **h4)
    {
        nd *i=*h3,*j,*t4=*h4;
        for(i=*h3;i!=NULL;i=i->next)
        {
            for(j=i->next;j!=NULL;j=j->next)
            {
                if(i->pow==j->pow)
                {
                    t4->coef=i->coef + j->coef;
                    t4->pow=i->pow;
                    j->coef=0;
                }
                else
                {
                    t4->coef=i->coef;
                    t4->pow=i->pow;
                    t4->next=new;
                    t4=t4->next;
                    break;
                }
               
            }
        }
    }   
                   
   
    main()
        {
            printf("\nProgram to multiply two polynomials : \n");
            nd *h1,*h2,*h3,*h4;
            h1=new;
            h2=new;
            h3=new;
            h4=new;
            printf("\nEnter the elements of 1st polynomial : \n");
            create(&h1);
            sort(&h1);
            printf("Polynomial 1 :  ");
            display(&h1);
            printf("\b\b  ");
            printf("\n");
            printf("\nEnter the elements of 2nd polynomial : \n");
            create(&h2);
            sort(&h2);
            printf("Polynomial 2 :  ");
            display(&h2);
            printf("\b\b  ");
            printf("\n");
            mul(&h1,&h2,&h3);
            sort(&h3);
            //printf("\nProduct of Polynomials :  ");
           //display(&h3);
            printf("\b\b   ");
            search(&h3,&h4);
            printf("\n\nProduct of polynomials :   ");
            display(&h4);
            printf("\b\b   ");
            printf("\n\n");
        }

Read More...

Polynomial Addition

/* Program to add two polynomials */

    #include
    #include
    #define new (nd *)malloc(sizeof(nd))
    struct poly
        {
            int coef;
            int pow;
            struct poly *next;
        };
    typedef struct poly nd;
    void swap(int *x,int *y)
    {
        int temp=*x;
        *x=*y;
        *y=temp;
    }
    create(nd **h1)
        {
            char ch;
            nd *t=*h1;
            do
            {
                printf("Enter coef : ");
                scanf("%d",&t->coef);
                printf("Enter power : ");
                scanf("%d",&t->pow);
                printf("Want to continue ? (y/n)  ");
                scanf("%s",&ch);
                printf("\n");
                if(ch=='y'||ch=='Y')
                    {
                        t->next=new;
                        t=t->next;
                    }
            }while(ch=='y'||ch=='Y');
            t->next=NULL;
        }
    display(nd **h1)
    {
    nd *t=*h1;
    while(t!=NULL)
    {   
        if(t->coef==0)
            printf("");
        else if((t->coef==1) && (t->pow==1))
            printf("x + ");
        else if((t->coef<0)&&(t->pow>0 && t->pow!=1))
        {
            printf("\b\b\b");
            printf(" %dx^%d + ",t->coef,t->pow);
        }
        else if((t->coef<0)&&(t->pow==1))
        {    printf("\b\b\b");
            printf(" %dx + ",t->coef);
        }
        else if((t->coef<0)&&(t->pow>1))
        {    printf("\b\b\b");
            printf(" -x^%d + ",t->pow);
        }
        else if((t->coef==-1)&&(t->pow==1))
        {
            printf("\b\b\b");
            printf("- x + ");
        }
        else if((t->coef==-1)&&(t->pow==0))
        {
            printf("\b\b\b");
            printf("- x + ");
        }
        else if(t->coef==-1)
        {
            printf("\b\b\b");
            printf("-x^%d + ",t->pow);
        }
        else if((t->coef==1) && ((t->pow!=1)||(t->pow!=0)))
            printf("x^%d + ",t->pow);   
        else if(t->pow==0)
            printf("%d + ",t->coef);
        else if(t->pow==1)
            printf("%dx + ",t->coef);
        else
            printf("%dx^%d + ",t->coef,t->pow);
        t=t->next;
    }
    }
    void sort(nd **ptr)
    {
        nd *i,*j;
        for(i=*ptr;i->next!=NULL; i=i->next)
            for(j=i->next; j!=NULL; j=j->next)
                if(i->pow < j->pow)
                {
                    swap(&i->pow,&j->pow);
                    swap(&i->coef,&j->coef);
                }
    }
    add(nd **h1,nd **h2,nd **h3)
    {
    nd *t1=*h1,*t2=*h2,*t3=*h3;
    while(t1!=NULL && t2!=NULL)
    {
        if(t1->pow > t2->pow)
        {
            t3->pow=t1->pow;
            t3->coef=t1->coef;
            t3->next=new;
            t3=t3->next;
            t1=t1->next;
        }
        else if(t1->pow < t2->pow)
        {
            t3->pow=t2->pow;
            t3->coef=t2->coef;
            t3->next=new;
            t3=t3->next;
            t2=t2->next;
        }
        else
        {
            t3->pow=t1->pow;
            t3->coef=t1->coef + t2->coef;
            t3->next=new;
            t3=t3->next;
            t1=t1->next;
            t2=t2->next;
        }
    }   
    while(t1!=NULL)
    {
        t3->pow=t1->pow;
        t3->coef=t1->coef;
        t3->next=new;
        t3=t3->next;
        t1=t1->next;       
    }
    while(t2!=NULL)
    {
        t3->pow=t2->pow;
        t3->coef=t2->coef;
        t3->next=new;
        t3=t3->next;
        t2=t2->next;       
    }
    }
    main()
        {
            printf("\nProgram to add two polynomials : \n");
            nd *h1,*h2,*h3,*h4;
            h1=new;
            h2=new;
            h3=new;
            h4=new;
            printf("\nEnter the elements of 1st polynomial : \n");
            create(&h1);
            sort(&h1);
            printf("Polynomial 1 :  ");
            display(&h1);
            printf("\b\b  ");
            printf("\n");
            printf("\nEnter the elements of 2nd polynomial : \n");
            create(&h2);
            sort(&h2);
            printf("Polynomial 2 :  ");
            display(&h2);
            printf("\b\b  ");
            printf("\n");
            add(&h1,&h2,&h3);
            printf("\nSum of Polynomials :  ");
            display(&h3);
            printf("\b\b   ");
            printf("\n\n");
        } 

Read More...

Linked list operations

 /* Program to perform operations on a linked list  */
    #include
    #include
    struct link
        {
            int info;
            struct link *next;
        };
    typedef struct link node;
    void swap(int *x,int *y)
    {
        int temp=*x;
        *x=*y;
        *y=temp;
    }
    void create(node **ptr)
        {
            char ch;
            node *temp;
            temp=*ptr;
            do
            {
                printf("Enter information : ");
                scanf("%d",&temp->info);
                printf("\nDATA INSERTED : \n");
                printf("Want to add more ? (press y to continue) : ");
                scanf("%s",&ch);
                if(ch=='y'||ch=='Y')
                    {
                        temp->next=(node *)malloc(sizeof(node));
                        temp=temp->next;
                    }
            }    while(ch=='y'||ch=='Y');
            temp->next=NULL;
        }
    void insert_front(node **ptr)
        {
            node *new;
            new=(node *)malloc(sizeof(node));
           
                printf("\nEnter the data to insert : ");
                scanf("%d",&new->info);
                    new->next=*ptr;
                    *ptr=new;
                printf("\nDATA INSERTED : \n");
        }
    void insert_end(node **ptr)
        {
           
            node *new;
            node *temp;
            temp=*ptr;
            new=(node *)malloc(sizeof(node));
           
                printf("\nEnter the data to insert : ");
                scanf("%d",&new->info);
                    while(temp->next!=NULL)
                        temp=temp->next;
                    new->next=NULL;
                    temp->next=new;
                printf("\nDATA INSERTED : \n");
        }
    void insert_pos(node **ptr)
        {
           
            int i,pos;
            node *new;
            node *temp;
            temp=*ptr;
            new=(node *)malloc(sizeof(node));
            printf("\nEnter the position : ");
            scanf("%d",&pos);
            printf("\nEnter data to insert : ");
            scanf("%d",&new->info);
                    for(i=0;inext;
                    new->next=temp->next;
                    temp->next=new;
                printf("\nDATA INSERTED : \n");
               
        }
    void display(node *temp)
        {
           
            printf("\nThe list is  :");
            while(temp!=NULL)
            {
                printf(" %d --> ",temp->info);
                temp=temp->next;
            }
            printf("\b\b\b\b   ");
            printf("\n");
        }
    void sort(node **ptr)
        {
           
            node *i,*j;
            int temp;

                for(i=*ptr;i->next!=NULL; i=i->next)
                    for(j=i->next; j!=NULL; j=j->next)
                        if(i->info > j->info)
                            swap(&i->info,&j->info);
                           
                           
            printf("\n");
        }
    void reverse(node **ptr)
        {
            node *current,*prev,*temp;
            current=*ptr;
            prev=temp=NULL;
            while(current!=NULL)
                {
                    temp=prev;
                    prev=current;
                    current=current->next;
                    prev->next=temp;
                }
            *ptr=prev;
        }
    void del_pos(node **ptr)
        {
            int nd,x;
            node *current,*prev=NULL;
            current=*ptr;
            printf("Enter the element to delete : ");
            scanf("%d",&x);
            if(*ptr==NULL)
                printf("\nList is empty !!!!");
            while(current!=NULL)
            {   
                if(current->info==x)
                {
                    if(current==*ptr)
                    {
                        *ptr=current->next;
                        free(current);
                    }
                    else
                    {
                        prev->next=current->next;
                        free(current);
                    }
                }
                else
                {
                    prev=current;
                    current=current->next;
                }
            }                   
            printf("\nElement deleted \n");
        }
    main()
        {
            printf("\nPROGRAM TO PERFORM OPERATIONS ON LINKED LIST : \n");    
            int ch,pos;
            node *head;
            head=(node *)malloc(sizeof(node));
            do
            {
            printf("[1] Create a node : \n");
            printf("[2] Insert at the front : \n");
            printf("[3] Insert at the end : \n");
            printf("[4] Insert at other postions : \n");
            printf("[5] Delete a node : \n");
            printf("[6] Sort the linked list : \n");
            printf("[7] Reverse the linked list : \n");
            printf("[8] Display the list : \n");
            printf("[9] Quit \n");
            printf("Enter your choice : ");
            scanf("%d",&ch);
            switch(ch)
                {
                    case 1:
                        create(&head);
                        break;
                    case 2:
                        insert_front(&head);
                        break;                   
                    case 3:
                        insert_end(&head);
                        break;
                    case 4:
                        insert_pos(&head);
                        break;
                    case 5:
                        del_pos(&head);
                        break;
                    case 6:
                        sort(&head);
                        break;
                    case 7:
                        reverse(&head);
                        break;
                    case 8:
                        display(head);
                        break;
                }
            }while(ch!=9);
        }

Read More...

Stack using linked list

    /* Program to implement stack using linked list */

    #include

    #include

    #define new1 (nd*)malloc(sizeof(nd))

    typedef struct stack

    {

        int info;

        struct stack *next;

    }nd;

    void push(nd **ptr)

    {

        nd *c=*ptr;

        if(*ptr==NULL)

        {

            *ptr=new1;

            printf("\nEnter element to push : ");

            scanf("%d",&(*ptr)->info);

            (*ptr)->next=NULL;

        }

        else

        {

            nd *t;

            t=new1;

            printf("\nEnter element to push : ");

            scanf("%d",&t->info);

            while(c->next!=NULL)

                c=c->next;

            t->next=NULL;

            c->next=t;

        }

    }

    void pop(nd **ptr)

    {

        nd *c=*ptr,*t=*ptr,*p;

        if(*ptr==NULL)

            printf("\nStack is empty...");

        else if(t->next==NULL)         // If queue contains single node

        {

            *ptr=NULL;

            free(t);

        }

        else

        {

            while(c->next!=NULL)

            {

                p=c;

                c=c->next;

            }

            p->next=NULL;

            free(c);

        }

    }

    void display(nd *ptr)

    {

        if(ptr==NULL)

            printf("\nStack is empty...\n");

        else

        {

            printf("\nStack  :   ");

            while(ptr!=NULL)

            {

                printf(" %d --> ",ptr->info);

                ptr=ptr->next;

            }

            printf("\b\b\b\b   ");

            printf("\n");

        }

    }

    main()

    {

        nd *h=NULL;

        printf("\nProgram to implement stack using linked list : \n");

        int ch;

        do

        {

            printf("\n[1] Push :");

            printf("\n[2] Pop : ");

            printf("\n[3] Display : ");

            printf("\n[4] Quit : ");

            printf("\nEnter your choice : ");

            scanf("%d",&ch);

            switch(ch)

            {

                case 1:

                    push(&h);

                    display(h);

                    break;

                case 2:

                    pop(&h);

                    display(h);

                    break;

                case 3:

                    display(h);

                    break;

                case 4:    break;

                default: printf("\nEnter correct choice ... ");

                     break;

            }

        }while(ch!=4);

        printf("\n\n");

    }

Read More...

Splitting of two linked lists

  /* Program to split a linked list  */

    #include
    #include
    struct link
        {
            int info;
            struct link *next;
        };
    typedef struct link node;   
    void create(node **ptr)
        {
            node *temp;
            temp=*ptr;
            char ch;
            do
            {
                printf("Enter data : " );
                scanf("%d",&temp->info);
                printf("Want to add more ?(y/n) : ");
                scanf("%s",&ch);
                if(ch=='y')
                    {
                        temp->next=(node *)malloc(sizeof(node));
                        temp=temp->next;
                    }
            }    while(ch=='y');
            temp->next=NULL;
        }
    void split(node **ptr1,node **ptr2,node **ptr3)
    {
    node *current1,*current2,*current3;
    node *prev1,*prev2;
    current1=*ptr1;       
    current2=*ptr2;       
    current3=*ptr3;       
        while(current1!=NULL)
            {
                prev1=current1;
                current1=current1->next;
                current2->info=prev1->info;
                if(prev1->next->next==NULL)
                    {
                        current2->next=NULL;
                        prev2=current1;
                        current3->info=prev2->info;
                        current3->next=NULL;
                        break;
                    }
                else
                    {
                        current2->next=(node *)malloc(sizeof(node));
                        current2=current2->next;
                    }
                prev2=current1;
                current1=current1->next;
                current3->info=prev2->info;
                if(prev2->next->next==NULL)
                    {
                        current3->next=NULL;
                        prev1=current1;
                        current2->info=prev1->info;
                        current2->next=NULL;
                        break;
                    }
                else
                    {
                        current3->next=(node *)malloc(sizeof(node));
                        current3=current3->next;
                    }
            }
    }
       
    void display(node *ptr)
    {
        while(ptr!=NULL)
        {
            printf(" %d --> ",ptr->info);
            ptr=ptr->next;
        }
        printf("\b\b\b\b   ");
    }
    main()
        {
            printf("\nProgram to split a linked list w.r.t alternative positions : \n");
            node *head1,*head2,*head3;
            head1=(node *)malloc(sizeof(node));
            head2=(node *)malloc(sizeof(node));
            head3=(node *)malloc(sizeof(node));
            printf("\nEnter data to insert in linked list : \n");
            create(&head1);
            printf("\nBefore splitting :  " );
            display(head1);
            split(&head1,&head2,&head3);
            printf("\n\nAfter splitting : \n");
            printf("\nLinked List 1 : ");
            display(head2);
            printf("\n\nLinked List 2 : ");
            display(head3);
            printf("\n\n\n");
        }

Read More...

Queue using linked list

 /* Program to implement queue using linked list */

    #include
    #include
    #define new1 (nd *)malloc(sizeof(nd))
    typedef struct queue
    {
        int info;
        struct queue *next;
    }nd;   
    void display(nd *ptr)
    {   
        if(ptr==NULL)
            printf("\nQueue is empty...\n");
        else
        {
            printf("\nQueue  :   ");
            while(ptr!=NULL)
            {
                printf(" %d --> ",ptr->info);
                ptr=ptr->next;
            }
            printf("\b\b\b\b   ");
            printf("\n");
        }
    }
    void insert(nd **ptr)
    {
       
        nd *c=*ptr;
        if(*ptr==NULL)
        {
            *ptr=new1;
            printf("\nEnter the element : ");
            scanf("%d",&(*ptr)->info);
            (*ptr)->next=NULL;
        }
        else
        {
            nd *t;
            t=new1;
            printf("\nEnter the element : ");
            scanf("%d",&t->info);
            while(c->next!=NULL)
                c=c->next;
            t->next=NULL;
            c->next=t;
        }
    }
    void delete(nd **ptr)
    {
        nd *c=*ptr,*t=*ptr;
        if(*ptr==NULL)
            printf("\nQueue is empty...");
        else if(t->next==NULL)        // If queue contains single node
        {
            *ptr=NULL;
            free(t);
        }
        else
        {
            *ptr=c->next;
            free(c);
        }
    }
    main()
    {
        nd *h=NULL;
        printf("\nProgram to implement queue using linked list : \n");
        int ch;
        do
        {
            printf("\n[1] Insert [2] Delete [3] Display [4] Exit : \n");
            printf("\nEnter your choice : ");
            scanf("%d",&ch);
            switch(ch)
            {
                case 1:
                    insert(&h);
                    display(h);
                    break;
                case 2:
                    delete(&h);
                    display(h);
                    break;
                case 3:
                    display(h);
                    break;
                case 4:
                    break;
                default : printf("\nEnter correct choice : \n");
                      break;
            }
        }while(ch!=4);
    }        

Read More...

Shuffle merge of two linked lists

/* Program to merge two linked lists  */

    #include
    #include
    struct link
        {
            int info;
            struct link *next;
        };
    typedef struct link node;   
    void create(node **ptr)
        {
            node *temp;
            temp=*ptr;
            char ch;
            do
            {
                printf("Enter data : " );
                scanf("%d",&temp->info);
                printf("Want to add more ?(y/n) : ");
                scanf("%s",&ch);
                if(ch=='y')
                    {
                        temp->next=(node *)malloc(sizeof(node));
                        temp=temp->next;
                    }
            }    while(ch=='y');
            temp->next=NULL;
        }
    void merge(node **ptr1,node **ptr2)
        {
            node *prev1,*prev2;
            node *current1=*ptr1;
            node *current2=*ptr2;                       
            while(current1!= NULL || current2!= NULL)
                {
                    prev1 = current1;
                    prev2 = current2;
                    current1 = current1->next;
                    current2 = current2->next;
                    if(prev1->next == NULL)
                        {
                            prev1->next = prev2;
                            break;
                        }
                    else if(prev2->next==NULL)
                        {
                            prev1->next = prev2;
                            prev2->next = current1;
                            break;
                        }
                    else
                        {
                            prev1->next = prev2;
                            prev2->next = current1;
                        }
                }
        }

    void display(node *ptr)
    {
        while(ptr!=NULL)
        {
            printf(" %d --> ",ptr->info);
            ptr=ptr->next;
        }
        printf("\b\b\b\b   ");
    }
    main()
        {
            printf("\nPROGRAM TO MERGE TWO LINKED LISTS : \n");   
            node *head1,*head2;
            head1=(node *)malloc(sizeof(node));
            head2=(node *)malloc(sizeof(node));
            printf("\nEnter data for list 1 : \n");           
            create(&head1);
            printf("\nEnter data for list 2 : \n");
            create(&head2);
            printf("\nLinked list 1 : ");
            display(head1);
            printf("\n\nLinked list 2 : ");
            display(head2);
            merge(&head1,&head2);
            printf("\n\nMerged Linked list : ");
            display(head1);
            printf("\n\n\n");
        }

Read More...

Josephus Problem using circular linked list

/* Program to implement josephus problem */
 
#include
#include
#define new (node *)malloc(sizeof(node))
struct link
{
   int info;
   struct link *next;
};
    typedef struct link node;
    void create(node **h,int n)
        {
            int x=0;
            char ch;
            node *c=*h;
            do
            {
                //printf("\nEnter data  : ");
                c->info=rand()%100;
                x++;
                if(x==n)
                    break;
                c->next=new;
                c=c->next;                   
            }while(x!=n);
            c->next=*h;
        }
    void display(node **h)
        {
            node *c=*h;
            printf("\nList :  ");
            while(c->next!=*h)
                {
                    printf(" %d --> ",c->info);
                    c=c->next;
                }
            printf(" %d --> ",c->info);
            printf("\b\b\b\b   ");
            printf("\n\n");
        }
    int joseph(node **h,int n,int x,int cnt)
        {
            node *c=*h,*p;
            int i=1;
            while(c->next!=*h)
                {   
                    if(c->info!=x)
                    {
                        p=c;
                        c=c->next;
                    }
                    else    break;
                }
                   
            while(c!=p)
            {
                if(i%cnt==0)
                {
                    p->next=c->next;
                    free(c);
                    c=p->next;
                }
                else
                {
                    p=c;
                    c=c->next;
                }
                i++;
            }
            int w=c->info;
            return w;
        }
    main()
        {
            int n,cnt,x;
            printf("\nProgram to implement Josephus Problem : \n");
            node *h;
            h=new;
            printf("Enter the number of elements : \n");
            scanf("%d",&n);
            printf("\nTo insert in the list : ");
            create(&h,n);
            printf("\nInitial list : \n");
            display(&h);
            printf("\nEnter the element from which count begins : \n");
            scanf("%d",&x);
            printf("Enter count : \n");
            scanf("%d",&cnt);
            int w=joseph(&h,n,x,cnt);
            printf("\nWinner :  %d ",w);
            printf("\n\n");
        }

Read More...

Deque using linked list

/*  Program to implement dequeue using linked list  */
    #include
    #include
    #define new1 (nd *)malloc(sizeof(nd))
    typedef struct deque
    {
        int info;
        struct deque *next;
    }nd;
    void display(nd *ptr)
    {   
        if(ptr==NULL)
            printf("\nQueue is empty...\n");
        else
        {
            printf("\nQueue  :   ");
            while(ptr!=NULL)
            {
                printf(" %d --> ",ptr->info);
                ptr=ptr->next;
            }
            printf("\b\b\b\b   ");
            printf("\n");
        }
    }
    void insfront(nd **ptr)
    {
        if(*ptr==NULL)
        {
            *ptr=new1;
            printf("\nEnter the element : ");
            scanf("%d",&(*ptr)->info);
            (*ptr)->next=NULL;
        }
        else
        {
            nd *t;
            t=new1;
            printf("\nEnter the element : ");
            scanf("%d",&t->info);
            t->next=*ptr;
            *ptr=t;
        }
    }
    void insrear(nd **ptr)
    {
        nd *c=*ptr;
        if(*ptr==NULL)
        {
            *ptr=new1;
            printf("\nEnter the element : ");
            scanf("%d",&(*ptr)->info);
            (*ptr)->next=NULL;
        }
        else
        {
            nd *t;
            t=new1;
            printf("\nEnter the element : ");
            scanf("%d",&t->info);
            while(c->next!=NULL)
                c=c->next;
            t->next=NULL;
            c->next=t;
        }
    }
    void delfront(nd **ptr)
    {
        nd *c=*ptr,*t=*ptr;
        if(*ptr==NULL)
            printf("\nQueue is empty...");
        else if(t->next==NULL)        // If queue contains single node
        {
            *ptr=NULL;
            free(t);
        }
        else
        {
            *ptr=c->next;
            free(c);
        }
    }
    void delend(nd **ptr)
    {
        nd *c=*ptr,*t=*ptr,*p;
        if(*ptr==NULL)
            printf("\nQueue is empty...");
        else if(t->next==NULL)         // If queue contains single node
        {
            *ptr=NULL;
            free(t);
        }
        else
        {
            while(c->next!=NULL)
            {
                p=c;
                c=c->next;
            }
            p->next=NULL;
            free(c);
        }
    }   
main()
{
    int n;
    nd *h;
    h=NULL;
    printf("\nProgram to implement dequeue using linked list :\n");
    int ch1,ch2,ch3,ch4,ch5,ch6,ch7;
    do
    {
    printf("\n[1] Create input restricted queue \n[2] Create output restricted queue ");
    printf("\n[3] Quit from program \n");
    printf("\nEnter your choice : ");
    scanf("%d",&ch1);
    switch(ch1)
    {
        case 1:
            do
            {
            printf("\n[1] Insert at front restricted \n[2] Insert at end restricted ");
            printf("\n[3] Quit to previous menu \n");
            printf("\nEnter your choice : ");
            scanf("%d",&ch2);
            switch(ch2)
            {
                case 1:
                    do
                    {
                    printf("\n[1] Insert at end      [2] Delete from front ");
                    printf("\n[3] Delete from end    [4] Quit to previous menu \n");
                    printf("\nEnter your choice : ");
                    scanf("%d",&ch3);
                    switch(ch3)
                    {
                        case 1:
                            insrear(&h);
                            display(h);
                            break;
                        case 2:
                            delfront(&h);
                            display(h);
                            break;
                        case 3:
                            delend(&h);
                            display(h);
                            break;
                        case 4:
                            break;
                        default:printf("\nEnter correct choice..\n");
                            break;
                           
                    }
                    }while(ch3!=4);
                    break;
                case 2:   
                    do
                    {
                    printf("\n[1] Insert at front    [2] Delete from front ");
                    printf("\n[3] Delete from end    [4] Quit to previous menu \n");
                    printf("\nEnter your choice : ");
                    scanf("%d",&ch4);
                    switch(ch4)
                    {
                        case 1:
                            insfront(&h);
                            display(h);
                            break;
                        case 2:
                            delfront(&h);
                            display(h);
                            break;
                        case 3:
                            delend(&h);
                            display(h);
                        case 4:
                            break;
                        default:printf("\nEnter correct choice...\n");
                            break;
                    }
                    }while(ch4!=4);
                    break;
                case 3:
                    break;
                default:printf("\nEnter correct choice...\n");
                    break;
            }
            }while(ch2!=3);
            break;
        case 2:
            do
            {
            printf("\n[1] Delete at front restricted  [2] Delete at end restricted ");
            printf("\n[3] Quit to previous menu \n");   
            printf("\nEnter your choice : ");
            scanf("%d",&ch5);
            switch(ch5)
            {
                case 1:   
                    do
                    {
                    printf("\n[1] Insert at front    [2] Insert at end ");
                    printf("\n[3] Delete from end    [4] Quit to previous menu \n");
                    printf("\nEnter your choice : ");
                    scanf("%d",&ch6);
                    switch(ch6)
                    {
                        case 1:
                            insfront(&h);
                            display(h);
                            break;
                        case 2:
                            insrear(&h);
                            display(h);
                            break;
                        case 3:
                            delend(&h);
                            display(h);
                            break;
                        case 4:
                            break;
                        default:printf("\nEnter correct choice...\n");
                            break;
                    }
                    }while(ch6!=4);
                    break;
                case 2:
                    do
                    {
                    printf("\n[1] Insert at front      [2] Insert at end ");
                    printf("\n[3] Delete from front      [4] Quit to previous menu \n");
                    printf("\nEnter your choice : ");
                    scanf("%d",&ch7);
                    switch(ch7)
                    {
                        case 1:
                            insfront(&h);
                            display(h);
                            break;
                        case 2:
                            insrear(&h);
                            display(h);
                            break;
                        case 3:
                            delfront(&h);
                            display(h);
                            break;
                        case 4:
                            break;
                        default:printf("\nEnter correct choice...\n");
                            break;
                    }
                    }while(ch7!=4);
                    break;
                case 3:
                    break;
                default:printf("\nEnter correct choice...\n");
                    break;
            }
            }while(ch5!=3);
        case 3:
            break;
        default:printf("\nEnter correct choice ... \n");
            break;
    }
    }while(ch1!=3);
}  

Read More...

Circular Queue using linked list

   /* Program to implement circular queue using linked list */

    #include
    #include
    #define new1 (nd *)malloc(sizeof(nd))
    typedef struct queue
    {
        int info;
        struct queue *next;
    }nd;   
    void display(nd **ptr,nd **rear)
    {
        nd *t=*ptr;   
        if(*ptr==NULL)
            printf("\nQueue is empty...\n");
        else
        {   
            printf("\nQueue  :    ");
            while(t!=*rear)
            {
                printf(" %d --> ",t->info);
                t=t->next;
            }
            printf("\b\b\b\b   ");
        }
        printf("\n");
    }
    void insert(nd **ptr,nd **rear)
    {
        nd *t=*ptr;
        (*rear)->next=*ptr;
        if(*ptr==NULL)
        {
            *ptr=new1;
            printf("\nEnter 1st element : ");
            scanf("%d",&(*ptr)->info);
            (*ptr)->next=*rear;
        }
        else
        {
            nd *t1=new1;
            printf("\nEnter element  : ");
            scanf("%d",&t1->info);
            while(t->next!=*rear)
                t=t->next;
            t1->next=*rear;
            t->next=t1;
        }
    }
    void delete(nd **ptr,nd **rear)
    {
        nd *c=*ptr,*t=*ptr;
        if(*ptr==NULL)
            printf("\nQueue is empty...\n");
        else if(t->next==*rear)        // If head contains the address of "rear" pointer
        {
            *ptr=NULL;
            free(t);
        }
        else
        {
            *ptr=c->next;
            free(c);
        }
    }
    main()
    {
        nd *h=NULL;
        nd *rear=new1;
        printf("\nProgram to implement circular queue using linked list : \n");
        int ch;
        do
        {
            printf("\n[1] Insert  [2] Delete [3] Display [4] Exit : \n");
            printf("\nEnter your choice : ");
            scanf("%d",&ch);
            switch(ch)
            {
                case 1:
                    insert(&h,&rear);
                    display(&h,&rear);
                    break;
                case 2:
                    delete(&h,&rear);
                    display(&h,&rear);
                    break;
                case 3:
                    display(&h,&rear);
                    break;
                case 4:
                    break;
                default : printf("\nEnter correct choice : \n");
                      break;
            }
        }while(ch!=4);
    }

Read More...

Binary Search Tree

    /* Program to perform operations on a binary search tree  */
   
    #include
    #include
    #define new1 (nd *)malloc(sizeof(nd))
    typedef struct binary_search_tree
    {
        int info;
        struct binary_search_tree *lc;
        struct binary_search_tree *rc;
    }nd;

    void create(nd **current,int val)
    {
        char ch;
        nd *c=*current,*p,*new=new1;
        new->info=val;
        new->lc=NULL;
        new->rc=NULL;   
        if(*current==NULL)
            *current=new;
        else
        {
            while(c!=NULL)
            {
                if(new->info < c->info)
                {
                    p=c;
                    c=c->lc;
                }
                else if(new->info > c->info)
                {
                    p=c;
                    c=c->rc;
                }
                else if(new->info==c->info)
                {
                    printf("\nElement already present....\n");
                    return;
                }   
            }
            if(c==NULL)
            {
                if(new->info < p->info)
                     p->lc=new;
                else
                    p->rc=new;       
            }
        }
    }

    void inorder(nd *c)
    {
        if(c!=NULL)
        {
            inorder(c->lc);
            printf(" %4d ",c->info);
            inorder(c->rc);
        }
    }
    void preorder(nd *c)
    {
        if(c!=NULL)
        {
            printf(" %4d ",c->info);
            preorder(c->lc);
            preorder(c->rc);
        }
    }
    void postorder(nd *c)
    {   
        if(c!=NULL)
        {
            postorder(c->lc);
            postorder(c->rc);
            printf(" %4d ",c->info);
        }
    }
   
       
    main()
    {
        int val,ch,del;
        printf("\nProgram to perform operations on a binary tree : \n");
        nd *h=NULL;
        do
        {
            printf("[1] Create Node        [2] Traverse In-order \n");
            printf("[3] Traverse Pre-order    [4] Traverse Post-Order \n");
            printf("[5] Quit \n");
            printf("\nEnter your choice : ");
            scanf("%d",&ch);
            switch(ch)
            {
                case 1:
                    printf("\nEnter value to insert : ");
                    scanf("%d",&val);
                    create(&h,val);
                    break;
           
                case 2:
                    printf("\nBinary Tree : \n");
                    inorder(h);
                    printf("\n");
                    break;
                case 3:
                    printf("\nBinary Tree : \n");
                    preorder(h);
                    printf("\n");
                    break;
                case 4:
                    printf("\nBinary Tree : \n");
                    postorder(h);
                    printf("\n");
                    break;
                               
                case 5 : break;

                default : printf("\nEnter correct choice ...\n");
                    break;
            }
        }while(ch!=5);
        printf("\n\n");
    }

Read More...