12数据结构课程设计报告

算法与数据结构课程设计

报告

系 （院）： 计算机科学学院 专业班级： 教育技术学1001班 姓 名： 宋佳 学 号： 201003901 指导教师： 詹泽梅 设计时间： 2012.6.16 - 2012.6.24 设计地点： 4号楼2号机房

《算法与数据结构》课程设计任务书

班级：教育技术11001

课程设计题目：图的基本操作及应用

数据结构课程设计是在学完数据结构课程之后的实践教学环节。本实践教学是培养学生数据抽象能力，进行复杂程序设计的训练过程。要求学生能对所涉及问题选择合适的数据结构、存储结构及算法，并编写出结构清楚且正确易读的程序，提高程序设计基本技能和技巧。 一．设计目的

1．提高数据抽象能力。根据实际问题，能利用数据结构理论课中所学到的知识选择合适的逻辑结构以及存储结构，并设计出有效解决问题的算法。

2．提高程序设计和调试能力。学生通过上机实习，验证自己设计的算法的正确性。学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。

3．初步了解开发过程中问题分析、整体设计、程序编码、测试等基本方法和技能。

二．设计任务

设计一个基于DOS菜单的应用程序。要利用多级菜单实现各种功能。内容如下：

1． 无向图的基本操作及应用

① 创建无向图的邻接矩阵

② 创建无向图的邻接表 ③ 无向图的深度优先遍历 ④ 无向图的广度优先遍历 2．

有向图的基本操作及应用

① 创建有向图的邻接矩阵 ② 创建有向图的邻接表 ③ 拓扑排序 3．

无向网的基本操作及应用

① 创建无向网的邻接矩阵 ② 创建无向网的邻接表 ③ 求最小生成树 4．

有向网的基本操作及应用

① 创建有向网的邻接矩阵

② 创建有向网的邻接表 ③ 关键路径 ④ 单源最短路径 三．设计指导

第一步：根据设计任务，设计DOS菜单。

第二步：设计菜单（c语言） #include

void ShowMainMenu(){ printf(\

printf(\图的基本操作及应用***************\\n\printf(\ 无向图的基本操作及应用 *\\n\printf(\ 有向图的基本操作及应用 *\\n\printf(\ 无向网的基本操作及应用 *\\n\printf(\ 有向网的基本操作及应用 *\\n\printf(\ 退出\\n\

printf(\}

void UDG(){ int n; do{

printf(\

printf(\无向图的基本操作及应用***************\\n\printf(\ 创建无向图的邻接矩阵 *\\n\printf(\ 创建无向图的邻接表 *\\n\printf(\ 无向图的深度优先遍历 *\\n\printf(\ 无向图的广度优先遍历 *\\n\printf(\ 退出\\n\

printf(\printf(\请选择：\scanf(\switch(n){ case 1: printf(\case 2: printf(\case 3: printf(\

case 4: printf(\case 5:break; default: printf(\}

}while(n!=5); }

void DG(){ int n; do{

printf(\

printf(\有向图的基本操作及应用***************\\n\printf(\ 创建有向图的邻接矩阵 *\\n\printf(\ 创建有向图的邻接表 *\\n\printf(\ 拓扑排序 *\\n\printf(\ 退出 *\\n\printf(\printf(\请选择：\scanf(\switch(n){ case 1: printf(\case 2: printf(\case 3: printf(\case 4:break; default: printf(\}

}while(n!=4); }

void UDN(){ int n; do{

printf(\

printf(\无向网的基本操作及 ***\\n\printf(\ 创建无向网的邻接矩阵 *\\n\printf(\ 创建无向网的邻接表 *\\n\printf(\ Prim算法求最小生成树 *\\n\printf(\ kraskal算法求最小生成树 *\\n\printf(\ 退出\\n\