数据结构课程设计学校超市选址问题

1、WORD格式学校超市选址问题学生*专业班级学号题目学校超市选址问题课题性质工程设计课题来源自选课题指导教师同组*无对于某一学校超市，其他各单位到其的距离不同，专业资料整理WORD格式主要内容任务要求参考文献审查意见同时各单位人员去超市的频度也不同。请为超市选址，要*现总体最优。1. 实现公司到超市距离，频率最优。2. 确定超市位置，要*现总体最优。 C程序设计"第三版谭浩强 著 清华大学"数据构造" C 语言版严蔚敏著清华大学"数据构造及应用"沈华等编著机械工业指导教师签字：教研室主任签字：专业资料整理WORD格式一、需求分析1 核心问题 :

2、求最短路径 ( 选址的要求就是超市到各单位权值之和最少 )2数据模型逻辑构造 : 带权有向图 ( 权值计算 : 距离 * 频度 )3存储构造 : typedef structstring vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum;/ ,arcnum;MGraph;核心算法 : Floyd算法 ( 弗洛伊德算法 - 每一对顶点之间的最短路径)输入数据 :各单位名称，距离，频度，单位个数输出数据 :所选单位名称总体思路 :如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离 / 最小

3、权值。假设顶点个数有n 个，那么就得到n*n 的一X表格， arcs(i,j)表示 i 单位到 j单位的最短距离 / 最小权值 ,这X表格中和最小的那一行( 假设为第 t 行) ，那么超市选在 t 单位处就是最优解。2 运行环境Visual Stdio C+6.0Windows Vista/2003/XP3 概要设计Floyd 算法利用动态规划思想， 通过把问题分解为子问题来解决任意两点见的最短路径问题。设 G=(V, E, w)是一个带权有向图，其边 V=v1, v2, , vn 。对于 kn，考虑其结点 V 的一个子集。对于 V 中任何两个结点 vi 、vj ，考虑从vi 到 vj 的中间

4、结点都在 vk 中的所有路径，设该路径是其中最短的，并设它的路径长度为最短路径长度。如果结点 vk 不在从 vi 到 vj 的最短路径上，那么；反之那么可以把分为两段，其中一段从 vi 到 vk，另一段从 vk 到 vj ，这样便得到表专业资料整理WORD格式1专业资料整理WORD格式达式。上述讨论可以归纳为如下递归式：原问题转化为对每个i 和 j 求，或者说求矩阵流程图开场Main 输入根本信息GreatMgraphGh 建立邻接矩阵的存储构造Floyd 算法NYAij=INF,i!=ji 到 j 不存在路FloyedGh 输出 i->j 的路径和路径长度输出超市的最正确地址：i完毕4

5、 详细设计第一步，让所有路径加上中间顶点1，取 Aij与 Ai1+A1j中较小的值作 Aij的新值，完成后得到 A(1), 如此进展下去， 当第 k 步完成后， A专业资料整理WORD格式2专业资料整理WORD格式 k ij表示从 i 到就且路径上的中间顶点的路径的序号小于或等于k 的最短路径长度。当第n-1 步完成后，得到 A n-1 ，An-1 即所求结果。 An-1 ij表示从 i 到 j且路径上的中点顶点的序号小于或等于n-1 的最短路径长度，即 A(n-1)ij表示从 i 到 j 的最短路径长度。4.1 头文件和变量设定#include <string.h>#includ

6、e <stdio.h>#include <stdlib.h>#include <time.h>#include "malloc.h"#include <iostream.h>#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767const int MAXVEX=100;typedef char Vextype;4.2 构造体的定义typedef structVextype vexsMAXVEXMAX

7、VEX;/单位名称顶点信息；int adjMAXVEXMAXVEX;/ 单位之间的相通情况是否有边；int disMAXVEXMAXVEX;/ 单位间距离边的长度 ；int fMAXVEX;/ 各单位去超市的频率；专业资料整理WORD格式3专业资料整理WORD格式int n;/ 顶点数和边数；int e;Mgraph;4.3 变量的输入void CreatMgraph(Mgraph *G)int i,j,k;printf("请输入单位个数 :n");scanf("%d",&(G->n);printf("请输入单位间的路径数 :n&

8、quot;);scanf("%d",&(G->e);printf("请输入单位名称 :n");for(i=0;i<G->n;i+)printf("请输入第 %d个单位名称 :n",i);scanf("%s",&G->vexsi);for(i=0;i<G->n;i+)/ 构造体的初始化； for(j=0;j<G->n;j+)G->adjij=0;G->disij=0;G->fi=0;for(k=0;k<G->e;k+)pri

9、ntf("请输入相通的两单位( 输入格式 :i,j):n");scanf("%d,%d",&i,&j);/在距离上表达为无向；专业资料整理WORD格式4专业资料整理WORD格式printf("请输入一样两个单位间的距离( 格式： dis) ： n");scanf("%d",&(G->disij);G->adjij=1;G->adjji=1;G->disji=G->disij;for(k=0;k<G->n;k+)printf(" 请输入第 %

10、d个单位去超市的相对频率 :n",k); scanf("%d",&(G->fk);for(i=0;i<G->n;i+)/以距离和频率之积作为权值；for(j=0;j<G->n;j+)G->disij*=G->fi;/最终权值非完全无向；if(G->adjij=0&&i!=j)G->disij=INF;4.4 带权有向图求最短路径floyd算法void Floyed(Mgraph *G)/带权有向图求最短路径floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX

11、;int i,j,k,pre;int countMAXVEX;for(i=0;i<G->n;i+)/初始化 A和 path专业资料整理WORD格式5专业资料整理WORD格式数组for(j=0;j<G->n;j+)/置初值；Aij=G->disij;pathij=-1;counti=0;for(k=0;k<G->n;k+)/k代表运算步骤for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij>(Aik+Akj)/从 i 经 j 到 k 的一条路径更短Aij=Aik+Akj;pathij=k;co

12、ut<<endl<<"Floyed算法求解如下 :"<<endl;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(i!=j)cout<<" "<<i<<"->"<<j<<""if(Aij=INF)if(i!=j)cout<<" 不存在路径 "<<"n"<<endl;专业资料整理WORD格

13、式6专业资料整理WORD格式elsecout<<" 路径长度为 :"<<Aij<<"n"cout<<" 路径为 :"<<i<<"*"pre=pathij;while(pre!=-1)cout<<pre<<"n"pre=pathprej;cout<<j<<endl;/ 以下为选择总体最优过程，然后确址；for(i=0;i<G->n;i+)for(j=0;j<G-

14、>n;j+)if(Aij=INF)counti=0;elsecounti=1;for(i=0;i<G->n;i+)if(counti)for(j=0;j<G->n;j+)if(i!=j)Aii+=Aji;专业资料整理WORD格式7专业资料整理WORD格式k=0;for(i=0;i<G->n;i+)if(counti)if(Akk>Aii)k=i;cout<<" 超市的最正确地址为 :"<<G->vexsk<<endl;4.5 主函数模块void main()Mgraph *Gh=NUL

15、L;Gh=(Mgraph *)malloc(sizeof(Mgraph);CreatMgraph(Gh);Floyed(Gh);system("pause");5 调试分析5.1 此题目的关键点之一：有两个权值：各单位到超市的距离及各单位人去超市的频度。这使得图的建立出现了困难，经过分析这两个值可以合并为一个权值即distance*frequency；这样就使得图的建立轻而易举。专业资料整理WORD格式8专业资料整理WORD格式5.2 此题目的关键点之二：利用 floyd算法求出每一对顶点之间的最短路径。5.3 此题目的关键点之三：选出最短路径， 即最正确地点应使其到其他单

16、位权值最小。注意：每比较一次 path 应清 0 一次 Path=0。6 设计程序如下：#include <string.h>#include <stdio.h>#include <stdlib.h>#include <time.h>#include "malloc.h"#include <iostream.h>#define TURE 1#define FALSE 0#define OK 1#define ERROR 0#define OVERFLOW -1#define INF 32767const int M

17、AXVEX=100;typedef char Vextype;typedef structVextype vexsMAXVEXMAXVEX;/ 单位名称顶点信息 ；int adjMAXVEXMAXVEX;/单位之间的相通情况是否有边；int disMAXVEXMAXVEX;/单位间距离边的长度；int fMAXVEX;/各单位去超市的频率；int n;/顶点数和边数；int e;Mgraph;void CreatMgraph(Mgraph *G)int i,j,k;printf(" 请输入单位个数:n");scanf("%d",&(G->n

18、);printf(" 请输入单位间的路径数:n");scanf("%d",&(G->e);printf(" 请输入单位名称:n");for(i=0;i<G->n;i+)专业资料整理WORD格式9专业资料整理WORD格式printf(" 请输入第 %d 个单位名称 :n",i);scanf("%s",&G->vexsi);for(i=0;i<G->n;i+)/构造体的初始化；for(j=0;j<G->n;j+)G->adjij=

19、0;G->disij=0;G->fi=0;for(k=0;k<G->e;k+)printf(" 请输入相通的两单位(输入格式 :i,j):n");scanf("%d,%d",&i,&j);/在距离上表达为无向；printf(" 请输入一样两个单位间的距离(格式： dis)： n");scanf("%d",&(G->disij);G->adjij=1;G->adjji=1;G->disji=G->disij;for(k=0;k<G-&

20、gt;n;k+)printf(" 请输入第 %d 个单位去超市的相对频率:n",k);scanf("%d",&(G->fk);for(i=0;i<G->n;i+)/以距离和频率之积作为权值；for(j=0;j<G->n;j+)G->disij*=G->fi;/ 最终权值非完全无向；if(G->adjij=0&&i!=j)G->disij=INF;void Floyed(Mgraph *G)/ 带权有向图求最短路径floyd 算法int AMAXVEXMAXVEX,pathMAX

21、VEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;i<G->n;i+)/初始化 A 和 path 数组for(j=0;j<G->n;j+)/置初值；Aij=G->disij;pathij=-1;专业资料整理WORD格式10专业资料整理WORD格式counti=0;for(k=0;k<G->n;k+)/k 代表运算步骤for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij>(Aik+Akj)/ 从 i 经 j 到 k 的一条路径更短Aij=Aik+A

22、kj;pathij=k;cout<<endl<<"Floyed算法求解如下:"<<endl;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(i!=j)cout<<" "<<i<<"->"<<j<<""if(Aij=INF)if(i!=j)cout<<" 不存在路径 "<<"n"<<end

23、l;elsecout<<" 路径长度为 :"<<Aij<<"n"cout<<" 路径为 :"<<i<<"*"pre=pathij;while(pre!=-1)cout<<pre<<"n"pre=pathprej;cout<<j<<endl;/ 以下为选择总体最优过程，然后确址； for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if

24、(Aij=INF)counti=0;专业资料整理WORD格式11专业资料整理WORD格式elsecounti=1;for(i=0;i<G->n;i+)if(counti)for(j=0;j<G->n;j+)if(i!=j)Aii+=Aji;k=0;for(i=0;i<G->n;i+)if(counti)if(Akk>Aii)k=i;cout<<" 超市的最正确地址为:"<<G->vexsk<<endl;void main()Mgraph *Gh=NULL;Gh=(Mgraph *)malloc(sizeof(Mgraph);CreatMgraph(Gh);Floyed(Gh);system("pause");/* 测试数据：输入：单位个数4单位间的路径数6第 0 个单位名称A第 1 个单位名称B第 2 个单位名称C第 3 个单位名称D相通两单位之间的距离0,121,23专业资料整理WORD格式12专业资料整理WORD格式2,340,310,221,33第 0 个单位去超市的频率2第 1 个单位去超市的频率4第 2 个单位去超市的频率3