集合的并交和差运算数据结构C课程设计.docx
《集合的并交和差运算数据结构C课程设计.docx》由会员分享，可在线阅读，更多相关《集合的并交和差运算数据结构C课程设计.docx（17页珍藏版）》请在冰点文库上搜索。
集合的并交和差运算数据结构C课程设计
数据结构C++课程设计
题 目:
集合的并、交和差运算
1、设计题目
集合的并、交和差运算
2、小组成员分工说明
一个人
3、需求分析
1）运行环境（软、硬件环境）
软件环境：
MicrosoftVista操作系统，VisualC++6.0
硬件环境：
2.0GB内存
2）输入的形式和输入值的范围
运行所给的测试数据，集合的元素限定为小写字符〔a..z〕：
第一组：
Set1＝magazine，Set2＝paper
第二组：
Set1＝0120per4a6tion89，Set2＝errordata
输出的形式描述
程序运行并、交和差运算后得到数据，输出字符。
3）功能描述
能演示执行集合的并、交和差运算。
4）测试数据
（1）Set1＝magazine，Set2＝paper，
Set1∪Set2＝aeginmprz，Set1∩Set2＝ae，Set1－Set2＝gimnz。
（2）Set1＝0120per4a6tion89，Set2＝errordata，
Set1∪Set2=adeinoprt，Set1∩Set2=aeort，Set1－Set2＝inp。
四、概要设计
1）抽象数据类型定义描述
（顺序表的抽象数据类型描述）
ADTSeqlistis
Data
线性表的长度
Operation
Seqlist
初始化值：
无
动作：
置顺序表的长度为0
Length
输入：
无
前置条件：
表已存在
功能：
求表的长度
输出：
返回表的长度，即表中数据元素的个数
后置条件：
表不变
Get
输入：
元素的序号i
前置条件：
表已存在，i合法
功能：
在表中取序号为i的数据元素
输出：
若i合法，返回序号为i的元素值，否则抛出异常
后置条件：
表不变
Locate
输入：
数据元素item
前置条件：
表已存在
功能：
在线性表中查找值等于item的元素
输出：
若查找成功，返回x在表中的序号，否则返回0
后置条件：
表不变
Insert
输入：
插入位置i；待插元素item
前置条件：
表已存在,i合法
功能：
在表的第i个位置处插入一个新元素x
输出：
若插入不成功，抛出异常
后置条件：
若插入成功，表中增加一个新元素
Delete
输入：
删除位置i
前置条件：
表已存在
功能：
删除表中的第i个元素
输出：
若删除成功，返回被删元素，否则抛出异常
后置条件：
若删除成功，表中减少一个元素
Empty
输入：
无
前置条件：
表已存在
功能：
判断表是否为空
输出：
若是空表，返回1，否则返回0
后置条件：
表不变
Clear
输入：
无
前置条件：
无
功能：
清空顺序表
输出：
无
后置条件：
表的长度是0
endADTseqList
2）功能模块设计（如主程序模块设计）
3）模块层次调用关系图
五、详细设计
实现概要设计中定义的所有的类的定义及类中成员函数，并对主要的模块写出伪码算法。
1、顺序表存储结构的定义。
2、成员函数类的定义。
3、并、交和差三个操作函数的实现。
1）并运算：
将B中的元素插到A后面后形成新的集合，定义字符i在a到z之间，并将新的集合中的个元素与i进行比较，若相同则将此时i的值插入C中作为输出值，若不同则i++继续比较。
template
SeqListbin（SeqListA,SeqListB）
{
SeqListC;
intm=1;
inta=A.Length（）;
for（intb=0;b<=B.Length（）;b++）
{
A.Insert（a+b+1,B.Get（b））;//将B的元素插到的A的后面成组合
}
for（chari='a';i<='z';i++）//定义字符i在a到z之间
{
for（intd=0;d<=A.Length（）;d++）
{
if（A.Get（d）==i）//取组合后元素将元素与i进行比较
{
C.Insert（m,i）;//相同的插入C
m++;//不相同继续
break;
}
}
}
returnC;
}
2）交运算：
定义定义字符i在a到z之间，先将i与A中数据元素进行比较，再将i与B中元素进行比较，如果两次比较都有与i相同的元素，则将该i值插入C中作为输出。
template
SeqListjiao（SeqListA,SeqListB）
{
SeqListC;
intm=1;
intflag=0;
for（chari='a';i<='z';i++,flag=0）//定义字符i在a到z之间
{
for（inta=0;a<=A.Length（）;a++）
{
if（A.Get（a）==i）//将i与A中元素进行比较
{
for（intb=0;b<=B.Length（）;b++）
{
if（B.Get（b）==i）//将i与B中元素进行比较
{
C.Insert（m,i）;//两次比较都有与i相同的元素，则将i插入C
m++;
flag=1;
break;
}
}
if（flag==1）
break;
}
}
}
returnC;
}
3）差运算：
定义字符i在a到z之间，先将i与A中数据元素进行比较，如果相同，再将i与B中元素进行比较，，如果不同则将i插入C作为输出。
template
SeqListcha（SeqListA,SeqListB）
{
SeqListC;
intm=1;
intflag=0;
for（chari='a';i<='z';i++,flag=0）//定义字符i在a到z之间
{
for（inta=0;a<=A.Length（）;a++）
{
if（A.Get（a）==i）//将i与A中元素进行比较
{
for（intb=0;b<=B.Length（）;b++）
{
if（B.Get（b）==i）//如果i与A中元素相同，则将i与a中元素进行比较
{flag=m;}
}
if（flag==0）
{C.Insert（m,i）;//如果不同则将i插入C
m++;
break;
}
}
}
}
returnC;
}
4、main函数。
intmain（）
{
chara[50];
charb[50];
cout<<"Set1:
";//输入set1数据
cin.getline（b,'/0'）;//所给数据中有空格，所以不能直接用cin
cout<cout<<"Set2:
";//输入set2数据
cin.getline（a,'/0'）;
cout<SeqListA（a,50）,B（b,50）,C,D,E;
C=bin（A,B）;//调用集合的并运算
cout<<"Set1∪Set2=";
C.display（）;
cout<D=jiao（A,B）;//调用集合的交运算
cout<<"Set1∩Set2=";
D.display（）;
cout<E=cha（B,A）;//调用集合的差运算
cout<<"Set1-Set2=";
E.display（）;
cout<return0;
}
六、调试分析
包括调试过程中遇到的问题及解决的方法、算法的时间空间复杂性分析、经验体会。
七、用户使用说明
详细列出每一步的操作说明。
1、输入Set1的数据
2、输入Set2的数据
3、分别输出Set1∪Set2=
Set1∩Set2=
Set1-Set2=
八、测试结果
九、附录：
程序设计源代码
#include
usingnamespacestd;
constintMaxSize=200;//MaxSize是顺序表中最大项数
template//定义模板类SeqList
classSeqList
{public:
SeqList（）;//无参构造函数
SeqList（Ta[],intn）;//有参构造函数
SeqList（constSeqList&A）;//A中元素固定不变
intLength（）;//求线性表的长度
TGet（inti）;//按位查找，取线性表的第i个元素
intLocate（Titem）;//查找元素item
voidInsert（inti,Titem）;//在第i个位置插入元素item
TDelete（inti）;//删除线性表的第i个元素
voiddisplay（）;//遍历线性表，按序号依次输出各元素
intempty（）;//判断线性表是否为空表
voidclear（）;//清空线性表
private:
Tdata[MaxSize];//存放数据元素的数组
intlength;//线性表的长度
};//存储结构定义
template
SeqList:
:
SeqList（）
{length=0;
}//无参构造函数实现,初始化表，置表的长度为0
template
SeqList:
:
SeqList（Ta[],intn）
{if（n>MaxSize）throw"数组元素个数不合法";
for（inti=0;idata[i]=a[i];
length=n;
}//有参构造函数实现
template
SeqList:
:
SeqList（constSeqList&A）
{for（inti=0;idata[i]=A.data[i];
length=A.length;
}//A的元素长度不变
template
intSeqList:
:
Length（）
{returnlength;
}//求线性表的长度
template
TSeqList:
:
Get（inti）
{returndata[i];
}//取序号为i的数据元素,返回序号为i的元素值
template
intSeqList:
:
Locate（Titem）
{for（inti=1;i<=length;i++）
if（data[i]==item）
returni+1;//下标为i的元素等于item，返回其序号i+1
return0;//查找失败
}//返回数据元素item在表中的位置
template
voidSeqList:
:
Insert（inti,Titem）
{intj;
if（length>=MaxSize）throw"溢出";
if（i<1||i>length+1）throw"i不合法！
";
for（j=length;j>=i;j--）
data[j]=data[j-1];
data[i-1]=item;
length++;
}//在线性表的第i个位置插入一个元素item
template
TSeqList:
:
Delete（inti）
{intitem,j;
if（length==0）throw"表为空,无法删除元素!
";
if（i<1||i>length）throw"i不合法!
";
item=data[i-1];
for（j=i;jdata[j-1]=data[j];
length--;
returnitem;
}//删除线性表的第i个位置上的元素item
template
voidSeqList:
:
display（）
{for（inti=0;icout<}//遍历线性表，按序号依次输出各元素
template
intSeqList:
:
empty（）
{if（length==0）
return1;
return0;
}//判断线性表是否为空表
template
voidSeqList:
:
clear（）
{length=0;
}//清空线性表
template
SeqListbin（SeqListA,SeqListB）
{SeqListC;
intm=1;
inta=A.Length（）;
for（intb=0;b<=B.Length（）;b++）
{
A.Insert（a+b+1,B.Get（b））;//将B的元素插到的A的后面成组合
}
for（chari='a';i<='z';i++）//定义字符i在a到z之间
{
for（intd=0;d<=A.Length（）;d++）
{
if（A.Get（d）==i）//取组合后元素将元素与i进行比较
{
C.Insert（m,i）;//相同的插入C
m++;//不相同继续
break;
}
}
}
returnC;
}//并运算
template
SeqListjiao（SeqListA,SeqListB）
{
SeqListC;
intm=1;
intflag=0;
for（chari='a';i<='z';i++,flag=0）//定义字符i在a到z之间
{
for（inta=0;a<=A.Length（）;a++）
{
if（A.Get（a）==i）//将i与A中元素进行比较
{
for（intb=0;b<=B.Length（）;b++）
{
if（B.Get（b）==i）//将i与B中元素进行比较
{
C.Insert（m,i）;//两次比较都有与i相同的元素，则将i插入C
m++;
flag=1;
break;
}
}
if（flag==1）
break;
}
}
}
returnC;
}//交运算
template
SeqListcha（SeqListA,SeqListB）
{
SeqListC;
intm=1;
intflag=0;
for（chari='a';i<='z';i++,flag=0）//定义字符i在a到z之间
{
for（inta=0;a<=A.Length（）;a++）
{
if（A.Get（a）==i）//将i与A中元素进行比较
{
for（intb=0;b<=B.Length（）;b++）
{
if（B.Get（b）==i）//如果i与A中元素相同，则将i与a中元素进行比较
{flag=m;}
}
if（flag==0）
{C.Insert（m,i）;//如果不同则将i插入C
m++;
break;
}
}
}
}
returnC;
}//减运算
intmain（）
{
chara[50];
charb[50];
cout<<"Set1:
";//输入set1数据
cin.getline（b,'/0'）;//所给数据中有空格，所以不能直接用cin
cout<cout<<"Set2:
";//输入set2数据
cin.getline（a,'/0'）;
cout<SeqListA（a,50）,B（b,50）,C,D,E;
C=bin（A,B）;//调用集合的并运算
cout<<"Set1∪Set2=";
C.display（）;
cout<D=jiao（A,B）;//调用集合的交运算
cout<<"Set1∩Set2=";
D.display（）;
cout<E=cha（B,A）;//调用集合的减法运算
cout<<"Set1-Set2=";
E.display（）;
cout<return0;
}
升级会员 