学校超市选址问题

1、数据结构课程设计报告设计题目：学校超市选址问题专业班级学生学号指导教师起止时间 2009.12.282009.12.312009年秋季学期数据结构课程设计1、问题描述对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请 为超市选址，要求实现总体最优。2、需求分析核心问题：求最短路径（选址的要求就是超市到各单位权值之和最少）数据模型（逻辑结构）：带权有向图（权值计算：距离*频度）存储结构：typedef structstri ng vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum

2、;/ ,arc num;MGraph;核心算法：Floyd算法（弗洛伊德算法-每一对顶点之间的最短路径）输入数据：各单位名称，距离，频度，单位个数.输出数据：所选单位名称.总体思路：如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个，那么就得到n*n的一张表格，arcs（i,j） 表示i单位到j单位的最短距 离/最小权值，这张表格中和最小的那一行（假设为第t行），那么超市选在t单位处就是最优解。3、开发环境1.硬件环境：PC兼容机2.软件环境：DEV-C+53.操作系统：Win dows XP4、算法设计思想Floyd算法利用动态规划思想，通过

3、把问题分解为子问题来解决任意两点间的最短路径问题。设G=（V, E, w）是一个带权有向图，其边V=v1, v2,vn。对于k< n,考虑其结点 V的一个子集。对于V中任何两个结点vi、vj，考虑从vi到vj的中间结点都在 vk中的所有路径，设是其中最短 的，并设的路径长度为。如果结点vk不在从vi到vj的最短路径上，则；反之则可以把分为两段，其中一段从vi到vk，另一段从vk到vj，这样便得到表达式。上述讨论可以归纳为如下递归式： 原问题转化为对每个i和j求，或者说求矩阵。利用上述递归表达式，串行Floyd算法可以写成下面的样子：a) 初始化：Du,v=Au,vb) For k:=1

4、to nFor i:=1 to nFor j:=1 to nIf Di,j>Di,k+Dk,jThen Di,j:=Di,k+Dk,j;c) 算法结束：D即为所有点对的最短路径矩阵算法包括三个循环，每个循环需要运行步骤n,最内部的循环体可以在常数时间内完成，因此算法的复杂度为：0(nA3)。5、流程图6、课程设计过程中的关键算法Floyd算法表述：第一步，让所有路径加上中间顶点1,取Aij 与Ai1+A1j中较小的值作Aij 的新值，完成后得到A(1),如此进行下去，当第k步完成后，A(k)ij 表示从i到就且路径上的中间顶点的路 径的序号小于或等于 k的最短路径长度。当第n-1步完成后

5、，得到A(n-1)，A(n-1)即所求结果。A(n-1) ij 表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度，即 A(n-1)ij 表示从i到j的最短路径长度。代码表示如下：void Floyed(Mgraph *G)/带权有向图求最短路径floyd 算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;in t coun tMAXVEX;for(i=0;i<G-> n;i+)/for(j=0;j<G-> n;j+)/Aij=G->disij; pathij=-1; coun ti=0;初始化A

6、和path数组 置初值；for(k=0;k<G-> n;k+)kfor(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;cout<<endl<<"Floyed算法求解如下:"<<endl;for(i=0;i<G-> n;i+)for(j=0;j<G-> n;j+)if(i!=j)cout<<" "<&l

7、t;i<<"->"<<j<<""if(Aij=INF)if(i!=j)cout<<"不存在路径"<<"n"<<endl;elsecout<<"路径长度为:"<<Aij<<"n"cout<<"路径为:"<<i<<""pre=pathij;while(pre!=-1)cout<<p

8、re<<"n"pre=pathprej;cout<<j<<e ndl;/以下为选择总体最优过程，然后确址；for(i=0;i<G-> n;i+)for(j=0;j<G-> n;j+)if(Aij=INF)coun ti=0;elsecoun ti=1;for(i=0;i<G-> n;i+)if(cou nti)for(j=0;j<G-> n;j+)Ai0+=Aij;for(i=0;i<G-> n;i+)k=0;if(cou nti)if(Ak0>Ai0) k=i; cout

9、<<"超市的最佳地址为："<<G->vexsk<<endl;7、测试及结果测试数据：输入：单位个数、单位间的路径数、单位名称、相通两单位以及之间的距离、和各单位去超市的频率输出：相通两单位之间的路径和他的长度结果:诂输入单桂个数匕:输人单桂间的路径数=4郵翳聽希希输入第2个单位名称=和输入第3亍单位容称：話输人第4个单位容称：峯输入柏通的两茨位嘶入格式1,2请输入梱通两个单位间的距离f格式；距离”2H请输人相通的两单位I辙入榕式曲真菩嘉入柚谧两个聲位间的鉅劈格式，距詡:3U请输入相通的两单位t输入格武比加：学爲人相通两个单桂间的距离

10、I格式，距藹”40清输入相通的两单位£输人格式4,1一请输入相通两个单位间的距离f格式；距离; 黒输人第土个单位去超芾的相对频率=1诒输入弟：!个单位去超市的梱对颔率=I请输入第m个单位去超市的栩对顼率=1请输人第竝个单位去超芾的相对坂率=1PloyodMgW?"F = 0->±；不存在5备径不存在路径不存在路径径长度沟：20=1 2I :L-A阳路径长度均=5 踣径为注232->0；不存在路径2->±5路径长度湘止0 跖径为屹1 ,2- >3；路径长度为询0 路径为冷33- >0;yp存在路径3->2；路径长度为汩臼

11、 路径为泊2i青按任意链继续-&总结与收获这次的程序软件基本上运行成功，可以简单的对已经输入的数据进行计算，求出超市的最佳选址单位。但是程序较小，功能不全面，只是理论，并未实践。同时，这次数据结构课程设计让我们感触很深，使我们每个人都了解到的学习不应该只局限于我们的课本，因为课本上告诉我们的只是很有限的一部分，所涉及的面也是狭窄的。但是怎样在有 限的范围内学习到无限的知识呢？那就要我们自己懂得竞争，懂得自学，懂得充分利用身边的任何资源。应该说，我们在这次的课程设计中学到了很多知识，这并不仅仅包括书本上的知识，更重要 的是我们学会了如何去和别人交流，怎样用语言去实现自己的想法，在这个过程

12、中使我懂得了勤学好问的重要性。虽然在我的程序中有一部分是从网上搜索得来的，但我竭力将所获得的信息变成自己的资源。 在我动手上机操作的同时，我在了解和看懂的基础上有所改变和创新，但是在我的程序软件中还有部分的不足，需要加以更新。同时，通过这次课程设计，我们都意识到了自己动手实践的弱势，特 别是在编程方面，于是我们知道了计算机的实践操作是很重要的，只有通过上机编程才能充分的了解自己的不足。相信通过这次的课程设计，更让我深刻意识到自己在学习中的弱点，同时也找到了克服这些弱点的方法，这也是一笔很大的资源。在以后的时间中，我应该利用更多的时间去上机实验，多编写 程序，相信不久后我的编程能力都会有很大的提

13、高。经过这次课程设计，通过对程序的编制，调试和运行，使我更好的掌握了图基本性质和关于选址问题的解决方法，熟悉了各种调用的数据类型，在调试和运行过程中使我更加的了解和熟悉程序运行的环境，提高了我对程序调试分析的能力和对错误的纠正能力。这次数据结构的程序设计，对于我来说是一个挑战。我对数据结构的学习在程序 的设计中也有所体现。 课程设计是培养学生综合运用所学知识、发现、提出、分析和解决实际问题，锻炼实践能力的重要环节，是对学生实际工作能力的具体训练和考察过程。随着科学技术发展的日新月异，当今计算机应用在生活中可以说得是无处不在。因此作为二十一世纪的大学来说掌握计算机开发技术是十分重要的。在整个课程

14、程序中， 我们充分应用和调用各个程序模块，从而实现了此次程序设计的所应该有的功能。在本组看来这就是我们在课程设计是比较成功的，而在这个过程中，让我们感觉收获最大 的就是我们都能利用这次课程设计学到很多我们在课本上没有的知识（Floyd算法），充分的发挥了我们的主动性，使我们自主的去学习。9、参考文献1. 马秋菊 主编 数据结构（C语言描述）北京：中国水利水电出版20062. 严蔚敏吴伟民编著数据结构（C语言版） 北京：清华大学出版社20023. 李春葆苏光奎编著 数据结构与算法教程 北京：清华大学出版社20054. 戴敏主编数据结构北京：机械工业出版社20085. 李春葆编著数据结构教程上机实

15、验知道清华大学出版社 2005附件一：程序清单#include <string.h>#include <stdio.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;typedef struct单

16、位名称（顶点信息）；/单位之间的相通情况（是否有边）/单位间距离（边的长度）；/各单位去超市的频率；/顶点数和边数；Vextype 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);printf("请输入单位间的路径数：n");scanf(

17、"%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+)printf("请输入相通的两单位

18、(输入格式: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->n;k+)printf(" 请输入第d个单位去超市的相对频率：n",k); scanf("%d"，&

19、(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,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;i<G->n;i+)/初始化 A和 path数组for

20、(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; cout<<endlvv"Floyed 算法求解如下:"<<endl;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(i!=j)coutvv&quo