链表实现集合交、并、补
#include<stdio.h>
#include<stdlib.h>
typedef struct node
//定义集合的有序单链表的存储
{
int data;
struct node *next;
}LinkList;
void ListInset(LinkList *&L,int e);
//将数组中的字符用有序单链表存储
void DispList(LinkList *L);
//输出单链表所有的元素
void InitList(LinkList *&L);
//对链表进行初始化
void sort(LinkList *&L);
//对单链表进行递增排序
void sum(LinkList *L1,LinkList *L2,LinkList *&L);
//两个集合求并集的算法实现
void mix(LinkList *L1,LinkList *L2,LinkList *&L); //两个集合求交运算算法
void supplement(LinkList *L1,LinkList *L2,LinkList *&L);
//求两个集合差集运算算法实现
int main()
{
int m=0,n=0,i=0;
char c;
LinkList *L1,*L2,*L3,*L4,*L5;//L1、L2分别为存储集合A、B的单链表，L3、L4、L5分别为存放求集合并、交、差运算结果的单链表
int s1[100],s2[100];
InitList(L1);
InitList(L2);
InitList(L3);
InitList(L4);
InitList(L5);
printf("请输入第一个集合A(不同数据用空格隔开，回车结束)\n");
while(1)
{
scanf("%d",&s1[i]);
c=getchar();
if(c=='\n')
break;
i++;
m++;
}
m++;
printf("请输入第二个集合B(不同数据用空格隔开,回车结束）\n");
i=0;
while(1)
{
scanf("%d",&s2[i]);
c=getchar();
if(c=='\n')
break;
i++;
n++;
}
n++;
for(i=0;i<m;i++)
{
if(s1[i]==32);
else
ListInset(L1,s1[i]);
}
for(i=0;i<n;i++)
{
if(s2[i]==32);
else
ListInset(L2,s2[i]);
}
printf("集合A,B的并集如下\n");
sum(L1,L2,L3);
sort(L3);
DispList(L3);
printf("集合A,B的交集如下\n");
mix(L1,L2,L4);
if(L4->next!=NULL)
sort(L4);
DispList(L4);
printf("集合A,B的差集如下\n");
supplement(L1,L2,L5);
if(L5->next!=NULL)
sort(L5);
DispList(L5);
system("pause");
return 0;
}
void ListInset(LinkList *&L,int e)
//将数组中的字符用有序单链表存储
{
LinkList *pre=L,*p;
while(pre->next!=NULL&&pre->next->data<e)
pre=pre->next;
p=(LinkList *)malloc(sizeof(LinkList));
p->data=e;
p->next=pre->next;
pre->next=p;
}
void DispList(LinkList *L)
//输出单链表所有的元素
{
LinkList *p=L->next;
while(p!=NULL)
{
printf("%d
",p->data);
p=p->next;
}
printf("\n");
}
void InitList(LinkList *&L)
//对链表进行初始化
{
L=(LinkList *)malloc(sizeof(LinkList));
L->next=NULL;
}
void sort(LinkList *&L)
//对单链表进行递增排序
{
LinkList *s,*p,*q,*r,*m,*n;
p=L->next;
q=L->next->next;
r=L;
while(q!=NULL)
{
while(q!=NULL&&q->data>p->data)
//当单链表L元素不为空并且当前元素q大于此元素的前面一个p，则p,q各自指向后一个元素
{
p=p->next;
q=q->next;
}
if(q==NULL)
//if单链表L元素为空时，停止循环
break;
else if(q->data==p->data)
//else if当前元素q等于此元素的前面一个p，则删除q
{
p->next=q->next;
free(q);
q=p->next;
}
else
//else 当前元素q小于此元素的前面一个p，则将q删除，并将p插入到单链表适当的位置
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=q->data;
p->next=q->next;
free(q);
q=p->next;
while(r->next->data<s->data)
//此循环的作用是找到q->data比链表中某一个节点刚好大的节点
r=r->next;
s->next=r->next;
r->next=s;
}
}
}
void sum(LinkList *L1,LinkList *L2,LinkList *&L)
//两个集合求并集的算法实现
{
LinkList *s,*q,*p,*r,*k;
int judge=false;
//判断是否有元素赋值给k
p=L1->next;
q=L2->next;
while(p!=NULL)
//将第一个集合的所有元素复制给单链表L
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=p->data;
if(L->next==NULL)
L->next=s;
else
r->next=s;
r=s;
p=p->next;
}
r->next=NULL;
while(q!=NULL)
//将L中没有L2的部分元素复制给L
{
p=L1->next;
if(q->data==p->data)
//如果L1与L2的元素相等，则分别指向下一个节点
q=q->next;
else
//如果L1与L2的元素不相等
{
while(p!=NULL&&q->data>p->data)
//当L1的元素不为空值并且L2元素的值大于L1元素的值时，L1指向下一个节点
{
p=p->next;
}
if(p==NULL||q->data<p->data)
//当L1为空时或者L2元素的值小于L1元素的值时，将L2元素的值赋值给L
{
s=(LinkList *)malloc(sizeof(LinkList));
s->data=q->data;
if(r->next==NULL)
//给L链表赋值，这里容易发生错误，要考虑L是否为空的情况
r->next=s;
else
k->next=s;
k=s;
judge=true;
}
q=q->next;
}
}
if(judge==true)
//给L链表最后一个指针赋值为NULL
k->next=NULL;
}
void mix(LinkList *L1,LinkList *L2,LinkList *&L) //两个集合求交运算算法
{
LinkList *p,*q,*r;
int judge=false; //判断是否有值赋值给s
q=L2->next;
while(q!=NULL)
{
LinkList *s;
s=(LinkList *)malloc(sizeof(LinkList));
p=L1->next;
if(p->data==q->data)
//如果L1与L2元素的值相等，则将该值赋值给L
{
s->data=q->data;
if(L->next==NULL)
//判断L链表中元素是否为空
L->next=s;
else
r->next=s;
r=s;
judge=true;
}
if(q->data>p->data)
//L2元素的值比L1元素的值大。当L2元素的值比L1元素的值小时，L2就会不断指向它的下一个节点直到L2元素的值比L1元素的值大。
{
while(p!=NULL&&q->data>p->data)
p=p->next;
if(p!=NULL&&p->data==q->data)
{
s->data=q->data;
if(L->next==NULL)
L->next=s;
else
r->next=s;
r=s;
judge=true;
}
}
q=q->next;
}
if(judge==true)
r->next=NULL;
}
void supplement(LinkList *L1,LinkList *L2,LinkList *&L)
//求两个集合差集运算算法实现
{
LinkList *prea=L1,*pa=L1->next,*pb,*p,*q;
L=L1;
//将L1元素的值赋值给L
while(pa!=NULL)
{
pb=L2->next;
while(pb!=NULL&&pb->data!=pa->data) //当L2元素不为空并且L2与L1元素的值不相等时，让L2指向它的下一个节点
pb=pb->next;
if(pb!=NULL)
//当L1与L2元素的值相等时，删除L中该元素的值
{
prea->next=pa->next;
free(pa);
pa=prea->next;
}
else
{
prea=pa;
pa=pa->next;
}
}
p=L2;
q=L2->next;
while(q!=NULL)
{
free(p);
p=q;
q=q->next;
}
free(p);
}
我得慢慢啃