数据结构课程设计之集合的并交和差.doc

1、课程设计任务书计算机与通信工程学院 计算机科学技术专业 课程名称数据结构课程设计时间20092010学年第2学期1819周学生姓名指导老师题 目用C+语言解决集合的并、交和差问题主要内容：编制一个能执行集合的并、交和差运算的程序。集合的元素限定为小写字母字符；演示程序以用户和计算计的对话方式执行；以有序链表表示集合。要求：（1）通过实际项目的分析、设计、编码、测试等工作，掌握用C语言来开发和维护软件。（2）按要求编写课程设计报告书，能正确编写分析、设计、编码、测试等技术文档和用户使用手册。应当提交的文件：（1）课程设计学年论文。（2）课程设计附件（主要是源程序）。用C+语言解决集合的并、交和差

2、问题摘 要 本课程设计主要解决如何进行集合的运算，已有两个集合，设计程序而求它们的的并、交和差结果。在课程设计中，系统开发平台为Windows 2000，程序设计设计语言采用Visual C+，程序运行平台为Windows 98/2000/XP。通过运行程序，已实现题目要求，得正确结果，此虽为仅两个集合的运算，但若干个集合都可以慢慢的通过拿出两个来解决，可以改进后用于教学等。关键词 程序设计；集合；并、交和差；C+目录1 引言 11.1 课程设计背景 11.2 课程设计目的 1 1.3 课程设计要求 1 1.4 课程设计内容 12 设计思路与方案 32.1 设计思路 32.2 设计方案与函数

3、33 详细实现 53.1 各目标实现 5 3.2 用户与计算机对话实现 6 3.3 异常处理 74 运行环境与结果 94.1 运行环境 9 4.2 运行结果 95 结束语 12参考文献 13源程序 141 引 言本程序主要解决对两个集合编程序来求它们的并、交和差。1.1 课程设计背景 在很多教学课（如数据结构）上，经常要比较两个集合的大小，求它们的并、交和差，如果集合较短还好，但是集合很长的话，我们就没有这么多的心思来弄，不如利用学的知识，用C+编制一个程序可以一举解决这些问题就好了。这样既不会有错，又很方便，于是有了编制集合运算的诞生1。1.2 课程设计目的在程序设计中，可以用两种方法解决问

4、题：一是传统的结构化程序设计方法，二是更先进的面向对象程序设计方法2。深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的从何运用能力，增起那个对算法的理解能力，提高软件设计能力。在时间中培养独立分析问题和解决问题的作风和能力。1.3 课程设计的要求 熟练引用C+语言、基本数据接够和算法的奔出只是，独立编制一个具有中等难度的、解决实际问题的应用程序。通过提议分析、选择数据结构、算法设计、编制程序、调制程序、软件测试、结果分析、撰写课程设计报告等环节完成软件设计的全过程，不断的完善程序一提高程序的性能。1.4 程序设计的内容本程

5、序的目的是求两个集合的并、交和差，集合的元素限定为小写字母a-z，并一用户和计算机的对话方式执行，即以计算机终端上显示“提示信息”后，由用户在键盘上输入演示程序中规定的运算。流程如下图：计算机用户构造两个集合并为其分配空间输入两个集合输出两个集合弹出对话框，供用户选择用户选择相对的命令123其它0输出相应的结果输出集合的并结果输出集合的交结果输出集合的差结果提示用户输入有误结束演示图1.1 流程图2 设计思路与方案2.1 设计思路类是所有面向对象语言的共同特征，因此类是C+中十分重要的概念，是实现面向对象程序设计的基础。是C+的灵魂3。C+支持面向过程的程序设计，也支持基于对象的程序设计，又支

6、持面向对象的程序设计。基于对象就是基于类，与面向过程的程序不同，基于对象的程序是以类和对象为基础的，程序的操作是围绕对象进行的。在此基础上利用了继承机制和多态性，就成为面向对象的程序设计。C+中对象的类型称为类，类代表了某一批对象的共性和特征，类是对象的抽象，而对象是类的具体实例。在类体中是类的成员列表，列出类中的全部成员。它是一种广义的数据类型，除了数据部分以外，还包括了对这些数据操作的函数。这体现了把数据和操作封装在一起。2.2 设计方案与函数先构造两个结婚并为其分配空间，待用户输入集合后，输出供用户选择的命令。集合的并：调用集合并的函数，输出结果，清空集合dest；集合的交：调用集合交的

7、函数，输出结果，清空集合dest;集合的差：调用集合差的函数，输出结果，清空集合dest。下图是程序中用到的函数与其功能：函数名称函数功能LengthOf(Set src)返回一个集合的长度CreateSet(Set dest)创建一个新的字母集合，限定a-zEmptySet(Set dest)清空一个集合，保留头结点DestroySet(Set dest)销毁集合SortSet(Set dest)对一个集合进行从小到大的排序DisplaySet(Set src)打印集合的所有元素ExistElem(Set dest, ElemType e)判断元素是否存在于集合中DelElem(Set de

8、st, ElemType e)删除集合中的一个元素一次AddSet(Set dest, Set src1, Set src2)集合并运算MulSet(Set dest, Set src1, Set src2)集合交运算SubSet(Set dest, Set src1, Set src2)集合差运算ExistSubset(Set dest, Set src)子集判断AddElem(Set dest, ElemType e)在链表尾部追加一个元素表 2.1 程序涉及到的函数与其功能3 详细实现3.1 各目标实现1）如何给用户提供选择并作出相应的对话：用一个while循环，当输入命令数为非0时，插

9、入case循环，当输入0时，跳出while循环。while(cinitem)/选择循环if(item)switch(item)/非0选择case 1: cout集合并运算：Set1Set2 = ;/求两集合的并，并输出结果AddSet(dest, src1, src2);/调用求集合并的函数DisplaySet(dest);/输出结果EmptySet(dest);/清空集合destcoutendl;break;case 2: cout集合交运算：Set1Set2 = ;/求两集合的交，并输出结果MulSet(dest, src1, src2);/调用求集合交的函数DisplaySet(dest

10、);/输出结果EmptySet(dest);/清空集合destcoutendl;break;case 3: cout集合差运算：Set1-Set2 = ;/求两集合的差，并输出结果SubSet(dest, src1, src2);/调用求集合差的函数DisplaySet(dest);/输出结果EmptySet(dest);/清空集合destcoutendl;break;default: cout输入错误！重输！endl;break;else cout结束演示endl;break;/跳出循环DestroySet(dest);/调用摧毁函数摧毁集合destreturn 0;2）集合并实现：分别调用

11、函数AddSet(Set dest, Set src1, Set src2)；DisplaySet(Set src)；EmptySet(Set dest)；case 1:cout集合并运算：Set1Set2 = ;AddSet(dest, src1, src2);DisplaySet(dest);EmptySet(dest);coutendl;break;集合交实现：分别调用函数MulSet(Set dest, Set src1, Set src2)；DisplaySet(Set src)；EmptySet(Set dest)；case 2:cout集合交运算：Set1Set2 = ;MulS

12、et(dest, src1, src2);DisplaySet(dest);EmptySet(dest);coutendl;break;集合差实现：分别调用函数SubSet(Set dest, Set src1, Set src2)；DisplaySet(Set src)；EmptySet(Set dest)；case 3:cout集合差运算：Set1-Set2 = ;SubSet(dest, src1, src2);DisplaySet(dest);EmptySet(dest);coutendl;break;3）另外AddSet,MulSet，SubSet也分别调用了其余重要的函数，少了任何

13、一个程序都不能正常运行。函数可参看表2.1。3.2 用户与计算机对话实现 WHILE循环用户选择命令123其余整数0输出两集合并结果输出两集合交结果输出两集合差结果提示出入错误，重输结束循环，结束对话图 3.1 简化用户与计算机对话图用户输入命令1时，输出集合并结果；用户输入命令2时，输出集合交结果；用户输入命令3时，输出集合差结果；用户输入命令其它时，输出提示输入错误；用户输入命令0时，结束对话。用一个while循环，当输入命令为非0时：用一个case循环，来判断命令并输出结果，当输入命令为0时，结束演示。3.3 异常处理程序在执行时经常会出现一些违反设计期望的异常情况（如除零），过去的解决

14、方法是利用操作系统中断代为处理。由于这种解决方法强行中止了应用程序的运行，一些大型的应用系统的开发人员提出，可以在允许的范围内由应用程序自身来处理一般性的程序运行错误。C+语言异常处理由三个部分构成。异常检测的触发、异常检测的捕获和异常检测的处理3。它们分别对应了“try”、“throw”和“catch”三个关键字。这三者的关系如图3.2所示。图3.2 C+异常处理流程图被throw语句扔出的数据实际上被压入了相应层的catch语句所对应的堆栈内，最后才被catch语句捕获到的。当try语句出现嵌套时，情况可能会更加复杂。4 运行环境与结果4.1 运行环境在本课程设计中，系统开发平台为Wind

15、ows2000,程序设计语言为C+，程序的运行环境为Visual C+ 6.0。Visual C+一般分为三个版本:学习版、专业版和企业版，不同的版本适合于不同类型的应用开发。实验中可以使用这三个版本的任意一种，在本课程设计中，以Visual C+ 6.0为编程环境3。Microsoft Visual C+ 6.0是Microsoft公司的Microsoft Visual Studio 6.0开发工具箱中的一个C+程序开发包。Visual C+包中除包括C+编译器外，还包括所有的库、例子和为创建Windows应用程序所需要的文档。自1993年Microsoft公司推出Visual C+1.0后

16、，随着其新版本的不断问世，Visual C+已成为专业程序员进行软件开发的首选工具。 Visual C+从最早期的1.0版本，发展到最新的7.0版本，Visual C+已经有了很大的变化，在界面、功能、库支持方面都有许多的增强。最新的7.0版本在编译器、MFC类库、编辑器以及联机帮助系统等方面都比以前的版本做了较大改进。虽然微软公司推出了Visual C+.NET(Visual C+7.0)，但它的应用的很大的局限性，只适用于Windows 2000,Windows XP和Windows NT4.0。所以实际中，更多的是以Visual C+6.0为平台。Visual C+ 6.0是Micros

17、oft公司推出的目前使用最广泛的基于Windows平台的可视化编程环境。Visual C+ 6.0是在以往版本不断更新的基础上形成的，由于其功能强大，灵活性好，完全课扩展以及具有强大的Internet支持，因而在各种C+语言开发工具中脱颖而出，成为目前最为流行的C+语言集成开发环境。Visual C+ 6.0秉承Visual C+以前版本的优异特性，为用户提供了一套良好的可视化开发环境：主要包括文本编辑器、资源编辑器、工程创建工具、Debugger调试器等等。用户可以在集成开发环境中创建工程、打开工程、建立、打开和编辑文件、编译、链接、运行、调试应用程序。4.2 运行结果输出用户要处理的集合；

18、图 4.1 显示用户输入的两个集合求两集合的并、交和差：图 4.2 输出对应用户要求的结果错误输入：图 4.3 提示用户出入有误，重输结束演示：图 4.4 结束演示5 结束语在大一的时候已经做过一次课程设计了，心里还是有底的，比起那是成熟多了，熟练多了，感觉也没那么的难吧。当我一开始选了题，我心里就有了粗略的打算，一步一步底地进行着。这学期学了数据结构，又加深了对C的了解，学到了更好更强的编程方法。尤其是C语言的进步让深刻的感受到任何所学的知识都需要实践，没有时间就无法真正理解这些知识以及掌握它们，使其成为自己的财富。在理论学习和上级实践的各个环节中，通过自主学习和请教老师，我收获了不少。当然

19、也遇到了不少的难题，如怎样正确使用链表结构，也正是这些问题引发的思考给我带了不少的收获。从大一的时候不喜欢编程，没有兴趣，不主动写程序，不知如何下手到现在不会有那些标点符号的小错误发生，对编程有很深的兴趣，主动去写程序，还用不同的方法来实现结果，业余时间跟老师和同学的交流心得更频繁了，收获就不用说了。在实际的上级操作过程中，不仅是让那个我们了解数据结构的连理论知识，更重要的是培养解决实际问题的能里，所以相信通过此次实习可以提高我们分析设计能力和编程能力，为后续的学习及实践打下良好的基础。我选的题目是求集合并、交和差运算，其实不算难，就是要细心，稍不留神就会出错，我就早在中犯了好多此其实简单的错

20、误。本程序主要运用了线性表中的知识，现行结构的特点，在数据结构的非空有限集合中，存在唯一的一个被称做“一个”的数据元素，存在唯一的一个被称作“最后一个”数据元素，除第一个外，集合的每个数据元素均只有一个前驱，除最后一个之外，集合中每个数据元素均只有一个后继。在这次短短的课程实践里，我们得到了何锫老师的关心和帮助。他给了我们很多的信心，与我们一起探讨问题，询问我们遇到了哪些问题并耐心给予指导。当我们遇到技术上难以解决的问题时，他就会指导我们解决问题，他把自己多年来积累的经验传授给我们，使我们顺利的完成了课程实践任务。现在我们已是大2并结束了的准大三学生，两年的大学学习与实践培训，使我们学到并学稳

21、了知识，心中深怀感激情，对未来工作有了信心，相信未来会有我们美好的天空。参考文献1严蔚敏，吴伟民. 数据结构(C语言版). 北京：清华大学出版社，1997.42 谭浩强. C语言程序设计.北京：清华大学出版社，20053谭浩强. C+程序设计. 北京：清华大学出版社, 2005 附录 原程序#include#include#includeusing namespace std;#define ElemType chartypedef struct ElemNode ElemType elem;struct ElemNode *next;ElemNode, *Set;/-FunctionList

22、-/-函数原型-int LengthOf(Set src);/返回一个集合的长度void CreateSet(Set dest);/创建一个新的字母集合，限定a-zvoid EmptySet(Set dest);/清空一个集合，保留头结点void DestroySet(Set dest);/销毁集合void SortSet(Set dest);/对一个集合进行从小到大的排序void DisplaySet(Set src);/打印集合的所有元素int ExistElem(Set dest, ElemType e);/判断元素是否存在于集合中void DelElem(Set dest, ElemT

23、ype e);/删除集合中的一个元素一次void AddElem(Set dest, ElemType e);/在链表尾部追加一个元素void AddSet(Set dest, Set src1, Set src2);/集合并运算void MulSet(Set dest, Set src1, Set src2);/集合交运算void SubSet(Set dest, Set src1, Set src2);/集合差运算int ExistSubset(Set dest, Set src);/子集判断int main()/主函数Set dest=(Set)malloc(sizeof(ElemNod

24、e);/分配空间Set src1=(Set)malloc(sizeof(ElemNode);/分配空间Set src2=(Set)malloc(sizeof(ElemNode);/分配空间dest-next=NULL;cout输入两个集合：endl;CreateSet(src1);CreateSet(src2);/输入集合1和2coutendl;coutSet1 = ;DisplaySet(src1);/输出集合1coutt;coutSet2 = ;DisplaySet(src2);/输出集合2coutendlendl;int item;cout集合并 集合交 集合差 错误！重输 结束演示it

25、em)/选择循环if(item)switch(item)/非0选择case 1: cout集合并运算：Set1Set2 = ;/求两集合的并，并输出结果AddSet(dest, src1, src2);/调用求集合并的函数DisplaySet(dest);/输出结果EmptySet(dest);/清空集合destcoutendl;break;case 2: cout集合交运算：Set1Set2 = ;/求两集合的交，并输出结果MulSet(dest, src1, src2);/调用求集合交的函数DisplaySet(dest);/输出结果EmptySet(dest);/清空集合destcout

26、endl;break;case 3: cout集合差运算：Set1-Set2 = ;/求两集合的差，并输出结果SubSet(dest, src1, src2);/调用求集合差的函数DisplaySet(dest);/输出结果EmptySet(dest);/清空集合destcoutendl;break;default: cout输入错误！重输！endl;break;else cout结束演示next!=NULL)i+;src=src-next;return i;/LengthOfvoid CreateSet(Set dest)/创建一个新的字母集合，限定a-zElemType ch;Set p=

27、dest,n;for(;)ch=getchar();if(ch=n) break;if(ch122) continue;/确定输入的是小写字母n=(Set)malloc(sizeof(ElemNode);/分配空间p-next=n;n-elem=ch;n-next=NULL;p=n;return ;/CreateSetvoid EmptySet(Set dest)/清空一个集合，保留头结点Set p,n;while(dest-next!=NULL)p=dest;n=p-next;for(;n-next!=NULL;)/令集合里的每个元素都为空p=n;n=n-next;free(n);/释放np

28、-next=NULL;/EmptySetvoid DestroySet(Set dest)/销毁集合EmptySet(dest);/调用清空集合函数free(dest);/释放集合/DestroySetvoid SortSet(Set dest)/对一个字母集合进行从小到大的排序int i,j,l,flag;Set p,q,n;l=LengthOf(dest);/求集合的长度if(l0&flag=1;i-)flag=0;p=dest;q=p-next;n=q-next;for(j=0;jelemn-elem)/排序flag=1;p-next=n;q-next=n-next;n-next=q;q

29、=p-next;n=q-next;p=q;q=n;n=n-next;/SortSetvoid DisplaySet(Set src)/打印集合的所有元素Set p;if(src-next=NULL)printf();return ;p=src;dop=p-next;putchar(p-elem);/输出每个字母 while(p-next!=NULL);/DisplaySetint ExistElem(Set dest, ElemType e)/判断元素是否存在于集合中Set p=dest;if(LengthOf(p)=0)return 0;elsep=p-next;while(p-elem!=

30、e)if(p-next=NULL)return 0;p=p-next;return 1;/ExistElemvoid DelElem(Set dest, ElemType e)/删除集合中的一个元素一次Set p=dest,q;if(LengthOf(p)=0)return ;q=p-next;if(LengthOf(p)=1)/判断集合长度调用函数Lengthp-next=NULL;free(q);while(q-elem!=e)p=p-next;q=q-next;if(q-next=NULL)p-next=NULL;free(q);elsep-next=q-next;/DelElemvoi

31、d AddElem(Set dest, ElemType e)/在链表尾部追加一个元素Set p=dest, n;while(p-next!=NULL)p=p-next;n=(Set)malloc(sizeof(ElemNode);/分配空间p-next=n;n-elem=e;n-next=NULL;/AddElemvoid AddSet(Set dest, Set src1, Set src2)/集合并运算SortSet(src1);SortSet(src2);int i=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2);src1=src1-next

32、;src2=src2-next;while(ilen1&jelemelem)i+;if(!ExistElem(dest, src1-elem)/调用函数EistElemAddElem(dest, src1-elem);/调用函数AddElemsrc1=src1-next;elsesrc1=src1-next;elsej+;if(!ExistElem(dest, src2-elem) /调用函数EistElemAddElem(dest, src2-elem); /调用函数AddElemsrc2=src2-next;elsesrc2=src2-next;while(ielem) /调用函数Eist

33、ElemAddElem(dest, src1-elem); /调用函数AddElemsrc1=src1-next;while(jelem) /调用函数EistElemAddElem(dest, src2-elem); /调用函数AddElemsrc2=src2-next;/AddSetvoid MulSet(Set dest, Set src1, Set src2)/集合交运算SortSet(src1);SortSet(src2);int i=0,j=0,len1=LengthOf(src1),len2=LengthOf(src2);src1=src1-next;src2=src2-next;

34、while(ilen1&jelemelem) i+;src1=src1-next;else if(src1-elemsrc2-elem) j+;src2=src2-next;else i+;j+;if(!ExistElem(dest, src1-elem) /调用函数EistElemAddElem(dest, src1-elem); /调用函数AddElemsrc1=src1-next;src2=src2-next;/MulSetvoid SubSet(Set dest, Set src1, Set src2)/集合差运算SortSet(src1);SortSet(src2);int i=0,len=LengthOf(src1);src1=src1-next;while(ielem)if(!ExistElem(dest, src1-elem)AddElem(dest, src1-elem);src1=src1-next;elsesrc1=src1-next;/SubSet .