#include <stdio.h>
#include <malloc.h>
#define null 0

typedef struct  yunsuan
{char zifu;
yunsuan *next;
}lnode;


lnode *la,*lb,*lc,*p,*q,*m,*n,*l,*x;
char overgame;


void main()
{void shuru(lnode *head);
void  bingji(lnode *la,lnode *lb,lnode *lc);
void  jiaoji(lnode *la,lnode *lb,lnode *lc);
void  chaji(lnode *la,lnode *lb,lnode *lc);
int t;
la=(lnode*)malloc(sizeof(lnode));
la->next=null;
lb=(lnode*)malloc(sizeof(lnode));
lb->next=null;
lc=(lnode*)malloc(sizeof(lnode));
lc->next=null;
printf("请输入la:\n");
shuru(la);
printf("请输入lb:\n");
shuru(lb);
printf("1:并集,2:交集,3:差集");
scanf("%d",&t);
switch(t)
{case 1 :bingji(la,lb,lc); break;
case 2 :jiaoji(la,lb,lc); break;
case 3 :chaji(la,lb,lc);}}

void shuru(lnode *head)
{char a[100],*l;
l=a;
gets(l);
p=head;
for(;*l!='\0';l++)
{q=(lnode*)malloc(sizeof(lnode));
q->next=null;
p->next=q;
p=p->next;
p->zifu=*l;}}

void  bingji(lnode *la,lnode *lb,lnode *lc)   
{int h=1;
m=la->next;
while(h<3){
p=lc;
while(m->zifu<'a'||m->zifu>'z')
{m=m->next;if(m==null)break;}
if(m==null) {m=lb->next;h++;continue;}

if(p->next==null)
{q=(lnode*)malloc(sizeof(lnode));
q->next=null;
p->next=q;
q->zifu=m->zifu;}
if(h==1) m=m->next;
while(m!=null)
{q=lc;
p=lc->next;
while(m->zifu<'a'||m->zifu>'z')
{m=m->next;if(m==null)break;}
if(m==null) break;
while(m->zifu>p->zifu)
{q=p;p=p->next;if(p==null)break;}
if(p==null) {n=(lnode*)malloc(sizeof(lnode));
q->next=n;
n->next=null;
n->zifu=m->zifu;
m=m->next;
continue;}
if(m->zifu<p->zifu)
{n=(lnode*)malloc(sizeof(lnode));
q->next=n;
n->next=p;
n->zifu=m->zifu;}
m=m->next;
}
if(m==null) {m=lb->next;h++;}}
printf("la,lb的并集是:\n");
p=lc->next;
while(p!=null)
{printf("%c",p->zifu);
p=p->next;}



}

void  jiaoji(lnode *la,lnode *lb,lnode *lc)
{m=lc;

p=la->next;
q=lb->next;

for(p=la->next;p!=null;p=p->next)

{while(p->zifu<'a'||p->zifu>'z')
{p=p->next;if(p==null)break;}
if(p==null) break;

for(q=lb->next;q!=null;q=q->next)

  {while(q->zifu<'a'||q->zifu>'z')
{q=q->next;if(q==null)break;}
if(q==null)break;

if(p->zifu==q->zifu)
{if(m->next==null)
{l=(lnode*)malloc(sizeof(lnode));
l->next=null;
m->next=l;
l->zifu=p->zifu;

}
else if(p->zifu>lc->next->zifu)
{n=lc->next;
while(p->zifu>n->zifu)
{ m=n;n=n->next;if(n==null) break;}
if(n==null) {l=(lnode*)malloc(sizeof(lnode));
m->next=l;
l->next=null;
l->zifu=p->zifu;
break;
}
if(p->zifu<n->zifu)
{
l=(lnode*)malloc(sizeof(lnode));
m->next=l;
l->next=n;
l->zifu=p->zifu; break;}}

else if(p->zifu<lc->next->zifu)
{l=(lnode*)malloc(sizeof(lnode));
l->next=lc->next;
l->zifu=p->zifu;
lc->next=l;
break;}

 }

}}
m=lc->next;
while(m!=null)
{printf("%c ",m->zifu);
m=m->next;
}
}

void  chaji(lnode *la,lnode *lb,lnode *lc)
{int y=1;
m=lc;
x=lc;
p=la->next;
q=lb->next;


for(p=la->next;p!=null;p=p->next)

{while(p->zifu<'a'||p->zifu>'z')
{p=p->next;if(p==null)break;}
if(p==null) break;

for(q=lb->next;q!=null;q=q->next)
{while(p->zifu<'a'||p->zifu>'z')
{p=p->next;if(p==null)break;}
if(p==null) break;


if(p->zifu==q->zifu) break;}


if(q==null)
{
if(m->next==null)
{l=(lnode*)malloc(sizeof(lnode));
l->next=null;
m->next=l;
l->zifu=p->zifu;
x=x->next;
}



else if(p->zifu>lc->next->zifu)
{n=lc->next;
while(p->zifu>n->zifu)
{m=n;n=n->next;if(n==null) break;}

if(n==null)
{l=(lnode*)malloc(sizeof(lnode));
m->next=l;
l->next=null;
l->zifu=p->zifu;
}

else if(p->zifu<n->zifu)
{
l=(lnode*)malloc(sizeof(lnode));
l->next=n;
m->next=l;
l->zifu=p->zifu;

}}

else if(p->zifu<lc->next->zifu)
{l=(lnode*)malloc(sizeof(lnode));
l->next=lc->next;
l->zifu=p->zifu;
lc->next=l;
}





}

}
m=lc->next;
while(m!=null)
{printf("%c ",m->zifu);
m=m->next;
}
}