学校超市选址问题1 需求分析核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少) 数据模型规律构造: 带权有向图 (权值计算: 距离*频度)存储构造: typedef structstring vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum;/ ,arcnum;MGraph;核心算法: Floyd 算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称，距离，频度，单位个数输出数据: 所选单位名称总体思路: 假设超市是要选在某个单位，那么先用 floyd 算法得出各顶点间的最短距离/最小权值。假设顶点个数有 n 个，那么就得到 n*n 的一张表格，arcs(i,j)表示 i 单位到 j 单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第 t 行)，那么超市选在 t 单位处就是最优解。2 概要设计Floyd 算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问题。设 G=(V, E, w)是一个带权有向图，其边 V=v1, v2, , vn。对于 kn，考虑其结点 V 的一个子集。对于 V 中任何两个结点 vi、vj，考虑从vi 到 vj 的中间结点都在 vk 中的全部路径，设是其中最短的，并设的路径长度为。假设结点 vk 不在从 vi 到 vj 的最短路径上，则；反之则可以把分为两段， 其中一段从 vi 到 vk，另一段从 vk 到 vj，这样便得到表达式。上述争论可以归纳为如下递归式：1原问题转化为对每个 i 和 j 求，或者说求矩阵开头流程图Main输入根本信息GreatMgraphGh建立邻接矩阵的存储构造Floyd 算法NYAij=INF,i!=ji 到 j 不存在路FloyedGh输出i-j 的路径和路径长度输出超市的最正确地址：i完毕3 具体设计第一步，让全部路径加上中间顶点 1，取 Aij与 Ai1+A1j中较小的值作 Aij的值，完成后得到 A(1),如此进展下去，当第 k 步完成后，Akij表示从 i 到就且路径上的中间顶点的路径的序号小于或等于 k 的最2短路径长度。当第n-1 步完成后，得到 An-1，An-1即所求结果。An-1 ij表示从 i 到 j 且路径上的中点顶点的序号小于或等于 n-1 的最短路径长度，即 A(n-1)ij表示从 i 到 j 的最短路径长度。3.1 头文件和变量设定#include”stdafx.h” #include #include #include #include #include “malloc.h“ #include #define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767 const int MAXVEX=100; typedef char Vextype;3.2 构造体的定义typedef structVextype vexsMAXVEXMAXVEX;/单位名称顶点信息；int adjMAXVEXMAXVEX;边；int disMAXVEXMAXVEX;int fMAXVEX;/ 单位之间的相通状况 是否有/单位间距离边的长度；/各单位去超市的频率；3int n; int e;Mgraph;3.3 变量的输入void CreatMgraph(Mgraph *G)/顶点数和边数；int i,j,k;printf(“请输入单位个数:n“); scanf(“%d“,&(G-n);printf(“请输入单位间的路径数:n“); scanf(“%d“,&(G-e);printf(“请输入单位名称:n“); for(i=0;in;i+)printf(“请输入第%d 个单位名称:n“,i); scanf(“%s“,&G-vexsi);for(i=0;in;i+) for(j=0;jn;j+)/构造体的初始化；G-adjij=0;G-disij=0;G-fi=0;for(k=0;ke;k+)printf(“请输入相通的两单位 (输入格式:i,j):n“); scanf(“%d,%d“,&i,&j);/在距离上表达为无向；4printf(“请输入一样两个单位间的距离(格式：dis)：n“); scanf(“%d“,&(G-disij);G-adjij=1;G-adjji=1;G-disji=G-disij;for(k=0;kn;k+)printf(“请输入第%d 个单位去超市的相对频率:n“,k); scanf(“%d“,&(G-fk);for(i=0;in;i+)/以距离和频率之积作为权值；for(j=0;jn;j+)G-disij*=G-fi;/最终权值非完全无向； if(G-adjij=0&i!=j)G-disij=INF;3.4 带权有向图求最短路径floyd 算法void Floyed(Mgraph *G)/带权有向图求最短路径 floyd 算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;in;i+)/初始化A和path5数组for(j=0;jn;j+)/置初值；Aij=G-disij; pathij=-1; counti=0;for(k=0;kn;k+)/k 代表运算步骤for(i=0;in;i+) for(j=0;jn;j+)if(Aij(Aik+Akj)/从 i 经 j 到 k 的一条路径更短Aij=Aik+Akj;pathij=k;printf(“nFloyed 算法求解如下:n“); for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)printf(“n”); printf(“%d-%d;”,i,j); if(Aij=INF)if(i!=j)6printf(“不存在路径n“);elseprintf(“路径长度为:%d”, Aij);printf(“路径为:%d*”,i);pre=pathij; while(pre!=-1)printf(“%dn”,pre); pre=pathprej;printf(“%d”,j);/以下为选择总体最优过程，然后确址； for(i=0;in;i+)for(j=0;jn;j+)if(Aij=INF)counti=0; elsecounti=1;for(i=0;in;i+) if(counti)for(j=0;jn;j+)7if(i!=j)Aii+=Aji;k=0;for(i=0;in;i+)if(counti)if(AkkAii) k=i;printf(“超市的最正确地址为:“); printf(“%sn”,G-vexsk);3.5 主函数模块void mainMgraph *Gh=NULL;Gh=(Mgraph *)malloc(sizeof(Mgraph); CreatMgraph(Gh);Floyed(Gh); system(“pause“);4 调试分析4.1 此题目的关键点之一：有两个权值：各单位到超市的距离及各单位人去超市的频度。这使得图的 建 立 出 现 了 困 难 ， 经 过 分 析 这 两 个 值 可 以 合 并 为 一 个 权 值 即8distance*frequency；这样就使得图的建立轻而易举。4.2 此题目的关键点之二：利用 floyd 算法求出每一对顶点之间的最短路径。4.3 此题目的关键点之三：选出最短路径，即最正确地点应使其到其他单位权值最小。留意：每比较一次 path 应清 0 一次Path=0。4.4 此题目的关键点之四：运行输入时留意输入的格式。5 课设总结总结数据构造课程设计完成了，对我来说这是一项小小的挑战，它不仅检验了我的学习状况，也考验了我的意志力，收获非颇丰！通过一学期的学习，我知道数据构造是一门理论性强、思维抽象、难度较大的课程，是根底课和专业课之间的桥梁。之前我们我们已经学习了 C 程序设计、离散数学等，以后还要学操作系统、编译原理、数据库原理、软件工程等。 通9过本门课程的学习，我们应当能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培育良好的程序设计力量和解决实际问题的力量， 而且该课程的争论方法对我们学生在校和离校后的学习和工作，也有着重要的意义。学以致用，这才是我的目标，课程设计给了我这个时机。数据构造是计算机科学与技术专业的一门核心专业根底课程，在我们专业的课程体系中起着承上启下的作用，学好数据构造对于提高理论认知水平和实践力量有着极为重要的作用。学习数据构造的最终目的是为了获得求解问题的力量。对于现实世界中的问题，应当能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据构造来表示，然后设计一个解此数学模型的算法，再进展编程调试，最终获得问题的解答。通过数据构造课程实践，加上教师的全力指导，无论是理论学问，还是实践动手力量，我都有了不同程度上的提高。10