数据结构课程设计报告--课程表设计

软件学院课程设计报告书课程名称数据结构设计题目教学计划编制专业班级软件1004班学号1020010432姓名张小龙指导教师刘玲玲2011年1月目录说明按住Ctrl并单击可访问当前链接页数为文件中所标页码1设计时间12设计目的13设计任务14设计内容141需求分析142总体设计243详细设计644测试与分析12441测试12442分析1845附录195总结与展望26参考文献28成绩评定2811设计时间2012年1月3日至2012年1月5日2设计目的1加强学生分析问题能力和应用所学知识解决问题的能力2使学生对所学内容更深入的了解和应用3提高C程序调试能力加强程序设计和实践能力4加深学生对数据结构和C语言等相关课程的认识5培养学生自主软件设计能力和开发能力6加强个人程序设计能力和学生与学生之间的交流和研讨3设计任务大学的每个专业都要制定教学计划假设任何专业都有固定的学习年限每学年含两学期每学期的时间长度和学分上限值均相等每个专业开设的课程都是确定的而且课程在开设时间的安排必须满足先修关系每门课程有哪些先修课程是确定的可以有任意多门也可以没有每门课恰好占一个学期试在这样的前提下设计一个教学计划编制程序任选软件专业几门课程作为顶点通过这几门课程的先修关系来构建一个有向图用邻接表来储存通过栈和有向图来完成课程教学计划安排4设计内容41需求分析1程序所能达到的功能1数据结构使用有向图和栈2课程先修关系表4145012表课程先修关系3如果输入的先修课程号不在该专业开设的课程序列内则作为错误处理2输入的形式和输入值的范围输入参数包括学期总数一学期的学分上限每门课的课程号固定占3位的字母数字串学分和直接先修课的课程号3输出的形式每学期课程安排4测试数据学期总数6一学期的学分上限16该专业共开课程数目14按照表414501输入课程名课程号课程学分输出正确的课程编排结果42总体设计1说明本程序中用到的所有抽象数据类型的定义数据对象是具有相同特性的数据元素的集合称为顶点集数据关系表示和之间存在直接先修关系3基本操作操作结果创造图操作结果构造一个空栈初始条件栈已存在操作结果若栈为空栈则返回否则初始条件栈已存在操作结果插入元素为新的栈顶元素初始条件栈已存在且非空操作结果删除的栈顶元素并用返回其值初始条件拓扑排序完成操作结果构造关键路径的先修关系网初始条件图已存在4操作结构进行拓扑排序并完成关系网的构造使课程尽可能集中在前几个学期初始条件图已存在操作结果进行拓扑排序并完成关系网的构造使课程尽量均匀分布2说明主程序的流程53说明各程序模块之间的层次调用关系图423主程序模块拓扑排序模块顺序栈SqStack模块图423各程序模块之间的层次调用关系开始输入学期总数一学期学分上限输出编排结果结束构造图表G选择编排方式拓扑排序2课程尽量均匀分布拓扑排序1课程尽可能集中到前几个学期选择1选择2图422主程序流程图643详细设计1实现概要设计中定义的所有数据类型对每个操作只需要写出伪码算法78910112对主程序和其它主要函数写出伪码算法123画出函数的调用关系图图43450344测试与分析441测试学期总数6一学期的学分上限16该专业共开课程数目141键入学期总数学分上限安排课程总数mainGreatGraphInitStackFindInDegree图434503函数的调用关系图FindInDegreeInitStackTopologicalsort1Topologicalsort213说明CUsersdellAppDataRoamingTencentUsers729611757QQWinTempRichOleTF9VL7DIH6XQCB1D7jpg2输入课程名课程号及相应学分说明DProgramFilesx86Tencent新建文件夹729611757Image8GKLMNNPAK6YE5GTjpg14说明CUsersdellAppDataRoamingTencentUsers729611757QQWinTempRichOleKE1J4XY6FKZK34jpg说明DProgramFilesx86Tencent新建文件夹729611757ImageML6570HVX45GCUKUNSjpg15说明DProgramFilesx86Tencent新建文件夹729611757ImagePADBFUIRL08X1Kjpg输入课程先修关系总数说明CUsersdellAppDataRoamingTencentUsers729611757QQWinTempRichOleLTLTA3QE4IQZTLUYjpg顺序输入先修关系16说明CUsersdellAppDataRoamingTencentUsers729611757QQWinTempRichOleRFOTL17EC9DXI3jpg5输出邻接表说明CUsersdellAppDataRoamingTencentUsers729611757QQWinTempRichOleXWXA1BQM2LY156FIHPFPjpg6选择编排策略1输出编排结果17说明DProgramFilesx86Tencent新建文件夹729611757ImageKMZK284IF248BJEQjpg7选择编排策略2输出编排结果说明CUsersdellAppDataRoamingTencentUsers729611757QQWinTempRichOleJ39QZW56I66BN5SF1XHjpg8错误运行当输入两个相同课程号的不同课程当输入先修顺序有环时18说明CUsersdellAppDataRoamingTencentUsers729611757QQWinTempRichOleJE5KWM93FP4AYYDRNZ1Yjpg9运行结果说明DProgramFilesx86Tencent新建文件夹729611757ImageKMZK284IF248BJEQjpg442分析1调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析调试过程中出现了很多问题例如定义了无关变量程序逻辑性错误等在种19种错误下自己根据提示修改了一部分简单错误对于其他错误常常误认为是正确的而不得改正无奈下求助同学帮助在几个同课题同学帮助下纠正了大多数问题其他几个复杂问题上网查阅资料询问老师才最终解决设计两个不同拓扑的程序是遇到很多大麻烦平时实验不涉及该内容书上仅仅提供了一个算法在上网查阅资料求助同学下才完成了框架面对程序考略不足漏缺重要条件和关键步骤遇到到了很大麻烦究其原因还是基础不牢缺乏实验动手能力差2算法的时间复杂度和空间复杂度的分析本程序算法的时间复杂度为On空间复杂度为O2n45附录源程序代码及必要注释图的邻接表存储表示最大课程总数存储空间的初时分配量存储空间的分配增量该弧所指向的顶点的位置指向下一条弧的指针课程名课程号课程的学分该结点的入度该节点的状态第一个表结点的地址指向第一条依附该顶点的弧的指针20图的当前顶点数和弧数在栈构造之前和销毁之后的值为栈顶指针当前已分配的存储空间以元素为单位顺序栈图的构建采用邻接表存储结构构造没有相关信息的图并储存键入的相关信息请输入需要编排课程总数构造顶点向量请输入课程名请输入课程号课程号重复请重新输入请输入该课程的学分请输入课程先修关系总数请顺序输入每个课程先修关系先修课程在前并以逗号作为间隔构造顶点向量请输入存在先修关系的两个课程的序号21输入的顶点序号不正确请重新输入建立的邻接表为输出建立好的邻接表顺序栈的基本操作构造一个空栈存储分配失败若栈为空栈则返回否则返回入栈22插入元素为新的栈顶元素存储分配失败出栈若栈不空则删除的栈顶元素用返回其值并返回否则返回寻找各节点入度求图中各节点的入度课程尽量集中到前几学期的拓扑排序有向图采用邻接表存储结构若无回路则输出的顶点的一个拓扑序列并返回否则返回23存放各节点的入度课程编排数目计数器每个学期的课程学分累加器对各顶点求入度初始化栈入度为零的节点入栈即无先修的课程入栈避免入度为零节点重复入栈第个学期学得课程有入度为零的节点入栈即无先修的课程入栈栈非空学分总数小于学分上限24对号顶点每个邻接点的入度减一将未输出的节点重新压入栈课程编排出错课程编排成功课程尽量平均分配的拓扑排序课程编排数目计数器每个学期的课程学分累加器入度为零的节点入栈即无先修的课程入栈25第个学期学得课程有入度为零的节点入栈即无先修的课程入栈栈非空学分总数小于学分上限学期课程数目小于学期最大数目出栈对号顶点每个邻接点的入度减一课程编排出错课程编排成功主函数26学期总数一个学期的学分上限请输入学期总数请输入一个学期的学分上限请选择编排策略课程尽可能集中到前几个学期课程尽量均匀分布5总结与展望在这次课程设计试验中遇到了种种麻烦出了各种错误面对这些问题我常常感到头大心烦然而在压力下重新思考问题解决问题时那种投入的感觉让我痴迷解决问题那一瞬间我感到极其的畅快也许很多人的收获在于完成了这次课程以及其中得到的经验然而对于我来说在挫折打击下的那种坦然必将影响我一生我性格中或多或少带有那种逃避性面对问题感到头大不自觉的想逃避这种坦然让我渐渐放弃了最初的慌乱这无疑会给我以后生活带来巨大好处在这次实验中发现了不少错误最大问题就是基础不牢面对设计是不能快速做出反应将相关知识调用并合理分配不管麻烦多大经过百般周折把程序编写出来我为此长长出了一口气然而我发现程序调试更难因为阻碍人们前进的总是已知的知识其中大多是不正确的知识在种种错误下自己根据提示修改了一部分简单错误对于其他错误常常误认为是正确的而不得改正无奈下求助同学帮助27在几个同课题同学帮助下纠正了大多数问题其他几个复杂问题上网查阅资料询问老师才最终解决设计两个不同拓扑的程序是遇到很多大麻烦平时实验不涉及该内容书上仅仅提供了一个算法在上网查阅资料求助同学下才完成了框架面对程序考略不足漏缺重要条件和关键步骤遇到到了很大麻烦究其原因还是基础不牢缺乏实验动手能力差不过看着成功的劳动果实心中的喜悦无以言表自己也从实践中不断中不断成长此次课程设计中我觉得这种实践形式真的是我们需要的他是知识与实践的桥梁可以让我们学到更多包括书本和实践甚至人的品格在学拓扑排序时读了书上知识和算法描述时觉得自己明白了理论了解了但真的到编程中实践时又不能正确无误的完成总是会出各种小错误循环的边界条件啊排序表的设计啊遗漏一些关键步骤像累加器等等只能慢慢修改询问实验最终才能真正应用该算法实践和理论永远差一些不实践我永远不会做在查阅资料时不能很好区分c语言和c总把两种语言搞混以至于造成很多程序的错用和乱用原来粗浅的认为只不过是把换成了把printf换成cout大体一样然而就是这样的错误导致了程序四不像这也是一种信号我们需要掌握尤其是真真掌握两种语言通过这次的课程设计我学习到了很多知识也认识到了自己目前的不足那就是缺乏相应的知识与经验所以在运用和操作方面体现了不足但是经过这段时间对相关书籍的阅读和查找我顺利的完成了设计我还明白了在编写程序的时候应该尽量是界面简洁大方布局统一变量类型的定义一定要用好准确这样程序就可以尽可能的减少对系统资源的占用在设计时也免不了存在一些不足所以在今后的学习中我会多做些实验努力掌握知识来取得更大的进步虽然课程设计结束了但是我发现知识无论是数据结构还是其他方面的知识都远远不够也正是因为如此我更加珍惜这次的课程设计我明白这实验必须要有牢固的基础对知识要学通透不明白不能想当然的糊弄过去当然更离不开团体的力量询问同学是一种快捷方法达着为先嘛今后我将多做实验加强自己动手能力我也坚信这次体验必将成为我人生的一笔巨额财富我也将开启更好的未来28参考文献1严蔚敏数据结构C语言版M北京清华大学出版社20072赵文静等数据结构辅导M西安交通大学出版社19993张乃笑编数据结构与算法M电子工业出版社20044陈文博朱青著数据结构与算法M机械工业出版社1996成绩评定成绩教师签字