2022年c++数据结构课程设计 .pdf

重庆大学信息科学与工程学院实验报告课程名称：数据结构实验名称：宿舍管理查询软件专业：计算机科学与技术班级：2009 级 3 班姓名：张无忌时间：2011 年 7 月 1 日名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 6 页 -课程数据结构课程设计班级计算机 09 级 3 班指导教师盛明兰题目宿舍管理查询软件完成时间2011 年 6 月 20 日至 2011年 7月 1 日主要内容1)任务：为宿舍管理人员编写一个宿舍管理查询软件,程序设计要求：A.采用交互工作方式B.建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)2)查询菜单:(用二分查找实现以下操作)A.按姓名查询B.按学号查询C.按房号查询3)打印任一查询结果（可以连续操作）设计报告要求课程设计报告要求规范书写。应当包括如下八个部分：1.问题描述：描述要求编程解决的问题。2.基本要求：给出程序要达到的具体的要求。3.测试数据：设计测试数据，或具体给出测试数据。要求测试数据能全面地测试所设计程序的功能。4.算法思想：描述解决相应问题算法的设计思想。5.模块划分：描述所设计程序的各个模块（即函数）功能。6.数据结构：给出所使用的基本抽象数据类型,所定义的具体问题的数据类型,以及新定义的抽象数据类型。7.源程序：给出所有源程序清单，要求程序有充分的注释语句，至少要注释每个函数参数8.设计感想版面要求1 题目用黑体三号，段后距18 磅（或 1 行），居中对齐；2 标题用黑体四号，段前、段后距6 磅（或 0.3 行）；3 正文用小四号宋体，行距为1.25 倍行距；4.标题按“一”、“”、“1”、“”顺序编号。指导时间安排星期周次二三四173-4 节(10:00-11:45)9-12 节(19:00-22:00)7-8 节（16.00-17.50）5-6 节（1400-1540）189-12 节(19:00-22:00)7-8（1600-1750）3-6 节（1000-1140）（14.00-15.40）地点指导信息科学与工程学院机房评定成绩成绩由三部分组成：平时上机、设计报告书和上机答辩1、实验内容 1)任务：为宿舍管理人员编写一个宿舍管理查询软件,程序设计要求：名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 6 页 -A.采用交互工作方式B.建立数据文件，数据文件按关键字（姓名、学号、房号）进行排序(冒泡、选择、插入排序等任选一种)2)查询菜单:(用二分查找实现以下操作)A.按姓名查询B.按学号查询C.按房号查询3)输出任一查询结果（可以连续操作）2、预备知识和参考资料1、二分查找法(折半搜索法)2、数据排序方法（冒泡、选择、插入等任何一种）3、流程图输出结果按姓名查询按学号查询按房号查询查询菜单退出名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 6 页 -4、算法分析(1)二分查找法算法：若设有 n 个元素存放在一个有序的顺序表中，采用折半搜索时。先求出位于搜索区间正中的元素的下标mid，用其关键码Elementmid.key与给定值x 进行比较，比较结果有3 种可能：1、若 Elementmid.key=x，搜索成功，报告成功信息并返回其下标；2、若 xElementmid.key，说明如果表中存在要找的元素，该元素一定在mid 右侧，可把搜索区间缩小到表的后半部分，再继续进行二分查找。每比较一次，搜索区间缩小一半。因此在最坏的情况下搜索到要求元素所需的关键码比较次数约为O（log2n）。对于较大的n，显然比顺序搜索快得多。如果搜索区间已经缩小到一个元素，经过与给定值比较仍未找到想要搜索元素，则搜索失败。（2）选择法排序（把数组中n 个数按自小到大排列）排序需解决两个问题：一是如何选择值最小的数据；二是如何交换两个数据值。从第 i 个元素到第n-1 个元素中选择最小元素可以采取如下做法：先假定第 i 个元素值最小，用k 标示它；然后顺序检查第i+1，第 i+2，,，第n-1 个，若检测到还有比刚才最小的还要小的元素，用k 标示它。在检查结束后k 标示的就是值最小的数据。交换两个数据中的值时需要一个暂存变量，如用temp 作为中介，以进行交换：Temp=ai;ai=ak;ak=temp;5、设计心得这次的课程设计，加强了我们的动手、思考和解决问题的能力。巩固和加深了对数据结构的理解，提高了综合应用本课程所学知识的能力。培养了我选用参考书，查阅手册及相关文献资料的能力。培养了独立思考，深入研究，分析问题，解决问题的能力。通过实际编译系统的分析设计、编程调试，掌握了应用软件的分析方法和过程设计方法。做课程设计同时也是对课本知识的巩固和加强，平时看课本时，有些问题不是很理解，做完课程设计，那些问题就迎刃而解了。二姐还可以记住很多东西。认识来源于实践，实践是认识的动力和最终目的，实践是检验真理的唯一标准。所以这个期末测试之后的课程设计对我们的作用是非常大的。这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能真正提高自己的实际动手能力和独立思考的能力。在整个设计过程中，构思是最花费时间的。调试是经常会遇到这样那样的错误，有的是因为粗心造成的语法错误。当然，很多也是用错了方法，总是实现不名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 6 页 -了。同时在设计过程中发现了自己的不足之处，对以前学过的知识理解的不够深刻，掌握的不够牢固。根据我在课程设计中遇到的问题，我将在以后的学习过程中注意一下几点：1、认真上好专业实验课，多在实践中锻炼自己。2、写程序的过程中要考虑周到、严密。3、认真学习课本知识，掌握课本中的知识点，并在此基础上学会灵活运用。4、在课余时间里多写程序，熟练掌握在调试程序过程中所遇到的常见错误，以便能节省调试程序的时间。这次课程设计最终顺利完成，在设计中遇到很多专业知识问题，最后在查找相关资料及和别的同学的交流下，完成了本次设计。6、参考资料数据结构（用面象对象方法与语言描述）7、附录课程设计代码：1）选择法排序选择排序是这样实现的：设数组内存放了n 个待排数字，数组下标从1 开始，到n 结束。i=1 从数组的第i 个元素开始到第n 个元素，寻找最小的元素。将上一步找到的最小元素和第i 位元素交换。如果 i=n 1 算法结束，否则回到第3 步选择排序的平均时间复杂度也是O(n²)的。举个例子：要排序的数字有564 比如说这个，我想让它从小到大排序，怎么做呢？第一步：从第一位开始找最小的元素，564 中 4 最小，与第一位交换。结果为465 第二步：从第二位开始找最小的元素，465 中 5 最小，与第二位交换。结果为456 第三步：i=2，n=3，此时 i=n-1，算法结束选择法排序简单代码如下：void select(int a,int n)for(i=1;in-1;i+)名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 6 页 -For(j=i+1 t;ia(j)Int tmp=a(i)a(i)=a(j)a(j)=tmp 2）冒泡法排序插入法排序首先将所有待排序的数字放入工作列表中。从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。重复 2 号步骤，直至再也不能交换。冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法，由于程序中这部分代码较多，下面就不全部给出实现代码，重点只介绍算法，冒泡法经典代码如下：void maopao(int*a,int n)int i,j,t;for(i=1;in;i+)/冒泡是第i次循环在数组末尾倒数第 i 个位置依次产生第i 大得数值 for(j=0;jaj+1)/大值后移 aj+1=aj;aj=t;名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 6 页 -