1、 1 课程设计报告课程设计报告 课程名称课程名称： 数据结构 设计题目设计题目： 最短路径求最大利润 院院 部部： 计算机与信息工程学院 专专 业业： 计算机科学与技术 组组 别别： 起止日期起止日期: 2012 年 5 月 16 日 2012 年 6 月 24 日 指导教师指导教师: 2 课程设计题目 最短路径求最大利润 组长 学号 班级 计科 111 班 院部 计算机与信息工程学院 专业 计算机科学与技术 组员 指导教师 赵瑞斌 课程设计目的 了解并掌握数据结构与算法的设计方法，具备初步的独 立分析和设计能力；初步掌握软件开发过程的问题分析、 系统设计、程序编码、测试等基本方法和技能；提高
2、综 合运用所的理论知识和方法独立分析和解决问题的能 力；训练用系统的观点和软件开发一般规范进行软件开 发，培养软件工作者所具备的科学工作方法和作风。 课程设计所需环境 VC+6.0 课程设计任务要求 （1）将该图存储为邻接矩阵或邻接表的形式。 （2）若这批商品要从滁州市卖往其余各市，需给出选择 走那条路线，并求出所能获得的最大利润。 课程设计工作进度计划 序 号 起止日期 工 作 内 容 分工情况 1 2012/5/162012/5/20 分析课程设计题目，讨 论解题思路 全体组员 2 2012/5/212012/5/23 根据讨论，确定最佳解 题思路 黄静，许凡 3 2012/5/25201
3、2/5/30 确定编写环境 李双祥，严安 4 2012/6/12012/6/10 编写代码 黄静 5 2012/6/112012/6/13 讨论已编写的代码，检 查是否符合题目要求， 完善代码 全体组员 6 2012/6/152012/6/22 写课程设计报告 夏振卫，柏云飞，李双祥 指导教师签字： 年 月 日 系（教研室）审核意见： 系（教研室）主任签字： 年 月 日 3 目 录 1 引言 . 1 2 需求分析 1 2.1 问题描述 1 2.2 功能需求 2 2.3 实现要点 2 2.4 实现环境 2 3 概要设计 2 3.1 抽象数据类型图的定义 . 2 3.2 主程序 . 3 4 详细设
4、计 3 4.1 数学模型 3 4.2 核心代码 3 4.2.1 定位函数模块 . 3 4.2.2 构造无向网 G 的邻接矩阵函数模块 . 4 4.2.3 邻接矩阵输出模块 5 4.2.4 最短路径和求最大利润模块 5 4.2.5 主函数模块 . 7 5 调试与操作说明：. 8 5.1 调试界面 8 5.2 使用说明 9 6 程序设计总结与体会 . 9 7 致谢 . 11 8 参考文献 12 9 附录 . 13 1 1 引言引言 “数据结构” 是计算机程序设计的重要理论技术基础， 它不仅是计算机学科的核心课程， 而且已成为其他理工科的专业选修课。 图的有关知识在很多领域有着广泛的应用， 在很多情
5、况下是要在寻找两个顶点之间的最 短路径，本课程设计是商品销售问题，求从滁州销售商品到各个城市的最大利润。 2 需求分析需求分析 2.1 问题描述问题描述 现有一批商品， 需要从滁州市销售到另一城市中。 图 1 给出了滁州市到其余 8 个城市的 距离以及该商品在这 8 个城市中的销售价格。 图 2 给出了这 8 个城市之间的距离。 假设该商 品在滁州市的价格为 2 元/千克，运送 1 吨商品所需运费为每公里 0.5 元，现有 10 吨商品， 编程实现求从滁州市销售到各个城市所能获得的最大利润。 表 2-1 滁州到各个城市之间的距离及商品在各个城市之间的售价 CI TY C OST Tianjin
6、g Beijing Shanghai Hefei Nanjing Hangzhou Suzhou Ningbo 距 离（公 里） 974km 1112km 351 km 90km 59 km 554 km 267km 713km 销 售价 格（元 /千克） 3.7 4.0 3.9 2.9 3.3 3.8 3.6 3.6 表 1-2 各个城市之间的距离 2 设计要求： （1）将该图存储为邻接矩阵或邻接表的形式。 （2）若这批商品要从滁州市卖往其余各市，需给出选择走那条路线，并求出所能获得 的最大利润。 2.2 功能需求功能需求 要求完成以下功能： 以无向网邻接矩阵形式输出表格 1 和表格 2 中两城市间的路径长度。 输出从滁州到各城市最短路径上经过的城市及最短路径长度和商品卖到的最大利
