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

计算机科学与技术专业课程设计任务书学生姓名专业班级学号题目学校超市选址问题课题性质工程设计课题来源自拟课题指导教师同组姓名无主要内容对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。任务要求1.实现公司到超市距离，频率最优。2.确定超市位置，要求实现总体最优。参考文献《C程序设计》第三版谭浩强著清华大学出版社《数据结构》（C语言版）严蔚敏著清华大学出版社《数据结构与算法》赵文静祁飞等编著科学出版社审查意见指导教师签字：教研室主任签字：11需求分析核心问题:求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型（逻辑结构）:带权有向图(权值计算:距离*频度)存储结构:typedefstruct{stringvexs[MAX_VERTEX_SIZE];intarcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];intvexnum;//,arcnum;}MGraph;核心算法:Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径)输入数据:各单位名称，距离，频度，单位个数．输出数据:所选单位名称．总体思路:如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。假设顶点个数有n个，那么就得到n*n的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值,这张表格中和最小的那一行(假设为第t行)，那么超市选在t单位处就是最优解。2运行环境VisualStdioC++6.0WindowsVista/2003/XP3概要设计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，这样便得到表达式。上述讨论可以归2纳为如下递归式：原问题转化为对每个i和j求，或者说求矩阵流程图4详细设计第一步，让所有路径加上中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的新值，完成后得到A(1),如此进行下去，当第k步完成后，A开始Main（）输入基本信息建立邻接矩阵的存储结构GreatMgraph（Gh）Floyd算法A[i][j]==INF,i!=j输出i-j的路径和路径长度输出超市的最佳地址：i结束Floyed（Gh）Ni到j不存在路径Y3（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的最短路径长度。4.1头文件和变量设定#includestring.h#includestdio.h#includestdlib.h#includetime.h#includemalloc.h#includeiostream.h#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineINF32767constintMAXVEX=100;typedefcharVextype;4.2结构体的定义typedefstruct{Vextypevexs[MAXVEX][MAXVEX];//单位名称（顶点信息）；intadj[MAXVEX][MAXVEX];//单位之间的相通情况（是否有边）；intdis[MAXVEX][MAXVEX];//单位间距离（边的长度）；intf[MAXVEX];//各单位去超市的频率；4intn;//顶点数和边数；inte;}Mgraph;4.3变量的输入voidCreatMgraph(Mgraph*G){inti,j,k;printf(请输入单位个数:\n);scanf(%d,&(G-n));printf(请输入单位间的路径数:\n);scanf(%d,&(G-e));printf(请输入单位名称:\n);for(i=0;iG-n;i++){printf(请输入第%d个单位名称:\n,i);scanf(%s,&G-vexs[i]);}for(i=0;iG-n;i++)//结构体的初始化；for(j=0;jG-n;j++){G-adj[i][j]=0;G-dis[i][j]=0;G-f[i]=0;}for(k=0;kG-e;k++){printf(请输入相通的两单位(输入格式:i,j):\n);scanf(%d,%d,&i,&j);//在距离上体现为无向；5printf(请输入相同两个单位间的距离(格式：dis)：\n);scanf(%d,&(G-dis[i][j]));G-adj[i][j]=1;G-adj[j][i]=1;G-dis[j][i]=G-dis[i][j];}for(k=0;kG-n;k++){printf(请输入第%d个单位去超市的相对频率:\n,k);scanf(%d,&(G-f[k]));}for(i=0;iG-n;i++)//以距离和频率之积作为权值；for(j=0;jG-n;j++){G-dis[i][j]*=G-f[i];//最终权值非完全无向；if(G-adj[i][j]==0&&i!=j)G-dis[i][j]=INF;}}4.4带权有向图求最短路径floyd算法voidFloyed(Mgraph*G)//带权有向图求最短路径floyd算法{intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];inti,j,k,pre;intcount[MAXVEX];for(i=0;iG-n;i++)//初始化A[][]和path[][]6数组for(j=0;jG-n;j++)//置初值；{A[i][j]=G-dis[i][j];path[i][j]=-1;count[i]=0;}for(k=0;kG-n;k++)//k代表运算步骤{for(i=0;iG-n;i++)for(j=0;jG-n;j++)if(A[i][j](A[i][k]+A[k][j]))//从i经j到k的一条路径更短{A[i][j]=A[i][k]+A[k][j];path[i][j]=k;}}coutendlFloyed算法求解如下:endl;for(i=0;iG-n;i++)for(j=0;jG-n;j++){if(i!=j){couti-j;;if(A[i][j]==INF){if(i!=j)cout不存在路径\nendl;7}else{cout路径长度为:A[i][j]\n;cout路径为:i*;pre=path[i][j];while(pre!=-1){coutpre\n;pre=path[pre][j];}coutjendl;}}}//以下为选择总体最优过程，然后确址；for(i=0;iG-n;i++)for(j=0;jG-n;j++){if(A[i][j]==INF)count[i]=0;elsecount[i]=1;}for(i=0;iG-n;i++)if(count[i]){for(j=0;jG-n;j++)if(i!=j)A[i][i]+=A[j][i];8}k=0;for(i=0;iG-n;i++){if(count[i])if(A[k][k]A[i][i])k=i;}cout超市的最佳地址为:G-vexs[k]endl;}4.5主函数模块voidmain(){Mgraph*Gh=NULL;Gh=(Mgraph*)malloc(sizeof(Mgraph));CreatMgraph(Gh);Floyed(Gh);system(pause);}5调试分析5.1本题目的关键点之一：有两个权值：各单位到超市的距离及各单位人去超市的频度。这使得图的建立出现了困难，经过分析这两个值可以合并为一个权值即distance*frequency；这样就使得图的建立轻而易举。95.2本题目的关键点之二：利用floyd算法求出每一对顶点之间的最短路径。5.3本题目的关键点之三：选出最短路径，即最佳地点应使其到其他单位权值最小。注意：每比较一次path应清0一次（Path=0）。6测试结果6.1输入106.2输出11参考文献：1、《C程序设计》第三版谭浩强著清华大学出版社2、《数据结构》（C语言版）严蔚敏著清华大学出版社3、《数据结构与算法》赵文静祁飞等编著科学出版社12总结数据结构课程设计完成了，对我来说这是一项小小的挑战，它不仅检验了我的学习情况，也考验了我的意志力，收获非颇丰！通过一学期的学习，我知道数据结构是一门理论性强、思维抽象、难度较大的课程，是基础课和专业课之间的桥梁。之前我们我们已经学习了C程序设计、离散数学等，以后还要学操作系统、编译原理、数据库原理、软件工程等。通过本门课程的学习，我们应该能透彻地理解各种数据对象的特点，学会数据的组织方法和实现方法，并进一步培养良好的程序设计能力和解决实际问题的能力，而且该课程的研究方法对我们学生在校和离校后的学习和工作，也有着重要的意义。学以致用，这才是我的目标，课程设计给了我这个机会。数据结构是计算机科学与技术专业的一门核心专业基础课程，在我们专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。通过数据结构课程实践，加上老师的全力指导，无论是理论知识，还是实践动手能力，我都有了不同程度上的提高。13#includestring.h#includestdio.h#includestdlib.h#includetime.h#includemalloc.h#includeiostream.h#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineINF32767constintMAXVEX=100;typedefcharVextype;typedefstruct{Vextypevexs[MAXVEX][MAXVEX];//单位名称（顶点信息）；intadj[MAXVEX][MAXVEX];//单位之间的相通情况（是否有边）；intdis[MAXVEX][MAXVEX];//单位间距离（边的长度）；intf[MAXVEX];//各单位去超市的频率；intn;//顶点数和边数；inte;}Mgraph;voidCreatMgraph(Mgraph*G){inti,j,k;printf(请输入单位个数:\n);scanf(%d,&(G-n));printf(请输入单位间的路径数:\n);scanf(%d,&(G-e));printf(请输入单位名称:\n);for(i=0;iG-n;i++){printf(请输入第%d个单位名称:\n,i);scanf(%s,&G-vexs[i]);}for(i=0;iG-n;i++)//结构体的初始化；for(j=0;jG-n;j++){G-adj[i][j]=0;G-dis[i][j]