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

《数据结构课程设计---学校超市选址问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机科学与技术专业课程设计任务书学生姓名专业班级学号题目学校超市选址问题课题性质工程设计课题来源自拟课题指导教师同组姓名无主要内容对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。任务要求1.实现公司到超市距离，频率最优。2.确定超市位置，要求实现总体最优。参考文献《C程序设计》第三版谭浩强著清华大学出版社《数据结构》（C语言版）严蔚敏著清华大学出版社《数据结构与算法》赵文静祁飞等编著科学出版社审查意见指导教师签字：教研室主任签字：1需求

2、分析核心问题:求最短路径(选址的要求就是超市到各单位权值之和最少)数据模型（逻辑结构）:带权有向图(权值计算:距离*频度)存储结构:typedefstruct{stringvexs[MAX_VERTEX_SIZE];intarcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];intvexnum;//,arcnum;}MGraph;核心算法:Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径)输入数据:各单位名称，距离，频度，单位个数．输出数据:所选单位名称．总体思路:　如

3、果超市是要选在某个单位，那么先用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,…,

4、vn}。对于k≤16n，考虑其结点V的一个子集。对于V中任何两个结点vi、vj，考虑从vi到vj的中间结点都在vk中的所有路径，设是其中最短的，并设的路径长度为。如果结点vk不在从vi到vj的最短路径上，则；反之则可以把分为两段，其中一段从vi到vk，另一段从vk到vj，这样便得到表达式。上述讨论可以归纳为如下递归式：原问题转化为对每个i和j求，或者说求矩阵开始流程图Main（）输入基本信息GreatMgraph（Gh）建立邻接矩阵的存储结构Floyd算法NYA[i][j]==INF,i!=ji到j

5、不存在路径Floyed（Gh）输出i->j的路径和路径长度输出超市的最佳地址：i结束4详细设计16第一步，让所有路径加上中间顶点1，取A[i][j]与A[i][1]+A[1][j]中较小的值作A[i][j]的新值，完成后得到A(1),如此进行下去，当第k步完成后，A（k）[i][j]表示从i到就且路径上的中间顶点的路径的序号小于或等于k的最短路径长度。当第n-1步完成后，得到A（n-1），A（n-1）即所求结果。A（n-1）[i][j]表示从i到j且路径上的中点顶点的序号小于或等于n-1的最短路径长

6、度，即A(n-1)[i][j]表示从i到j的最短路径长度。4.1头文件和变量设定#include#include#include#include#include"malloc.h"#include#defineTURE1#defineFALSE0#defineOK1#defineERROR0#defineOVERFLOW-1#defineINF32767constintMAXVEX=100;typede

7、fcharVextype;4.2结构体的定义typedefstruct{Vextypevexs[MAXVEX][MAXVEX];//单位名称（顶点信息）；intadj[MAXVEX][MAXVEX];//单位之间的相通情况（是否有边）；intdis[MAXVEX][MAXVEX];//单位间距离（边的长度）；intf[MAXVEX];//各单位去超市的频率；16intn;//顶点数和边数；inte;}Mgraph;4.3变量的输入voidCreatMgraph(Mgraph*G){inti,j,k;

8、printf("请输入单位个数:");scanf("%d",&(G->n));printf("请输入单位间的路径数:");scanf("%d",&(G->e));printf("请输入单位名称:");for(i=0;in;i++){printf("请输入第%d个单位名称:",i);scanf("%s",&G->vexs[i]);}for(i=0;in;i++)//结构体的初始化；for(j=0;jn;j++){G->adj[i]