数据结构课程设计-超市选址.docVIP

课 程 设 计 任 务 书 专 业 计算机科学与技术 班 级 姓 名 设 计 起 止 日 期 2015年5月1日-205年5月7日 设计题目： 超市选址 设计任务（主要技术参数）： 硬件环境： CPU：P4 2.8GHz以上; 内存:256MB以上；硬盘大小:80G以上。 软件环境： (1)操作系统：WINDOWS XP。 (2)开发软件: VC++6.0或TC。 实现功能：熟练掌握权值的计算和弗洛伊德算法，通过带权又向图和弗洛伊德算法求出最短路径，让我们更加了解、熟悉数据结构中各种算法的运用与计算，并且学会如何去实现它，对我们的生活也增加了一些常识。 指导教师评语： 成绩： 签字： 年 月 日 PAGE \* MERGEFORMAT 1 课程设计说明书 PAGE \* MERGEFORMAT 1 超市选址 课程设计目的 通过对数据结构中权值的计算和弗洛伊德算法的学习，将其在课程设计中实现、表达出来，数据结构是计算机软件和计算机应用专业的核心课程之一，在众多的计算机系统软件和应用软件中都要用到各种数据结构。在数据结构中，在设计中可以处理数值计算问题 、选取合适数据结构、写出更有效的算法。 计算机核心课程，程序=算法+数据结构，数据结构的重要性可见一斑。事实上，想要写出优美高效的代码，数据结构的知识一定要有的，学习的过程中更重要的是去理解它的思想。 2.设计方案论证 2.1 设计思路 核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少) 数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度) 存储结构: typedef struct { string vexs[MAX_VERTEX_SIZE]; int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE]; int vexnum;// ,arcnum; }MGraph； 核心算法: Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称，距离，频度，单位个数． 输出数据: 所选单位名称． 总体思路:　如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。 假设顶点个数有n个，那么就得到n*n的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值 ,这张表格中和最小的那一行(假设为第t行)，那么超市选在t单位处就是最优解。 2.2设计方法 Floyd算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问题。设G=(V, E, w)是一个带权有向图，其边V={v1, v2, …, vn}。对于k≤n，考虑其结点V的一个子集。对于V中任何两个结点vi、vj，考虑从vi到vj的中间结点都在vk中的所有路径，设该路径是其中最短的，并设它的路径长度为最短路径长度。如果结点vk不在从vi到vj的最短路径上，则；反之则可以把分为两段，其中一段从vi到vk，另一段从vk到vj，这样便得到表达式。上述讨论可以归纳为如下递归式：算法结构图，如图1 开始 开始 M Main（） 输入基本信息 输入基本信息 GreatMgraph（Gh） GreatMgraph（Gh） 建立邻接矩阵的存储结构 建立邻接矩阵的存储结构 Floyd算法 Floyd算法 N N YA[i][j]==INF,i!=j Y A[i][j]==INF,i!=j Floyed（Gh）i到j不存在路径 Floyed（Gh） i到j不存在路径 输出i-j的路径和路径长度 输出i-j的路径和路径长度 输出超市的最佳地址：i 输出超市的最佳地址：i 结束 结束 图1 算法结构图 2.3详细设计 让所有路径加上中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的新值，完成后得到A(1),如此进行下去，当第k步完成后，A（k）[i][j]表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。当第n-1步完成后，得到A（n-1），A（n-1）即所求结果。A（n-1）[i][j]表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度，即A(n-1)[i][j]表示从i到j的最短路径长度。 2.3.1 typedef struct { Vextype vexs[MAXVEX][MAXVEX]; //单位名称（顶点信息）； int adj[MAXVEX][MAXVEX]; //单位之间的相通情况（是否有边）； int dis[MAXVEX][MAXVEX]; //单位间距离（