数据结构超市选址问题

1、课程设计报告书题目： 学校超市选址问题 目录1. 需求分析32. 概要设计33. 详细设计34. 调试分析95. 用户使用说明96. 测试结果97. 参考文献151需求分析输入数据：各单位编号；各单位到超市的距离；各单位人去超市的频度；按照以上输入数据创建图；为超市选址实现总体最优1、该程序可以读取文件中相邻两地点的距离信息，在程序中用邻接矩阵构造一个有向网，并计算网中任意节点到其它节点的最短路径并输出。2、在磁盘中新建一个文件存储两个地点的距离信息，要求先输入起点，以空格间隔，然后输入终点，再以空格间隔，然后输入这两个地点间的距离，如此法，依次输入各路径间的起点，终点和距离。3、根据界面所给

2、的提示信息首先输入保存交通网的文件名，然后输入要求哪一个节点到其它节点的最短路径。4、程序运行后，在屏幕上将输出所求节点经过某些中转站到达它所能达到的节点及最短路径的值，并将各节点与其对应的编号保存到文件“编号与地名对照表”中，以便它用。5、程序执行的命令包括：（1）求place数组中的记录在顶点向量中的坐标、（2）采用邻接矩阵存储结构，构造有向网6.输出最优解。2概要设计本程序主要采用带权图来实现超市选址实现总体最优的一些功能。1.刚开始我们用频度(即人流量)X距离作为权值,算权值最小的,但当距离一定时,人流量大的反而不被选择如果用距离/频度(即人流量)作为权值,比如一个离1M频度为1人的单

3、位,和离100M频度为100人的单位就出现问题了2.最后我们想还是人流量最重要了,但网上都说要用在main函数中通过子函数sistant()来求出各单位到超市的距离的平方和，之后求出距离平方和与人数的关系，最后算出相对的最短距离从而确定超市的最优地址。基本操作： CreatGraph(MGraph &G)操作结果：采用邻接矩阵存储结构，构造有向网G LocateVex(MGraph &G,char * place) 初始条件：用邻接矩阵存储的有向网G已存在操作结果：返回place数组中的记录在顶点向量中的坐标3详细设计 实现概要设计中定义的所有数据类型，对每个操作只需要写出伪码算法；对主程序和

4、其他模块也都需要写出伪码算法(伪码算法达到的详细程度建议为：按照伪码算法可以在计算机键盘直接输入高级程序设计语言程序)；可采用流程图 N S 图或PAD图进行描述，画出函数和过程的调用关系图。(1)元素类型：typedef int VRType;typedef struct VRTypefloat Adj;int Adjnum;int Adjfrequency;VRType;/存储距离和频度作为权值，权值类型typedef char * VertexType;typedef char PathMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef int * Sh

5、ortPathTable;（2）结点类型：typedef struct AreCellVRType adj;/权值InfoType * info;/附加信息ArcCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef struct VertexType vexsMAX_VERTEX_NUM;AdjMatrix arcs;/邻接矩阵int vexnum,arcnum;/顶点个数，弧的条数MGraph;（3）主程序模块：void main()MGraph G;int v,Adjcountminvexnum;/Adjcountmin记录当前总权值的最小值

6、 double Adjcountmin;/Adjcountminvexnum记录当前总权值的最小值对应的起点顶点编号PrintProMember();/输出程序编程组员/从文本中输入数据并且创建图CreatGraph(G);/创建带权有向图/计算最优解Adjcountmin=sistant(G,0);/第一轮计算以编号0为起点的相对最短路径的总权值，并将之作为当前相对总权值的最小值记录for(v=1;vG.vexnum;v+)/循环比较以所有编号为起点的的总权值，并且记录下相对总权值的最小值及对应的起点顶点编号 if(sistant(G,v)Adjcountmin) Adjcountmin=s

7、istant(G,v); Adjcountminvexnum=v; /输出最优解Print(G,v,Adjcountminvexnum,Adjcountmin);system(pause);（4）输出程序编程组员函数模块void PrintProMember()printf(*n);printf(* 海南师范大学 *n);printf(* 计本二班 数据结构 课程设计 *n);printf(* 小组成员:杨振平（组长）、唐田、章捷 *n);printf(*n);（5）构造有向网的模块：void CreatGraph(MGraph &G)FILE *fp;int i,j;char filenam

8、e20,place110,place210,num10,c;/初始化邻接矩阵G.vexnum=0;G.arcnum=0;for(i=0;iMAX_VERTEX_NUM;i+)for(j=0;jMAX_VERTEX_NUM;j+)G.arcsij.adj=INFINITY;G.=NULL; for(i=0;iMAX_VERTEX_NUM;i+)G.vexsi=NULL;printf(请输入保存交通网的文档名n);gets(filename);if(fp=fopen(filename,r)=NULL)printf(不能打开文件%sn,filename);exit(0);c=f

9、getc(fp);while(c!=EOF)/逐个读取文件中的字符while(c= | c=n)c=fgetc(fp);i=0;while(c!= & c!=n & c!=EOF)/将第一个地名保存在place1数组中*(place1+i)=c;c=fgetc(fp);i+;*(place1+i)=0;/添加结束符while(c= | c=n)c=fgetc(fp);i=0;while(c!= & c!=n & c!=EOF)/将第二个地名保存在place2数组中*(place2+i)=c;c=fgetc(fp);i+;*(place2+i)=0;/添加结束符while(c= | c=n)c=

10、fgetc(fp);i=0;while(c!= & c!=n & c!=EOF)/将权值保存在num数组中*(num+i)=c;c=fgetc(fp);i+;*(num+i)=0;/添加结束符while(c= | c=n)c=fgetc(fp);G.arcnum+;/边数加1i=LocateVex(G,place1);/确定第一个地名在邻接矩阵中的位置j=LocateVex(G,place2);/确定第二个地名在邻接矩阵中的位置G.arcsij.adj.Adjnum=Translation(num);G.arcsij.adj.Adjfrequency=Translationfrequency(

11、frequency);G.arcsij.adj.Adj=(float)(Translation(num)*Translationfrequency(frequency);/构造邻接矩阵fclose(fp);if(fp=fopen(标号与地名对照表.txt,w)=NULL)printf(不能打开文件标号与地名对照表n);exit(0);/打印一张标号与地名对照表for(i=0;iG.vexnum;i+)fprintf(fp,%d表示%sn,i,G.vexsi);fclose(fp);/向屏幕输出一张标号与地名对照表for(i=0;iG.vexnum;i+)printf(%d表示%sn,i,G.v

12、exsi);/该函数中调用另两个子模块：/*求place数组中的记录在顶点向量中的坐标*/int LocateVex(MGraph &G,char * place)int i=0,n;n=strlen(place);/数组长度while(i=MAX_VERTEX_NUM)/空间不足printf(内存不足n);exit(0);G.vexsi=(char *)malloc(n+1)*sizeof(char);/顶点向量中没有place中的记录，则建立新记录strcpy(G.vexsi,place);G.vexnum+;/结点个数加1return i;/*将s数组中保存的权值转换成整型*/int T

13、ranslation(char *s)int n,i,j,weight=0,a;n=strlen(s);/字符串长度for(i=0;in;i+)/求权值a=1;/系数for(j=1;j=n-1-i;j+)a=a*10;weight+=a*(si-48);/权值return weight;（6）求各单位到超市v0的相对距离函数模块float sistant(MGraph &G,int v0)/求出各单位到超市v0的相对距离int v;float sn=0,sm=0;/sn为各单位到超市v0的距离的平方和,sm为各单位到超市v0的距离和人流量的积的和for(v=0;vG.vexnum;v+)/v0

14、到v有路径if(G.arcsv0v.adj.AdjINFINITY) sn+=G.arcsv0v.adj.Adjnum*G.arcsv0v.adj.Adjnum;for(v=0;vG.vexnum;v+)/v0到v有路径if(G.arcsv0v.adj.AdjINFINITY) sm+=G.arcsv0v.adj.Adj;return sn/sm;/G.arcsv0v.adj.Adj=将相对距离sn/sm做为权值（7）输出最优解函数模块void Print(MGraph &G,int v,int Adjcountminvexnum,double Adjcountmin)printf(最优相对总

15、权值为%fn是以编号%d为起点到其余各单位总体最优的解：n,Adjcountmin,Adjcountminvexnum); for(v=0;vG.vexnum;v+)printf(相对总权值为%fn是以编号%d为起点到其余各单位总体最优的解：n,sistant(G,v),v);函数和过程的调用关系图如下：main（）主函数PrintProMember();/输出程序编程组员函数CreatGraph(G);/创建带权有向图函数sistant(G,v); /求各单位到超市v0的相对距离函数Print(G,v,Adjcountminvexnum,Adjcountmin);/输出最优解函数Locate

16、Vex(G,place);/求place数组中的记录在顶点向量中的坐标函数Translation(s);/将num数组中保存的权值转换成整型函数函数和过程的调用关系图4调试分析内容包括：a调试过程中遇到的问题是如何解决的以及对设计与实现的回顾讨论和分析；1、当输入的地点编号到其于地点没有路径时，程序将输出运行结果。2、当输入的图不是联通图时，当输入地点编号时，程序照常输出该地点到它所能到达地点的相对最短路径，即在同一个联通分量中的地点。3、调试中的错误及解决办法文件输入问题调试过程中匹配问题的纠正和改进，各模块在共同数据结构下的整合，以及一些小错误如函数返回值匹配和权衡。b算法的时空分析(包括

17、基本操作和其他算法的时间复杂度和空间复杂度的分析)和改进设想； 刚开始我们用最优解决算法采用Dijkstra算法计算相对的最短距离，后来我们为符合实际人流量占主要选取标准的原则，改变了算法例如：有三个点A，B，C。对应的人数是：pA,pB,pC.如果确定另一个点为D（未知的）。A，B，C三点到D的距离为：AD，BD，CD。那么k1=AD2+BD2+CD2,k2=pA*AD+pB*BD+pC*CD,满足k1/k2值尽可能的小的地址即为所选。选择路径规划算法的依据是希望算法的时间复杂性和空间复杂性较小，尤其是前者。从运筹学的学习中大家熟悉的Dijkstra算法是个常用的算法，它计算从一个节点到路网

18、其它各节点的最短路径的时间复杂度是O（n3），表明算法运行时间与网络节点数n的立方成正比。采用符合实际的新算法后，算法的时间复杂度是O（n2），表明算法运行时间与网络节点数n的平方成正比。不仅符合实际，而且算法的时间复杂度减少，程序的效率更高更好了。c经验和体会等。 通过一个多月的努力，我们终于设计并实现出一个既符合实际由相对高效的超市选址系统。这个过程中让我们体会到团队的精神和力量之所在，为以后发展走出了第一步，当算法发生变化时所要调整和修改模块以及相应数据结构的修改的策略以及框架，这次实验设计给我们学习的机会，又学了挺多知识和经验真高兴。5用户使用说明说明如何使用你编写的程序，详细列出每一

19、步的操作步骤。（1）本程序的运行环境为VC6.0。（2）进入演示程序后即显示提示信息：请输入保存交通网的文档名：（输入保存交通网的文档名，如graph.txt）当将数据文件调入程序中，程序将通过算法的实现计算出相对最优的超市地址并将结果打印在屏幕上。6测试结果列出你的测试结果，包括输入和输出。这里的测试数据应该完整和严格，最好多于需求分析中所列。/测试一/测试人流量对超市选址的影响，即人流量多的优先选址/输入数据存放在1.txt中，内容如下：（四个数据分别是起点、终点、距离、人/流量即频度）A B 400 300A D 400 300A E 300 300B A 400 300B E 200 300B F 200 400B C 400 300C B 400 300C D 400 300C F 300 400D E 200 300D F 200 400D C 400 300D A 400 300E A 300 300E D 200 300E C 500 300F B 200 400F C 300 400F D 200 400/实际模型图如下：/测试结果如下：/结果显示是人流量大的F点被选做超市/测试二/测试距离相对长短对