Saturday, September 3, 2011

Union and intersection of two sorted link list


/* Union and intersection of two sorted link list */
#include <stdio.h>
#include <stdlib.h>
typedef struct node
   { int data;
     struct node *next;
   }node;
node *create();
node *insert(node *,int);
void print(node *head);
node * intersection(node *,node *);
node * un(node *,node *);
int main()
  { node *l1=NULL,*l2=NULL,*l3=NULL,*l4=NULL;
    int x,op,position;
   printf("\nEnter 1st sorted Linked list");
l1=create();
printf("\nEnter 2nd sorted Linked list");
l2=create();
printf("\n First Linked List");
print(l1);
printf("\n Second Linked List");
print(l2);
l3=intersection(l1,l2);
printf("\n The intersection is:");
print(l3);
l4=un(l1,l2);
printf("\n The union is :");
print(l4);

  }
 node *create()
{ node *head,*p;
  int i,n;
  head=NULL;
  printf("\n Enter no of data:");
  scanf("%d",&n);
  printf("\nEnter  data(in sorted sequence): ");
  for(i=0;i<n;i++)
   {
     if(head==NULL)
p=head=(node*)malloc(sizeof(node));
     else
       {
p->next=(node*)malloc(sizeof(node));
p=p->next;
       }
       p->next=NULL;
       scanf("%d",&(p->data));
   }
 return(head);
}

void print(node *head)
{ node *p;
 printf("\n");
 for(p=head;p!=NULL;p=p->next)
  printf("%d  ",p->data);
}


node * insert(node *head,int x)
{
node *p,*q;
p=(node *)malloc(sizeof(node));
p->data=x;
p->next=NULL;
if(head==NULL)
return(p);
q=head;
while(q->next!=NULL)
q=q->next;
q->next=p;
return(head);
}


node * intersection(node *l1,node *l2)
{
 node *l4,*p;
 l4=NULL;
 for(p=l1;p!=NULL;p=p->next)
     if(search(l2,p->data))
l4=insert(l4,p->data);
 return(l4);
}

node * un(node *l1,node *l2)
{
 node *l4,*p;
 l4=NULL;

 for(p=l1;p!=NULL;p=p->next)
l4=insert(l4,p->data);
 for(p=l2;p!=NULL;p=p->next)
     if(!search(l1,p->data))
l4=insert(l4,p->data);
 return(l4);
}

int search(node *head,int x)
 {
node *p;
p=head;
while(p!=NULL && p->data !=x)
p=p->next;

if(p==NULL)
    return(0);
return 1;
 }

No comments:

Post a Comment