数据结构课程设计-floyd算法求解最短路径.doc

数据结构课程设计报告撰写要求数据结构课程设计报告撰写要求 一 纸张与页面要求 1 采用国际标准 A4 型打印纸或复印纸 纵向打印 2 封页和页面按照下面模板书写 正文为 小四宋体 1 5 倍行距 3 图表及图表标题按照模板中的表示书写 二 课设报告书的内容应包括以下各个部分 按照以下顺序装订 1 封页 见课设模版 2 学术诚信声明 所有学生必须本人签字 否则教师拒绝给予成绩 2 任务书 学生教师均要签字 信息填写完整 3 目录 4 正文一般应包括以下内容 1 题目介绍和功能要求 或描述 课程设计任务的详细描述 注意不能直接抄任务书 将内容做更详细的具体的分析与描述 2 系统功能模块结构图 绘制系统功能结构框图及主要模块的功能说明 3 使用的数据结构的描述 数据结构设计及用法说明 4 涉及到的函数的描述 5 主要算法描述 程序流程图 6 给出程序测试 运行的结果 设计多组数据加以描述 包括输入数据和输出结果 7 课程设计的总结及体会 8 参考文献 格式要求 1 作者 等 书名 出版地 出版社 出版年 5 附录 程序清单 应带有必要的注释 沈阳航空航天大学 课课 程程 设设 计计 报报 告告 课程设计名称 数据结构课程设计数据结构课程设计 课程设计题目 利用弗洛伊德 利用弗洛伊德 Floyd Floyd 算法求解算法求解 最短路径最短路径 院 系 计算机学院 专 业 计算机科学与技术 物联网方向 班 级 34010105 学 号 姓 名 指导教师 说明 结论 优秀 良好 中等 及格 不及格 作为相关教环节考核必要依据 格式不符合要说明 结论 优秀 良好 中等 及格 不及格 作为相关教环节考核必要依据 格式不符合要 求 数据不实求 数据不实 不予通过 报告和电子数据必须作为实验现象重复的关键依据 不予通过 报告和电子数据必须作为实验现象重复的关键依据 沈阳航空航天大学课程设计报告 I 学术诚信声明 本人声明本人声明 所呈交的报告 含电子版及数据文件 是我个人在导师指 导下独立进行设计工作及取得的研究结果 尽我所知 除了文中特别 加以标注或致谢中所罗列的内容以外 报告中不包含其他人己经发表 或撰写过的研究结果 也不包含其它教育机构使用过的材料 与我一 同工作的同学对本研究所做的任何贡献均己在报告中做了明确的说明 并表示了谢意 报告资料及实验数据若有不实之处 本人愿意接受本 教学环节 不及格 和 重修或重做 的评分结论并承担相关一切后 果 本人签名 日期 2015 年 1 月 5 日 沈阳航空航天大学课程设计报告 II 沈阳航空航天大学沈阳航空航天大学 课课程程设设计计任任务务书书 课程设计名称 数数据据结结构构课课程程设设计计专业 计计算算机机科科学学与与技技术术 物物联联网网方方向向 学生姓名孙思孙思班级 34010105 学号 2013040101204 题目名称 起止日期2015年1月5日起至2015年1月16日止 课设内容和要求 给出一张无向图 图上每一个顶点表示一个城市 顶点之间的边表示城市之间给出一张无向图 图上每一个顶点表示一个城市 顶点之间的边表示城市之间 存在路径 边上的权值表示城市间的路经长度 利用弗洛伊德 存在路径 边上的权值表示城市间的路经长度 利用弗洛伊德 FloydFloyd 算法求解 算法求解 最短路径求解任意两个城市之间的最短路径问题 最短路径求解任意两个城市之间的最短路径问题 参考资料 算法与数据结构 C 语言程序设计 教教研研室室审审核核意意见见 教教研研室室主主任任签签字字 指导教师 签名 指导教师 签名 年月日 学学 生 签名 生 签名 年月日 沈阳航空航天大学课程设计报告 III 目目 录录 第一章第一章 需求设计需求设计 1 1 题目介绍 1 1 2 功能要求 2 第二章第二章 程序设计程序设计 3 2 1 详细设计 3 2 1 1 总体模块图 3 2 1 2 函数描述 4 2 2 主要算法描述 5 第三章第三章 使用说明使用说明 6 3 1 用法说明 9 第四章第四章 程序测试程序测试 11 4 1 运行结果 11 4 2 存在的缺陷 12 参考文献参考文献 13 附附 录 关键部分程序清单 录 关键部分程序清单 14 沈阳航空航天大学课程设计报告 1 第一章 需求设计 1 1 题目介绍题目介绍 给出一张无向图 图上每一个顶点表示一个城市 顶点之间的边表示城市之 间存在路径 边上的权值表示城市间的路经长度 利用弗洛伊德 Floyd 算法 求解最短路径求解任意两个城市之间的最短路径问题 将问题分解为三个方面 第一个方面是对于无向图的存储问题 第二个方面 是实现弗洛伊德 Floyd 算法求解最短路径 第三个方面是将最短路径输出 首 先对于图的建立选择合适的存储结构 考虑到之后要用的弗洛伊德算法所以选择 采用邻接矩阵存储无向图 然后采用弗洛伊德算法 该算法又叫插点法 是利用 三重循环产生一个存储每个结点最短距离的矩阵 基本思想是设置一个 n 阶矩阵 D k D k i j 表示从 i 到 j 的路径长度 k 表示运算步骤 用两个顶点之间边的 权值作为路径长度 无边连接记做无穷 多次循环 向原路径加入新的顶点 若 增加的顶点使得路径比原路径短 则用新路径代替原始路径 将顶点信息存储在 另一个三维数组 p 中 p v w u 存储的是由 i 到 j 路径经过的所有顶点 三重循 环执行完毕最短路径的信息存储在两个数组中 最后将最短路径的信息输出 沈阳航空航天大学课程设计报告 2 1 2 功能要求功能要求 一个无向图用每个顶点代表城市 顶点之间边的权重表示城市之间的路径 将顶点信息和边的信息输入程序 即可得到每两个城市之间的最短路径长度值以 及这条路径经过的城市 可以为建址问题提供参考 设计环境 1 WINDOWS 7 系统 2 VisualC 开发环境 开发语言 C 语言 沈阳航空航天大学课程设计报告 3 第二章 程序设计 2 1 详细设计详细设计 2 1 1 功能模块图功能模块图 图图 2 1 功能模块图功能模块图 用弗洛伊德算法求解最短路径 主 函 数 输 出 最 短 路 径 信 息 调 用 弗 洛 伊 德 算 法 输 入 无 向 图 顶 点 及 权 值 沈阳航空航天大学课程设计报告 4 2 1 2 函数描述函数描述 Find 根据名称得到指定顶点在顶点集合中的下标 利用此函数找到顶点所在位 置 进而对无向图赋权值 Create 创建无向图的邻接矩阵 因为每条边都有权值 创建的是无向网的邻接 矩阵 用权值代替 1 没有边连接则为无穷 FLOYD 设置一个 n 阶矩阵 D k D k i j 表示从 i 到 j 的路径长度 k 表示运 算步骤 用两个顶点之间边的权值作为路径长度 无边连接记做无穷 多次循环 向原路径加入新的顶点 若增加的顶点使得路径比原路径短 则用新路径代替原 始路径 将顶点信息存储在另一个三维数组 p 中 p v w u 存储的是由 i 到 j 路 径经过的所有顶点 三重循环执行完毕最短路径的信息存储在两个数组中 主函数 在主函数里定义一个无向图 一个三维矩阵 p 二维矩阵 D 对各个函 数进行调用 实现无向网的建立 运用弗洛伊德算法求解出最短路径 将路径长 度以及经过的顶点信息输出 沈阳航空航天大学课程设计报告 5 2 2 主要算法描述主要算法描述 开始 Int u v w V 0 V vexnum P v w u false v u vexnum W vexnum 记录相对路径 和权重 u 结束 N Y N Y N Y 图图 2 2 1 FLOYD 函数函数 沈阳航空航天大学课程设计报告 6 开始 Int i i 0 i vexnum vexs i vex Return 0 i 结束 Y N N Y 图图 2 2 2 Find 函数函数 沈阳航空航天大学课程设计报告 7 开始 创建矩阵 Create G 建立路径和权 值矩阵 FLOYD 输出最短 路径 结束 图图 2 2 3 Main 函数函数 沈阳航空航天大学课程设计报告 8 开始 输入边数 和结点值 边权值初始化 K 0 k G arcnum v1 Find c1 G arcs v1 v2 w K 结束 输入边和 权重 图图 2 2 4 Create 函数函数 沈阳航空航天大学课程设计报告 9 第三章 使用说明 3 1 用法说明用法说明 1 将顶点数和边数输出 中间用空格隔开 图 3 1 1 2 输入顶点信息 图 3 1 2 沈阳航空航天大学课程设计报告 10 3 依次输入每条边连接的两个顶点用空格间隔 边的权值 图 3 1 3 4 得到每两个顶点城市间的最短距离以及经过的城市 图 3 1 4 4 沈阳航空航天大学课程设计报告 11 第四章 程序测试 4 1 运行结果运行结果 图 4 1 沈阳航空航天大学课程设计报告 12 4 2 存在的缺陷存在的缺陷 1 无向图的顶点信息只能用一个字符表示 将存储顶点信息的字符型改为字 符数组就可以完善该缺陷 2 将两点的最短路径输出时只能显示经过的顶点有哪些 无法显示真实的路 径顺序 3 输入无向图信息只能用手动输入 无法用文件直接写入 4 输入不符合要求的数据会使程序自动停止 沈阳航空航天大学课程设计报告 13 参考文献 1 张长海 C 语言程序设计 M 北京 高等教育出版社 2006 2 吴启武 C 语言课程设计案例精编 北京 清华大学出版社 2011 3 郭翠英 C 语言课程设计案例精编 北京 中国水利水电出版社 2004 4 姜灵芝 余键 C 语言课程设计案例精编 北京 清华大学出版社 2008 5 黄明 梁旭 万洪莉 C 语言课程设计 北京 电子工业出版社 2006 沈阳航空航天大学课程设计报告 14 附 录 关键部分程序清单 include stdio h include stdlib h define MAX 20 define INFINITY 9999 typedef bool PathMatrix MAX MAX MAX typedef int DistanceMatrix MAX MAX typedef struct int vexnum arcnum char vexs MAX int arcs MAX MAX MGraph int Find char vex MGraph MG 根据名称得到指定顶点在顶点集合中的下标 vex 表示顶点 return 如果找到则返回下标 否则 返回 int i for i 0 i MG vexnum i if MG vexs i vex return i 沈阳航空航天大学课程设计报告 15 return 0 void Create MGraph printf 请输入顶点数和边数 scanf d d getchar for i 0 i G vexnum i printf 请输入第 d 个结点 i 1 scanf c getchar for i 0 i G vexnum i for j 0 j G vexnum j G arcs i j INFINITY for k 0 k G arcnum k char c1 c2 printf 请输入与第 d 条边相连的两条边 v1 v2 k 1 scanf c getchar scanf c printf 请输入该边的权重 沈阳航空航天大学课程设计报告 16 scanf d getchar v1 Find c1 G v2 Find c2 G G arcs v1 v2 w G arcs v2 v1 w void FLOYD MGraph G PathMatrix for v 0 v G vexnum v for w 0 w G vexnum w D v w G arcs v w for u 0 u G vexnum u P v w u false if D v w INFINITY P v w v true P v w w true for u 0 u G vexnum u 沈阳航空航天大学课程设计报告 17 for v 0 v G vexnum v for w 0 w G vexnum w if D v u D u w D v w D v w D v u D u w for i 0 i G vexnum i P v w i P v u i P u w i int main MGraph G int i j k Create G PathMatrix p DistanceMatrix D FLOYD G p D for i 0 i G vexnum i for j 0 j G vexnum j if i j continue 沈阳航空航天大学课程设计报告 18 else printf c 到 c 经过的顶点有 G vexs i G vexs j for k 0 k G vexnum k if p i j k 0 continue else printf c G vexs k printf 最短路径长度为 d n n D i j return 0 沈阳航空航天大学课程设计报告 19 课程设计总结 课程设计总结 此次课程设计中 我了解到了许多以前不太会的知识 也在对程序的不断 的调试中认识到调试时的细心是很重要的 这些都让我受益匪浅 譬如 getchar 的使用 用在输入字符型数据的时候