#include <stdio.h>
#include <stdlib.h>
#define OK 1
typedef int Status;
typedef struct LNode
{
char data;
struct LNode *next;
}LNode,*LinkList;
LinkList InitList()
{//建立链表
LinkList L, p,q;
char d;
L = (LinkList)malloc(sizeof(LNode));
p = L;
scanf("%c", &d);
while (d != '#')
{
p=p->next=(LinkList)malloc(sizeof(LNode));
p->data = d;
scanf("%c", &d);
}
p->next=NULL;
q=L;
L=L->next;
free(q);
return L;
}
LinkList Intersection(LinkList a, LinkList b)
{//求交集
LinkList LA, LB,q;
LA =(LinkList)malloc(sizeof(LNode));
LB = LA;
while (a!=NULL)
{
q=b;
while (q!=NULL)
{
if (q->data == a->data)
{
LB=LB->next=(LinkList)malloc(sizeof(LNode));
LB->data = a->data;
break;
}
q = q->next;
}
a = a->next;
}
LB->next=NULL;
LinkList p;
p = LA;
LA = LA->next;
free(p);
return LA;
}
LinkList Unionset(LinkList a, LinkList b)
{//求并集
LinkList L,q;
L=b;
while (a!=NULL)
{
while (b)
{
q=b;
if(a->data==b->data)
break;
b=b->next;
}
if(b==NULL)
{
q=q->next=(LinkList)malloc(sizeof(LNode));
q->data=a->data;
q->next=NULL;
}
b=L;
a=a->next;
}
return L;
}
Status traverselist(LinkList a)
{//遍历链表
while(a!=NULL)
{
printf("%3c",a->data);
a=a->next;
}
return OK;
}
int main()
{
LinkList A,B,INT,UNION;
printf("请输入集合A的值（输入#结束）：");
A = InitList();
printf("请输入集合B的值（输入#结束）：");
B = InitList();
INT=Intersection(A,B);
printf("\n所求交集为：");
traverselist(INT);
UNION=Unionset(A,B);
printf("\n所求并集为：");
traverselist(UNION);
return 0;
}
交集：就是求2个链表里面相同的元素；
并集：就是合并2个链表，相同的只留一个元素。
LinkList Intersection(LinkList a, LinkList b)
{//求交集
LinkList LA, LB,q;
LA =(LinkList)malloc(sizeof(LNode));
LB = LA;
while (a!=NULL)
{
q=b;
while (q!=NULL)
{
if (q->data == a->data) //判断2个链表的元素是否相等，
{
LB=LB->next=(LinkList)malloc(sizeof(LNode));
//相等就为交集，保存到LB
LB->data = a->data;
break;
}
q = q->next;
}
a = a->next;
}
LB->next=NULL;
LinkList p;
p = LA;
LA = LA->next;
free(p);
return LA;
}
LinkList Unionset(LinkList a, LinkList b)
{//求并集
LinkList L,q;
L=b;
while (a!=NULL)
{
while (b)
{
q=b;
if(a->data==b->data) //判断2个链表的元素是否相等，相等就表示a里面已经存在，相同的只要一个，废弃
break;
b=b->next;
}
if(b==NULL) //不相同的加到a里面
{
q=q->next=(LinkList)malloc(sizeof(LNode));
q->data=a->data;
q->next=NULL;
}
b=L;
a=a->next;
}
return L;
}