图的遍历数据结构课程设计.doc.doc

长沙理工大学 《用C语言解决图的遍历》课程设计报告 徐俊 学 院 计算机与通信工程 专 业 计算机科学与技术 班 级 计算机08-03 学 号 200850080307 学生姓名 徐俊 指导教师 湛新霞 课程成绩 完成日期 2010年6月23日 课程设计成绩评定 学 院 计算机与通信工程学院 专 业 计算机科学与技术 班 级 计算机08-03 学 号 200850080307 学生姓名 徐俊 指导教师 湛新霞 完成日期 2010.6.23 指导教师对学生在课程设计中的评价 评分项目 优 良 中 及格 不及格 课程设计中的创造性成果 学生掌握课程内容的程度 课程设计完成情况 课程设计动手能力 文字表达 学习态度 规范要求 课程设计论文的质量 指导教师对课程设计的评定意见 综合成绩 指导教师签字 2010年6月25日  用C语言解决图的遍历的问题 学生姓名：徐俊 指导老师：湛新霞 摘 要 本课程设计主要目的在于更深一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用有向图和无向图分别实现图的遍历，广度优先遍历和深度优先遍历的实现，用邻接矩阵和邻接表等多种结构存储存储图。在课程设计中，程序设计设计语言采用Visual C，程序运行平台为Windows 98/2000/XP。在程序设计中我主要是解决的是给出一个图如何用多种方法完成图的遍历的问题，也包括如何创建一个图，深度优先遍历和广度优先遍历一个图，递归和非递归的方法实现图的遍历。程序最终通过调试运行，初步实现了设计目标。 关键词 程序设计；数据结构；有向图；无向图；存储结构；邻接矩阵；递归算法 一 引 言 数据结构是一门专业基础课，它对学习者的的要求很明确：学会分析、研究计算机加工的数据结构的特性，以便为应用设计所需的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间分析和空间分析的技术。其次，该课程的学习过程也是复杂程序设计的训练过程，要求学习者编写的程序结构或设计的程序结构体清楚、正确、易读，符合软件工程的规范。 图是一种较为复杂且重要的数据结构，其特殊性在于图形结构中结点之间的关系可以是任意的，图中任意两个数据元素之间都有可能相关。就本课程设计而言应用图论的知识讨论如何在计算机上实现图的遍历的操作，主要解决图的遍历的几种方法的实现。 本设计采用目前最通用的程序设计语言之一—C语言作为数据结构和算法的描述语言。 二 设计目的与任务 2.1课程设计的目的 进一步的了解图的遍历的问题，图的DFS,BFS的递归和非递归算法的实现，用有向图和无向图来实现图的遍历，用邻接矩阵和邻接表的存储方式存储图。 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能 训练用系统的观点和软件开发一般规范进行软件开发，提高综合运用所学的理论知识和方法独立分析和解决问题的能力typedef struct{ char *vexs; //顶点向量 int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵 int vexnum,arcnum; //图的当前顶点数和弧数 }Graph; CreateUDN(Graph G) 操作结果：用邻接矩阵创建带权无向网图。 DFS(Graph G,int k) 操作结果：对已存在的图进行深度优先遍历。 BFS(Graph G) 操作结果：对已存在的图进行广度优先遍历。 choose(Graph G) 操作结果：对将要实现的操作步骤进行选择。 程序包含两个模块 主程序模块，其中主函数为 int main{ 输入信息； 根据输入要求进行选择操作和输出； 输出结果； } 选择操作模块——实现具体选择的对应操作及输出操作。 两模块之间的简单调用关系如图1所示。 递归调用 图1 模块调用图 3.2 详细设计 各个函数之间的调用关系如图2所示。 图2 函数调用关系图 函数设计 程序设计中主要包括下列函数 用邻接矩阵创建一个图： void CreateUDN(Graph G) {