数据结构课程设计--城市交通咨询系统、航班信息的查询与检索.doc

课程设计题目 课程设计题目 城市交通咨询系统城市交通咨询系统 一 课程设计的原始资料及依据 在交通网络非常发达 交通工具和交通方式不断更新的今天 人们的出差 旅游或做其他的出行时 不仅关心节省交通运费问题 而且对里程和所需要时 间等问题感兴趣 可用一个图结构来表示交通网络系统 利用计算机建立一个 交通咨询系统 图中顶点表示城市 边表示城市之间的交通关系 这个交通咨 询系统可用回答旅客提出的各种问题 二 课程设计主要内容及要求 1 建立交通网络图的存储结构 2 画出主要的功能结构图和主要模块的流程图 3 使用迪杰斯特拉算法 求一个城市到其它所有城市最短路径 4 使用弗洛伊德算法 求任意两个城市间最短路径 三 对课程设计说明书撰写内容 格式 字数的要求 1 课程设计说明书是体现和总结课程设计成果的载体 主要内容包括 设 计题目 设计目的 设备器材 设计原理及内容 设计步骤 遇到的问题及解 决方法 设计总结 设计小组评语 参考文献等 一般不应少于 3000 字 2 在适当位置配合相应的实验原理图 数据通路图 微程序流程图 实验 接线图 微指令代码表等图表进行说明 应做到文理通顺 内容正确完整 书 写工整 装订整齐 3 设计总结部分主要写本人完成工作简介以及自己的设计体会 包括通过 课程设计学到了什么 哪里遇到了困难 解决的办法以及今后的目标 设计小 组评语处注明设计组编号 设计组组长 设计组成员 并由设计组组长给出评 语 4 课程设计说明书手写或打印均可 手写要用学校统一的课程设计用纸 用黑或蓝黑墨水工整书写 打印时采用 A4 纸 页边距均为 20mm 正文采用宋 体小四号字 行间距 18 磅 文中大标题采用黑体小三号字 一级节标题采用黑 体四号字 二级节标题采用黑体小四号字 表题与图题采用宋体五号字 5 课程设计说明书装订顺序为 封面 任务书 成绩评定表 目录 正文 参考文献 四 设计完成后应提交成果的种类 数量 质量等方面的要求 1 完成 任务书 中指定的操作功能 运行稳定 2 课程设计说明书 五 时间进度安排 顺序阶段日期计 划 完 成 内 容备注 1 第 1 天 阅读资料 2 第 2 3 天 系统分析设计 3 第 4 8 天 程序编制 调试及运行 4 第 9 天 成绩评定 5 第 10 天 撰写课程设计说明书 六 主要参考资料 文献 1 郭翠英 C 语言课程设计案例精编 北京 中国水利水电出版社 2004 3 2 谭浩强 C 语言程序设计 北京 清华大学出版社 1999 12 3 张翔 C 语言函数大全 北京 清华大学出版社 2002 4 4 浦滨 C 游戏编程从入门到精通 北京 北京希望电子出版社 2002 5 5 陈天洲 C 语言高级程序设计 北京 人民邮电出版社 2002 6 杨旭 C 语言程序设计案例教程 北京 人民邮电出版社 2005 7 王为青 C 语言高级编程及实例剖析 北京 人民邮电出版 社 2008 02 8 徐慧 C 语言实例解析精粹 北京 人民邮电出版社 2006 04 9 姚大鹏 栾好利 张翼英 等编著 C 语言程序设计教程习题与上机实训 指导 中国水利水电出版社 2005 10 王为青 C 语言实例解析 北京 人民邮电出版社 2008 02 课程设计题目 课程设计题目 航班信息的查询与检索航班信息的查询与检索 一 课程设计的原始资料及依据 当今乘飞机旅行的人越来越多 使愈来愈多的人选择了飞机为长距离出行的交通工具 这就使航空公司以及机场的工作量愈来愈大 需要用电脑来解决问题 人们需要关心了解 各类航班的班次 时间 价格及机型等信息 在这个飞行航班数据的信息模型中 航班号 是关键字 查阅有关程序设计的案例资料 进一步理解程序设计模块化的思想 并利用此思想 根据对程序设计学习编写一个航班信息的查询与检索系统 通过本设计可以加深理解利用 程序设计思想开发一个系统的整个流程 提高分析问题 解决问题和实际动手的能力 二 课程设计主要内容及要求 1 建立 建立一个线性表的存储结构 2 录入功能 输入航班信息 3 排序 按航班号进行排序 3 查询功能 输入航班号显示相应数据元素 输入起点站显示相应数据元素 输入终点站显示相应数据元素 输入起飞时间显示相应数据元素 输入到达时间显示相应数据元素 4 退出 退出查询系统 三 对课程设计说明书撰写内容 格式 字数的要求 1 课程设计说明书是体现和总结课程设计成果的载体 主要内容包括 设 计题目 设计目的 设备器材 设计原理及内容 设计步骤 遇到的问题及解 决方法 设计总结 设计小组评语 参考文献等 一般不应少于 3000 字 2 在适当位置配合相应的实验原理图 数据通路图 微程序流程图 实验 接线图 微指令代码表等图表进行说明 应做到文理通顺 内容正确完整 书 写工整 装订整齐 3 设计总结部分主要写本人完成工作简介以及自己的设计体会 包括通过 课程设计学到了什么 哪里遇到了困难 解决的办法以及今后的目标 设计小 组评语处注明设计组编号 设计组组长 设计组成员 并由设计组组长给出评 语 4 课程设计说明书手写或打印均可 手写要用学校统一的课程设计用纸 用黑或蓝黑墨水工整书写 打印时采用 A4 纸 页边距均为 20mm 正文采用宋 体小四号字 行间距 18磅 文中大标题采用黑体小三号字 一级节标题采用黑体四号 字 二级节标题采用黑体小四号字 表题与图题采用宋体五号字 5 课程设计说明书装订顺序为 封面 任务书 成绩评定表 目录 正文 参考文献 四 设计完成后应提交成果的种类 数量 质量等方面的要求 1 完成 任务书 中指定的操作功能 运行稳定 2 课程设计说明书 五 时间进度安排 顺序阶段日期计 划 完 成 内 容备注 1 第 1 天 阅读资料 2 第 2 3 天 系统分析设计 3 第 4 7 天 程序编制 调试及运行 4 第 8 9 天 成绩评定 5 第 10 天 撰写课程设计说明书 六 主要参考资料 文献 1 严蔚敏 吴伟民 数据结构 C 语言版 北京 清华大学出版社 2007 2 谭浩强 C 程序设计 北京 清华大学出版社 1999 12 3 滕国文 数据结构课程设计 北京 清华大学出版社 2010 09 4 苏仕华 等编著 数据结构课程设计 北京 机械工业出版社 2005 05 5 李春葆 数据结构 C 语言版 习题与解析 北京 清华大学出版社 2002 04 沈阳工程学院课程设计报告 摘要 摘 要 新世纪需要具有丰富的现代科学知识 能够独立解决面临的任务 充满活力 又有创新 意识的新型人才 近年来 我国在计算机应用 计算机软件和电子类相关专业的人才培养方 面取得了长足的进展 每年的计算机相关专业毕业生都有数十万人 但是毕业生走进企业 公司 政府机构或研究单位之后 往往深刻地感觉到缺乏实际开发项目的经验 不善于综合 运用所学理论 对知识的把握缺乏融会贯通能力 作为新世纪的大学生 我们应当站在时代 发展的前列 掌握现代科学技术知识 调整自己的知识结构和能力结构 以适应社会发展的 要求 开展数据结构课程设计有助于提高我们的实际动手操作能力以及项目开发能力 本次数据结构课程设计城市交通咨询这个题目 在存储方式上是运用了图的结构 在编 写程序的过程中遇到了许多问题 例如 如何定义图的存储结构 怎样实现单源路径最短等 一系列问题 但经过讨论和改正 使程序达到预期的要求 航班信息查询与检索要求对航班信息进行查找和排序 需要利用二分法对排好序的航班 号快速进行查找 而如何进行排序使用哪种方法排序引起了我们的热切讨论 最后决定使用 基数排序法 在为期两周的数据结构课程设计学习中 先要学习数据结构课程的目的掌握数据结构存 储的方法 学习会用计算机语言编写程序 以实现所需要处理的任务 要正确处理算法与语 法的关系 算法结构存储是程序的核心 是灵魂 语法是外壳 是工具 不应把学习重点放 在语法规则上 语法是重要的 不掌握语法规则就无法编写出正确的程序 一定要把重点放 在解题的思路上和运用何种存储的方法 通过思考和大量的阅读 来构造一个完整的程序 数据结构存储的设计直接关系到程序的好坏 最后 感谢老师在我们程序设计的过程中辛勤的指导和不倦的教诲 关键词关键词 图 数据结构 最短路径 查找 排序 沈阳工程学院课程设计报告 目录 目录 第一章 问题分析 1 1 1 引言 1 1 2 背景 1 1 3 分析 1 1 3 1 城市交通咨询系统 1 1 3 2 航班信息的查询与检索 2 第二章 原理与运行环境 3 2 1 数据结构理论 3 2 1 1 城市交通咨询数据结构理论 3 2 1 2 航班信息查询与检索数据结构理论 4 2 2 运行环境 4 第三章 系统分析与设计 8 3 1 城市交通咨询系统系统分析与设计 8 3 1 1 系统的功能 8 3 1 2 系统模块分析及其流程图 9 3 2 航班信息的查询与检索 12 3 2 1 系统的功能 12 3 2 2 系统模块分析及其流程图 12 第四章 系统功能实现 17 4 1 城市交通咨询系统功能实现 17 4 1 1 定义主函数 17 4 1 2 对城市间数据的存储 19 4 1 3 定义迪杰斯特拉算法 19 4 1 4 定义费洛伊德算法 21 4 2 航班信息查询与检索系统功能实现 22 4 2 1 定义相关数据类型 22 4 2 2 实现排序各函数说明 24 4 2 3 航班信息的查询 26 结论 30 致谢 31 参考文献 32 沈阳工程学院课程设计报告 第一章 问题分析 0 第一章 问题分析 1 1 引言 数据结构的教学要求是 学会分析研究计算机加工的数据结构的特征 以便为应用涉及 的数据选择适当的逻辑结构 存储结构及其相应的算法 并初步掌握算法的时间分析和空间 分析的技术 另一方面 本课程的学习过程也是复杂程序设计的训练过程 要求学生编写的 程序结构清楚和正确易读 符合软件工程的规范 在学习中 先要学习程序设计课程的目的掌握设计程序的思路 学习会用计算机语言编 写程序 以实现所需要处理的任务 要正确处理算法与语法的关系 算法是程序的核心 是 灵魂 语法是外壳 是工具 不应把学习重点放在语法规则上 语法是重要的 不掌握语法 规则就无法编写出正确的程序 一定要把重点放在解题的思路上 通过思考 和大量的阅读 来构造一个完整的程序 请记住 重要的是学会编程 而不是背语法 程序设计是为了锻炼我们的实际动手能力 在一定程度上 又增加了我们的各方面的知 识 特别是一些联系实际的课程设计 它的完成需要自己平时积累的大量知识 并且需要勤 于思考的能力和无限的激情 本次课程设计主要是学习程序设计的方法 进行程序设计的基 本训练 大多数的学生应该把精力放在最基本 最常用的内容上 学好基本功 通过本次课程设计 相信我们一定能加强对数据结构这门课程的学习 尤其在动手实践 上会有很大的进步 1 2 背景 在交通网络非常发达 交通工具和交通方式不断更新的今天 人们的出差 旅游或做其 他的出行时 由于不同目的的旅客对交通工具有不同的要求 可用一个图结构来表示交通网 络系统 利用计算机建立一个交通咨询系统 图中顶点表示城市 边表示城市之间的交通关 系 这个交通咨询系统可用回答旅客提出的各种问题 交通是社会经济和社会生活的大动脉 良性运作的交通系统是国民经济和人们正常工作 生活的根本保证 随着时代的发展及社会的进步 愈来愈多的人们开始采用新的代步工具 乘坐飞机旅行的人越来越多 人们需要了解各类航班的班次 时间 价格及机型等信息 这 就需要一个专门的系统供人们查询各类航班的信息 1 3 分析 1 3 1 城市交通咨询系统 该设计共分三个部分 一是建立交通网络图的存储结构 二是解决单源最短路径问题 最后再实现两个城市顶点之间的最短路径问题 1 建立图的存储结构 要实现设计要求 首先要定义交通图的存储结构 邻接矩阵是表示图形中顶点之间相邻 沈阳工程学院课程设计报告 第一章 问题分析 1 关系的矩阵 一个图的邻接矩阵表示是唯一的 图的邻接矩阵表示 除了需要用一个二维数组存储顶 点之间相邻关系的邻接矩阵外 通常还需要使用一个具有 n 个元素的一维数组来存储顶点信 息 2 单源最短路径 最短路径问题的提法很多 在这里先讨论单源最短路径问题 即已知带权图 我们希望 找出从某个源点 S 到 G 中其余各顶点的最短距离 此处要用到迪杰斯特拉算法 即按路径长 度递增产生诸顶点的算法 3 任意一对顶点间的最短路径 要解决这个问题 我们可以依次把有向图网络中每个顶点做为源点重复执行迪杰斯特拉 算法 n 次 即可求得每对顶点之间的最短距离 这里用到另一种算法 称为费洛伊德算法 1 3 2 航班信息的查询与检索 对于本设计可采用基数排序法对于一组具有结构特点的航班进行排序 利用二分法对排 好序的航班记录按航班号实现快速查找 按其他方式的查找可采用最基本的顺序查找方法进 行 因为它们用到的比较少 每个航班记录包括八项 分别是 航班号 起点站 终点站 班期 起飞时间 到达时 间 飞机型号以及票价等 其中航班号的格式比较特别开头为航班公司名称的缩写 用两个 大写字母表示 后四位为航班号 这种航班号关键字分为两部分 即字母和数字 其余七项 输入内容不涉及项目核心 因此除票价为数值型外 均定义为字符串型即可 沈阳工程学院课程设计报告 第二章 原理与运行环境 2 第二章 原理与运行环境 2 1 数据结构理论 2 1 1 城市交通咨询数据结构理论 图是一种较线性表和树更为复杂的数据结构 在线性表中 数据元素之间仅有线性关系 每个数据元素只有一个肢解前驱和一个直接后继 在树形结构中 数据元素之间有着明显的 层次关系 并且每一层上的数据元素可能和下一层中的多个元素 及其孩子结点 有关 但 只能和上一层中一个元素 即其双亲结点 相关 而在图形结构中 结点之间的关系可以是 任意的 图中任意的两个数据元素之间都可能有关 由此 图的应用极为广泛 特别是近年 来的迅速发展 已渗入到诸如语言学 物理 化学 电讯工程 计算机科学以及数学的其他 分支中 本次课程设计的城市交通咨询系统实验分三个部分 一是建立交通网络图的存储结构 二是解决单源最短路径问题 最后再实现两个城市顶点之间的最短路径问题 建立图的存储结构 首先定义交通图的存储结构 邻接矩阵是表示图形中顶点之间相邻关系的矩阵 设 G V E 是具有 n 个顶点的图 则 G 的邻接矩阵是具有如下定义的 n 阶方阵 A i j 当不满足上述条件时或 或 若 0 GEvjvivjviWij 一个图的邻接矩阵表示是唯一的 图的邻接矩阵表示 除了需要用一个二维数组存储 顶点之间相邻关系的邻接矩阵外 通常还需要使用一个具有 n 个元素的一维数组来存储顶点 信息 其中下标为 i 的元素存储顶点 vi 的信息 单源最短路径 初始化 S 和 D 置空最短路径终点集 置初始的最短路径值 S v1 TRUE D v1 0 S 集初始时只有源点 源点到源点的距离为 0 while S 集中顶点数 n 开始循环 每次求得 v1 到某个 v 顶点的最短路径 并加 v 到 S 集中 S v TRUE 更新当前最短路径及距离 任意一对顶点间最短路径 假设求从顶点 vi 到 vj 的最短路径 如果从 vi 到 vj 存在一条长度为 arcs i j 的路径 该 路径不一定是最短路径 还需要进行 n 次试探 首先考虑路径 vi v1 和 v1 vj 是否 存在 如果存在 则比较路径 vi vj 和 vi v1 vj 的路径长度 取长度较短者为当前 所求得的最短路径 该路径是中间顶点序号不大于 1 的最短路径 其次 考虑从 vi 到 vj 是 否包含有顶点 v2 为中间顶点的路径 vi v2 vj 若没有 则说明从 vi 到 vj 的当 前最短路径就是前一步求出的 若有 那么 vi v2 vj 可分解为 vi v2 和 v2 vj 而这两条路径是前一次找到的中间点序号不大于 1 的最短 沈阳工程学院课程设计报告 第二章 原理与运行环境 3 路径 将这两条路径长度相加就得到路径 vi v2 vj 的长度 将该长度与前一 次中求出的从 vi 到 vj 的中间顶点序号不大于 2 的最短路径 依次类推 直至顶点 vn 加入当 前从 vi 到 vj 的最短路径出从 vi 到 vj 的中间顶点序号不大于 n 的最短路径为止 由于图 G 中顶点序号不大于 n 所以 vi 到 vj 的中间顶点序号不大于 n 的最短路径 已考虑了所有顶 点作为中间顶点的可能性 因此 它就是 vi 到 vj 的最短路径 2 1 2 航班信息查询与检索数据结构理论 二分查找又称折半查找 优点是比较次数少 查找速度快 平均性能好 其缺点是要求 待查表为有序表 且插入删除困难 因此 折半查找方法适用于不经常变动而查找频繁的有 序列表 首先 我们采用的基数排序法将航班号升序排列 将表中间位置记录的关键字与查 找关键字比较 如果两者相等 则查找成功 否则利用中间位置记录将表分成前 后两个子 表 如果中间位置记录的关键字大于查找关键字 则进一步查找前一子表 否则进一步查找 后一子表 重复以上过程 直到找到满足条件的记录 使查找成功 或直到子表不存在为止 此时查找不成功 折半查找法也称为二分查找法 它充分利用了元素间的次序关系 采用分治策略 可在 最坏的情况下用 O log n 完成搜索任务 它的基本思想是 将 n 个元素分成个数大致相同的 两半 取 a n 2 与欲查找的 x 作比较 如果 x a n 2 则找到 x 算法终止 如 果 xa n 2 则我们只要在数组 a 的右 半部继续搜索 x 对航班号的排序是采用的基数排序法 基数排序法又称 桶子法 bucket sort 或 bin sort 顾名思义 它是透过键值的部份资讯 将要排序的元素分配至某些 桶 中 藉以达 到排序的作用 基数排序法是属于稳定性的排序 其时间复杂度为 O nlog r m 其中 r 为 所采取的基数 而 m 为堆数 在某些时候 基数排序法的效率高于其它的比较性排序法 最高位优先 Most Significant Digit first 法 简称 MSD 法 先按 k1 排序分组 同一组中 记录 关键码 k1 相等 再对各组按 k2 排序分成子组 之后 对后面的关键码继续这样的排 序分组 直到按最次位关键码 kd 对各子组排序后 再将各组连接起来 便得到一个有序序 列 最低位优先 Least Significant Digit first 法 简称 LSD 法 先从 kd 开始排序 再对 kd 1 进行排序 依次重复 直到对 k1 排序后便得到一个有序序列 2 2 运行环境 在数据结构程序的运行环境为 Visual C 6 0 其工作环境如图 2 1 所示 沈阳工程学院课程设计报告 第二章 原理与运行环境 4 图 2 1 Visual C 6 0 的工作环境 C 与 C 程序 Visual C 6 0 的材料如下 Visual C 6 0 由 Microsoft 开发 它不仅是一个 C 编译器 而且是一个基于 Windows 操作系统的可视化集成开发环境 Visual C 6 0 由许多组件组成 包括编辑器 调试器以及 程序向导 AppWizard 类向导 Class Wizard 等开发工具 这些组件通过一个名为 Developer Studio 的组件集成为和谐的开发环境 Visual C 是一个功能强大的可视化软件开发工具 自 1993 年 Microsoft 公司推出 Visual C 1 0 后 随着其新版本的不断问世 Visual C 已成 为专业程序员进行软件开发的首选工具 虽然微软公司推出了 Visual C NET Visual C 7 0 但它的应用的很大的局限性 只适用于 Windows 2000 Windows XP 和 Windows NT4 0 所以实际中 更多的是以 Visual C 6 0 为平台 总体来讲 运行环境方便快捷 建立 C 语言源程序文件 建立方法 选择菜单命令 文件 新建 或直接点击 对话框中的 新建 选择 Win32Console 并在右上方 工程名 称下键入工程名如图 2 2 所示 在工程建立完成后选择 C Source 并在 文件名 下键入文件名如图 2 3 所示 沈阳工程学院课程设计报告 第二章 原理与运行环境 5 图 2 2 建立 C 语言源程序建立工程 程序的编辑与编译 编辑完成后 选择菜单栏中的 运行 调试程序 即可对程 序进行编译 当输出区显示 0 errors 0 warnings 时表示没有错误和警告 反之 则会 按序号列出错误和警告 双击错误或警告 编辑标志会出现在源文件可能出错的位置 当然 有时提示位置不一定很准确 图 2 3 建立 C 语言源程序建立文件 沈阳工程学院课程设计报告 第二章 原理与运行环境 6 程序的执行 单击工具栏上的 红色感叹号 按钮或 Ctrl F5 即可执行刚编写程序 如图 2 4 所示 图 2 4 对源程序进行编写 使用 C 与 C 程序设计 VC 6 0 开发环境 对源程序执行编译 如图 2 5 所示 图 2 5 执行编写的程序 沈阳工程学院课程设计报告 第三章 系统分析与设计 7 第三章 系统分析与设计 3 1 城市交通咨询系统系统分析与设计 3 1 1 系统的功能 本系统主要有两个功能 首先是找到已知源点所表示的城市到其余结点所表示的城市之 间的最短距离和该距离下的最短路径并输出找到的最短距离和路径 第二个功能是找到任意 两个结点城市之间的最短距离并保存两城市之间的最短路径 按用户的需求输出所需要的两 城市之间的最短路径与距离 1 数据存储 城市信息 城市名 代码 交通信息 城市间的里程 存储于内存中 2 数据的逻辑结构 根据设计任务的描述 其城市之间的旅游交通问题是典型的图结 构 可看作为有向图 图的顶点是城市 边是城市之间的距离 3 数据的存储结构 采用邻接表和邻接矩阵都可作为数据的存储结构 但当邻接边不 多时 宜采用邻接表 以提高空间的存储效率 这里建议采用邻接表作为数据的存储结构 4 选择功能模块 用费洛伊德算法找任意两城市间的最短距离与路径 根据具体最优决策的要求 用 Dijkstra 算法求出出发城市到其它各城市的最优值 最短距离 首先 引进一个辅助向量 它的每个分量 D i 表示当前所找到的从始点 v 到 每个终点 vi 的最短路径的长度 它的初态为 输出结果 从目的城市出发 依次输出保存着最短路径的辅助数组中的值 5 主程序可以有系统界面 菜单 也可用命令提示方式 选择功能模块执行 要求在 程序运行过程中可以反复操作 其主程序的流程图如图 3 1 所示 沈阳工程学院课程设计报告 第三章 系统分析与设计 8 N Y Y N 图 3 1 主函数流程图 3 1 2 系统模块分析及其流程图 1 在找从已知城市到其余城市之间的最短距离和路径 我们用迪杰斯特拉算法实现 其 流程图如图 3 2 所示 2 在找任意两个城市间的最短路径及距离时我们用到了费洛伊德算法 其流程图如图 3 3 所示 开始 输入 x X 2 调用费洛伊德算法 X 1 调用迪杰斯特拉 算法 结束 沈阳工程学院课程设计报告 第三章 系统分析与设计 9 Y Y N Y N N 图 3 2 迪杰斯特拉算法求最短路径 开始 输入源点 v1 图的邻接矩阵中 v1 行 arcs v1 i 赋给辅助数组 D i 且 S i 1 在 D n 中找到最小值 D w S w 0 v w S j 0 且 D w arcs v w D v D w arcs v w D v j j 1 j 0 j n 结束 m 0 m m 1 m n 沈阳工程学院课程设计报告 第三章 系统分析与设计 10 Y Y Y Y N N N 图 3 3 费洛伊德算法求最短路径 开始 k 0 i 0 j 0 D i k D k j D i j D i j D i k D k j j j 1 j n i i 1 i n k k 1 k n 结束 沈阳工程学院课程设计报告 第三章 系统分析与设计 11 3 2 航班信息的查询与检索 3 2 1 系统的功能 本任务要求对飞机航班信息进行排序和查找 可按航班的航班号 起点站 到达站 起 飞时间以及到达时间等信息进行查询 本设计主要是对排序以及查找等概念进行综合练习 以链式基数排序为主线 用到二分查找和顺序查找等知识 还有建立静态链表等相关概念 其主要功能模块图如 3 4 所示 航班信息查询与检索系统 按 航 班 号 查 询 退 出 系 统 输入航班信息 按 起 点 站 查 询 按 终 点 站 查 询 按 到 达 时 间 查 询 按 起 飞 时 间 查 询 图 3 4 航班信息查询与检索系统功能模块图 3 2 2 系统模块分析及其流程图 1 航班排序 对输入系统内的航班首先要进行排序 我们采用的基数排序 从低位到高位依次对关键 字进行分配和收集 分两段实现其算法流程图如 3 5 所示 沈阳工程学院课程设计报告 第三章 系统分析与设计 12 N 每段进行串式基数排序 Y 开始 输入数据数组 基数 n 长度 Max 分配收集操作轮数 nT 0 将数据分成 P 段每段 n p 个 nT 1 nT Max 结束 图 3 5 基数排序 2 时间查找 根据航班的起飞时间 到达时间 查找航班的信息 如图 3 6 所示 3 二分法查找功能 二分法查找功能见图 3 7 沈阳工程学院课程设计报告 第三章 系统分析与设计 13 开始 输入查询时间 Time 1 按抵达时间查询 按起飞时间查询 返回查询信息 否 是 图 3 6 时间查找 4 显示功能 显示功能是将所求单词的所有行列信息依次显示在屏幕上 其功能流程图如图 3 8 所示 沈阳工程学院课程设计报告 第三章 系统分析与设计 14 开始 输入航班号 输入航班号对应序号 Low high Mid high low 2 Low mid 1 Num mid fight number Num d w k P k w printf d w printf 路径长度 d n D v w else if xz 1 printf 求单源路径 输入源点 v scanf d Dijkstra G v n printf 结束求最短路径 n 运行后的主界面如图 4 1 所示 图 4 1 主界面 沈阳工程学院课程设计报告 第四章 系统功能实现 18 4 1 2 对城市间数据的存储 在这部分主要是用邻接矩阵对城市间交通网络的存储 其主要代码如下 void CreatMGraph MGraph G int n int e int i j k w for i 1 ivexs i A i for i 1 i n i for j 1 jarcs i j Maxint printf 输入 d 条边的 i j 及 w n e for k 1 karcs i j w printf 有向图的存储结构建立完毕 n 运行的界面如图 4 2 所示 图 4 2 城市交通网络的存储 4 1 3 定义迪杰斯特拉算法 迪杰斯特拉算法是用来求从已知源点到其他各个顶点最短距离的 其运行的结果是找 到从源点到其他各个顶点的路径和最短距离 其主要代码如下 沈阳工程学院课程设计报告 第四章 系统功能实现 19 void Dijkstra MGraph G int v1 int n int D2 MVNum P2 MVNum int v i w min int S MVNum for v 1 varcs v1 v if D2 v Maxint P2 v v1 else P2 v 0 D2 v1 0 S v1 1 for i 2 i n i Min Maxint for w 1 w n w if S w 1 min D2 w S v 1 for w 1 warcs v w arcs v w P2 w v printf 路径长度 路径 n for i 1 i n i printf 5d D2 i printf 5d i v P2 i while v 0 printf d v v P2 v printf n 运行后的界面如图 4 3 所示 沈阳工程学院课程设计报告 第四章 系统功能实现 20 图 4 3 运用地迪杰斯特拉算法求最短距离 4 1 4 定义费洛伊德算法 费洛伊德算法主要是用来求任意两个城市间的最短距离 相当于多次运用迪杰斯特拉算 法 其主要代码如下 void Floyd MGraph G int n int i j k v w for i 1 i n i for j 1 jarcs i j Maxint P i j j else P i j 0 D i j G arcs i j for k 1 k n k for i 1 i n i for j 1 j n j if D i k D k j D i j 沈阳工程学院课程设计报告 第四章 系统功能实现 21 D i j D i k D k j P i j P i k 运行后的界面如图 4 4 所示 图 4 4 用费洛伊德算法求最短距离 4 2 航班信息查询与检索系统功能实现 4 2 1 定义相关数据类型 根据设计要求我们知道所用的记录中只有航班信息 因此要定义相关的数据类型 其源 程序如下 typedef struct char start 6 起点 char end 6 终点 char sche 10 班期 char time1 5 起飞时间 char time2 5 到达时间 沈阳工程学院课程设计报告 第四章 系统功能实现 22 char model 4 机型 int price 票价 infotype 航班记录类型 typedef struct keytype keys keylen 关键字 航班号 infotype others int next slnode 静态链表类型 typedef struct slnode sl maxspace 静态链表 sl 0 为头结点 int keynum 记录当前关键字字符个数 int length 当前表长 sllist 静态链表类型 typedef int arrtype n radix n 十进制数字指针 typedef int arrtype c radix c 26 个字母指针 运行后的主界面如图 4 5 所示 图 4 5 主界面 沈阳工程学院课程设计报告 第四章 系统功能实现 23 4 2 2 实现排序各函数说明 1 一趟分配函数 void distribute c slnode sl int i arrtype c f arrtype c e 一趟字母分配字符函数 int j p for j 0 j radix c j f j e j 0 for p sl 0 next p p sl p next j sl p keys i 65 if f j f j p else sl e j next p e j p 2 一趟收集函数 void collect c slnode sl int i arrtype c f arrtype c e int j t for j 0 f j j sl 0 next f j t e j while j radix c 1 for j j 1 j radix c 1j if f j sl t next f j t e j sl t next 0 3 链式基数排序 沈阳工程学院课程设计报告 第四章 系统功能实现 24 void radixsort sllist arrtype n fn en arrtype c fc ec for i 0 i 2 i distribute l sl i fn en collect l sl i fn en for i 1 i 0 i distribute c l sl i fc ec collect c l sl i fc ec 4 二分法查找函数 int binsearch sllist l keytype key int low high mid low 1 high l length while low high mid low high 2 if strcmp key l sl mid keys 0 return mid else if strcmp key l sl mid keys 1 printf 航班信息查询系统 n printf n printf 1 航 班 号 n printf 2 起 点 站 n printf 3 终 点 站 n printf 4 起飞时间 n printf 5 到达时间 n printf 0 退出系统 n printf n 沈阳工程学院课程设计报告 第四章 系统功能实现 26 printf 请选择 0 5 scanf d printf n switch i case 1 printf 输入要查询的航班号 字母要大写 scanf s key k binsearch l key printf n if k 0 printf 无此航班信息 可能是输入错误 n else printf 航班号 起点站 终点站 航班期 起飞时间 到达时间 机型 票价 n printf 8s 7s 6s 11s 9s 7s 5s 4d n l sl k keys l sl k others start l sl k others end l sl k others sche l sl k others time1 l sl k oth ers time2 l sl k others model l sl k others price printf n break case 2 printf 输入要查询的航班起点站名 scanf s key seqsearch l key i break case 3 printf 输入要查询的航班终点站名 scanf s key seqsearch l key i break case 4 printf 输入要查询的航班起飞时间 scanf s key seqsearch l key i break case 5 printf 输入要查询的航班到达时间 scanf s key seqsearch l key i break case 0 printf n n n 再 见 n n n 沈阳工程学院课程设计报告 第四章 系统功能实现 27 按航班号查询时 应注意航班号字母的大小写 其运行界面如图 4 7 所示 图 4 7 运行界面 按起点站查询其运行界面如图 4 8 所示 图 4 8 查询运行界面 沈阳工程学院课程设计报告 第四章 系统功能实现 28 若输入查询信息有误 系统会提示你输入有误其运行界面如图 4 9 所示 图 4 9 输入有误运行界面 还可以按时间来查询 可根据起飞时间和到达时间来查询 其运行界面如图 4 10 所示 沈阳工程学院课程设计报告 第四章 系统功能实现 29 图 4 10 时间查询界面 沈阳工程学院课程设计报告 结论 30 结论 紧张的两周数据结构课程设计很快过去了 通过这周的学习使我们巩固了以前的知识并 在此基础上对数据结构的特点和算法有了更深的了解 数据结构是计算机程序设计的重要 理论技术基础 它不仅是计算机科学的核心课程 而且已经成为其他理工专业的热门选修课 在计算机的研究和应用中已展现出强大的生命力 它兼顾了诸多高级语言的特点 是一种典 型的结构化程序设计语言 它处理能力强 使用灵活方便 应用面广 具有良好的可移植性 同时这两周的学习也提高了我们适应实际 实践编程的能力 首先这两周的学习 使我在巩固了原有的理论知识上 培养了我灵活运用和组合集成所 学过知识及技能来分析 解决实际问题的能力 使我体会到自身知识和能力在实际中的应用 和发挥 其次 激发了我创新意识 开发创造的能力和培养沟通能力 另外 让我们进一步 熟悉了数据结构的设计应用 每一处编码都是在反复的熟悉数据结构的结构特性 及其语法 函数和程序设计思想的过程 对我们数据结构的学习和提高很有益处 并且使我明白了程序 设计过程有如解决一实际问题 从解决实际问题的角度 我们可以这样来看 第一要了解这 个问题的基本要求 即输入 输出 完成从输入到输出的要求是什么 第二 从问题的要害 入手 从前到后的解决问题的每个方面 即从输入开始入手 着重考虑如何从输入导出输出 在这个过程中 可确定所需的数据结构的基本类型 线性表 栈 队列 串 数组 树和 二叉树以及图等 然后确定处理过程 算法 可得最后结论 最后 在这次课程设计过程 中 我们深刻的认识到了自己在学习方面的不足之处 我们知道我们还有太多的基本的思想 没有真正的理解 当然我们不会灰心 我们会在以后的日子里努力弥补我们的不足 总之 两个礼拜的课程设计让我们受益匪浅 要学好一门学科 没有刻苦钻研的精神是 不行的 只有在不断的尝试中 不断经历失败 然后又不断的尝试才能获得成功 两个多礼 拜中 我们有过山穷水尽的困惑 有过柳暗花明的惊喜 有过唇枪舌