Set Operation

Algorithm : Set Operations


Let us consider two sorted sets pointed by heders p1 and p2 respectively.
In real, each element of a set is a node of a single linked list.We will need to
store their union set,intersection set and difference set in a linked list 
pointed by header node p3.


Intersection(p1, p2,p3)
{
  m1=p1->link               //m1 points to the 1st element of 1st set
  while(m1≠NULL)            //until 1st set becomes empty
  {
    m2=p2->link             //m2 points to the 1st element of 2nd set 
    while(m2≠NULL)          //until 2nd set becomes empty
    {
      if(m1->ele=m2->ele)
      {
	  t=getnode()
	  t->ele=m1->ele
	  if(p3->link=NULL)
	  {
	   p3->link=t
	   m3=t
	  }
	  else
	  {
	   m3->link=m1
	   m3=m3->link      //m3 moves to next node
	  }
      }
      m2=m2->link             //m2 moves to next node
    }
   m1=m1->link                //m1 moves to next node
  }
  show(p3)
}


union(p1, p2,p3)
{
  m1=p1->link               //m1 points to the 1st element of 1st set
  while(m1≠NULL)            //until 1st set becomes empty
  {
    t=getnode()
    t->ele=m1->ele
    if(p3->link=NULL)
    {
      p3->link=t
      trav=t
    }
    else
     {
       trav->link=t
       trav=trav->link
     }
     m1=m1->link               //m1 moves to next node
  }

   m2=p2->link             //m2 points to the 1st element of 2nd set
  while(m2≠NULL)           //until 2nd set becomes empty
  {
   ptr=p3->link            //ptr points to the 1st element of p3
   while(ptr≠NULL)
   {
     if(ptr->ele=m2->ele)    //if element of 1st set & 2nd set is 
     {                         equal then control breaks from this           
       Break                   loop
     }
     save2=ptr
     ptr=ptr->link
   }
   if(ptr=NULL)
   {
     t=getnode()
     t->ele=m2->ele
     save2->link=t
     t->link=ptr
   }
   m2=m2->link               //m2 moves to next node
  }
  show(p3)
}


Difference(p1, p2,p3)
{  
  m1=p1->;link             //m1 points to the 1st element of 1st set
  while(m1≠NULL)          //until 1st set becomes empty
  {
    m2=p2->link           //m2 points to the 1st element of 2nd set
    while(m2≠NULL)        //until 2nd set becomes empty
    {
      if(m1->ele=m2->ele)
      {
	  break
      }
      else if(m1->ele≠m2->ele)
      {
       m2=m2->link               //m2 moves to next node
      }
    }
    if(m2=NULL)
    {
     if(p3->link=NULL)
     {
      p3->link=m1
      trav=m1
     }
     else
     {
       trav->link=m1
       trav=trav->link
     }
    }
    m1=m1->link                 //m1 moves to next node
  }
    show(p3)
}


Here we use two functions show(header) and getnode().
The 1st one shows the elements in the linked list pointed by header.
The 2nd one creates a node and return it's address to the pointer variable.


C Program For Set Operation

Source Code:


#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<alloc.h>

struct node
{
 int ele;
 struct node *link;
};


struct node * getnode()
{
 struct node *t;
 t=(struct node *)malloc(sizeof(struct node));
 t->link=NULL;
 return t;
}

void create(struct node *P)
{
  struct node *trav,*t;
  int i,n,el;

  printf("\nEnter number of elements:");
  scanf("%d",&n);
  for(i=1;i<=n;i++)
   {
     t=getnode();
     printf("\nEnter element-%d :",i);
     scanf("%d",&el);
     t->ele=el;
     if(P->link==NULL)
      {
	 P->link=t;
	 trav=P->link;
      }
     else
      {
	 trav->link=t;
	 trav=t;
      }
   }
}
void show(struct node *P)
{
  struct node *trav;
  if(P->link==NULL)
   {
     printf("\nSet not created.");
   }
  else
   {
     printf("\nThe set is: { ");
     trav=P->link;
     while(trav!=NULL)
      {
	printf(" %d,",trav->ele);
	trav=trav->link;
      }
      printf("}");
   }
}


void uni_on(struct node *p1,struct node *p2)
{
  struct node *p3,*m1,*m2,*trav,*save1,*save2,*ptr,*t;
  p3=getnode();
  p3->link=NULL;
  m1=p1->link;
  while(m1!=NULL)
  {
    t=getnode();
    t->ele=m1->ele;
    if(p3->link==NULL)
    {
      p3->link=t;
      trav=t;
    }
    else
     {
       trav->link=t;
       trav=trav->link;
     }
     m1=m1->link;
  }

  m2=p2->link;
  while(m2!=NULL)
  {
   ptr=p3->link;
   while(ptr!=NULL)
   {
     if(ptr->ele==m2->ele)
     {
       break;
     }
     save2=ptr;
     ptr=ptr->link;
   }
   if(ptr==NULL)
   {
     t=getnode();
     t->ele=m2->ele;
     save2->link=t;
     t->link=ptr;
   }
   m2=m2->link;
  }
  show(p3);
}

void intersection(struct node *p1,struct node *p2)
{
  struct node *p3,*trav,*m1,*m2,*t,*m3;
  p3=getnode();
  p3->link=NULL;
  m1=p1->link;
  while(m1!=NULL)
  {
    m2=p2->link;
    while(m2!=NULL)
    {
      if(m1->ele==m2->ele)
      {
	t=getnode();
	t->ele=m1->ele;
	if(p3->link==NULL)
	{
	  p3->link=t;
	  m3=t;
	}
	else
	{
	  m3->link=m1;
	  m3=m3->link;
	}
      }
      m2=m2->link;
    }
   m1=m1->link;
  }
  show(p3);
}

void difference(struct node *p1,struct node *p2)
{
  struct node *p3,*trav,*m1,*m2,*t;
  p3=getnode();
  p3->link=NULL;
  m1=p1->link;
  while(m1!=NULL)
  {
    m2=p2->link;
    while(m2!=NULL)
    {
      if(m1->ele==m2->ele)
      {
	break;
      }
      else if(m1->ele!=m2->ele)
      {
       m2=m2->link;
      }
    }
    if(m2==NULL)
    {
     t=getnode();
     t->ele=m1->ele;
     if(p3->link==NULL)
     {
      p3->link=t;
      trav=t;
     }
     else
     {
       trav->link=t;
       trav=trav->link;
     }
    }
    m1=m1->link;
  }
    show(p3);
}



main()
{
  int ch,ch1,x,ch4,ch3;
  struct node *p1,*p2;
  p1=getnode();
  p2=getnode();

  while(1)
  {
    printf("\n@ Set operations:");
    printf("\n\t1.Creation.\n\t2.Union\n\t3.Tntersection\n\t4.Difference.\n\t5.Display\n\t6.Exit");
    printf("\nEnter your choice:");
    scanf("%d",&ch);
    switch(ch)
     {
       case 1:printf("\nCreate=>1.set-1 2.set-2");
	      printf("\nEnter your choice:");
	      scanf("%d",&ch4);
	      switch(ch4)
	      {
		case 1:
		       create(p1);
		       break;
		case 2:
		       create(p2);
		       break;
	      }
	      break;
       case 2:
	      uni_on(p1,p2);
	      break;

       case 3:
	      intersection(p1,p2);

	      break;
       case 4:
	      difference(p1,p2);

	      break;
       case 5:
	      printf("\nshow=>1.set-1 2.set-2");
	      printf("\nEnter your choice:");
	      scanf("%d",&ch3);
	      switch(ch3)
	      {
		case 1:

		       show(p1);
		       break;
		case 2:

		       show(p2);
		       break;
	      }
	      break;
       case 6:
	      exit(0);
     }
  }
}