图的邻接矩阵存储结构建立 顾云康E01114300.doc

数据结构课程设计报告 数据结构课程设计实验数据结构课程设计实验 报告报告 图的邻接矩阵存储结构建立图的邻接矩阵存储结构建立 姓名 顾云康姓名 顾云康 学号 学号 E1114300 指导老师 王爱平指导老师 王爱平 日期 日期 2013 10 8 数据结构课程设计报告 I 目目 录录 1 课程设计的目的课程设计的目的 2 2 需求分析需求分析 2 3 课程设计报告内容课程设计报告内容 2 3 1 概要设计 2 3 2 详细设计 3 3 3 调试分析 6 4 总结总结 6 5 程序清单程序清单 7 6 参考文献参考文献 7 7 程序运行结果程序运行结果 7 附附 录录 8 数据结构课程设计报告 2 1 课程设计的目的 1 熟练使用熟练使用 C 语言编写程序 解决实际问题语言编写程序 解决实际问题 2 了解并掌握数据结构与算法的设计方法 具备初步的独立分了解并掌握数据结构与算法的设计方法 具备初步的独立分 析和设计能力析和设计能力 3 初步掌握软件开发过程的问题分析 系统设计 程序编码 初步掌握软件开发过程的问题分析 系统设计 程序编码 测试等基本方法测试等基本方法 和技能和技能 4 提高综合运用所学的理论知识和方法独立分析和解决问题的提高综合运用所学的理论知识和方法独立分析和解决问题的 能力能力 2 需求分析 1 设置图的邻接矩阵存储结果 设置图的邻接矩阵存储结果 2 编写图的基本操作函数 包括图的建立 邻接矩阵的输出 编写图的基本操作函数 包括图的建立 邻接矩阵的输出 3 编写深度遍历 广度遍历的递归与非递归算法 编写深度遍历 广度遍历的递归与非递归算法 4 编写主函数 控制程序运行编写主函数 控制程序运行 3 课程设计报告内容 3 1 概要设计 1 图的邻接矩阵存储结构 图的邻接矩阵存储结构 typedef enum 数据结构课程设计报告 3 DG DN UDG UDN GraphKind 有向图有向图 有向网有向网 无向图无向图 无向无向 网网 typedef struct ArcCell 邻接矩阵表示法的各个数据结构邻接矩阵表示法的各个数据结构 VrType adj 顶点关系类型 对无权图 用或表顶点关系类型 对无权图 用或表 示相邻否 对带权图 则为权值类型 示相邻否 对带权图 则为权值类型 InfoType info 该弧相关信息的指针该弧相关信息的指针 ArcCell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM typedef struct VertexType vertex MAX VERTEX NUM 顶点向量顶点向量 AdjMatrix arcs 邻接矩阵邻接矩阵 int vexnum arcnum 图的当前顶点数和弧图的当前顶点数和弧 边边 数数 GraphKind kind 图的种类标志图的种类标志 MGraph 2 主函数流程 首先选择输入图的种类 再输入图的顶点 主函数流程 首先选择输入图的种类 再输入图的顶点 数据结构课程设计报告 4 边的信息 最后给边的信息 最后给 出四种算法的遍历结果 出四种算法的遍历结果 3 2 详细设计详细设计 1 主函数 主函数 void main int i MGraph G printf 请输入要构造的图的类型请输入要构造的图的类型 无向图无向图 1 无向网无向网 2 n scanf d switch G kind case 1 CreateUDG G break case 2 CreateUDN G break default break DepthFirstSearch1 G BreadthFirstSearch1 G DFS G 数据结构课程设计报告 5 BFS G Display G scanf d 2 构造图的邻接矩阵函数 构造图的邻接矩阵函数 void CreateUDG MGraph i j k 为计数器为计数器 IncInfo 为标志符为标志符 char ch 用于吃掉多余的字符用于吃掉多余的字符 VertexType v1 v2 用于放置输入的弧的两个顶点用于放置输入的弧的两个顶点 printf 请输入无向图请输入无向图 G 的顶点数的顶点数 边数边数 弧是否含相关信息 是弧是否含相关信息 是 1 否 否 0 n scanf d d d ch getchar 用于吃掉回车用于吃掉回车 printf 请输入请输入 d 个顶点的值个顶点的值 1 个字符 空格隔开个字符 空格隔开 n G vexnum for i 0 i G vexnum i 构造顶点向量构造顶点向量 scanf c ch getchar 数据结构课程设计报告 6 printf 请输入请输入 d 条边的顶点顶点条边的顶点顶点 以空格作为间隔以空格作为间隔 n G arcnum for i 0 i G vexnum i 初始化邻接矩阵初始化邻接矩阵 for j 0 j G vexnum j G arcs i j adj 0 G arcs i j info NULL for k 0 k G arcnum k scanf c c ch getchar ch 吃掉回车符吃掉回车符 i LocateVertex G v1 j LocateVertex G v2 if IncInfo scanf d G arcs i j adj G arcs j i adj 1 置置的对称的对称 弧弧 3 递归深度遍历函数 递归深度遍历函数 数据结构课程设计报告 7 void DFSTraverse MGraph Visit i true for int j 0 j G vexnum j if G arcs i j adj 1 void DFS MGraph int i for i 0 i G vexnum i Visit i false for i 0 i G vexnum i if Visit i 数据结构课程设计报告 8 DFSTraverse G i 4 非递归深度遍历函数 非递归广度遍历函数 递归广度遍非递归深度遍历函数 非递归广度遍历函数 递归广度遍 历函数详见源程序 历函数详见源程序 3 3 调试分析调试分析 数据结构课程设计报告 9 4 总结 在完成本次课程设计中 我发现很多理论性知识在实际使用在完成本次课程设计中 我发现很多理论性知识在实际使用 时与单纯的理论还是有所差别的 比如图的邻接矩阵存储 广度时与单纯的理论还是有所差别的 比如图的邻接矩阵存储 广度 优先遍历 深度优先遍历等 我认识到了图的模型在解决实际问优先遍历 深度优先遍历等 我认识到了图的模型在解决实际问 题中的作用 使我对数据结构的学习有了更进一步的理解 今后题中的作用 使我对数据结构的学习有了更进一步的理解 今后 我会更加注重培养自己的实践动手能力我会更加注重培养自己的实践动手能力 5 程序清单 见附录见附录 6 参考文献 1 严蔚敏 吴伟民严蔚敏 吴伟民 编著编著 数据结构数据结构 C 语言版语言版 北京北京 清华大学清华大学 出版社 出版社 2007 2 严蔚敏 吴伟民严蔚敏 吴伟民 米米 宁宁 编著编著 数据结构题集数据结构题集 C 语言版语言版 北京北京 清华大学出版社 清华大学出版社 2007 7 程序运行结果 数据结构课程设计报告 10 数据结构课程设计报告 11 附 录 程序清单 程序清单 include stdafx h include include include include include define ERROR 0 define OK 1 define MAX VERTEX NUM 20 定义最大值定义最大值 define INFINITY 32768 定义极大值定义极大值 define MAX INFO 20 bool Visit MAX INFO typedef int VrType 定义新的类型定义新的类型 typedef int InfoType typedef char VertexType typedef enum 数据结构课程设计报告 12 DG DN UDG UDN GraphKind 有向图有向图 有向网有向网 无向图无向图 无向网无向网 typedef struct ArcCell 邻接矩阵表示法的各个数据结构邻接矩阵表示法的各个数据结构 VrType adj 顶点关系类型 对无权图 用或表示相邻否 对带顶点关系类型 对无权图 用或表示相邻否 对带 权图 则为权值类型 权图 则为权值类型 InfoType info 该弧相关信息的指针该弧相关信息的指针 ArcCell AdjMatrix MAX VERTEX NUM MAX VERTEX NUM typedef struct VertexType vertex MAX VERTEX NUM 顶点向量顶点向量 AdjMatrix arcs 邻接矩阵邻接矩阵 int vexnum arcnum 图的当前顶点数和弧图的当前顶点数和弧 边边 数数 GraphKind kind 图的种类标志图的种类标志 MGraph typedef struct 设置栈设置栈 int elem1 MAX VERTEX NUM int top SeqStack 数据结构课程设计报告 13 int LocateVertex MGraph G VertexType v void CreateUDG MGraph void CreateUDN MGraph void DepthFirstSearch1 MGraph G void BreadthFirstSearch1 MGraph G int CreateGraph MGraph void Display MGraph G int LocateVertex MGraph G VertexType v 用于返回输弧端点所表示的数值用于返回输弧端点所表示的数值 int j 0 k for k 0 k G vexnum k if G vertex k v j k break return j void CreateUDG MGraph i j k 为计数器为计数器 IncInfo 为标志符为标志符 char ch 用于吃掉多余的字符用于吃掉多余的字符 数据结构课程设计报告 14 VertexType v1 v2 用于放置输入的弧的两个顶点用于放置输入的弧的两个顶点 printf 请输入无向图请输入无向图 G 的顶点数的顶点数 边数边数 弧是否含相关信息 是弧是否含相关信息 是 1 否 否 0 n scanf d d d ch getchar 用于吃掉回车用于吃掉回车 printf 请输入请输入 d 个顶点的值个顶点的值 1 个字符 空格隔开个字符 空格隔开 n G vexnum for i 0 i G vexnum i 构造顶点向量构造顶点向量 scanf c ch getchar printf 请输入请输入 d 条边的顶点顶点条边的顶点顶点 以空格作为间隔以空格作为间隔 n G arcnum for i 0 i G vexnum i 初始化邻接矩阵初始化邻接矩阵 for j 0 j G vexnum j G arcs i j adj 0 G arcs i j info NULL for k 0 k G arcnum k scanf c c 数据结构课程设计报告 15 ch getchar ch 吃掉回车符吃掉回车符 i LocateVertex G v1 j LocateVertex G v2 if IncInfo scanf d G arcs i j adj G arcs j i adj 1 置置的对称弧的对称弧 CreateUDG void CreateUDN MGraph i j k 为计数器 为计数器 w 用于放置权值用于放置权值 IncInfo 为标志符为标志符 char ch 用于吃掉多余的字符用于吃掉多余的字符 VertexType v1 v2 用于放置输入的弧的两个顶点用于放置输入的弧的两个顶点 printf 请输入无向图请输入无向图 G 的顶点数的顶点数 边数边数 弧是否含相关信息 是 弧是否含相关信息 是 否 否 n scanf d d d ch getchar 用于吃掉回车用于吃掉回车 printf 请输入请输入 d 个顶点的值个顶点的值 1 个字符 空格隔开个字符 空格隔开 n G vexnum for i 0 i G vexnum i 构造顶点向量构造顶点向量 数据结构课程设计报告 16 scanf c ch getchar printf 请输入请输入 d 条边的顶点顶点条边的顶点顶点 以空格作为间隔以空格作为间隔 n G arcnum for i 0 i G vexnum i 初始化邻接矩阵初始化邻接矩阵 for j 0 j G vexnum j G arcs i j adj 0 G arcs i j info NULL adj info for k 0 k G arcnum k scanf c c ch getchar ch 吃掉回车符吃掉回车符 printf 请输入该边的权值请输入该边的权值 scanf d ch getchar i LocateVertex G v1 j LocateVertex G v2 G arcs i j adj w if IncInfo scanf d 数据结构课程设计报告 17 G arcs i j G arcs j i 置置的对称弧的对称弧 CreateUDN void DepthFirstSearch1 MGraph G 无向图 无向网深度优先遍历无向图 无向网深度优先遍历 int i j k visited 20 t 1 a 1 i j k 为计数器 为计数器 visited 20 为标志符为标志符 用于表示是否已经访问过用于表示是否已经访问过 SeqStack p for i 0 i G vexnum i 初始化标志符初始化标志符 visited i 0 visited 0 1 规定以第一个字符开始遍历规定以第一个字符开始遍历 printf 非递归深度优先遍历开始 非递归深度优先遍历开始 n k 0 i 0 printf c G vertex 0 while i G vexnum 不断以行循环在遇到符合条件时打印 每打印出一个就不断以行循环在遇到符合条件时打印 每打印出一个就 让让 t 加 把合适的值用栈来表示 把指针指向新的项加 把合适的值用栈来表示 把指针指向新的项 for j 0 j G vexnum j if G arcs i j adj 0 visited j 1 p elem1 k i p top k k i a t break if j G vexnum 当在某一行无法找到合适值时 输出栈内的值 当在某一行无法找到合适值时 输出栈内的值 返回上一行重新开始循环返回上一行重新开始循环 i p elem1 p top p top k if t G vexnum break 当全部的定点都打印出来了当全部的定点都打印出来了 就退出循环就退出循环 printf n 数据结构课程设计报告 19 void BreadthFirstSearch1 MGraph G 无向图 无向网广度优先遍历无向图 无向网广度优先遍历 int i j k visited 20 t 1 i j 为计数器 为计数器 visited 20 为标志符用于表为标志符用于表 示是否已经访问过示是否已经访问过 SeqStack p for i 0 i G vexnum i 初始化标志符初始化标志符 visited i 0 visited 0 1 规定以第一个字符开始遍历规定以第一个字符开始遍历 printf 非递归广度优先遍历开始 非递归广度优先遍历开始 n k 0 i 0 printf c G vertex 0 while i G vexnum for j 0 j G vexnum j 不断以行循环在遇到符合条件不断以行循环在遇到符合条件 时打印 每打印出一个就让时打印 每打印出一个就让 t 加 把指针指向新的项加 把指针指向新的项 if G arcs i j adj 0 visited j 1 p elem1 k i 数据结构课程设计报告 20 p top k k t i 换行 重新开始循环换行 重新开始循环 if t G vexnum break printf n void BFS MGraph G 递归广度优先遍历递归广度优先遍历 int i j k visited 20 t 1 i j 为计数器 为计数器 visited 20 为标志符用于表为标志符用于表 示是否已经访问过示是否已经访问过 SeqStack p for i 0 i G vexnum i 初始化标志符初始化标志符 visited i 0 visited 0 1 规定以第一个字符开始遍历规定以第一个字符开始遍历 printf n 递归广度优先遍历开始 递归广度优先遍历开始 n k 0 i 0 printf c G vertex 0 数据结构课程设计报告 21 while i G vexnum for j 0 j G vexnum j 不断以行循环在遇到符合条件不断以行循环在