数据结构Word格式.docx
《数据结构Word格式.docx》由会员分享，可在线阅读，更多相关《数据结构Word格式.docx（15页珍藏版）》请在冰点文库上搜索。
3.程序的执行命令有
1）选择操作；
2）程序结束
4.测试数据
1）Set1=“magazine”，set2=“paper”，
Set1∪set2=“aegimnprz”，set1∩set2=“ae”，set1－set2=“gimnz”；
2）Set1=“012oper4a6tion89”，set2=“errordata”，
Set1∪set2=“adeinoprt”，set1∩set2=“aeort”，set1－set2=“inp”；
二、详细设计
●首先对于用户输入的字符进行筛选和过滤，若用户输入的内容不合法，即包括不为字母的其他字符，可以根据字符输入后在计算机中的存储形式为ASCⅡ，完成操作。
●设有集合A、B，A与B的交集为A∩B。
A∩B指既属于集合A又属于集合B的元素。
因为要求另外申请存储空间，可另找一个新的集合C，C中存储A和B共同的元素。
问题即变为求：
C=A∩B。
算法思想为：
以A为标准，对B进行遍历，把B中和A相同的元素存储到C中。
具体过程如下：
1.扫描A，对A中每个元素执行2
2.在B中查找该元素
1）如果B中有，则保留到C中
2）否则，继续查找
3.显示C=A∩B
●求集合的并就是求A和B中所有的元素，先定义两个集合的并，设计思路如下：
1.把A中的元素全部放到一个集合C中
2.以A每一个元素为基准，对B进行循环
1）B中存在元素与该元素不同，则把该元素放到C中
2）B中存在元素与该元素相同，继续循环
3.显示C=A+B
●我们定义两个集合的差，设计思路如下：
1.假定A大于B，计算C=A-B
1）B中元素都与该元素不同，则把该元素放到C中
2）B中存在元素与该元素相同，继续循环
3.显示C=A-B
三、调试分析
1、本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：
结构体定义、操作函数、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。
2、在设计中为了实现对输入字符串的筛选功能，使用了布尔类型定义，判断真假。
3、通过查阅书籍，对顺序表，链表有了更清晰的认识
四、用户手册
根据界面的提示信息进行输入即可，当用户的输入出现非小写字母，如数字、特殊符号等，程序会根据运算的要求自动过滤与集合运算无关的字符，不用的担心出现错误的输入。
1.本程序的运行环境为DOS操作系统，可执行文件为：
未命名2.exe
2.为了界面更加友好特将背景颜色设计为黑色，字体为白色。
3.进入演示程序后的用户界面（见下，测试结果截图）。
五、测试结果
●Set1=“magazine”，set2=“paper”，
●Set1=“012oper4a6tion89”，set2=“errordata”，
1.输入字符串中无重复元素，对两集合进行的运算结果如下：
2.当某一集合中出现重复的元素时，程序自动将重复的元素过滤后在进行运算
3.当用户输入的字符包括数字、特殊符号时，运算结果如下
4.当输入的两个集合为相同元素时，运算如下：
六、源代码
#include<
iostream>
//C++输入输出流，预处理指令
List>
//链表类
usingnamespacestd;
//使用C++的命名空间std
#defineDataTpyechar//定义数据类型
boolIsElementInList（list<
DataTpye>
aSet,DataTpyeiElement）
//使用布尔函数，判断iElement元素是否在aSet集合中
{list<
:
iteratoriter;
for（iter=aSet.begin（）;
iter!
=aSet.end（）;
iter++）
//遍历aSet单链表中的所有元素，直到找到与iElement元素相同的元素，返回true表明存在iElement元素
{if（*iter==iElement）
//在单链表中找到了与iElement元素相同的元素，此时开始执行if语句块
{returntrue;
}
returnfalse;
//由于不满足for中的条件表明iElement元素在aSet中不存在
}
voidTrim（list<
&
aSet）
//去除集合aSet中的重复元素
newSet;
//在这里新创建一个单链表newSet，后面对aSet中的相同元素删除其仅剩一个为止，并放入newSet
list<
{if（!
IsElementInList（newSet,*iter）&
&
（*iter>
=97&
*iter<
=122））
//（*iter>
=122）这是极其关键的一部分，它的作用是删除链表中的数字
//在存储的时候数字是以字符的形式存储的，此时通过使用小写英文字母的ASCII码来限制插入单链表的元素
{newSet.push_back（*iter）;
}
aSet=newSet;
//操作进行完成将newSet有重新赋给aSet
voidUnion（list<
set1,list<
set2）
//实现集合的并集运算，找出Set,Set_2中的所有元素
newSet=set1;
for（iter=set2.begin（）;
=set2.end（）;
{if（IsElementInList（newSet,*iter））
{continue;
//在newSet中查找与iter相同的元素，如果if语句条件成立，表明IsElementInList（）操作完成后返回了true
//不做处理，跳出循环继续向后查找在newSet中查找与iter相同的元素
else
//if不满足条件表明是在set2中存在的元素而在set1中没有，此时插入到newSet
Trim（newSet）;
newSet.sort（）;
//类中的方法，将单链表中的元素按照升序排列
cout<
<
"
集合的并操作结果是：
endl;
{"
;
for（iter=newSet.begin（）;
=newSet.end（）;
{cout<
"
cout<
}"
voidInter（list<
//实现集合的交集运算，找出Set,Set中的相同元素
{list<
for（iter=set1.begin（）;
=set1.end（）;
{if（IsElementInList（set2,*iter））
{//在newSet中查找与iter相同的元素，如果if语句条件成立，表明IsElementInList（）操作完成后返回了true
//if条件成立找到了set2与set1相同的元素此时插入到newSet
newSet.push_back（*iter）;
}
集合的交操作结果是：
voidDiffer（list<
//实现集合的差集运算，其本质是：
在Set中找出与Set相同的元素将其删除
for（iter=set1.begin（）;
{if（IsElementInList（set2,*iter））
{//在set2中找出与iter相同的元素，不做插入操作
continue;
//将set1中与set2不相同的元素插入到newSet，其意义就是作set1-set2
Trim（newSet）;
集合的差操作结果是：
for（iter=newSet.begin（）;
{cout<
intmain（void）
{cout<
输入集合Set1的元素，按'
#'
结束"
set1,set2;
//定义两个单链表set1,set2用来实现测试数据元素的输入
DataTpyeiIn=-1;
//初始化输入的元素
while（'
!
=iIn）//用#来作为结束输入的结束标志
{cin>
>
iIn;
set1.push_back（iIn）;
set1.pop_back（）;
Trim（set1）;
set1.sort（）;
输入的集合set1是：
输入集合set2的元素，按'
iIn=-1;
//回置数据标志
=iIn）
{cin>
set2.push_back（iIn）;
set2.pop_back（）;
Trim（set2）;
set2.sort（）;
输入的集合set2是：
here:
选择操作：
1并集，2交集，3差集，0退出"
cin>
switch（iIn）
{case'
1'
Union（set1,set2）;
break;
case'
2'
Inter（set1,set2）;
3'
Differ（set1,set2）;
case'
0'
return0;
default:
break;
gotohere;
七、参考文献
《数据结构》（C语言版）严蔚敏、吴伟民著清华大学出版社出版
《数据结构题集》（C语言版）严蔚敏、吴伟民著清华大学出版社出版
《C++程序设计》谭浩强著清华大学出版社出版
《数据结构习题集与实验指导书》
升级会员 