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

《数据结构课程设计学校超市选址问题》由会员分享，可在线阅读，更多相关《数据结构课程设计学校超市选址问题（18页珍藏版）》请在装配图网上搜索。

1、.学校超市选址问题学生姓名专业班级学号题 目学校超市选址问题课题性质工程设计课题来源自选课题指导教师同组姓名无主要内容对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。任务要求1.实现公司到超市距离，频率最优。2. 确定超市位置，要求实现总体最优。参考文献C程序设计第三版 谭浩强 著 清华大学出版社数据结构（C语言版） 严蔚敏 著 清华大学出版社数据结构及应用沈华 等编著 机械工业出版社审查意见指导教师签字：教研室主任签字： .;一、需求分析 1）核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少)2）数据模型（逻辑结构）

2、: 带权有向图 (权值计算: 距离*频度)3）存储结构: 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单位的最短距

3、离/最小权值 , 这张表格中和最小的那一行(假设为第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的中间结点都在vk中的所有路径，设该路径是其中最短的，并设它的路径长度为最短路径长度。如果结点vk不在从vi到vj的最短路径上，则；反之则可以把分为两段，其中一

4、段从vi到vk，另一段从vk到vj，这样便得到表达式。上述讨论可以归纳为如下递归式：原问题转化为对每个i和j求，或者说求矩阵开始流程图Main（）输入基本信息GreatMgraph（Gh）建立邻接矩阵的存储结构Floyd算法NYAij=INF,i!=ji到j不存在路径Floyed（Gh）输出i-j的路径和路径长度输出超市的最佳地址：i结束4 详细设计第一步，让所有路径加上中间顶点1，取Aij与Ai1+A1j中较小的值作Aij的新值，完成后得到A(1),如此进行下去，当第k步完成后，A（k）ij表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。当第n-1步完成后，得到A（n-

5、1），A（n-1）即所求结果。A（n-1）ij表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长度，即A(n-1)ij表示从i到j的最短路径长度。4.1头文件和变量设定 #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 32767const int MAXVEX=100;typedef char Vextype;4.2结构体的定义typ

6、edef structVextype vexsMAXVEXMAXVEX; /单位名称（顶点信息）；int adjMAXVEXMAXVEX;/单位之间的相通情况（是否有边）；int disMAXVEXMAXVEX;/单位间距离（边的长度）；int fMAXVEX;/各单位去超市的频率；int n;/顶点数和边数；int e;Mgraph;4.3变量的输入void CreatMgraph(Mgraph *G) int i,j,k;printf(请输入单位个数:n);scanf(%d,&(G-n);printf(请输入单位间的路径数:n);scanf(%d,&(G-e);printf(请输入单位名称

7、: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);/在距离上体现为无向；printf(请输入相同两个单位间的距离(格式：dis)：n);scanf(%d,&(G-disij);G-adjij=1;G-adjji=1;G-disji=G-disij;for(k=0;kn;

8、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;4.4带权有向图求最短路径floyd算法void Floyed(Mgraph *G) /带权有向图求最短路径floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;in;i+) /初始化A和pat

9、h数组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;coutendlFloyed算法求解如下:endl;for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)cout ij;if(Aij=INF)if(i!=j)cout不存在路径nendl;elsecout路径长度为:Aijn;cout路径为:i*;pre=pathij

10、;while(pre!=-1)coutpren;pre=pathprej;coutjendl; /以下为选择总体最优过程，然后确址；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+)if(i!=j)Aii+=Aji; k=0;for(i=0;in;i+)if(counti)if(AkkAii)k=i;cout超市的最佳地址为:vexskendl;4.5主函数模块void main()Mgraph *Gh=NULL;Gh=(Mgraph *)mall

11、oc(sizeof(Mgraph);CreatMgraph(Gh);Floyed(Gh);system(pause);5 调试分析 5.1本题目的关键点之一：有两个权值：各单位到超市的距离及各单位人去超市的频度。这使得图的建立出现了困难，经过分析这两个值可以合并为一个权值即distance*frequency；这样就使得图的建立轻而易举。5.2本题目的关键点之二： 利用floyd算法求出每一对顶点之间的最短路径。5.3本题目的关键点之三： 选出最短路径，即最佳地点应使其到其他单位权值最小。注意：每比较一次path应清0一次（Path=0）。6 设计程序如下：#include #include

12、#include #include #include malloc.h#include #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 structVextype vexsMAXVEXMAXVEX; /单位名称（顶点信息）；int adjMAXVEXMAXVEX;/单位之间的相通情况（是否有边）；int disMAXVEXMAXVEX;/单位间距离（边的长度）；

13、int fMAXVEX;/各单位去超市的频率；int n;/顶点数和边数；int e;Mgraph;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;f

14、or(k=0;ke;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;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-ad

15、jij=0&i!=j)G-disij=INF;void Floyed(Mgraph *G) /带权有向图求最短路径floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;in;i+) /初始化A和path数组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;

16、pathij=k;coutendlFloyed算法求解如下:endl;for(i=0;in;i+)for(j=0;jn;j+)if(i!=j)cout ij;if(Aij=INF)if(i!=j)cout不存在路径nendl;elsecout路径长度为:Aijn;cout路径为:i*;pre=pathij;while(pre!=-1)coutpren;pre=pathprej;coutjendl; /以下为选择总体最优过程，然后确址；for(i=0;in;i+)for(j=0;jn;j+)if(Aij=INF)counti=0;elsecounti=1;for(i=0;in;i+)if(cou

17、nti)for(j=0;jn;j+)if(i!=j)Aii+=Aji;k=0;for(i=0;in;i+)if(counti)if(AkkAii)k=i;cout超市的最佳地址为:vexskendl;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,1 21,2 32,3 40,3 10,2 21,3 3第

18、0个单位去超市的频率 2第1个单位去超市的频率 4第2个单位去超市的频率 3第3个单位去超市的频率 1*/7 测试结果 7.1输入 7.2输出参考文献： 1、C程序设计第三版 谭浩强 著 清华大学出版社 2、数据结构（C语言版） 严蔚敏 著 清华大学出版社 3、数据结构及应用沈华 等编著 机械工业出版社 总 结 终于完成了本次数据结构课程设计，对我来说这是一项不小的挑战，它不仅检验了我的学习情况，也考验了我的意志力，让我有了很大的收获！ 通过一学期的学习，我知道数据结构是一门纯属于设计的科目，它需用把理论变为上机调试。在学习科目的第一节课起，老师就为我们阐述了它的重要性。它对我来说具有一定的难

19、度。它是其它编程语言的一门基本学科。之前我刚学习数据结构时感觉很吃力，因为书上都只是提供一些通用的结构算法，并没有具体的题目和完整的程序来让我体会数据结构在程序中所体现的作用。 但是经过自己到图书馆借阅相应的书籍，并且在每次上机时大胆实践，我逐渐体会到数据结构是计算机科学与技术专业的一门核心专业基础课程，在我们专业的课程体系中起着承上启下的作用，学好数据结构对于提高理论认知水平和实践能力有着极为重要的作用。学习数据结构的最终目的是为了获得求解问题的能力。对于现实世界中的问题，应该能从中抽象出一个适当的数学模型，该数学模型在计算机内部用相应的数据结构来表示，然后设计一个解此数学模型的算法，再进行编程调试，最后获得问题的解答。 书本知识用于实际应用，才是我的目标，这次课程设计给了我锻炼自我突破自己的机会。 通过这次数据结构课程实践，我对数据结构这门课程有了更深的认识和体会，同时实践的成功极大增强了我对继续学习相关知识的信心和兴趣！.;