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

集合的并、交和差运算 软件工程3班 尚杰 20112344922 需求分析 设计目的: 通过集合运算的实现，熟练掌握线性表的基本操作在两种存储结构上的实现，其中以各种链表的操作和应用作为重点内容。 1.本演示程序中，集合的元素限制在小写字母‘a’-‘z’之间。集合的大小不限制，集合的输入形式为一个以“#”为结束标志的字符串，串中字符顺序不限，且允许出现重复字符或非法字符，程序运用时自动过滤去，输出的运算结果中将不含重复字符和非法字符。 2.演示程序以用户和计算机对话的形式进行，即在计算机终端中显示提示信息之后，有用户自行选择下一步命令，相应输入数据和运算结果在其后显示。 3.程序的执行命令有：1）选择操作 2）任意键清屏 概要设计 详细设计 #include iostream //C++输入输出流 #include List //链表类 using namespace std; #define DataTpye char //定义数据类型 bool IsElementInList(listDataTpye aSet, DataTpye iElement) //查看iElement元素是否在aSet集合中 { listDataTpye::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(listDataTpye aSet) //去除集合aSet中的重复元素 { listDataTpye newSet; //在这里新创建一个单链表newSet，后面对aSet中的相同元素删除其仅剩一个为止，并放入newSet listDataTpye::iterator iter; 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 } void Union(listDataTpye set1, listDataTpye set2) //实现集合的并集运算，找出Set,Set_2中的所有元素 { listDataTpye newSet = set1; listDataTpye::iterator iter; 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集合的并操作结果是：endl; cout{; for (iter = newSet.begin(); iter != newSet.end(); iter++) { cout*iter ; } cout}endl; } void Inter(listDataTpye set1, listDataTpye set2) //实现集合的交集运算，找出Set,Set中的相同元素 {