Monday 2 April 2012

Program : Doubly Linked List – Merging


Program : Doubly Linked List – Merging

// Merging two doubly linked list

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

struct link
{
          int no;
          struct link *next;
          struct link *pre;
};

struct link *node,start,start1,*new1,*local;

void create_link(struct link *node);
void display(struct link *node);
void insert(struct link *node);

void main()
{
          clrscr();
          printf("\n creating doubly linked list");

          node=(struct link *)malloc(sizeof(struct link));
          create_link(node);
          printf("\n First list is as follow\n");
          display(node);

          insert(node);

          printf("\n after merging two list in ascending order : ");
          display(node);

          getch();

}

void create_link(struct link *node)
{
          int i;
          start.next=NULL;
          start.pre=NULL;
          node=&start;
          //printf("%u",node);

          // create first list
          for(i=1;i<=10;i+=2)
          {
                   node->next=(struct link *)malloc(sizeof(struct link));
                   node->next->pre=node;
                   node=node->next;
                   node->no=i;
                   node->next=NULL;
          }
}

void display(struct link *node)
{
          node=start.next;
          while(node)
          {
                   printf("\n  %d",node->no);
                   node=node->next;
          }
}

void insert(struct link *node)
{
   int i;
 
   start1.next=NULL;
   start.pre=NULL;
   new1=&start1;

  // create second list
          for(i=2;i<=10;i+=2)
          {
                   new1->next=(struct link *)malloc(sizeof(struct link));
                   new1->next->pre=new1;
                   new1=new1->next;
                   new1->no=i;
                   new1->next=NULL;
          }
          printf("\n second list is as follow");
       new1=start1.next;

          while(new1)
          {
                   printf("\n  %d",new1->no);
                   new1=new1->next;
          }


          // merging two list
          new1=start1.next;


          while(new1)
           {
              int found=0;
              local=(struct link *)malloc(sizeof(struct link));
              local=new1;
              new1=new1->next;
              node=start.next;
              do
              {
               if(node->no > local->no)
                 {
                     local->next=node;
                     local->pre=node->pre;
                     node->pre->next=local;
                     node->pre=local;
                     found=1;
                     break;
                 }
                 else
                 {
                    node=node->next;
                 }
              }while((node->next) && (!found));

              if(!found)
                {
                     if(node->no > local->no)
                 {
                     local->next=node;
                     local->pre=node->pre;
                     node->pre->next=local;
                     node->pre=local;

                 }
                 else
                 {
                    local->next=NULL;
                    local->pre=node;
                    node->next=local;
                 }
           }
     }
}


Posted  By : Ruchita Pandya
Posted by at No comments:
Labels:

Program : Doubly Linked List – Deletion


Program : Doubly Linked List – Deletion

// Deletion  in doubly linked list(Delete First, Last and node at desire position)

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

struct link
{
          int no;
          struct link *next;
          struct link *pre;
};

struct link *node,*start,*new1;

void create_link(struct link *node);
void display(struct link *node);
void delete_first(struct link *node);
void delete_last(struct link *node);
void delete_desireposition(struct link *node);

void main()
{
          int ch;
          clrscr();
          do
          {
          printf("\n Doubly Linked List");
          printf("\n---------------------------");
          printf("\n 1. Create Link");
          printf("\n 2. Traverse Link");
          printf("\n 3. Delete First node");
          printf("\n 4. Delete Last node ");
          printf("\n 5. Delete node at Desire Position ");
          printf("\n 6. Exit");
          printf("\n-----------------------------");

          printf("\n Enter your choice:-");
          scanf("%d",&ch);

                   switch(ch)
                   {
                             case 1:
                                      node=(struct link *)malloc(sizeof(struct link));
                                      create_link(node);
                                      printf("\n Linked list is as follow");
                                      display(node);
                                      break;
                             case 2:
                                      printf("\n Output\n");
                                      display(node);
                                      break;
                             case 3:
                                      delete_first(node);
                                      printf("\n After Deleting First Node");
                                      display(node);
                                      break;
                             case 4:
                                      delete_last(node);
                                      printf("\n After Deleting Last Node");
                                      display(node);
                                      break;
                             case 5:
                                      delete_desireposition(node);
                                      printf("\n After Deleting At Desire Position");
                                      display(node);
                                      break;

                             case 6:
                                      exit(0);
                                      break;
                             default:
                                      printf("\n Wrong Choice");
                   }
          }while(ch!=6);
          getch();


}

void create_link(struct link *node)
{
          char ans;
          start->next=NULL;
          start->pre=NULL;
          node=start;
          fflush(stdin);
          printf("\n Enter 'n' for break:-");
          ans=getchar();
          while(ans!='n')
          {
                   node->next=(struct link *)malloc(sizeof(struct link));
                   node->next->pre=node;
                   node=node->next;
                   printf("\n Enter data for node:-");
                   scanf("%d",&node->no);
                   node->next=NULL;
                   fflush(stdin);
                   printf("\n Enter 'n' for break:-");
                   ans=getchar();
          }
}

void display(struct link *node)
{
          node=start->next;
          while(node)
          {
                   printf("\n  %d",node->no);
                   node=node->next;
          }
}

void delete_first(struct link *node)
{
          node=start->next;
          node->pre->next=node->next;
          node->next->pre=node->pre;
          free(node);
}

void delete_last(struct link *node)
{
          int node_no=0;
          node=start->next;
          if(node==NULL)
          {
                   printf("\n List is empty");
                   exit(0);
          }
          while(node)
          {
                   node=node->next;
                   node_no++;
          }
          node=start->next;
          while(node_no!=1)
          {
                   node=node->next;
                   node_no--;
          }
          if(node_no==1)
          {
                   node->pre->next=node->next;
                   node->next->pre=node->pre;
                   node->next=NULL;
                   free(node);
          }
}

void delete_desireposition(struct link *node)
{
          int node_no=1,delete_no,flag=0;
          node=start->next;
          if(node==NULL)
          {
                   printf("\n List is emplty");
                   getch();
                   exit(0);
          }
          printf("\n Enter position where you want to delete node:-");
          scanf("%d",&delete_no);

          while(node)
          {
                   if(node_no==delete_no)
                   {
                             node->pre->next=node->next;
                             node->next->pre=node->pre;
                             free(node);
                             flag=1;
                             break;
                   }
                   else
                   {
                             node=node->next;
                   }
                   node_no++;
          }
          if(flag==0)
          {
                   printf("\n Position not found");
          }
}

Posted By : Ruchita Pandya
Posted by at No comments:
Labels:

Program : Doubly Linked List – Insertion


Program : Doubly Linked List – Insertion

// Insertion in doubly linked list (Insert First, Last and node at desire position)


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

struct link
{
          int no;
          struct link *next;
          struct link *pre;
};

struct link *node,*start,*new1;

void create_link(struct link *node);
void display(struct link *node);
void insert_first(struct link *node);
void insert_last(struct link *node);
void insert_desireposition(struct link *node);

void main()
{
          int ch;

          clrscr();
          do
          {
          printf("\n Doubly Linked List");
          printf("\n---------------------------");
          printf("\n 1. Create Linked list");
          printf("\n 2. Traverse Linked list");
          printf("\n 3. Insert First node");
          printf("\n 4. Insert Last node");
          printf("\n 5. Insert node at Desire Position");
          printf("\n 6. Exit");
          printf("\n-----------------------------");

                   printf("\n Enter your choice:-");
                   scanf("%d",&ch);
                   switch(ch)
                   {
                             case 1:
                                      node=(struct link *)malloc(sizeof(struct link));
                                      create_link(node);
                                      printf("\n List is as follow");
                                      display(node);
                                      break;
                             case 2:
                                      printf("\n Output\n");
                                      display(node);
                                      break;
                             case 3:
                                      insert_first(node);
                                      printf("\n After Inserting First Node");
                                      display(node);
                                      break;
                             case 4:
                                      insert_last(node);
                                      printf("\n After Inserting Last Node");
                                      display(node);
                                      break;
                             case 5:
                                      insert_desireposition(node);
                                      printf("\n After Inserting At Desire Position");
                                      display(node);
                                      break;
                             case 6:
                                      exit(0);
                                      break;
                             default:
                                      printf("\n Wrong Choice");
                   }
          }while(ch!=6);
          getch();

}

void create_link(struct link *node)
{
          char ans;
          start->next=NULL;
          start->pre=NULL;
          node=start;
          fflush(stdin);
          printf("\n Enter 'n' for break:-");
          ans=getchar();
          while(ans!='n')
          {
                   node->next=(struct link *)malloc(sizeof(struct link));
                   node->next->pre=node;
                   node=node->next;
                   printf("\n Enter data for node:-");
                   scanf("%d",&node->no);
                   node->next=NULL;
                   fflush(stdin);
                   printf("\n Enter 'n' for break:-");
                   ans=getchar();
          }
}

void display(struct link *node)
{
          node=start->next;
          while(node)
          {
                   printf("\n  %d",node->no);
                   node=node->next;
          }
}

void insert_first(struct link *node)
{
          node=start->next;
          new1=(struct link *)malloc(sizeof(struct link));
          printf("\n Insert data for first node:-");
          scanf("%d",&new1->no);
          node->pre->next=new1;
          new1->pre=node->next;
          new1->next=node;
          node->pre=new1;
}

void insert_last(struct link *node)
{
          node=start->next;
          while(node->next)
          {
                   node=node->next;
          }
          new1=(struct link *)malloc(sizeof(struct link));
          printf("\n Insert data for last node:-");
          scanf("%d",&new1->no);
          node->next=new1;
          new1->pre=node;
          new1->next=NULL;
}

void insert_desireposition(struct link *node)
{
          int node_no=1,insert_no,flag=0;
          node=start->next;
          printf("\n Enter position where you want to insert new node :-");
          scanf("%d",&insert_no);

          while(node)
          {
                   if(node_no==insert_no)
                   {
                             new1=(struct link *)malloc(sizeof(struct link));
                             printf("\n Insert data for new node:- ");
                             scanf("%d",&new1->no);
                             node->pre->next=new1;
                             new1->pre=node->pre;
                             new1->next=node;
                             node->pre=new1;
                             flag=1;
                             break;
                   }
                   else
                   {
                             node=node->next;
                   }
                   node_no++;
          }
          if(flag==0)
          {
                   printf("\n Position not found");
          }
}

Posted By : Ruchita Pandya
Posted by at No comments:
Labels:
Subscribe to: Posts (Atom)