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

计算机科学与技术专业课程设计任务书 学生姓名 专业班级 学号 题 目 学校超市选址问题对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。超市，要求实现总体最优。{ string vexs[MAX_VERTEX_SIZE]; int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE]; int vexnum;// ,arcnum; }MGraph; 核心算法: Floyd算法(弗洛伊德算法-每一对顶点之间的最短路径) 输入数据: 各单位名称，距离，频度，单位个数． 输出数据: 所选单位名称． 总体思路:　如果超市是要选在某个单位，那么先用floyd算法得出各顶点间的最短距离/最小权值。 假设顶点个数有n个，那么就得到n*n的一张表格，arcs(i,j)表示i单位到j单位的最短距离/最小权值 , 这张表格中和最小的那一行(假设为第t行)，那么超市选在t单位处就是最优解。 2 运行环境 Visual Stdio C++6.0 Windows Vista/2003/XP 3 概要设计 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，这样便得到表达式。上述讨论可以归纳为如下递归式： 原问题转化为对每个i和j求，或者说求矩阵 流程图 4 详细设计 #include string.h #include stdio.h #include stdlib.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 32767 const int MAXVEX=100; typedef char Vextype; 4.2结构体的定义 typedef struct { Vextype vexs[MAXVEX][MAXVEX]; //单位名称（顶点信息）； int adj[MAXVEX][MAXVEX]; //单位之间的相通情况（是否有边）； int dis[MAXVEX][MAXVEX]; //单位间距离（边的长度）； int f[MAXVEX]; //各单位去超市的频率； 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;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);//在距离上体现为无向； printf(请输入相同两个单位间的距离(格式：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++) //以距离和频率之