数据结构课程设计报告---单链表表示集合---实现交并差

西安建筑科技大学华清学院课程设计（论文）题 目： 院 （系）： 专业班级： 计算机 姓 名： 学 号： 指导教师： 2016年 9 月 8日第12页 共？页西安建筑科技大学华清学院课程设计（论文）任务书专业班级： 学生姓名： 指导教师（签名）： 一、课程设计（论文）题目集合运算： 使用链表来表示集合，完成集合的合并，求交集等操作。二、本次课程设计（论文）应达到的目的数据结构是实践很强的课程，课程设计是加强学生实践能力的一个强有力的手段。课程设计要求我们完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于我们基本程序素养的培养和软件工作者工作作风的训练。将起到显著的促进作用。 本题目要达到目的：熟练掌握链表的各种操作三、本次课程设计（论文）任务的主要内容和要求（包括原始数据、技术参数、设计要求等）输入数据：输入10个以内的字符进行程序测试。1、自己输入两了任意集合。2、用对话框的形式显示集合运算的结果。3、优化对话框。四、应收集的资料及主要参考文献： 由于本课程没有安排“课内上机”学时，因此，在课程设计之前必须自己已经上机练习了“线性表”的基本操作。 参考文献：1. 数据结构-C语言描述，西安电子科技大学出版社，2011.5，耿国华编著2数决结构与算法分析(C+版),电子工业出版社,2005.7,Clifford A.Shaffer编著3. 数据结构与算法,科学出版社,2005.08,赵文静 祁飞等编著4. 数据结构-C+语言描述，西安交通大学出版社，1999.01，赵文静编著5. VC+深入详解,电子工业出版社,2007.7,孙鑫,于安萍编著五、审核批准意见教研室主任（签字） 设计总说明该设计主要应实现以下功能：1. 利用尾差法建立单链表2. 对于输入的链表进行有序排列3. 删除有序链表中不符合要求的元素4. 调用函数对单链表进行交，并，差运算，并输出系统主要由8个模块组成，分别是：1. 单链表的建立2. 单链表的有序排列3. 删除单链表中不符合条件的元素4. 集合交集5. 集合并集6. 集合差集7. 单链表输出8. 主函数目录1.设计目的12.问题描述13.需求分析14.概要设计15.详细设计16.调试分析17.使用说明28.设计总结29.参考文献2目录在你完成后面的内容后要更新页码！数据结构课程设计集合运算1.设计目的这部分不用改“数据结构”是计算机科学与技术专业一门十分重要的专业技术基础课，计算机科学各领域及有关的应用软件都要使用到各种数据结构。在我国，”数据结构与算法”已经作为理工科非计算机专业必修的信息技术基础课程之一。世界上许多科技人员对学习、研究数据结构和算法都非常重视，对于从事计算机科学及其应用的科技工作者来说，数据结构与算法更是必须透彻地掌握的重要基础。学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。课程设计是加强学生实践能力的一个强有力手段。课程设计所安排的题目，在难度和深度方面都大于平时的上机训练，要求同学在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，强化面向对象的程序设计理念；使同学的程序设计与调试水平有一个明显的提高。课程设计要求学生在完成程序设计的同时能够写出比较规范的设计报告。严格实施课程设计这一环节，对于学生基本程序设计素养的培养和软件工作者工作作风的训练，将起到显著的促进作用。页脚中的“共？页”中的？号调整成你的2.问题描述简要介绍你的题目要做些啥，有什么用用有序单链表表示集合，实现集合的交、并、差运算。3.需求分析3.1 数据需求字符范围：小写字母a,b,.,y,z,大写字母A,B,.Y，Z，和数字0,1，.8,9;数据对象：属于同一个结构体的集合。数据关系：具有线性关系。3.2 基本功能需求可快速的分别求出两个字符集合的交、并、差。3.3 非功能性需求用户界面需求：简洁、易用、易懂、友好的用户界面。硬件要求：装有Visual C+6.0的计算机。可靠性需求：保证用户在正常使用本系统时，用户的操作或误操作不会产生数据的丢失。5. 概要设计主要说明对软件中有关信息设计的数据结构；画出整个软件的系统结构图，说明各个模块的功能。4.1 数据结构数据结构的基本操作实现如下：（1） InitLinkList(LinkList Head)：初始化集合（2） Check(char ch,LinkList Head)：检查p1或p2所指向数据结点该不该加入到Head为起始的集合中（3）Merge(LinkList Head1,LinkList Head2)：合并两个集合 （4）IsExist(char data,LinkList Head)； IsExist2(char data,LinkList Head)：集合A中的元素，B中是否存在（5）Deprive(LinkList Head1,LinkList Head2)：两个集合的差集 （6）Insection(LinkList Head1,LinkList Head2)：两个集合交集（7）PrintLinkList(LinkList Head)：打印集合元素4.2 系统包含的函数InitLinkList(LinkList Head)Check(char ch,LinkList Head)Merge(LinkList Head1,LinkList Head2)IsExist2(char data,LinkList Head)Deprive(LinkList Head1,LinkList Head2)Insection(LinkList Head1,LinkList Head2)PrintLinkList(LinkList Head)4.3 函数间的关系1.求两个集合的并集时，Merge(LinkList Head1,LinkList Head2)函数首先调用了InitLinkList(LinkList Head)函数，多次调用了Check(char ch,LinkList Head)函数。2.求两个集合的差集时，Deprive(LinkList Head1,LinkList Head2)函数首先也调用了InitLinkList(LinkList Head)函数，后面循环调用IsExist2(char data,LinkList Head)函数。3.求两个集合交集时，Insection(LinkList Head1,LinkList Head2)函数的思路同Deprive(LinkList Head1,LinkList Head2)函数类似，它同样也是先进行初始化，首先调用了InitLinkList(LinkList Head)函数，后面循环调用IsExist(char data,LinkList Head)函数。4.主函数也即main()依次调用成员函数。4.4 系统功能模块图主函数单链表的建立及由于排列删除不符合条件的元素集合交集集合差集单链表输出集合并集 系统功能模块图5.主要写出所设计数据结构的详细定义和组成；各个模块的算法流程图或伪码表示。详细设计这部分可以粘贴部分代码，诚信保证书可以放在这部分5.1 结构体的详细定义LinkList Merge(LinkList Head1,LinkList Head2) LinkList Head=(Node*)malloc(SIZE); Head-data=0;Head-next=NULL; Node *p1=Head1-next; Node *p2=Head2-next; Node *p=Head; while(p1!=NULL&p2!=NULL) if(p1-data=p2-data) if(Check(p1-data,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode-data=p1-data; p-next=newNode; p=newNode; p-next=NULL; else if(Check(p1-data,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode-data=p1-data; p-next=newNode; p=newNode; p-next=NULL; if(Check(p2-data,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode-data=p2-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; p2=p2-next; while(p1!=NULL) if(Check(p1-data,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode-data=p1-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; while(p2!=NULL) if(Check(p2-data,Head)=TRUE) Node *newNode=(Node*)malloc(SIZE); newNode-data=p2-data; p-next=newNode; p=newNode; p-next=NULL; p2=p2-next; return Head; /两个集合的差集 LinkList Deprive(LinkList Head1,LinkList Head2) LinkList Head=(Node*)malloc(SIZE); Node *p=Head; Node *p1=Head1-next; while(p1!=NULL) if(IsExist2(p1-data,Head2)=1) Node *newNode=(Node*)malloc(SIZE); newNode-data=p1-data; p-next=newNode; p=newNode; p-next=NULL; p1=p1-next; return Head; 5.2 系统函数详细介绍（1） void InitLinkList(LinkList Head)； /初始化集合（2） int Check(char ch,LinkList Head)； /检查p1或p2所指向数据结点该不该加入到Head为起始的集合中（3）LinkList Merge(LinkList Head1,LinkList Head2)； /合并两个集合 （4）int IsExist(char data,LinkList Head)； int IsExist2(char data,LinkList Head)； /集合A中的元素，B中是否存在（5）LinkList Deprive(LinkList Head1,LinkList Head2)； /两个集合的差集 （6）LinkList Insection(LinkList Head1,LinkList Head2)； /两个集合交集（7）void PrintLinkList(LinkList Head)； /打印集合元素 5.3 系统功能模块介绍求两个集合的并集时，Merge(LinkList Head1,LinkList Head2)函数首先调用了InitLinkList(LinkList Head)函数，多次调用了Check(char ch,LinkList Head)函数。求两个集合的差集时，Deprive(LinkList Head1,LinkList Head2)函数同Merge(LinkList Head1,LinkList Head2)函数一样首先也调用了InitLinkList(LinkList Head)函数，后面循环调用IsExist2(char data,LinkList Head)函数。求两个集合交集时，Insection(LinkList Head1,LinkList Head2)函数的思路同Deprive(LinkList Head1,LinkList Head2)函数类似，它同样也是先进行初始化，首先调用了InitLinkList(LinkList Head)函数，后面循环调用IsExist(char data,LinkList Head)函数。主函数也即main()依次调用成员函数。5.4 具体模块设计把各个模块用图示的方法画出流程图，注意图下方要有“图号 图名”，例如“图5-1宿舍信息的录入流程图”6.调试分析本软件是基于Windows的编程开发，所以，软件调试必须在Windows环境下进行。调试前须做好准备工作：(1) 需要安装Visual C+6.0的计算机一台；配置好之后，在Visual C+6.0环境下进行软件的调试。(2) 测试数据：集合输入：在“输入数据”模块中，根据主界面提示，请输入集合1，输入#截止，再输入另一个集合。确定，显示计算结果。如果错误输入，观察是否能正常显示信息。否则修改程序再进行调试。例如：输入集合1 2 3和1 2 4后确定，假设数据为：两个集合的并集为1234，两个集合的交集为12，两个集合的差集为3.程序正常运行。退出保存。(3) 算法改进设想：在程序设计前期，我们并没有用txt文件来保存学生信息。经过我不断的修改以及调试后，该程序总算可以进行txt文本的读出与写入，并且添加学生信息后可以直接将信息保存在txt文本文件中。仿照这段话来写，不能原封不动6. 使用说明1.按屏幕提示输入字符串1的元素，输入完成后输入“#”，回车后输入字符串2，并按“#”后，再按回车键，即出现运算结果；2.按屏幕提示输入选择是否继续，如果继续，则重复第一步，否则结束；3.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运算结果显示在其后。7. 设计总结包括课程设计过程的收获； 遇到的问题，解决问题过程的思考（存在问题？问题如何解决？）；程序调试能力的思考对数据结构这门课程的思考在课程设计过程中对数据结构课程的认识等内容1. 数据结构使用小结链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。单链表中每个结点的存储地址是存放在其前趋结点next域中，而开始结点无前趋，故应设头指针head指向开始结点。单链表的建立有头插法、尾插法两种方法。在本次课程设计中采取了尾差法进行建立单链表。尾插法建立链表时，头指针固定不动，故必须设立一个搜索指针，向链表右边延伸，则整个算法中应设立三个链表指针，即头指针、搜索指针、申请单元指针。在使用尾插法建立单链表时最先得到的一定是头结点。通过本次上机实验，使我掌握了C+面向对象程序的基本操作，在上机实践过程中，编程水平得到了进一步提升实践能力得到了加强与锻炼。全面掌握C+面向对象程序设计的方法和技术，通过课程设计我进一步理解和掌握了C+面向对象程序的意义和作用，在上机实践过程中，我也遇到了很多困难，老师和同学给了我很大的帮助。上机过程中遇到的主要问题是：1. 对一些语句的使用不太熟悉，不能够良好的应用，通过老师、同学的帮助了解了一部分，但还需更多的努力。2. 对程序运行的基本条件掌握不够，在调试过程中遇到很多困难，多亏有同学的帮忙，才使得程序最后能通畅运行。3. 对程序的设计学习还没有很好的理解，导致设计过程中漏洞较多，通过老师和同学的修改才得以正常运行。 在上机过程中还学习了很多课本上没有的知识，实践能力得到了大幅度的提高，程序的调试技能有所提高，但更多的是在上机过程中发现了很多不足之处，需要在以后的学习与工作中不断的学习和实践，扎扎实实的学习，一步一个脚印，积累程序设计的经验和方法。参考文献1. 耿国华编著，数据结构-C语言描述，西安电子科技大学出版社，2011.52Clifford