数据结构.docx
- 文档编号:1263703
- 上传时间:2023-04-30
- 格式:DOCX
- 页数:15
- 大小:188.58KB
数据结构.docx
《数据结构.docx》由会员分享,可在线阅读,更多相关《数据结构.docx(15页珍藏版)》请在冰点文库上搜索。
数据结构
数据结构课程设计
集合的交、并和差运算
班级学号
2123227
学生姓名
刘红廷
提交日期
2014年7月18日
成绩
:
计算机与通信工程学院
实验题目:
集合的交、并、差运算
一、需求分析
本程序主要实现对两个集合进行求交、并、差集的运算。
1.集合的元素限制在小写字母‘a’-‘z’之间。
集合的大小不限制,集合的输入形式为一个以“#”为结束标志的字符串,串中字符顺序不限,且允许出现重复字符或非法字符,程序运用时自动过滤去,输出的运算结果中将不含重复字符和非法字符。
2.演示程序以用户和计算机对话的形式进行,即计算机显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运算命令;,相应输入数据(滤出输入中的非法字符)和运算结果在其后显示。
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
2.以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∪set2=“aegimnprz”,set1∩set2=“ae”,set1-set2=“gimnz”;
●Set1=“012oper4a6tion89”,set2=“errordata”,
Set1∪set2=“adeinoprt”,set1∩set2=“aeort”,set1-set2=“inp”;
1.输入字符串中无重复元素,对两集合进行的运算结果如下:
2.当某一集合中出现重复的元素时,程序自动将重复的元素过滤后在进行运算
3.当用户输入的字符包括数字、特殊符号时,运算结果如下
4.当输入的两个集合为相同元素时,运算如下:
六、源代码
#include
#include//链表类
usingnamespacestd;//使用C++的命名空间std
#defineDataTpyechar//定义数据类型
boolIsElementInList(list
//使用布尔函数,判断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中的重复元素
{list
//在这里新创建一个单链表newSet,后面对aSet中的相同元素删除其仅剩一个为止,并放入newSet
list
:
iteratoriter;
for(iter=aSet.begin();iter!
=aSet.end();iter++)
{if(!
IsElementInList(newSet,*iter)&&(*iter>=97&&*iter<=122))
//(*iter>=97&&*iter<=122)这是极其关键的一部分,它的作用是删除链表中的数字
//在存储的时候数字是以字符的形式存储的,此时通过使用小写英文字母的ASCII码来限制插入单链表的元素
{newSet.push_back(*iter);
}
}
aSet=newSet;
//操作进行完成将newSet有重新赋给aSet
}
voidUnion(list
//实现集合的并集运算,找出Set,Set_2中的所有元素
{list
list
:
iteratoriter;
for(iter=set2.begin();iter!
=set2.end();iter++)
{if(IsElementInList(newSet,*iter))
{continue;
//在newSet中查找与iter相同的元素,如果if语句条件成立,表明IsElementInList()操作完成后返回了true
//不做处理,跳出循环继续向后查找在newSet中查找与iter相同的元素
}
else
{newSet.push_back(*iter);
//if不满足条件表明是在set2中存在的元素而在set1中没有,此时插入到newSet
}
}
Trim(newSet);
newSet.sort();//类中的方法,将单链表中的元素按照升序排列
cout<<"集合的并操作结果是:
"< cout<<"{"; for(iter=newSet.begin();iter! =newSet.end();iter++) {cout<<*iter<<""; } cout<<"}"< } voidInter(list //实现集合的交集运算,找出Set,Set中的相同元素 {list list : iteratoriter; for(iter=set1.begin();iter! =set1.end();iter++) {if(IsElementInList(set2,*iter)) {//在newSet中查找与iter相同的元素,如果if语句条件成立,表明IsElementInList()操作完成后返回了true //if条件成立找到了set2与set1相同的元素此时插入到newSet newSet.push_back(*iter); } else {continue; } } Trim(newSet); newSet.sort(); cout<<"集合的交操作结果是: "< cout<<"{"; for(iter=newSet.begin();iter! =newSet.end();iter++) {cout<<*iter<<""; } cout<<"}"< } voidDiffer(list //实现集合的差集运算,其本质是: 在Set中找出与Set相同的元素将其删除 {list list : iteratoriter; for(iter=set1.begin();iter! =set1.end();iter++) {if(IsElementInList(set2,*iter)) {//在set2中找出与iter相同的元素,不做插入操作 continue; } else {newSet.push_back(*iter); //将set1中与set2不相同的元素插入到newSet,其意义就是作set1-set2 } } Trim(newSet); newSet.sort(); cout<<"集合的差操作结果是: "< cout<<"{"; for(iter=newSet.begin();iter! =newSet.end();iter++) {cout<<*iter<<""; } cout<<"}"< } intmain(void) {cout<<"输入集合Set1的元素,按'#'结束"< list //定义两个单链表set1,set2用来实现测试数据元素的输入 list : iteratoriter; DataTpyeiIn=-1;//初始化输入的元素 while('#'! =iIn)//用#来作为结束输入的结束标志 {cin>>iIn; set1.push_back(iIn); } set1.pop_back(); Trim(set1); set1.sort(); cout<<"输入的集合set1是: "< cout<<"{"; for(iter=set1.begin();iter! =set1.end();iter++) {cout<<*iter<<""; } cout<<"}"< cout<<"输入集合set2的元素,按'#'结束"< iIn=-1;//回置数据标志 while('#'! =iIn) {cin>>iIn; set2.push_back(iIn); } set2.pop_back(); Trim(set2); set2.sort(); cout<<"输入的集合set2是: "< cout<<"{"; for(iter=set2.begin();iter! =set2.end();iter++) {cout<<*iter<<""; } cout<<"}"< here: cout<<"选择操作: 1并集,2交集,3差集,0退出"< cin>>iIn; switch(iIn) {case'1': Union(set1,set2);break; case'2': Inter(set1,set2);break; case'3': Differ(set1,set2);break; case'0': return0; default: break; } gotohere; } 七、参考文献 《数据结构》(C语言版)严蔚敏、吴伟民著清华大学出版社出版 《数据结构题集》(C语言版)严蔚敏、吴伟民著清华大学出版社出版 《C++程序设计》谭浩强著清华大学出版社出版 《数据结构习题集与实验指导书》
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构