数据结构实习报告--集合的并交叉运算.doc

集合的并、交和差运算软件工程3班 尚杰 20112344922一、 需求分析设计目的:通过集合运算的实现，熟练掌握线性表的基本操作在两种存储结构上的实现，其中以各种链表的操作和应用作为重点内容。1.本演示程序中，集合的元素限制在小写字母a-z之间。集合的大小不限制，集合的输入形式为一个以“#”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。 2.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。 3.程序的执行命令有：1）选择操作 2）任意键清屏二、 概要设计三、 详细设计#include /C+输入输出流#include /链表类using namespace std;#define DataTpye char/定义数据类型bool IsElementInList(list aSet, DataTpye iElement)/查看iElement元素是否在aSet集合中list:iterator iter;for (iter = aSet.begin(); iter != aSet.end(); iter+)/遍历aSet单链表中的所有元素【后面同理】，直到找到与iElement元素相同的元素，返回true表明存在iElement元素if (*iter = iElement) /在单链表中找到了与iElement元素相同的元素，此时开始执行if语句块return true;/由于不满足for中的条件表明iElement元素在aSet中不存在 return false;void Trim(list &aSet)/去除集合aSet中的重复元素list newSet;/在这里新创建一个单链表newSet，后面对aSet中的相同元素删除其仅剩一个为止，并放入newSetlist:iterator iter;for (iter = aSet.begin(); iter != aSet.end(); iter+)if (!IsElementInList(newSet, *iter)&(*iter=97&*iter=97&*iter=122)这是极其关键的一部分，它的作用是删除链表中的数字/在存储的时候数字是以字符的形式存储的，此时通过使用小写英文字母的ASCII码来限制入栈的元素newSet.push_back(*iter);aSet = newSet;/操作进行完成将newSet有重新赋给aSetvoid Union(list set1, list set2)/实现集合的并集运算，找出Set,Set_2中的所有元素list newSet = set1;list:iterator iter;for (iter = set2.begin(); iter != set2.end(); iter+)if (IsElementInList(newSet, *iter)continue;/在newSet中查找与iter相同的元素，如果if语句条件成立，表明IsElementInList()操作完成后返回了true/不做处理，跳出循环继续向后查找在newSet中查找与iter相同的元素elsenewSet.push_back(*iter);/if不满足条件表明是在set2中存在的元素而在set1中没有，此时入栈到newSet Trim(newSet); newSet.sort();/类中的方法，将单链表中的元素有序排列 cout集合的并操作结果是：endl; cout; for (iter = newSet.begin(); iter != newSet.end(); iter+)cout*iter ;coutendl;void Inter(list set1, list set2)/实现集合的交集运算，找出Set,Set中的相同元素 list newSet; list:iterator iter; for (iter = set1.begin(); iter != set1.end(); iter+) if (IsElementInList(set2, *iter)/在newSet中查找与iter相同的元素，如果if语句条件成立，表明IsElementInList()操作完成后返回了true/if条件成立找到了set2与set1相同的元素此时入栈到newSetnewSet.push_back(*iter);elsecontinue; Trim(newSet); newSet.sort(); cout集合的交操作结果是：endl; cout; for (iter = newSet.begin(); iter != newSet.end(); iter+) cout*iter ; coutendl;void Differ(list set1, list set2)/实现集合的差集运算，其本质是：在Set中找出与Set相同的元素将其删除 list newSet; list:iterator iter;for (iter = set1.begin(); iter != set1.end(); iter+)if (IsElementInList(set2, *iter)/在set2中找出与iter相同的元素，不做入栈continue;elsenewSet.push_back(*iter);/将set1中与set2不相同的元素入栈到newSet，其意义就是作set1-set2 Trim(newSet); newSet.sort(); cout集合的差操作结果是：endl; cout;for (iter = newSet.begin(); iter != newSet.end(); iter+) cout*iter ; coutendl;int main(void) cout输入集合Set1的元素，按#结束endl;list set1, set2;/定义两个单链表set1, set2用来实现测试数据元素的输入list:iterator iter;DataTpye iIn = -1; /初始化输入的元素 while (# != iIn) /用【#】来作为结束输入的结束标志 ciniIn; set1.push_back(iIn); set1.pop_back(); Trim(set1); set1.sort(); cout输入的集合set1是：endl; cout; for (iter = set1.begin(); iter != set1.end(); iter+) cout*iter ; coutendl; cout输入集合set2的元素，按#结束iIn; set2.push_back(iIn); set2.pop_back(); Trim(set2); set2.sort(); cout输入的集合set2是：endl; cout; for (iter = set2.begin(); iter != set2.end(); iter+) cout*iter ; coutendl; here: cout选择操作：1并集，2交集，3差集，0退出iIn; switch(iIn) case 1:Union(set1, set2);break; case 2:Inter(set1, set2);break; case 3:Differ(set1, set2);break; case 0:return 0 ; default:break; goto here;四、 调试分析1、 本实习作业采用数据抽象的程序设计方法，将程序划分为三个层次：结构体定义、操作函数、主控模块，使得设计思路清晰，实现时调试顺利，各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。2、 通过查阅书籍，对顺序表，链表有了更清晰的认识五、 用户手册1.本程序的运行环境为DOS操作系统，可执行文件为：JIhe2.exe 2.为了界面更加友好特将背景颜色设计为白色，字体为黑色。 3.进入演示程序后的用户界面（见下，测试结果截图）。六、测试结果 1.数据测试 （1）输入”server 123 $%& #” ; “success #” Set1=”e r s v”, Set2=”c e s u”; Set1Set2= “c e r s u v”,