/* 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