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

数据结构 课程设计报告

设计题目：学校超市选址问题

专 业 计算机科学与技术

班 级 10计本2班

学 生 朱冬

学 号 ********

联系方式 180****0381

年 学期

1

《数据结构》课程设计

问题描述

对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请为超市选址，要求实现总体最优。

1、需求分析

核心问题: 求最短路径(选址的要求就是超市到各单位权值之和最少) 数据模型（逻辑结构）: 带权有向图 (权值计算: 距离*频度) 存储结构: typedef struct {

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单位处就是最优解。

运行环境 DEV-C++ 2、概要设计

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求，或者说求矩阵

2

《数据结构》课程设计

流程图

3、详细设置

i到j不存在路Y 开始 Main（） 输入基本信息 GreatMgraph（Gh） 建立邻接矩阵的存储结构 Floyd算法 N A[i][j]==INF,i!=j Floyed（Gh） 输出i->j的路径和路径长度 输出超市的最佳地址：i 结束 第一步，让所有路径加上中间顶点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的最短路径长度，即A(n-1)[i][j]表示从i到j的最短路径长度。

代码表示如下：

void Floyed(Mgraph *G) //带权有向图求最短路径floyd算法

{

3

《数据结构》课程设计

int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX]; int i,j,k,pre; int count[MAXVEX]; for(i=0;in;i++) //初始化A[][]和path[][]数组 for(j=0;jn;j++) //置初值； { A[i][j]=G->dis[i][j]; path[i][j]=-1; count[i]=0; } for(k=0;kn;k++) //k代表运算步骤 { for(i=0;in;i++) for(j=0;jn;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; } } cout<n;i++) for(j=0;jn;j++) { if(i!=j) { cout<<\" \"<\"<//以下为选择总体最优过程，然后确址； for(i=0;in;i++) for(j=0;jn;j++) { if(A[i][j]==INF) count[i]=0; else count[i]=1; } for(i=0;in;i++)

4

《数据结构》课程设计

if(count[i]) { for(j=0;jn;j++) if(i!=j)A[i][i]+=A[j][i]; } k=0; for(i=0;in;i++) { if(count[i]) if(A[k][k]>A[i][i]) k=i; } cout<<\"超市的最佳地址为:\"<vexs[k]<4、调试分析

测试数据：

输入： 单位个数 4

单位间的路径数 6

第0个单位名称 a

第1个单位名称 b

第2个单位名称 c

第3个单位名称 d

相通两单位 之间的距离 0,1 3 1,2 2 2,3 2 0,3 3 0,2 4 1,3 1

第0个单位去超市的频率 1 第1个单位去超市的频率 2 第2个单位去超市的频率 4 第3个单位去超市的频率 3

5

《数据结构》课程设计

输出：相通两单位之间的路径和他的长度 结果：

附加程序

#include #include #include #include #include \"malloc.h\"

6

《数据结构》课程设计

#include #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; 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\ printf(\"请输入单位间的路径数:\\n\"); scanf(\"%d\ printf(\"请输入单位名称:\\n\"); for(i=0;in;i++) { printf(\"请输入第%d个单位名称:\\n\ scanf(\"%s\ } for(i=0;in;i++) //结构体的初始化； for(j=0;jn;j++) { G->adj[i][j]=0; G->dis[i][j]=0; G->f[i]=0; } for(k=0;ke;k++) { printf(\"请输入相通的两单位 (输入格式:i,j):\\n\"); scanf(\"%d,%d\在距离上体现为无向； printf(\"请输入相同两个单位间的距离(格式：dis)：\\n\"); scanf(\"%d\

7

《数据结构》课程设计

G->adj[i][j]=1; G->adj[j][i]=1; G->dis[j][i]=G->dis[i][j]; } for(k=0;kn;k++) { printf(\"请输入第%d个单位去超市的相对频率:\\n\ scanf(\"%d\ } for(i=0;in;i++) //以距离和频率之积作为权值； for(j=0;jn;j++) { G->dis[i][j]*=G->f[i]; //最终权值非完全无向； if(G->adj[i][j]==0&&i!=j) G->dis[i][j]=INF; } }

void Floyed(Mgraph *G) //带权有向图求最短路径floyd算法 { int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX]; int i,j,k,pre; int count[MAXVEX]; for(i=0;in;i++) //初始化A[][]和path[][]数组 for(j=0;jn;j++) //置初值； { A[i][j]=G->dis[i][j]; path[i][j]=-1; count[i]=0; } for(k=0;kn;k++) //k代表运算步骤 { for(i=0;in;i++) for(j=0;jn;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; } } cout<n;i++) for(j=0;jn;j++) {

8

《数据结构》课程设计

if(i!=j) { cout<<\" \"<\"<//以下为选择总体最优过程，然后确址； for(i=0;in;i++) for(j=0;jn;j++) { if(A[i][j]==INF) count[i]=0; else count[i]=1; } for(i=0;in;i++) if(count[i]) { for(j=0;jn;j++) if(i!=j)A[i][i]+=A[j][i]; } k=0; for(i=0;in;i++) { if(count[i]) if(A[k][k]>A[i][i])

9

《数据结构》课程设计

k=i; } cout<<\"超市的最佳地址为:\"<vexs[k]<int main() { Mgraph *Gh=NULL; Gh=(Mgraph *)malloc(sizeof(Mgraph)); CreatMgraph(Gh); Floyed(Gh); system(\"pause\"); }

10