实验 二集合的并交和差运算C++.docx
《实验 二集合的并交和差运算C++.docx》由会员分享，可在线阅读，更多相关《实验 二集合的并交和差运算C++.docx（12页珍藏版）》请在冰点文库上搜索。
实验二集合的并交和差运算C++
实验二 集合的并、交和差运算
// 在写代码的过程中，没有注意头结点~~~ 导致出现了很多野指针~~~，几乎重写.。
o0 ~~~
//经同学检查，发现有错误~~~ 红色部分代码已经修正
//集合的并、交和差运算
/*
选作内容
（1）集合元素的判定和子集判定运算
（2）求集合的补集
（3）集合的混合式运算表达求值
（4）集合的元素类型推广到其他类型，甚至任意类型
*/
/*
测试数据：
（1）Set1="magazine"，Set2="paper"，
Set1∪Set2="aegimnpra"，Set1∩Set2="ae"，Set1-Set2="gimnz"
（2）Set1=012oper4a6tion89"，Set2="errordate"，
Set1∪Set2="adeinoprt"，Set1∩Set2="aeort"，Set1-Set2="inp"
*/
#include
#include
#include
usingnamespacestd;
#defineElemTypechar
typedefstructElemNode
{
ElemTypeelem;
structElemNode*next;
}ElemNode,*Set;
//-------------FunctionList------------------------------
//---------------函数原型--------------------------------
intLengthOf（Setsrc）;//返回一个集合的长度
voidCreateSet（Setdest）;//创建一个新的字母集合，限定a-z
voidEmptySet（Setdest）;//清空一个集合，保留头结点
voidDestroySet（Setdest）;//销毁集合
voidSortSet（Setdest）;//对一个集合进行从小到大的排序
voidDisplaySet（Setsrc）;//打印集合的所有元素
intExistElem（Setdest,ElemTypee）;//判断元素是否存在于集合中
voidDelElem（Setdest,ElemTypee）;//删除集合中的一个元素一次
voidAddElem（Setdest,ElemTypee）;//在链表尾部追加一个元素
voidContactSet（Setdest,Setsrc）;//连接一个集合到另一个集合
voidAddSet（Setdest,Setsrc1,Setsrc2）;//集合并运算
voidMulSet（Setdest,Setsrc1,Setsrc2）;//集合交运算
voidSubSet（Setdest,Setsrc1,Setsrc2）;//集合差运算
intExistSubset（Setdest,Setsrc）;//子集判断
voidNegSet（Setdest,Setsrc）;//求补集
intmain（）
{
Setdest=（Set）malloc（sizeof（ElemNode））;
Setsrc1=（Set）malloc（sizeof（ElemNode））;
Setsrc2=（Set）malloc（sizeof（ElemNode））;
dest->next=NULL;
cout<<"输入两个集合：
"< CreateSet（src1）;CreateSet（src2）;
cout< cout<<"Set1=";DisplaySet（src1）;
cout<<"\t";
cout<<"Set2=";DisplaySet（src2）;
cout< intitem;
cout<<"1->集合并"<<" "<<"2->集合交"<<" "<<"3->集合差"<<" "<<"非零整数->错误！
重输"<<" "<<"0->进入下一步演示"< while（cin>>item）
{
if（item）
switch（item）
{
case1:
cout<<"集合并运算：
Set1∪Set2=";
AddSet（dest,src1,src2）;
DisplaySet（dest）;
EmptySet（dest）;
cout< case2:
cout<<"集合交运算：
Set1∩Set2=";
MulSet（dest,src1,src2）;
DisplaySet（dest）;
EmptySet（dest）;
cout< case3:
cout<<"集合差运算：
Set1-Set2=";
SubSet（dest,src1,src2）;
DisplaySet（dest）;
EmptySet（dest）;
cout< default:
cout<<"输入错误！
重输！
！
！
"<
}
else{cout<<"进入下一步演示..."< }
getchar（）;
cout<<"输入一个集合：
"< CreateSet（dest）;
cout<<"原集合为：
";
DisplaySet（dest）;
cout< charch;
cout<<"在链表尾部添加一个元素ch=";
cin>>ch;
AddElem（dest,ch）;
DisplaySet（dest）;
cout< cout<<"删除集合中的存在的某个元素ch="; cin>>ch;
DelElem（dest,ch）;
DisplaySet（dest）;cout< cout<<"再创建一个集合src=";
Setsrc=（Set）malloc（sizeof（ElemNode））;
getchar（）;
CreateSet（src）;
cout<<"将src集合链接到集合dest中..."< ContactSet（dest,src）;
cout<<"此时dest为：
";
DisplaySet（dest）;
cout< if（ExistSubset（dest,src））
cout<<"此时src是dest的子集..."< else
cout<<"此时src不是dest的子集..."< cout< DisplaySet（dest）;
cout< cout<<"dest的补集是：
";
Setp=（Set）malloc（sizeof（ElemNode））;
p->next=NULL;
NegSet（p,dest）;
DisplaySet（p）;
cout<!
!
"< DestroySet（dest）;
return0;
}
//---------------BasicFunctions-----------------------
//------------------函数实现--------------------------
intLengthOf（Setsrc）
{
//返回一个集合的长度
inti=0;
while（src->next!
=NULL）
{
i++;
src=src->next;
}
returni;
}//LengthOf
voidCreateSet（Setdest）
{
//创建一个新的字母集合，限定a-z
ElemTypech;
Setp=dest,n;
for（;;）
{
ch=getchar（）;
if（ch=='\n'）break;
if（ch<97||ch>122）continue;
n=（Set）malloc（sizeof（ElemNode））;
p->next=n;
n->elem=ch;
n->next=NULL;
p=n;
}
return;
}//CreateSet
voidEmptySet（Setdest）
{
//清空一个集合，保留头结点
Setp,n;
while（dest->next!
=NULL）
{
p=dest;
n=p->next;
for（;n->next!
=NULL;）
{
p=n;
n=n->next;
}
free（n）;
p->next=NULL;
}
}//EmptySet
voidDestroySet（Setdest）
{
//销毁集合
EmptySet（dest）;
free（dest）;
}//DestroySet
voidSortSet（Setdest）
{
//对一个字母集合进行从小到大的排序
inti,j,l,flag;
Setp,q,n;
l=LengthOf（dest）;
if（l<2）return;
flag=1;
for（i=l-1;i>0&&flag==1;i--）
{
flag=0;
p=dest;
q=p->next;
n=q->next;
for（j=0;j {
if（q->elem>n->elem）
{
flag=1;
p->next=n;
q->next=n->next;
n->next=q;
q=p->next;
n=q->next;
}
p=q;
q=n;
n=n->next;
}
}
}//SortSet
voidDisplaySet（Setsrc）
{
//打印集合的所有元素
Setp;
if（src->next==NULL）
{
printf（"φ"）;
return;
}
p=src;
do
{
p=p->next;
putchar（p->elem）;
}while（p->next!
=NULL）;
}//DisplaySet
intExistElem（Setdest,ElemTypee）
{
//判断元素是否存在于集合中
Setp=dest;
if（LengthOf（p）==0）
return0;
else{
p=p->next;
while（p->elem!
=e）
{
if（p->next==NULL）
return0;
p=p->next;
}
return1;
}
}//ExistElem
voidDelElem（Setdest,ElemTypee）
{
//删除集合中的一个元素一次
Setp=dest,q;
if（LengthOf（p）==0）
return;
q=p->next;
if（LengthOf（p）==1）
{
p->next=NULL;
free（q）;
}
while（q->elem!
=e）
{
p=p->next;
q=q->next;
}
if（q->next==NULL）
{
p->next=NULL;
free（q）;
}
else
p->next=q->next;
}//DelElem
voidAddElem（Setdest,ElemTypee）
{
//在链表尾部追加一个元素
Setp=dest,n;
while（p->next!
=NULL）
p=p->next;
n=（Set）malloc（sizeof（ElemNode））;
p->next=n;
n->elem=e;
n->next=NULL;
}//AddElem
voidContactSet（Setdest,Setsrc）
{
//连接一个集合到另一个集合
Setp=dest;
while（p->next!
=NULL）
p=p->next;
p->next=src->next;
}//ContactSet
voidAddSet（Setdest,Setsrc1,Setsrc2）
{
//集合并运算
SortSet（src1）;SortSet（src2）;
inti=0,j=0,len1=LengthOf（src1）,len2=LengthOf（src2）;
src1=src1->next;src2=src2->next;
while（i {
if（src1->elem<=src2->elem）
{
i++;
if（!
ExistElem（dest,src1->elem））
{
AddElem（dest,src1->elem）;
src1=src1->next;
}
else
{
src1=src1->next;
}
}
else
{
j++;
if（!
ExistElem（dest,src2->elem））
{
AddElem（dest,src2->elem）;
src2=src2->next;
}
else
{
src2=src2->next;
}
}
}
while（i {
i++;
if（!
ExistElem（dest,src1->elem））
{
AddElem（dest,src1->elem）;
src1=src1->next;
}
}
while（j {
j++;
if（!
ExistElem（dest,src2->elem））
{
AddElem（dest,src2->elem）;
src2=src2->next;
}
}
}//AddSet
voidMulSet（Setdest,Setsrc1,Setsrc2）
{
//集合交运算
SortSet（src1）;SortSet（src2）;
inti=0,j=0,len1=LengthOf（src1）,len2=LengthOf（src2）;
src1=src1->next;src2=src2->next;
while（i {
if（src1->elemelem）{i++;src1=src1->next;}
elseif（src1->elem>src2->elem）{j++;src2=src2->next;}
else
{
i++;j++;
if（!
ExistElem（dest,src1->elem））
{
AddElem（dest,src1->elem）;
src1=src1->next;
src2=src2->next;
}
}
}
}//MulSet
voidSubSet（Setdest,Setsrc1,Setsrc2）
{
//集合差运算
SortSet（src1）;SortSet（src2）;
inti=0,len=LengthOf（src1）;
src1=src1->next;
while（i {
i++;
if（!
ExistElem（src2,src1->elem））
{
if（!
ExistElem（dest,src1->elem））
{
AddElem（dest,src1->elem）;
src1=src1->next;
}
}
else
{
src1=src1->next;
}
}
}//SubSet
intExistSubset（Setdest,Setsrc）
{
//子集判断
inti=0,len=LengthOf（src）;
src=src->next;
while（i {
if（!
ExistElem（dest,src->elem））
return0;
i++;
src=src->next;
}
return1;
}//ExistSubset
voidNegSet（Setdest,Setsrc）
{
//求补集
SortSet（src）;
inti=0;
while（i<26）
{
if（!
ExistElem（src,i+97））
AddElem（dest,i+97）;
i++;
}
}//NegSet
运行示意图：
升级会员 