课程设计-图的遍历.doc

1 目目录录 一 课题的主要功能 2 1 1 设计内容 2 1 2 对课程设计功能的需求分析 2 二 课题的功能模块的划分 2 2 1 模块划分 2 2 2 系统的概要设计 3 三 主要功能的实现 4 3 1 算法思想 4 1 图的邻接矩阵的建立 4 2 图的遍历的实现 4 3 2 数据结构 4 3 3 主函数流程图 5 3 4 深度优先遍历流程图 6 3 5 深度优先遍历递归 7 3 6 深度优先遍历流程图 9 3 7 广度优先遍历递归流程图 10 四 程序调试 11 4 1 程序的调试分析 11 4 2 程序的测试结果 11 五 总结 16 六 附件 16 6 1 源程序 16 2 一 课题的主要功能 1 1 设计内容设计内容 演示图的深度优先 广度优先遍历过程 并输出原图结构及遍历结果 要求图的 结点数不能少于 6 个 可以由系统随机生成图 也可以由用户手动输入图 报告中要 写出画图的思路 画出图的结构 有兴趣的同学可以进一步改进图的效果 1 2 对课程设计功能的需求分析对课程设计功能的需求分析 图的遍历并不需要是一个过于复杂的工作环境 一般来说 最合适的才是最好的 软件设计必须符合我们使用实际情况的需要 根据要求 图的遍历主要功能如下 1 用户可以随时建立一个有向图或无向图 2 用户可以根据自己的需要 对图进行深度遍历或广度遍历 3 用户可以根据自己的需要对图进行修改 4 4 在整个程序中 用户可以不断的按照不同的方式对图进行遍历 若不继续 用户也 可以随时跳出程序 同时 如果用户输入的序号错误 程序会提示用户重新输入序号 二 课题的功能模块的划分 2 12 1 模块划分模块划分 1 1 队列的初始化 进队 出队 队列空 队列满的函数队列的初始化 进队 出队 队列空 队列满的函数 void InitQueue CirQueue Q 初始化队列 int QueueEmpty CirQueue Q 队列是否为空 int QueueFull CirQueue Q 队列满 Void EnQueue CirQueue Q int x 将队员进队 int DeQueue CirQueue Q 将队员出队 2 2 创建图的函数创建图的函数 void CreateMGraph MGraph G 根据用户需要创建一个图 3 3 图的深度优先遍历递归图的深度优先遍历递归 void DFSM MGraph G int i 含有输出已访问的顶点的语句 3 4 4 图的广度优先遍历递归图的广度优先遍历递归 void BFSM MGraph G int k 含有输出已访问的顶点的语句 5 5 深度优先遍历深度优先遍历 void DFSTraverseM MGraph G 调用 DFSM 函数 6 6 广度优先遍历广度优先遍历 void BFSTraverseM MGraph G 调用 BFSM 函数 7 7 主函数主函数 main 包含一些调用和控制语句 2 2 系统的概要设计系统的概要设计 开开 始始 信息录入信息录入 菜单选择菜单选择 深深 度度 优优 先先 修修 改改 信信 息息 广广 度度 优优 先先 退出程序退出程序 4 三 主要功能的实现 3 1 算法思想算法思想 本课题所采用的是邻接矩阵的方式存储图 实现图的深度 广度两种遍历 并将 每种遍历结果输出来 1 图的邻接矩阵的建立图的邻接矩阵的建立 对任意给定的图 顶点数和边数自定 根据邻接矩阵的存储结构建立图的邻接距 阵 2 图的遍历的实现图的遍历的实现 图的遍历包括图的广度优先遍历与深度优先遍历 对于广度优先遍历应利用队列 的五种基本运算 置空队列 进队 出队 取队头元素 判队空 来实现 首先建立 一空队列 从初始点出发进行访问 当被访问时入队 访问完出队 并以队列是否为 空作为循环控制条件 对于深度优先遍历则采用递归或非递归算法来实现 这里我所 采用的是递归算法 3 23 2 数据结构数据结构 define Max 10 define FALSE 0 define TRUE 1 define Error printf define QueueSize 30 typedef struct char vexs Max int edges Max Max int n e 5 MGraph int visited Max typedef struct int front int rear int count int data QueueSize CirQueue 3 33 3 主函数流程图主函数流程图 登陆开始登陆开始 输入 ch2 6 CreateMGraph G Ch1 y Ch1 y 真 假 0 1 2 3 3 4 深度优先遍历流程图深度优先遍历流程图 Ch2 Ch1 n CreateMGraph G DFSTraverseM G BFSTraverseM G BFSTraverseM G DFSTraverseM G DFSTraverseM G DFSTraverseM G DFSTraverseM G DFSTraverseM G DFSTraverseM G BFSTraverseM G B r e a k 结束程序 DFSTraverseM MGraph G 7 真 非零 零 3 5 深度优先遍历递归深度优先遍历递归 i 0 in visited i FALSE i i 0 visited i DFSM G i in i 结束程序 8 真 DFSM MGraph G int i visited i T RUE jn j 0 G edges i j 1 int edges Max Max int n e MGraph 以邻接矩阵作为图的存储结构 int visited Max 将 visited Max 定义为全局变量并分配最大空间 typedef struct 17 int front int rear int count int data QueueSize CirQueue 定义队列的数据结构 初始化队列 void InitQueue CirQueue Q Q front Q rear 0 Q count 0 队列空 int QueueEmpty CirQueue Q return Q count QueueSize 返回队列的最大长度 队列满 int QueueFull CirQueue Q return Q count QueueSize 返回队列的最大长度 进队 void EnQueue CirQueue Q int x if QueueFull Q 队列满则出错 Error Queue overflow 18 else Q count 否则 count 将 x 进队 Q data Q rear x Q rear Q rear 1 QueueSize 出队 int DeQueue CirQueue Q int temp 定义整型的变量 if QueueEmpty Q 若为真则出错 Error Queue underflow else 为假则 count 将队员出队 temp Q data Q front 用 temp 返回其值 Q count Q front Q front 1 QueueSize return temp 返回出队元素值 建立一个图 void CreateMGraph MGraph G int i j k 定义整型变量 char ch1 ch2 定义字符型变量 printf n 请输入顶点数 边数 格式 3 4 19 scanf d d 输入图的顶点数和边数 for i 0 in i getchar printf n 请输入第 d 个顶点序号 i 1 scanf c 输入顶点的序号 for i 0 in i for j 0 jn j G edges i j 0 初始化矩阵 for k 0 ke k getchar printf n 请输入第 d 条边的顶点序号 格式 i j k 1 scanf c c 输入边的顶点序号 for i 0 ch1 G vexs i i for j 0 ch2 G vexs j j G edges i j 1 有边则赋值为 1 深度优先遍历递归 void DFSM MGraph G int i int j printf c G vexs i visited i TRUE 标记 visited i 依次优先搜索访问 visited i 的每个邻接点 20 for j 0 jn j 若 visited i 的一个有效邻接点 visited j 未被访问过 则从 visited j 出 发进行递归调用 if G edges i j 1 广度优先遍历递归 void BFSM MGraph G int k int i j CirQueue Q 定义一个队列 Q 初始化队列为空 InitQueue printf c G vexs k 访问初始点 并将其标记已访问过 visited k TRUE EnQueue 将以访问过的初始点序号 k 入队 while QueueEmpty 将队首元素出队 for j 0 jn j 依次搜索 vexs k 的每一个可能的邻接点 if G edges i j 1 标记 vexs j 已访问过 EnQueue 顶点序号 j 入队 深度优先遍历 void DFSTraverseM MGraph G 21 int i printf n 深度优先遍历序列 for i 0 in i visited i FALSE 访问标志数组初始化 for i 0 in i if visited i 对尚未访问的顶点调用 DFSM DFSM G i 广度优先遍历 void BFSTraverseM MGraph G int i printf n 广度优先遍历序列 for i 0 in i visited i FALSE 访问标志数组初始化 for i 0 in i if visited i 对尚未访问的顶点调用 BFSM BFSM G i 22 main MGraph G a char ch1 int i j ch2 G printf n t t 深度优先搜索和广度优先搜索 n CreateMGraph G 调用创建图矩阵的函数 getchar ch1 y 设置控制语句标志 while ch1 y ch1 Y 菜单栏 printf n printf 选择菜单 printf n t t n printf t t 更改数据请按 1 n printf t t 深度优先搜索请按 2 n printf t t 广度优先搜索请按 3 n printf t t 退出搜索请按 0 n printf t t n printf n t t 请选择菜单号 0 3 scanf d getchar switch ch2 case 1 CreateMGraph G 选 1 创建一个新的图矩阵 break 23 case 2 DFSTraverseM G 选 2 进入深度优先搜索 break case 3 BFSTraverseM G 选 3 进入广度优先搜索 break case 0 选 0 结束搜索