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

资源描述

西安建筑科技大学华清学院课程设计（论文）题目：院（系）：专业班级：计算机姓名：学号：指导教师： 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.设计目的 1 2.问题描述 1 3.需求分析 1 4.概要设计 1 5.详细设计 1 6.调试分析 1 7.使用说明 2 8.设计总结 2 9.参考文献 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.5 2．Clifford A.Shaffer编著，数决结构与算法分析(C++版),电子工业出版社,2005.7 3. 赵文静祁飞等编著，数据结构与算法,科学出版社,2005.08 4. 赵文静编著，数据结构-C++语言描述，西安交通大学出版社，1999.01 5. 孙鑫,于安萍编著，VC++深入详解,电子工业出版社,2007.7 要写成类似的这种格式，这是标准格式各位同学：大家好！现将存在的共性问题描述如下，大家以此为标准进行撰写修改： 1.报告文件的命名统一命名成“学号-姓名-题目.doc"，方便我归档整理； 2.封面，页眉，页脚都调整好了，按照这个模板把你设计的内容一部分一部分填写进去，具体要求注意的问题已在模板中进行了批注； 3.论文中出现图的地方应该在图下方有标记，例如如果在”概要设计“部分有一个系统流程图，就在图的正下方居中写上“图4-1 系统流程图”，其他的地方依次类推。图的大小应该跟页面大小一致，太大的缩小一些，居中，“图号图名”也要居中。 4.有表的地方在表格上方正中写上类似于“表3-1 .。。。。表”的字样，不清楚可以看一下课本中是如何书写的。 5.使用说明应简明扼要，但也应该有相应的文字说明 6.课设总结要写你课设过程中遇到的诸多问题及解决方法，并且写出你的真实收获和感受，不应少于1页。 7.参考文献按照模板中的格式书写。 8.字体大小和行间距等均参照模板进行修改，段首空两个汉字的宽度。全文同级字体应统一. 9.文档修改完成之后，修改页脚的“共？页”中的问号为你正文的页数，最后更新目录中的页码。 10.全部修改完成,老师认可后再打印,打印纸张为16K. 11.上交材料为报告和程序的压缩包(删除其中的debug目录). 请各位同学务必认真参照上面的注意事项一条条修改，谢谢！李智杰目录第一章总论........................................................... ........................1 1、项目名称及承办单位................................................................1 2、编制依据........................................................ ...........................4 3、编制原则....................................................................................5 4、项目概况..................................................... ..............................6 5、结论............................................................................................6 第二章项目提出的背景及必要性................................................8 1、项目提出的背景........................................................................8 2、项目建设的必要性....................................................................9 第三章项目性质及建设规模........................................................13 1、项目性质...................................................................................13 2、建设规模...................................................................................13 第四章项目建设地点及建设条件................................................17 1、项目建设地点............................................................................17 2、项目建设条件............................................................................17 第五章项目建设方案..................................................................25 1、建设原则...................................................................................25 2、建设内容...................................................................................25 3、工程项目实施...........................................................................33 第六章节水与节能措施..............................................................37 1、节水措施...................................................................................37 2、节能措施...................................................................................38 第七章环境影响评价.................................................................39 1、项目所在地环境现状...............................................................39 2、项目建设和生产对环境的影响分析.......................................39 3、环境保护措施…………………………………........…...........40 4、环境影响评价结论……………………………..…………… 42 第八章劳动安全保护与消防.....................................................44 1、危害因素和危害程度...............................................................44 2、安全措施方案............................. .............................................44 3、消防设施………………………........................................…...45 第九章组织机构与人力资源配置.............................................46 1、组织机构...................................................................................46 2、组织机构图...............................................................................46 第十章项目实施进度..................................................................48 1、建设工期............................................... ...................................48 2、项目实施进度安排...................................................................48 3、项目实施进度表................................... ...................................48 第十一章投资估算及资金筹措..................................................49 1、投资估算依据...........................................................................49 2、建设投资估算...........................................................................49 3、资金筹措方案...........................................................................50 第十二章经济分析......................................................................52 1、国民经济评价...........................................................................52 第十三章社会评价......................................................................54 1、项目对社会的影响分析..........................................................54 2、互适性分析..............................................................................55 3、社会风险分析..........................................................................55 4、社会评价结论..........................................................................56 第十四章工程招标.....................................................................57 1、发包方式..................................................................................57 2、招标组织形式..........................................................................57 3、招标方式..................................................................................58 4、本项目招标形式和招标内容..................................................58 第十五章结论与建议..................................................................60 12.1结论........................................................................................60 12.2 建议.......................................................................................60

展开阅读全文