数据结构课程设计说明书最短路径

计算机科学与技术教研室 课程设计说明书课程设计说明书 2014 2015 学年 第 1 学期 课程名称算法与数据结构课程设计 设计题目火车路径查询系统 学号姓名 小组成员 起止时间 2015 年 1 月 7 日 至 2015 年 1 月 19 日 课程设计 评 语 在为期两周的课程设计中 该生课堂表现良好 参与了课程设计的整个过程 实现了火车路线查询的以下功能 录入 添加 修改 删除 查询最短路线和显 示等功能 课程设计说明书填写正确 条理清楚 对于课程设计过程介绍详细 代码正确 作品演示熟练 能按照设计要求完成指定的功能 答辩过程中 回答 问题正确 熟练 对自己的程序描述清楚 条理性强 平时成绩报告成绩 演示与答辩 成绩 成绩总评 指导教师 签字 年 月 日 注 成绩均用百分制注 成绩均用百分制 总成绩总成绩 平时成绩平时成绩 20 报告成绩报告成绩 40 演示与答辩成绩演示与答辩成绩 40 设计题目 火车路径查询系统 1 1 课程设计目的 课程设计目的 1 熟练掌握图的存储结构及其建立过程和常用操作 2 巩固和加深对数据结构的理解 通过上机实验 调试程序 加深对课本知识的理解 最终能够熟练应用数据结构的知识写程序 3 了解并掌握数据结构与算法的设计方法 具备初步的独立分析和设计能力 初步掌握 软件开发过程的问题分析 系统设计 程序编码 测试等基本方法和技能 4 提高综合运用所学的理论知识和方法独立分析和解决问题的能力 培养我们的创新思 维能力 2 2 课程设计正文 课程设计正文 2 12 1 概要设计概要设计 2 1 12 1 1 系统分析系统分析 该系统主要功能包括 录入信息 添加信息 修改信息 删除信息 按最短路径查询 信息等 分析 1 此系统要完成对火车站点信息的储存 修改 删除 添加和查询最短路线 因为涉 及到最短路线问题 所以数据结构优先考虑采用图的邻接矩阵储存结构 站点和行车线路 可以构成图状结构 站点作为图的顶点 行车路线作为图的边 边上的权值作为站点间的 距离 此结构便于完成任务的各种操作 2 录入信息 录入站点的名称 输入站点 i 到站点 j 的路长 3 添加信息 添加站点的名称 输入站点 i 到站点 j 的路长 4 修改信息 输入站点的名称 查询 如果有该站点 则输入新的站点名 新的从该 站点到其他站点的路长 5 删除信息 输入要删除站点前的序号 要删除路线的站点序号 vi vj 然后查找并 删除 6 最短路径查询 1 输入起点 终点 输出最短路长和需用的时间 并输出相应的路 线过程 2 输入用户所在地 查询所在地到其他各站点的所有最短路径 输出最短路长和 需用的时间 并输出相应的路线过程 2 1 22 1 2 系统结构图系统结构图 2 22 2 详细设计详细设计 2 2 12 2 1 数据类型定义数据类型定义 const int MAXVertices 20 const int MAXweight 500 struct Vertex string city class Graph public Graph void input void add void change void del void show void select path1 void select path2 private int Edge MAXVertices MAXVertices int numE numV Vertex Vertices MAXVertices 2 2 22 2 2 存储结构存储结构 2 2 32 2 3 函数声明函数声明 1 录入函数 函数名 void Graph input 操作结果 录入站点信息 分析 输入站点名 两站点距离 为图的顶点和边权值赋值 2 添加函数 函数名 void Graph add 操作结果 添加站点信息 3 修改函数 函数名 void Graph change 操作结果 修改其站点信息和两站点之间的距离值 4 删除函数 函数名 void Graph del 操作结果 删除站点信息和这个站点与其他站点的距离 分析 输入要删除站点序号和路线条数 用 for 语句查找并删除 5 显示函数 函数名 void Graph show 操作结果 显示出所有的站点信息 图 3 无向带权图 图 2 结构定 义 图 4 邻接矩阵 6 查找两地最短距离函数 函数名 void Graph select path1 操作结果 查找最短距离并输出 分析 输入起点 终点 利用 for 语句查找 根据迪杰斯特拉算法计算 然后输出最短路 长和需用的时间 并输出相应的路线过程 7 查找所有地点最短距离 函数名 void Graph select path2 操作结果 查找最短距离并输出 分析 输入用户所在地 利用 for 语句查找 查询所在地到其他各站点的所有最短路径 根据迪杰斯特拉算法计算 然后输出最短路长和需用的时间 并输出相应的路线过程 2 2 42 2 4 函数流程图函数流程图 1 查询所有地点最短路径 图 4 查询所有地点最短路 径 2 修改功能 2 2 52 2 5 代码 见附录 代码 见附录 2 32 3 程序测试结果程序测试结果 1 主菜单结果 2 录入函数结果 3 添加函数结果 图 6 主界面 图 7 录入函数 图 8 添加函数 4 修改函数结果 5 删除函数结果 6 查询两地最短路程结果 7 查询所有站点最短路程结果 图 9 修改函数 图 10 删除函数 图 11 查询两地最短路程函 数 图 12 查询所有站点最短路程 3 3 课程设计总结 课程设计总结 通过此次课程设计 我也学到了很多 比如团队的力量永远大于个人的力量 细节决 定成败等等 通过这次系统的编写 我明白了编程要细心 有耐心 有些程序看起来很多 很难 但只要抽丝剥茧的慢慢分析 就能明白它是怎么运行的 其实 只要踏踏实实一步 一步来 你会发觉原来编程难度也不过如此 通过这一次的编写程序不但重新温习了以前学到的知识 还学习到许多的新的知识 也认识到了自己的许多的不足 例如耐心不够 在调试程序时 发现了一个错误 但是总 是解决不了 心里就会感到厌烦 不想继续做下去 还有不够细心 每一次改写完程序后 检查了一遍 自己认为没有错了 结果调试发现又有错误等等 不过也发现了自己的一些 优点 比如善于听取他人意见 虚心求教等 通过这次次实验我们收获了很多 对数据结构这门课有更深的了解 让我们对链表 队 列和图的应用更娴熟 加强了对图的最短路径的认识与应用 巩固了迪杰斯特拉算法 为 我们更好的了解课本内容 改进不足提供了件 通过这次课程设计 我对用算法计算最短路径有了更深刻的认识 加强了我对数据结 构的了解 我知道如果要想在 C 语言有成就 必须多想多练习 现在我还是缺少练习 看程序可能看得懂 而当真正的编写程序起来就遇到困难了 同时 我懂得了要多思考 遇到问题或不解时不能不懂装懂 要尽量去想其缘由 要懂得查阅有用的资料 最后 通过全组人的齐心协力 最终将程序编写了出来 并且使之得到实现我们的预 期目的 通过此次课程设计 从一定成度上提高了我们对数据结构的熟悉度 也提高了我 们独立编程的能力 同时也体会到在程序设计过程中团体合作 共同解决问题的重要性 我知道在这次的课程设计中 还有许多的欠缺 在以后的日子中 我一定得更加严格 要求自己 改正缺点 不断努力 不断进步 4 4 参考文献 参考文献 1 严蔚敏等 数据结构 M C 语言版 清华大学出版社 1997 4 2 张乃孝主编 算法与数据结构 M C 语言版 高等教育出版社 2002 3 李廉治 姜文清 郭福顺 数据结构 M 大连理工大学出版社 1989 4 徐孝凯 魏荣 数据结构 M 机械工程出版社 2007 5 谭浩强 C 程序设计 M 清华大学出版社 2011 6 杨路明 C 语言程序设计教程 M 京邮电大学出版社 2003 答辩记录 答辩小组教师 答辩小组教师 提问与答辩情况记录如下 提问与答辩情况记录如下 1 为什么选择邻接矩阵存储结构 为什么选择邻接矩阵存储结构 答 邻接矩阵存储结构容易实现图的操作 如 求某顶点的度 判断顶点间是否有弧 找 顶点的邻接点 又因为站点作为图的顶点 线路作为图的边 边上的权值作为站点间的距 离 此结构便于完成任务的各种操作 2 程序的亮点在哪 程序的亮点在哪 答 查询最短路径部分分为两部分 一是分两地查询 这部分功能是输入起点 在输入终 点然后查询最短路径 输出其最短路程和相应的路径 二是该地到其他地方的最短路径 这部分的功能是输入用户的所在地 让后查询该所在