算法和数据结构课程设计报告.docVIP

算法与数据结构课程设计报告 系（院）： 计算机科学学院 专业班级： 计科11101 姓 名： 袁斌 学 号： 201103258 指导教师： 周云才 设计时间： 2013.6.17 - 2012.6. 29 设计地点： 12教机房 报告目录 一、课程设计目的 03 二、设计任务及要求 03 三、需求分析 04 四、总体设计 04 五、详细设计与实现 [含代码和实现界面] 06 六、课程设计小结 17 七、部分重要代码 18 一、课程设计目的： 1．能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。 4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5．培养根据选题需要选择学习书籍，查阅文献资料的自学能力 二、设计任务及要求： 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： 无向图的基本操作及应用： 创建无向图的邻接矩阵（5.1.1）； ② 创建无向图的邻接表（5.1.2）； ③ 无向图的深度优先遍历（5.1.3）； ④ 无向图的广度优先遍历（5.1.4）。 2． ① 创建无向网的邻接矩阵（5.2.1）； ② 创建无向网的邻接表（5.2.2）； ③ Prim求最小生成树（5.2.3）； ④ Kruskal求最小生成树（5.2.4）。 3． ① 创建有向图的邻接矩阵（5.3.1）； ② 创建有向图的邻接表（5.3.2）； ③ 拓扑排序（5.3.3）。 4． ① 创建有向网的邻接矩阵（5.4.1）； ② 创建有向网的邻接表（5.4.2）； 关键路径（5.4.3）； 单源最短路径（5.4.4）； ⑤ 每对顶点之间的最短路径（5.4.5）。 三、需求分析： 按照需求，需要设计四种图、两种存储结构、创建四种图的个两种存储结构的操作（8个）、其他基本操作、多级菜单显示，图的操作有用到了线性表、栈和队列的基本操作。 在老师给出了多级菜单现实的代码后，我们需要做的只是将函数写入其中。 四、总体设计： 我用的软件是Visual C++6.0。将不同的操作分在了不同的包里面。如右图所示。 Typedef.h包里面是所有的相关结构定义；UDG_Operation.h包里面是有关于无向图的有关操作；UDN_Operation.h包里面是有关于无向网的有关操作；DG_Operation.h包里面是有关于有向图的有关操作；DN_Operation.h包里面是有关于有向网的有关操作；Queue_Operation.h包里面是有关队列的有关操作；Stack_Operation.h包里面是顺序栈的有关操作。 包的引用很有规范，如下：#include stdafx.h #include iostream #includealgorithm #include stdlib.h #includestdio.h #includestdlib.h #include malloc.h using namespace std; int visited[20]; #include Typedef.h #include Queue_Operation.h #include Stack_Operation.h #include UDG_Operation.h #include UDN_Operation.h #include DG_Operation.h #include DN_Operation.h 菜单由于老师已经给出，主要就是将函数带上参数写入代码。在菜单选择后触发函数，得出结果。 函数总结： 创建无向图的邻接矩阵：Cr