/*  Operations covered :
      1) Create()     : for creating a new set with initial members
                of the set
      2) print()      : diaplays all members of the set
      3) Union()      : finds union of two sets, set1[] and set2[]  and
                stores the result in set3[]
      4) intersection() : finds intersection of two sets, set1[] and set2[]
                and stores the result in set3[]
      5) difference() :finds difference of two sets, set1[] and set2[]
               and stores the result in set3[]
      6) member()     :function returns 1 or 0 ,depending onwhether the
              element  x belongs or not to a  set.

      7) symmdiff()  : Finds Symmetric difference of two sets
Representation of a set
-----------------------
      A set is representrd using an  array of integers.
      It may be declared as:
           int set[30];
      set[0] - gives number of elements in a set.
      set[1] to set[29] are for storing set members.

      Example :
           A set,[2,11,3,5 6],when represebted will appear as:
           [5][2][3][5][6][11][ ][ ][ ] <--- array set[]
            0  1  2  3  4  5   6  7  8  <--- index
*/

#define MAX 30
#include<stdio.h>
#include<conio.h>
void create(int set[]);
void print(int set[]);
void Union(int set1[],int set2[],int set3[]);
void intersection(int set1[],int set2[],int set3[]);
void difference(int set1[],int set2[],int set3[]);
void symmdiff(int set1[],int set2[],int set3[]);
int member(int set[],int x);


void main()
{ int set1[MAX],set2[MAX],set3[MAX];
  int x,op;
  clrscr();
  flushall();
  set1[0]=set2[0]=set3[0]=0;
  do
   { printf("\n1)Create\n2)Print\n3)Union\n4)Intersection\n5)Difference");
     printf("\n6Symmetrec Difference \n7)Quit");
     printf("\nEnter Your Choice:");
     scanf("%d",&op);
     switch(op)
      {
    case 1: printf("\nCreting First Set*******");
        create(set1);
        printf("\nCreating Second Set*****");
        create(set2);
        break;
    case 2: printf("\nFirst Set :\n");
        print(set1);
        printf("\n\nSecond Set :\n");
        print(set2);
        printf("\n\nThird Set :\n");
        print(set3);
        break;
    case 3: Union(set1,set2,set3);print(set3);break;
    case 4: intersection(set1,set2,set3);print(set3);break;
    case 5: difference(set1,set2,set3);print(set3);break;
    case 6: symmdiff(set1,set2,set3);print(set3);break;
     }
  printf("\npress a key............");
  getch();
  }while(op!=7);
 }

 /*creates set[] with initial elements*/

 void create(int set[])
   {   int n,i,x;
       set[0]=0;/*make it a null set*/
       printf("\n No. of elements in the set:");
       scanf("%d",&n);
       printf("\n enter set elements :");
       for(i=1;i<=n;i++)
       scanf("%d",&set[i]);
       set[0]=n; //Number of elements.

   }

 void  print(int set[])
  { int i,n;
    n=set[0];/* number of elements in the set */
    printf("\Members of the set :-->");
    for(i=1;i<=n;i++)
       printf("%d  ",set[i]);
  }

 /* union of  set1[] and set2[] is stored in set3[]*/

void Union(int set1[],int set2[],int set3[])
  { int i,n;
    /* copy set1[] to set3[]*/
    set3[0]=0;/*make set3[] a null set */
    n=set1[0];/* number of elements in the set*/
    //Union of set1,set2= set1 + (set2-set1)
    for(i=0;i<=n;i++)
    set3[i]=set1[i];

    n=set2[0];
    for(i=1;i<=n;i++)
       if(!member(set3,set2[i]))
        set3[++set3[0]]=set2[i];  // insert and increment no. of elements
   }

 /*function returns 1 or 0 depending on whether x belongs
  to set[] or not */

 int member(int set[],int x)
  { int i,n;
    n=set[0]; /* number of elements in the set*/
    for(i=1;i<=n;i++)
      if(x==set[i])
     return(1);

     return(0);
  }

/*intersection of set1[] and set2[] is stored in set3[]*/

void intersection(int set1[],int set2[],int set3[])
     {
    int i,n;
    set3[0]=0; /* make a NULL set*/
    n=set1[0];/* number of elements in the set*/
    for(i=1;i<=n;i++)
      if(member(set2,set1[i])) /* all common elements are inserted in set3[]*/
           set3[++set3[0]]=set1[i];  // insert and increment no. of elements
     }

/*difference of set1[] and set2[] is stored in set3[]*/

void difference(int set1[],int set2[],int set3[])
      { int i,n;
    n=set1[0];/* number of elements in the set*/
    set3[0]=0;/*make it a null set*/
    for(i=1;i<=n;i++)
       if(!member(set2,set1[i]))
         set3[++set3[0]]=set1[i];  // insert and increment no. of elements
      }

 void symmdiff(int set1[],int set2[],int set3[])
      { int i,n;
    n=set1[0];/* number of elements in the set*/
    set3[0]=0;/*make it a null set*/
    //Calculate set1-set2
    for(i=1;i<=n;i++)
       if(!member(set2,set1[i]))
         set3[++set3[0]]=set1[i];  // insert and increment no. of elements
    //Calculate set2-set1
    n=set2[0];
    for(i=1;i<=n;i++)
       if(!member(set1,set2[i]))
         set3[++set3[0]]=set2[i];  // insert and increment no. of elements

      }

#include <stdio.h>

/* Accept input as a string and construct a Doubly Linked List for the input
   string with each node contains, as a data one character from the string and
   perform :
   a) Insert b) delete c)Display forward d) Display backward
*/

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

typedef struct node
   { char data;
     struct node *next,*prev;
   }node;

node *create();
node *insert_b(node *head,char x);
node *insert_e(node *head,char x);
node *insert_in(node *head,char x);
node *delete_b(node *head);
node *delete_e(node *head);
node *delete_in(node *head);
void displayforward(node *head);
void displaybackward(node *head);
void main()
{ int op,op1;
  char x;
  node *head=NULL;
  clrscr();
  do
    { flushall();
      printf("\n\n1)create\n2)Insert\n3)Delete");
      printf("\n4)Display forward\n5)Display backward\n6)Quit");
      printf("\nEnter your Choice:");
      scanf("%d",&op);
      switch(op)
       { case 1:head=create();break;
     case 2:printf("\n\t1)Beginning\n\t2)End\n\t3)In between");
        printf("\nEnter your choice : ");
        scanf("%d",&op1);
        printf("\nEnter the data to be inserted : ");
        flushall();
        x=getchar();
        switch(op1)
         {  case 1: head=insert_b(head,x);
                break;
            case 2: head=insert_e(head,x);
                break;
            case 3: head=insert_in(head, x);
                break;
          }
        break;
     case 3:printf("\n\t1)Beginning\n\t2)End\n\t3)In between");
        printf("\nEnter your choice : ");
        scanf("%d",&op1);
        switch(op1)
         {  case 1:head=delete_b(head);
               break;
            case 2:head=delete_e(head);
               break;
            case 3:head=delete_in(head);
               break;
          }
         break;
     case 4:displayforward(head);break;
     case 5:displaybackward(head);break;
       }
    }while(op!=6);
}

node *create()
{ node *head,*p;
  char x;
  head=NULL;
  printf("\n Enter a string :");
  flushall();
  while((x=getchar())!='\n')
   {
     if(head==NULL)
    {
          head=p=(node*)malloc(sizeof(node));
          head->next=head->prev=NULL;
    }
     else
       {
          p->next=(node*)malloc(sizeof(node));
          p->next->prev=p;
          p=p->next;
          p->next=NULL;
       }
    p->data=x;
   }
 return(head);
}

node *insert_b(node *head,char  x)
{   node *p;
    p=(node*)malloc(sizeof(node));
    p->data=x;
   if(head==NULL)
    {
          head=p;
          head->next=head->prev=NULL;
    }
   else
       {
          p->next=head;
          head->prev=p;
          p->prev=NULL;
          head=p;
       }
   return(head);
}
node *insert_e(node *head,char  x)
{   node *p,*q;
    p=(node*)malloc(sizeof(node));
    p->data=x;
   if(head==NULL)
    {
          head=p;
          head->next=head->prev=NULL;
    }
   else
       {
          for(q=head; q->next != NULL ; q=q->next)
          ;
          q->next=p;
          p->prev=q;
          p->next=NULL;

       }
   return(head);
}


node *insert_in(node *head,char x)
{   node *p,*q;
    char  y;
    p=(node*)malloc(sizeof(node));
    p->data=x;
    printf("\Insert after which character ? : ");
    flushall();
    y=getchar();
    //locate the lthe data 'y'
    for(q=head ; q != NULL && q->data != y; q=q->next)
    ;
    if(q->data==y)
      {
        p->next=q->next;
        p->prev=q;
        p->next->prev=p;
        p->prev->next=p;
      }
    else
       printf("\nData not found ");
    return(head);
}
node *delete_b(node *head)
{
  node *p,*q;
  if(head==NULL)
     {
      printf("\nUnderflow....Empty Linked List");
      return(head);
     }
  if(head->next==NULL)//delete the only node
    {
     p=head;
     free(p);
     head=NULL;
    }
  else
    {
     p=head;
     head=head->next;
     head->prev=NULL;
     free(p);
    }
  return(head);

}
node *delete_e(node *head)
{
  node *p;
  if(head==NULL)
     {
      printf("\nUnderflow....Empty Linked List");
      return(head);
     }
  if(head->next==NULL)//delete the only node
    {
      p=head;
      free(p);
      head=NULL;
    }
  else
    {
      for(p=head ; p->next != NULL ; p=p->next)
      ;
      p->prev->next=NULL;
      free(p);
    }
  return(head);

}

node *delete_in(node *head)
{
  node *p,*q;
  char x;
  if(head==NULL)
     {
    printf("\nUnderflow....Empty Linked List");
    return(head);
     }
  printf("\nEnter the data to be deleted : ");
  flushall();
  x=getchar();
  for(p=head ; p !=NULL && p->data != x ; p=p->next)
  ;

   if(p->data!=x)
     {
      printf("\nUnderflow.....data not found");
      return(head);
     }
 if(p==head)
  {
      head=head->next;
      if(head != NULL)
         head->prev=NULL;
      free(p);
  }
 else
  {
      p->prev->next=p->next;
      p->next->prev=p->prev;
      free(p);
   }
 return(head);
}

void displayforward(node *head)
{ node *p;
  printf("\n");
  if(head != NULL)
     {
     for(p=head ;p!=NULL ; p=p->next)
        printf("%c",p->data);
     }
}
void displaybackward(node *head)
{ node *p;
  printf("\n");
  if(head != NULL)
     {   // go to the last node
     for(p=head ;p->next!=NULL ; p=p->next)
     ;
     for( ;p!=NULL ; p=p->prev)
        printf("%c",p->data);
     }
}