地铁课设报告

沈沈 阳阳 工工 程程 学学 院院 课 程 设 计 设计题目 设计题目 地铁问题地铁问题 系系 别别 班级班级 学生姓名学生姓名 学号学号 指导教师指导教师 职称职称 讲师 讲师讲师 讲师 起止日期 起止日期 20152015 年年 6 6 月月 1515 日起日起 至至 20152015 年年 6 6 月月 2626 日止日止 沈 阳 工 程 学 院 课程设计任务书 课程设计题目 课程设计题目 地铁问题地铁问题 一 课程设计的原始资料及依据 地铁建设问题描述 某城市要在其各个辖区之间修建地铁来加快经济的发展 但由于建 设地铁的费用昂贵 因此需合理安排地铁的建设路线 使乘客可以沿地铁到达各个辖区 并 使总的建设费用最小 二 课程设计主要内容及要求 地铁建设内容及要求 1 从包含各辖区的地图文件中读入名称和各辖区间的直接距离 2 根据读入的各辖区间距离信息 计算应该建设哪些辖区建的地铁线路 3 输出应该建设的地铁路线及所需建设的总里程信息 三 对课程设计说明书撰写内容 格式 字数的要求 1 课程设计说明书是体现和总结课程设计成果的载体 主要内容包括 设计题目 设计目 的 设备器材 设计原理及内容 设计步骤 遇到的问题及解决方法 设计总结 设计小组 评语 参考文献等 一般不应少于 3000 字 2 在适当位置配合相应的实验原理图 数据通路图 微程序流程图 实验接线图 微指令 代码表等图表进行说明 应做到文理通顺 内容正确完整 书写工整 装订整齐 3 设计总结部分主要写本人完成工作简介以及自己的设计体会 包括通过课程设计学到了 什么 哪里遇到了困难 解决的办法以及今后的目标 4 课程设计说明书手写或打印均可 手写要用学校统一的课程设计用纸 用黑或蓝黑墨水 工整书写 打印时采用 A4 纸 页边距均为 20mm 正文采用宋体小四号字 行间距 18 磅 文中大标题采用黑体小三号字 一级节标题采用黑体四号字 二级节标题采用黑体小四号字 表题与图题采用宋体五号字 5 课程设计说明书装订顺序为 封面 任务书 任务分工表 成绩评定表 目录 正文 参考文献 磅 文中大标题采用黑体小三号字 一级节标题采用黑体四号字 二级节标题采用黑体小四 号字 表题与图题采用宋体五号字 5 课程设计说明书装订顺序为 封面 任务书 任务分工表 成绩评定表 目录 正 文 参考文献 四 设计完成后应提交成果的种类 数量 质量等方面的要求 1 完成 任务书 中指定的操作功能 运行稳定 2 课程设计说明书 五 时间进度安排 顺序阶段日期计 划 完 成 内 容备注 1 第 1 天 阅读资料 2 第 2 3 天 系统分析设计 3 第 4 7 天 程序编制 调试及运行 4 第 8 9 天 成绩评定 5 第 10 天 撰写课程设计说明书 六 主要参考资料 文献 1 滕国文 数据结构课程设计 北京 清华大学出版社 2010 09 2 Mark Allen Weiss 编著 数据结构与算法分析 北京 人民邮电出版社 2007 3 李春葆 数据结构 C 语言版 习题与解析 北京 清华大学出版社 2002 04 4 熊锡义主编 C 语言程序设计案例教程 大连理工大学出版社 09 年 3 月版 5 严蔚敏 吴伟民 数据结构 C 语言版 北京 清华大学出版社 2007 6 谭浩强 C 程序设计 北京 清华大学出版社 1999 12 沈沈 阳阳 工工 程程 学学 院院 程序设计基础课程设计成绩评定表程序设计基础课程设计成绩评定表 系 部 系 部 计算机科学与技术系计算机科学与技术系 班级 班级 计算机计算机B143B143 学生姓名 学生姓名 王世杰王世杰 指指 导导 教教 师师 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 调研 论证 能独立查阅文献 收集资料 能制定课程设计方 案和日程安排 0 15 54 43 32 2 工作能力 态度 工作态度认真 遵守纪律 出勤情况是否良好 能够独立完成设计工作 0 25 54 43 32 2 工作量 按期圆满完成规定的设计任务 工作量饱满 难度适宜 0 25 54 43 32 2 说明书的 质量 说明书立论正确 论述充分 结论严谨合理 文字通顺 技术用语准确 符号统一 编号齐 全 图表完备 书写工整规范 0 55 54 43 32 2 指导教师评审成绩指导教师评审成绩 加权分合计乘以 加权分合计乘以 8 8 分分加权分合计加权分合计 指指 导导 教教 师师 签签 名 名 年年 月月 日日 评评 阅阅 教教 师师 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 查阅 文献 查阅文献有一定广泛性 有综合归纳资料的能 力 0 25 54 43 32 2 工作量工作量饱满 难度适中 0 55 54 43 32 2 说明书的 质量 说明书立论正确 论述充分 结论严谨合理 文字通顺 技术用语准确 符号统一 编号齐 全 图表完备 书写工整规范 0 35 54 43 32 2 评阅教师评审成绩评阅教师评审成绩 加权分合计乘以 加权分合计乘以 4 4 分分加权分合计加权分合计 评评 阅阅 教教 师师 签签 名 名 年年 月月 日日 答答 辩辩 小小 组组 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 学生汇报 汇报准备充分 思路清晰 语言表达准确 概 念清楚 论点正确 有层次 有重点 基本上 反映了所完成任务的全部内容 时间符合要求 0 55 54 43 32 2 答 辩 思路清晰 回答问题有理论依据 基本概念清 楚 主要问题回答准确 深入 有说服力 0 55 54 43 32 2 答辩小组评审成绩答辩小组评审成绩 加权分合计乘以 加权分合计乘以 8 8 分分加权分合计加权分合计 答辩小组教师签名 答辩小组教师签名 年年 月月 日日 课课 程程 设设 计计 总总 评评 成成 绩绩分分 沈沈 阳阳 工工 程程 学学 院院 程序设计基础课程设计成绩评定表程序设计基础课程设计成绩评定表 系 部 系 部 计算机科学与技术系计算机科学与技术系 班级 班级 计算机计算机B143B143 学生姓名 学生姓名 张云朗张云朗 指指 导导 教教 师师 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 调研 论证 能独立查阅文献 收集资料 能制定课程设计方 案和日程安排 0 15 54 43 32 2 工作能力 态度 工作态度认真 遵守纪律 出勤情况是否良好 能够独立完成设计工作 0 25 54 43 32 2 工作量 按期圆满完成规定的设计任务 工作量饱满 难度适宜 0 25 54 43 32 2 说明书的 质量 说明书立论正确 论述充分 结论严谨合理 文字通顺 技术用语准确 符号统一 编号齐 全 图表完备 书写工整规范 0 55 54 43 32 2 指导教师评审成绩指导教师评审成绩 加权分合计乘以 加权分合计乘以 8 8 分分加权分合计加权分合计 指指 导导 教教 师师 签签 名 名 年年 月月 日日 评评 阅阅 教教 师师 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 查阅 文献 查阅文献有一定广泛性 有综合归纳资料的能 力 0 25 54 43 32 2 工作量工作量饱满 难度适中 0 55 54 43 32 2 说明书的 质量 说明书立论正确 论述充分 结论严谨合理 文字通顺 技术用语准确 符号统一 编号齐 全 图表完备 书写工整规范 0 35 54 43 32 2 评阅教师评审成绩评阅教师评审成绩 加权分合计乘以 加权分合计乘以 4 4 分分加权分合计加权分合计 评评 阅阅 教教 师师 签签 名 名 年年 月月 日日 答答 辩辩 小小 组组 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 学生汇报 汇报准备充分 思路清晰 语言表达准确 概 念清楚 论点正确 有层次 有重点 基本上 反映了所完成任务的全部内容 时间符合要求 0 55 54 43 32 2 答 辩 思路清晰 回答问题有理论依据 基本概念清 楚 主要问题回答准确 深入 有说服力 0 55 54 43 32 2 答辩小组评审成绩答辩小组评审成绩 加权分合计乘以 加权分合计乘以 8 8 分分加权分合计加权分合计 答辩小组教师签名 答辩小组教师签名 年年 月月 日日 课课 程程 设设 计计 总总 评评 成成 绩绩分分 沈沈 阳阳 工工 程程 学学 院院 程序设计基础课程设计成绩评定表程序设计基础课程设计成绩评定表 系 部 系 部 计算机科学与技术系计算机科学与技术系 班级 班级 计算机计算机B143B143 学生姓名 学生姓名 王丛伍王丛伍 指指 导导 教教 师师 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 调研 论证 能独立查阅文献 收集资料 能制定课程设计方 案和日程安排 0 15 54 43 32 2 工作能力 态度 工作态度认真 遵守纪律 出勤情况是否良好 能够独立完成设计工作 0 25 54 43 32 2 工作量 按期圆满完成规定的设计任务 工作量饱满 难度适宜 0 25 54 43 32 2 说明书的 质量 说明书立论正确 论述充分 结论严谨合理 文字通顺 技术用语准确 符号统一 编号齐 全 图表完备 书写工整规范 0 55 54 43 32 2 指导教师评审成绩指导教师评审成绩 加权分合计乘以 加权分合计乘以 8 8 分分加权分合计加权分合计 指指 导导 教教 师师 签签 名 名 年年 月月 日日 评评 阅阅 教教 师师 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 查阅 文献 查阅文献有一定广泛性 有综合归纳资料的能 力 0 25 54 43 32 2 工作量工作量饱满 难度适中 0 55 54 43 32 2 说明书的 质量 说明书立论正确 论述充分 结论严谨合理 文字通顺 技术用语准确 符号统一 编号齐 全 图表完备 书写工整规范 0 35 54 43 32 2 评阅教师评审成绩评阅教师评审成绩 加权分合计乘以 加权分合计乘以 4 4 分分加权分合计加权分合计 评评 阅阅 教教 师师 签签 名 名 年年 月月 日日 答答 辩辩 小小 组组 评评 审审 意意 见见 评价内容具 体 要 求权重评 分加权分 学生汇报 汇报准备充分 思路清晰 语言表达准确 概 念清楚 论点正确 有层次 有重点 基本上 反映了所完成任务的全部内容 时间符合要求 0 55 54 43 32 2 答 辩 思路清晰 回答问题有理论依据 基本概念清 楚 主要问题回答准确 深入 有说服力 0 55 54 43 32 2 答辩小组评审成绩答辩小组评审成绩 加权分合计乘以 加权分合计乘以 8 8 分分加权分合计加权分合计 答辩小组教师签名 答辩小组教师签名 年年 月月 日日 课课 程程 设设 计计 总总 评评 成成 绩绩分分 沈阳工程学院课程设计报告 摘要 I 摘摘 要要 某城市要在其各个辖区之间修建地铁来加快经济的发展 但由于建设地铁的费用昂贵 因此需合理安排地铁的建设路线 使乘客可以沿地铁到达各个辖区 并使总的建设费用最小 地铁建设可以缓解城市交通压力 城市交通问题 已经成为现代人无法面对的通病 经济发 展 汽车数量增长速度 远远快于城市道路的扩张速度 地铁这个交通的特点就是到达的快 捷性和可靠性 运载能力强 能够在很短的时间运输大量的人群 运行中不塞车 是城市中 最具可靠性的交通工具 第二 增加地铁交通体系 可以使城市规划更加科学和合理 可以 节约能源 缓解对石油 天然气消耗的压力 可以减少污染 地铁这种交通工具污染少 可 以节省时间 因为不塞车 速度快 节省上班族上下班的在途时间 因此我们小组利用数据结构输入各条线路起点 终点和直接距离 建立无向图 邻接矩 阵存储输出邻接矩阵中的普利姆算法计算最小生成树输出最有线路 关键词关键词 数据结构 最小生成树 地铁 邻接矩阵 沈阳工程学院课程设计报告 目录 目 录 摘 要 I 第一章 问题分析 1 1 1 引言 1 1 2 背景 1 1 3 分析 1 1 3 1 调试过程中的问题 1 第二章 原理与运行环境 2 2 1 数据理论 2 2 1 1 地铁问题的数据理论 2 2 2 运行环境 2 2 2 1 打开方法 2 2 2 2 打开 MICROSOFT VISUAL STDIO6 0 运行环境 3 2 2 3 源程序的建立与编辑 连接 4 第三章 系统分析与设计 6 3 1 地铁建设问题分析与设计 6 3 1 1 系统的功能 6 第四章 系统功能实现 7 4 1 地铁建设问题的系统功能实现 7 4 1 1 定义主函数 7 4 1 2 创建结构体数组 存储辖区名 8 4 1 3 创建无向图 邻接矩阵存储 9 4 1 4 输出邻接矩阵 10 4 1 5 普利姆算法求最小生成树 输出最优路线 11 结论 14 致谢 15 参考文献 16 沈阳工程学院课程设计报告 第一章 问题分析 1 第一章 问题分析 1 1 引言 数据结构是计算机存储 组织数据的方式 数据结构是指相互之间存在一种或多种特定 关系的数据元素的集合 通常情况下 精心选择的数据结构可以带来更高的运行或者存储效 率 数据结构往往同高效的检索算法和索引技术有关 一般认为 一个数据结构是由数据元素依据某种逻辑联系组织起来的 对数据元素间逻 辑关系的描述称为数据的逻辑结构 数据必须在计算机内存储 数据的存储结构是数据结构 的实现形式 是其在计算机内的表示 此外讨论一个数据结构必须同时讨论在该类数据上执 行的运算才有意义 一个逻辑数据结构可以有多种存储结构 且各种存储结构影响数据处理 的效率 在许多类型的程序的设计中 数据结构的选择是一个基本的设计考虑因素 许多大 型系统的构造经验表明 系统实现的困难程度和系统构造的质量都严重的依赖于是否选择了 最优的数据结构 许多时候 确定了数据结构后 算法就容易得到了 有些时候事情也会反 过来 我们根据特定算法来选择数据结构与之适应 不论哪种情况 选择合适的数据结构都 是非常重要的 选择了数据结构 算法也随之确定 是数据而不是算法是系统构造的关键因 素 这种洞见导致了许多种软件设计方法和程序设计语言的出现 面向对象的程序设计语言 就是其中之一 本次课程设计主要利用数据结构中最小生成树实现地铁最优线路问题 1 2 背景 随着经济的迅速发展 城市交通 外拥内堵 情况严峻 压力巨大 我们为了缓解城市 交通拥堵 改变过去以地上交通为主的单一格局 构建地上地下立体交通体系 并通过与其 他交通方式的有机衔接 将极大地缓解城市交通拥堵状况 解决人民群众出行难的问题 于 是我们建立了地铁建设项目 1 3 分析 1 3 1 调试过程中的问题 1 调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析 开始准备将辖区名和相应距离同存储在邻接矩阵中 但因为数据类型不同 这个想法 难以实现 而且就算实现了 在后面的程序中操作也非常麻烦 所以我创建了一个结构体数 组用来存储辖区名 这样辖区名和数组下标一一对应 简明 易懂 清晰 以后只要看数字 所对应的下标存储的是哪个辖区 就可以将其引用 运行程序时 我要输出最优路线对应的辖区 所以在输出时要直接引用结构体数组 但怎么都不行 我就分模块来调试 最后发现 原来是没有将结构体数组的地址传过来 修 改后 程序运行正常 没有使用指针 避免了指针指向错误存储区而造成的错误 沈阳工程学院课程设计报告 第一章 问题分析 2 2 算法的时间复杂度和空间复杂度的分析 改进设想 本程序的时间复杂度为 o n 2 主要是 for 循环的作用 沈阳工程学院课程设计报告 第二章 原理与运行环境 3 第二章 原理与运行环境 2 1 数据理论 2 1 1 地铁问题的数据理论 1 程序所能达到的功能 creatve 创建结构体数组 存储辖区名 CreateGraph 建立辖区间直接距离的无向图 用邻接矩阵存储 pri 输出无向图的邻接矩阵 prim 普利姆算法计算无向图的最小生成树 输出最优路线 2 输入的形式和输入值的范围 输入数字和字母 字母为辖区名 数字为直接距离 名称个数 n 线路个数 e 0 e n n 1 直接距离 weigth 0 weigth 99999 3 输出的形式 最佳建设路径为 辖区名 辖区名 直接路径 2 2 运行环境 数据结构程序的运行环境为 Microsoft visual c 6 0 2 2 1 打开方法 开始 程序 Microsoft visual stdio6 0 Microsoft Visual C 6 0 如图 2 1 所示 沈阳工程学院课程设计报告 第二章 原理与运行环境 4 图 2 1 打开 Visual C 的方法 2 2 2 打开 Microsoft visual stdio6 0 运行环境 其工作环境如图 2 2 所示 图 2 2 Visual C 工作环境 沈阳工程学院课程设计报告 第二章 原理与运行环境 5 2 2 3 源程序的建立与编辑 连接 建立 C 语言源程序文件 建立方法 选择菜单命令 File New 或直接点击对 话框中的 New 如图 2 3 所示 图 2 3 建立 C 语言源程序文件 程序的编辑与编译 编辑完成后 选择菜单栏中的 组建 调试程序 或者直 接点击工具栏中 箭头 按钮 即可对程序进行编译 当输出区显示 0 errors 0 warnings 时表示没有错误和警告 反之 则会按序号列 出错误和警告 双击错误或警告 编辑标志会出现在源文件可能出错的位置 我们可以在此 对源程序中的错误进行更改 当然有时提示位置不一定很准确 程序的编辑于编译操作 如图 2 4 所示 图 2 4 程序的编辑与编译 沈阳工程学院课程设计报告 第二章 原理与运行环境 6 程序的执行 单击工具栏上的 深红色感叹号 按钮 即可执行刚编写的程序 若程 序完全正确 即可弹出运行框 如图 2 5 所示 图 2 5 程序的执行 沈阳工程学院课程设计报告 第三章 系统分析与设计 7 第三章 系统分析与设计 3 1 地铁建设问题分析与设计 3 1 1 系统的功能 此系统为 某城市要在各个辖区之间修建地铁 由于地铁建设费用昂贵 因此需要合理 安排地铁建设线路 使市民可以沿地铁到达各个辖区 并使总费用最小 其主功能模块的流程图如图 3 1 所示 N Y 开始 判断 0 e n n 1 输入线路个数 建立无向图 邻接矩阵 存储 输入辖区个数和辖区名 输入各条线路起点 终 点和直接距离 普利姆算法计算最小生 成树 输出最优线路和总里程 结束 输出邻接矩阵 沈阳工程学院课程设计报告 第四章 系统功能实现 8 第四章 系统功能实现 4 1 地铁建设问题的系统功能实现 4 1 1 定义主函数 主函数是程序的入口 采用模块化设计 首先声明一些必要的变量函数如下 creatve 创建结构体数组 存储辖区名 CreateGraph 建立辖区间直接距离的无向图 用邻接矩阵存储 pri 输出无向图的邻接矩阵 prim 普利姆算法计算无向图的最小生成树 输出最优路线 主函数调用各模块的关系如下 主函数 main 调用 int creatve city vex max 创建结构体数组存储辖区名 主函数 main 调用 int CreateGraph int g max int n void pri int g max int n 建立 无向图 用邻接矩阵存储 int CreateGraph int g max int n void pri int g max int n 调用 void pri int g max int n 输出邻接矩阵 主函数 main 调用 void prim int g max int n city vex max 计算最小生成树 输出 最优线路和总里程 源代码如下 void main 主函数 int g max max n city vex max n creatve vex CreateGraph g n pri printf n n最佳建设路线为 n printf 辖区名 辖区名 直接距离 n n prim g n vex 功能实现图如图 4 1 所示 沈阳工程学院课程设计报告 第四章 系统功能实现 9 图 4 1 初始化界面 4 1 2 创建结构体数组 存储辖区名创建结构体数组 存储辖区名 进入主程序页面后 应输入各个辖区名 并调用函数对输入的辖区名进行存储 源代码如下 int creatve city vex max 创建辖区名数组 int i n printf 设置辖区的个数 城市中辖区的个数 scanf d for i 1 i n 1 i 建立城市辖区名数组 printf 第 d个城市辖区名称为 i scanf s vex i name return n 功能实现图 4 2 所示 沈阳工程学院课程设计报告 第四章 系统功能实现 10 图 4 2 4 1 3 创建无向图 邻接矩阵存储创建无向图 邻接矩阵存储 按照地铁建设问题的要求 要将各个辖区为顶点作为图 并用邻接矩阵将其存储 其源代码如下 int CreateGraph int g max int n void pri int g max int n 建立无向图 int e i j k v1 0 v2 0 weight 0 printf 输入可建地铁线线路个数 scanf d while e n n 1 n max error printf 输入可建地铁线线路个数 scanf d for i 1 i n i for j 1 j n j g i j inf 初始化矩阵 全部元素设为无穷大 for k 1 kn v2 n v1 1 v2 1 error printf 输入第 d 条线路的起始辖区 终点辖区 直接距离 k scanf d d d g v1 v2 weight g v2 v1 weight printf n输出存储矩阵 n pri g n return OK 功能实现图如图 4 3 所示 图 4 3 4 1 4 输出邻接矩阵输出邻接矩阵 此时将邻接矩阵存储的结果显示一下 以便检查下一步中结果的正确性 其源代码如下 void pri int g max int n 输出无向图的邻接矩阵 int i j for i 0 i n i printf d t i for i 1 i n i 沈阳工程学院课程设计报告 第四章 系统功能实现 12 printf n d t i for j 1 j n j 输出边的权值 if g i j inf printf t 354 else printf d t g i j printf n 功能实现如图 4 4 所示 图 4 4 4 1 5 普利姆算法求最小生成树 输出最优路线普利姆算法求最小生成树 输出最优路线 用普利姆算法求出最短路程 则为地铁建设的最优路线 其源代码如下 void prim int g max int n city vex max prim的函数 int lowcost max closest max int i j k min s 0 for i 2 i n i n个顶点 n 1条边 lowcost i g 1 i 初始化 closest i 1 顶点未加入到最小生成树中 沈阳工程学院课程设计报告 第四章 系统功能实现 13 lowcost 1 0 标志顶点1加入U集合 for i 2 i n i 形成n 1条边的生成树 min inf k 0 for j 2 j n j 寻找满足边的一个顶点在U 另 一个顶点在V的最小边 if lowcost j min k j s min printf s s d t vex closest k name vex k name min lowcost k 0 顶点k加入U for j 2 j n j 修改由顶点k到其他顶点边的权 值 if g k j lowcost j lowcost j g k j closest j k printf n printf n修建地铁最短总里程为 printf d s 功能实现如图 4 5 所示 沈阳工程学院课程设计报告 第四章 系统功能实现 14 图 4 5 沈阳工程学院课程设计报告 结论 15 结论结论 刚开始拿到题目的时候 没有什么思路 就翻书看了普利姆算法 然后也在网上搜索了 相关的资料 找到有相似的程序 但不符合我的题目的要求 不是邻接矩阵存储 输入输出 也不行 于是 我们小组就仔细的看了程序 弄懂之后我们就开始编我的程序 经过一个星 期的奋斗 我们终于是把程序整出来了 这是一个坚苦而又漫长的过程 看着劳动成果 很 欣慰 毕竟这是我们第一次自己动脑筋做课程设计 通过这次课程设计我们深刻的理解了普利姆算法 同时理解了数据结构中思想的严谨性 和准确性 在这次设计过程中让我们各自找到了自己在设计过程中的缺点