算法与数据结构课设（计科11级）.doc

《算法与数据结构课程设计》进度表 班级：计科11101-11105 课程设计题目：图的基本操作及应用 数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力，培养科学的软件工作方法。 一．设计目的 1．能根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，分析并正确确定数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。 2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。 3．初步掌握软件开发过程中问题分析、系统设计、程序编码、测试等基本方法和技能。 4．训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 5．培养根据选题需要选择学习书籍，查阅文献资料的自学能力。 二．设计任务 设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下： 无向图的基本操作及应用 创建无向图的邻接矩阵 创建无向图的邻接表 无向图的深度优先遍历 无向图的广度优先遍历 无向网的基本操作及应用 创建无向网的邻接矩阵 创建无向网的邻接表 求最小生成树 有向图的基本操作及应用 创建有向图的邻接矩阵 创建有向图的邻接表 拓扑排序 有向网的基本操作及应用 创建有向网的邻接矩阵 创建有向网的邻接表 关键路径 单源最短路径 每对顶点之间的最短路径 三．设计指导 第一步：根据设计任务，设计DOS菜单。例如 选择1之后应该类似于 第二步：设计菜单 void ShowMainMenu() { cout\n; cout ***************图的基本操作及应用******************\n; cout * 1 无向图的基本操作及应用 *\n; cout * 2 无向网的基本操作及应用 *\n; cout * 3 有向图的基本操作及应用 *\n; cout * 4 有向网的基本操作及应用 *\n; cout * 5 退出 *\n; cout ***************************************************\n; } void UDG() { MGraph MG; ALGraph ALG; int n; do { cout\n; cout ***************无向图的基本操作及应用***************\n; cout * 1 创建无向图的邻接矩阵 *\n; cout * 2 创建无向图的邻接表 *\n; cout * 3 无向图的深度优先遍历 *\n; cout * 4 无向图的广度优先遍历 *\n; cout * 5 退出 *\n; cout ****************************************************\n; cinn; switch(n){ case 1: CreatUDG_M(MG); break; case 2: CreatUDG_ALG(ALG); dispgraph(ALG); break; case 3: break; case 4: break; default: if (n!=5) cout错误，重新输入\n; } }while(n!=5); } void UDN() { MGraph ALGraph ALN; int n; do{ cout\n; cout ***************无向网的基本操作