集合的并交运算C语言.docx
《集合的并交运算C语言.docx》由会员分享，可在线阅读，更多相关《集合的并交运算C语言.docx（8页珍藏版）》请在冰点文库上搜索。
集合的并交运算C语言
题目一：
集合的并、交运算
1设计思想
首先，建立两个带头结点的有序单链表表示集合A和B。
须注意的是：
利用尾插入法建立有序单链表，输入数值是升序排列。
其次，根据集合的运算规则，利用单链表的有序性，设计交、并和差运算。
根据集合的运算规则，集合A∩B中包含所有既属于集合A又属于集合B的元素。
因此，须查找单链表A和B中的相同元素并建立一个链表存于此链表中。
根据集合的运算规则，集合A∪B中包含所有或属于集合A或属于集合B的元素。
因此，遍历两链表的同时若元素相同时只将集合A中的元素存于链表中，若集合A中的下一个元素小于B中的元素就将A中的元素存于新建的链表中。
反之将B中的元素存于链表中。
2所用数据结构
线性结构利用链式存储结构实现集合的基本运算。
3源代码分析
#include
#include
#defineERROR0
#defineOK1
typedefintStatus;
typedefcharElemtype;
typedefstructLNode{线性表的链式存储结构
Elemtypedata;
structLNode*next;
}Lnode,*Linklist;
#include"text.h"
LNode*Greatlist（int*N,intn）//建立一个带有头结点的单链表
{
Linklistp,q,L;
L=p=（LNode*）malloc（sizeof（LNode））;
L->next=NULL;
if（n!
=0）
{
for（inti=0;i{
q=（LNode*）malloc（sizeof（LNode））;//尾部插入结点建立带有头结点单链表
q->data=N[i];
p->next=q;//指针后移
p=q;
}
}
p->next=NULL;//对于非空表，最后结点的指针域放空指针
returnL;
}
LNode*jiaoji（Linklistla,Linklistlb）//求两集合的交集
{
Linklistpa,pb,pc,Lc;
pa=la->next;
pb=lb->next;
Lc=（Linklist）malloc（sizeof（LNode））;//申请存储空间
Lc->next=NULL;
pc=Lc;
while（pa&&pb）
{
if（pa->data==pb->data）
{
pc->next=（Linklist）malloc（sizeof（LNode））;//若相等就申请存储空间链到Lc上
pc=pc->next;
pc->data=pa->data;
pa=pa->next;//la，lb的指针后移
pb=pb->next;
}
elseif（pa->data>pb->data）//若pa所指的元素大于pb所指的元素pb指针后移
{pb=pb->next;}
else
{pa=pa->next;}
}
pc->next=NULL;//最后给pc的next赋NULL
returnLc;
}
LNode*bingji（Linklistla,Linklistlb）//求两集合的并集
{
Linklistpa,pb,pc,lc;
pa=la->next;
pb=lb->next;
lc=（Linklist）malloc（sizeof（LNode））;
lc->next=NULL;
pc=lc;
while（pa&&pb）
{
if（pa->data==pb->data）
{
pc->next=（Linklist）malloc（sizeof（LNode））;//若pa所指的元素等于pb所指的元素申请空间将值存入链表lc，pa，pb指针后移
pc=pc->next;
pc->data=pa->data;
pa=pa->next;
pb=pb->next;
}
elseif（pa->data>pb->data）
{
pc->next=（Linklist）malloc（sizeof（LNode））;//若pa所指的元素大于pb所指的元素申请空间将值存入链表lc，pb指针后移
pc=pc->next;
pc->data=pb->data;
pb=pb->next;
}
else
{
pc->next=（Linklist）malloc（sizeof（LNode））;//若pa所指的元素小于pb所指的元素申请空间将值存入链表lc，pa指针后移
pc=pc->next;
pc->data=pa->data;
pa=pa->next;
}
}
pc->next=pa?
pa:
pb;
returnlc;
}
voidPrint_LinkList（LinklistL）//输出元素
{
Linklistp=L->next;
while（p）//链表不为空时输出链表中的值
{
printf（"%3c",p->data）;
p=p->next;
}
printf（"\n"）;
}
voidmain（）
{
LinklistL1,L2,La,Lb;
intA[4]={'a','b','c','f'};
intB[4]={'c','d','e','f'};
printf（"1）含多个结点的顺序表[‘a’,’b’,’c’,’f’]和[‘c’,’d’,’e’,’f’]\n"）;
printf（"建立链表L1为\n"）;
L1=Greatlist（A,4）;
Print_LinkList（L1）;
printf（"建立链表L2为\n"）;
L2=Greatlist（B,4）;
Print_LinkList（L2）;
printf（"两链表的交集为：
\n"）;
La=jiaoji（L1,L2）;
Print_LinkList（La）;
printf（"两链表的并集为：
\n"）;
Lb=bingji（L1,L2）;
Print_LinkList（Lb）;
printf（"2）含一个结点的顺序表[‘a’]和空表[]\n"）;
intA1[1]={'a'};
intB1[1]={'0'};
printf（"建立链表L1为\n"）;
L1=Greatlist（A1,1）;
Print_LinkList（L1）;
printf（"建立链表L2为\n"）;
L2=Greatlist（B1,0）;
Print_LinkList（L2）;
printf（"两链表的交集为：
\n"）;
La=jiaoji（L1,L2）;
Print_LinkList（La）;
printf（"两链表的并集为：
\n"）;
Lb=bingji（L1,L2）;
Print_LinkList（Lb）;
printf（"3）2个空表\n"）;
intA2[1]={'0'};
intB2[1]={'0'};
printf（"建立链表L1为\n"）;
L1=Greatlist（A2,0）;
Print_LinkList（L1）;
printf（"建立链表L2为\n"）;
L2=Greatlist（B2,0）;
Print_LinkList（L2）;
printf（"两链表的交集为：
\n"）;
La=jiaoji（L1,L2）;
Print_LinkList（La）;
printf（"两链表的并集为：
\n"）;
Lb=bingji（L1,L2）;
Print_LinkList（Lb）;
free（L1）;
free（L2）;
free（La）;
free（Lb）;
}
4测试数据及运行结果
（1）含多个结点的顺序表[‘a’,’b’,’c’,’f’]和[‘c’,’d’,’e’,’f’]
（2）含一个结点的顺序表[‘a’]和空表[]（3）2个空表
5算法分析
（1）LNode*Greatlist（）//尾插法建立链表
算法的时间复杂度为O（n），n为输入元素个数。
（2）LNode*jiaoji（Linklistla,Linklistlb）
算法时间复杂度为O（m+n），m为集合A元素个数，n为集合B元素个数。
（3）LNode*bingji（Linklistla,Linklistlb）
算法时间复杂度为O（m+n），m为集合A元素个数，n为集合B元素个数。
（4）voidPrint_LinkList（LinklistL）
算法时间复杂度为O（n）n为集合元素个数。
升级会员 