算法与数据结构课程设计报告

《算法与数据结构课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法与数据结构课程设计报告系（院）：计算机科学学院专业班级：计科11101姓名：袁斌学号：201103258指导教师：周云才设计时间：2013.6.17-2012.6.29设计地点：12教机房-28-报告目录一、课程设计目的03二、设计任务及要求03三、需求分析04四、总体设计04五、详细设计与实现[含代码和实现界面]06六、课程设计小结17七、部分重要代码18-28-一、课程设计目的：1．能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2．提高程序设计和调试能力。学生通过上机实习，

2、验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3．初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。5．培养根据选题需要选择学习书籍，查阅文献资料的自学能力二、设计任务及要求：设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下：1．无向图的基本操作及应用：②创建无向图的邻接矩阵（5.1.1）；②创建无向图的邻接表（5.1.2）；-28-③无向图的深度优先遍历（5.1.3）；④无向图的广度优先遍历（5.1.

3、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）。三、需求分析：按照需求，需要设计四种图、两种存储结构、创建四种图的个两种存储结构的

4、操作（8个）、其他基本操作、多级菜单显示，图的操作有用到了线性表、栈和队列的基本操作。在老师给出了多级菜单现实的代码后，我们需要做的只是将函数写入其中。-28-四、总体设计：我用的软件是VisualC++6.0。将不同的操作分在了不同的包里面。如右图所示。Typedef.h包里面是所有的相关结构定义；UDG_Operation.h包里面是有关于无向图的有关操作；UDN_Operation.h包里面是有关于无向网的有关操作；DG_Operation.h包里面是有关于有向图的有关操作；DN_Operation.h包里面是有关于有向网的有关操作；Queue_Operation.h包里面是有关

5、队列的有关操作；Stack_Operation.h包里面是顺序栈的有关操作。包的引用很有规范，如下：#include"stdafx.h"#include"iostream"#include#include"stdlib.h"#include#include#include"malloc.h"usingnamespacestd;intvisited[20];#include"Typedef.h"#include"Queue_Operation.h"#include"Stack_Operation.h"#include"UDG_O

6、peration.h"#include"UDN_Operation.h"#include"DG_Operation.h"#include"DN_Operation.h"菜单由于老师已经给出，主要就是将函数带上参数写入代码。在菜单选择后触发函数，得出结果。函数总结：创建无向图的邻接矩阵：CreatUDG_M(MG);-28-打印无向图的邻接矩阵：dispgraph_MG(MG);创建无向图的邻接表：CreatUDG_ALG(ALG);打印无向图的邻接表：dispgraph_G(ALG);无向图的深度优先遍历：DFSTraverse(ALG);无向图的广度优先遍历：BFSTraverse(

7、ALG);创建无向网的邻接矩阵：CreatUDN_M(MN);打印无向网的邻接矩阵：dispgraph_MN(MN);创建无向网的邻接表：CreatUDN_ALG(ALN);打印无向网图的邻接表：dispgraph_N(ALN);Prim算法求最小生成树：MiniSpanTree(MN,1);kraskal算法求最小生成树：kruskal();创建有向图的邻接矩阵：CreatDG_M(MG);打印有向图的邻接矩阵：dispgraph_MG(MG