#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>
#define null 0
#define M 100
/*定義鏈表*/
typedef char ElemType;
typedef struct Lnode
{
    ElemType data;
    struct Lnode *next;
};

/*返回鏈表長度*/
int lenth(struct Lnode **L)
{
    int n=0;
    struct Lnode *t;
    t=*L;
    while(t!=null)
        {
           n++;
           t=t->next;
        }
    return n;
}
/*返回指定節點的值*/
ElemType get(struct Lnode **L,int n)
{
      int i=1;
      struct Lnode *t;
      t=*L;
while (i<n&&t!=null)
  {
   t=t->next;
    i++;
  }
  if(t!=null)
    {
        return(t->data);
      }
  else
  {
        printf("The %dth Lnode haven't find !\n",n);
      }
}
/*定位指定值的節點的位置*/
int locate(struct Lnode **L,ElemType x )
{
      int n=1;
  struct Lnode *t;
      t=*L;
while (t!=null&&t->data!=x)
  {
   t=t->next;
    n++;
  }
  if(t==null)
  {
        return(0);
      }
  else
      {
    return(n);
      }
}
/*顯示鏈表*/
void display(struct Lnode **L)
{
   struct Lnode *t;
    t=*L;
    if(t==null)
    {
        printf("The link is null!");
    }
    else
    {
do
          {
            printf("%c>>",t->data);
            t=t->next;
   }
while(t!=null);
    }
    printf("\n");
}

/*創建鏈表，并設置鏈表為空*/
void creat(struct Lnode **L)
{
    *L=null;
}
/*向鏈表中插入元素*/
void insert(struct Lnode **L,int n,ElemType x)
{
/*插在第n個節點的前面*/
    struct Lnode *t1,*t2;
    int j=1;
    t1=(struct Lnode *)malloc(sizeof(struct Lnode));
    t1->data=x;
    t2=*L;
    if(n==1)
    {
       t1->next=t2;
       *L=t1;
    }
    else
    {
        while(j<n-1&&t2->next!=null)
            {
               t2=t2->next;
               j++;
            }
        if(j==n-1)
            {
                t1->next=t2->next;
                t2->next=t1;
            }

    }
}
/*刪除指定位置的節點*/
void delete(struct Lnode **L,int n)
{
      int i=1;
  struct Lnode *t1,*t2;
      t1=*L;
  if(n==1)
   {
    t2=t1;
    *L=t1->next;
   }
  else
   {
    while(i<n-1&&t1->next!=null)
     {
      t1=t1->next;
       i++;
     }
      if(t1->next!=null&&i==n-1)
       {
        t2=t1->next;
        t1->next=t2->next;
       }
      else
      {
               printf("Delete error!\n");
            }
   }
    if(t2==null)
{
     free(t2);
      }
}
/*初始化鏈表*/
void init(struct Lnode **L,int len)
{
    int i,k=0;
    struct Lnode *t;
    char x;
    creat(&*L);
    printf("Any key to start!");
    for(i=0;i<=len;i++)
       { scanf("%s",&x);
         insert(&*L,i,x);
         k++;
       }
    printf("集合的數據為:");
    display(&*L);
}

/*復制鏈表L1到L2*/
void copy(struct Lnode **L1,struct Lnode **L2 )
{

  int i,len;
  ElemType t;
  len=lenth(&*L1);
  creat(&*L2);
    for(i=1;i<=len;i++)
       {
         t=get(&*L1,i);
         insert(&*L2,i,t);
       }
}
/*求交集*/
void intersection(struct Lnode **L1,struct Lnode **L2,struct Lnode **L3)
{

     int i,j,k=1;
     struct Lnode *t1,*t2;
     t1=*L1;
     t2=*L2;
     creat(&*L3);
     for(i=1;i<=lenth(&*L1);i++)
      {
       for(j=1;j<=lenth(&*L2);j++)
        {
          if(t1->data==t2->data)
            {
              insert(&*L3,k,t1->data);
              k++;
            }
          t2=t2->next;
        }
      t1=t1->next;
      t2=*L2;
     }

}
/*求并集*/
unionset(struct Lnode **L1,struct Lnode **L2,struct Lnode **L3)
{/*把L1復制到L3,然后比較L2與L3，得到L2在L3中沒有的元素在L3中的位置，并插入*/
  int i,j,k;
  struct Lnode *tt,*t2,*t3;
  creat(&*L3);
  copy(&*L1,&*L3);
  t2=*L2;
  t3=*L3;
  for(i=1;i<=lenth(&*L2);i++)
      {
       k=1;
       for(j=1;j<=lenth(&*L3);j++)
        {
          if(t2->data==t3->data)
           {
             k=0;
             break;
           }

          else if(t2->data!=t3->data)
           {
             k++;
             if(k<=lenth(&*L3))
             {
              t3=t3->next;
             }
           }
        }
       if(k>0&&k<=lenth(&*L3))
       {/*插在排序的位置上*/
         insert(&*L3,k,t2->data);
       }
       else if(k>lenth(&*L3))
       {/*插在鏈尾*/
         tt=(struct Lnode *)malloc(sizeof(struct Lnode));
         tt->data=t2->data;
         tt->next=null;
         t3->next=tt;
       }
       t2=t2->next;
       t3=*L3;
      }
}
/*求差集*/
void diffrenceset(struct Lnode **L1,struct Lnode **L2,struct Lnode **L3)
{
/*將第一個復制到第三個，查找第二個在第三個中有的元素，并確定它在第三個中的位置，然后從第三個中刪除*/
  int i,t,n;
  creat(&*L3);
  copy(&*L1,&*L3);
  for(i=1;i<=lenth(&*L2);i++)
   {
     t=get(&*L2,i);
     n=locate(&*L3,t);
     if(n)
     {
      delete(&*L3,n);
     }
   }
}
main()
{
  int len1,len2;
  char r;
  static struct Lnode *head1,*head2,*head3,*head4,*head5,*head6;
  printf("/************************************************************************/\n");
  printf("請輸入集合A的長度!");
  scanf("%d",&len1);
  printf("/************************************************************************/\n");
  printf("集合A的長度為%d，請輸入集合A的數據:",len1,len1);
  init(&head1,len1);
  printf("/************************************************************************/\n");
  printf("請輸入集合B的長度!");
  scanf("%d",&len2);
  printf("/************************************************************************/\n");
  printf("集合B的長度為%d,請輸入集合B的數據:",len2,len2);
  init(&head2,len2);
  printf("\n\n/-----------------------------fire works---------------------------------/\n");
  intersection(&head1,&head2,&head3);
  printf("集合A和集合B的交集為:");
  display(&head3);
  printf("/-----------------------------fire works---------------------------------/\n");
  unionset(&head1,&head2,&head4);
  printf("集合A和集合B的并集為:");
  display(&head4);
  printf("/-----------------------------fire works---------------------------------/\n");
  diffrenceset(&head1,&head2,&head5);/*第一個減第二個的差集*/
  printf("A與B的差A-B為:");
  display(&head5);
  diffrenceset(&head2,&head1,&head6);/*第二個減第一個的差集*/
  printf("B與A的差B-A為");
  display(&head6);
  printf("/-----------------------------fire works---------------------------------/\n");


}