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

《数据结构》课程设计

数据结构

课程设计报告

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

专业计算机科学与技术

班级

学生

学号

联系方式

年学期

1

《数据结构》课程设计

问题描述

对于某一学校超市，其他各单位到其的距离不同，同时各单位人员去超市的频度也不同。请

为超市选址，要求实现总体最优。

1、需求分析

核心问题：求最短路径（选址的要求就是超市到各单位权值之和至少）

数据模型（逻辑结构）：带权有向图（权值计算：距离*频度）

存储结构：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单位处就

是最优解。

运行环境

DEV-C++

2、概要设计

Floyd算法利用动态规划思想，通过把问题分解为子问题来解决任意两点见的最短路径问

题。设G=（V,E,w）是一个带权有向图，其边V={vl,v2,…，vn}。对于k〈n,考虑其结

点V的一个子集。对于V中任何两个结点vi、vj,考虑从vi到vj的中间结点都在vk中的

所有路径，设是其中最短的，并设的路径长度为。如果结点vk不在从vi到vj的最短路径

上，则；反之则可以把分为两段，其中一段从vi到vk,另一段从vk到vj,这样便得到表

达式。上述讨论可以归纳为如下递归式：

原问题转化为对每一个i和j求，或者说求矩阵

2

《数据结构》课程设计

流程图

第一步，让所有路径加之中间顶点1,取与中较小的值作

的新值，完成后得到A(1),如此进行下去，当第k步完成后，A(k)表示从i到就且

路径上的中间顶点的路径的序号小于或者等于k的最短路径长度。当第n-1步完成后，得到

A(n-1),A(n-1)即所求结果。A(n-1)表示从i到j且路径上的中点顶点的序号

小于或者等于n-1的最短路径长度，即表示从i到j的最短路径长度。

代码表示如下：

voidFloyed(Mgraph*G)〃带权有向图求最短路径floyd算法

3

《数据结构》课程设计

intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];

inti,j,k,pre;

intcount[MAXVEX];

for(i=0;i<G->n;i++)//初始化A叩和path加数组

for(j=0;j<G->n;j++)〃置初值；

(

A[i][j]=G->dis[i][j];

path[i]0]=-1;

count[i]=0;

)

for(k=0;k<G->n;k++)//k代表运算步骤

(

for(i=0;i<G->n;i++)

for(j=0;j<G->n;j++)

if(A[i]O]>(A[i][k]+A[k][j]))//从i经j到k的一条路径更短

A[i][j]=A[i][k]+A[k]O]；

path[i]0]=k;

)

算法求解如下

for(i=0;i<G->n;i++)

for(j=0;j<G->n;j++)

(

if(㈣)

if(A[i][j]==INF)

(

if(i!=j)

不存在路径

}

else

(

路径长度为

路径为

pre=path[i][j]；

while(pre!=-1)

(

pre=path[pre][j];

)

cout«j«endl;

)

)

)

〃以下为选择总体最优过程，然后确址；

for(i=0;i<G->n;i++)

for(j=0;j<G->n;j++)

(

if(A[i][j]==INF)

count[i]=0;

else

count[i]=1;

)

for(i=0;i<G->n;i++)

4

《数据结构》课程设计

if(count[i])

for(j=0;j<G->n;j++)

if(i!=j)A[i][i]+=AO][i]；

k=0;

for(i=0;i<G->n;i++)

if(count[i])

if(A[k][k]>A[i][i])

k=i;

)

超市的最佳地址为

)

4、调试分析

测试数据：

输入：

单位个数

4

单位间的路径数

6

第0个单位名称

a

第1个单位名称

b

第2个单位名称

c

第3个单位名称

d

相通两单位之间的距离

0,13

1,22

2,32

0,33

0,24

1,31

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

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

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

第3个单位去超市的频率3

5

《数据结构》课程设计

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

结果：

S3D:\李凌锋-O8O30D8094-踩程设一.._□X

请输入第1个单位去超市的相对频率:

请输入第2个单位去超市的相对频率:

请输入第3个单位去超市的相对频率:

loyed算法聿解如下:

0-〉1：照径长度为：3

路径为：0”

。-〉2：路径长度为:4

路径为：。*2

。-〉3：路径长度为：3

路径为：0*3

1-?。：路径长度为：6

路径为：1*«

1-〉2；路径长度为:4

路径为：1*2

1-〉3：路径长度为：2

路径为：1*3

2-）。：路径长度为：14

路径为：2*1

21

->为

cQS径

2

S

->

径

»3衿

3:2路

Sg长厮

度

3-«卡

僮

-):3路

径-t

Xl

”

度

«卡

-tl«1径

3->2路

径

为

址

S地

的

:3蜜»2

坦9

电

她

->任

径

l才

币

拂

附加程序

#include<string.h>

#include<stdio.h>

#include<stdlib.h>

include<time.h>

6

《数据结构》课程设计

include<iostream.h>

#defineTURE1

#defineFALSE0

#defineOK1

#defineERROR0

#defineOVERFLOW-1

#defineINF32767

constintMAXVEX=100;

typedefcharVextype;

typedefstruct

Vextypevexs[MAXVEX][MAXVEX];〃单位名称(顶点信息)；

intadj[MAXVEX][MAXVEX];〃单位之间的相通情况(是否有边);

intdis[MAXVEX][MAXVEX];〃单位间距离(边的长度)；

intf[MAXVEX];〃各单位去超市的频率；

intn;〃顶点数和边数；

inte;

JMgraph;

voidCreatMgraph(Mgraph*G)

(

int

请输入单位个数

请输入单位间的路径数

请输入单位名称

for(i=0;i<G->n;i++)

(

请输入第%(1个单位名称

for(i=0;i<G->n;i++)〃结构体的初始化;

for(j=0;j<G->n;j++)

(

G->adj[i]0]=O;

G->dis[i][j]=O;

G->f[i]=O;

)

for(k=0;k<G->e;k++)

(

请输入相通的两单位(输入格式

在距离上体现为无向；

请输入相同两个单位间的距离(格式：dis)：

7

《数据结构》课程设计

G->adj[i]U]=1；

G->adj[j][i]=1;

G->dis[j][i]=G->dis[i][j];

for(k=0;k<G->n;k++)

(

请输入第％d个单位去超市的相对频率

)

for(i=0;i<G->n;i++)〃以距离和频率之积作为权值;

for(j=0;j<G->n;j++)

(

G->dis[i][j]*=G->f[i];//最终权值非彻底无向；

if(G->adj[i][j]==O&&i!=j)

G->dis[i][j]=INF;

)

)

voidFloyed(Mgraph*G)〃带权有向图求最短路径floyd算法

(

intA[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];

inti,j,k,pre;

intcount[MAXVEX];

for(i=0;i<G->n;i++)//初始化A叩和path加数组

for0=O;j<G->n;j++)//置初值；

(

A[i][j]=G->dis[i][j];

path[i][j]=-1；

count[i]=0;

)

for(k=0;k<G->n;k++)//k代表运算步骤

(

for(i=0;i<G->n;i++)

for(j=0;j<G->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;

)

)

算法求解如下

for(i=0;i<G->n;i++)

for(j=0;j<G->n;j++)

8

《数据结构》课程设计

if(i!=j)

if(A[i][j]==INF)

(

if(i!=j)

不存在路径

)

else

(

路径长度为

路径为

pre=path[i][j];