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

学校超市选址问题

学生姓名专业班级学号

题目学校超市选址问题

课题性质工程设计课题来源自选课题

指导教师同组姓名无

对于某一学校超市，其他各单位到其的距离不同，

主要内容同时各单位人员去超市的频度也不同。

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

1.实现公司到超市距离，频率最优。

任务要求

2.确定超市位置，要求实现总体最优。

《C程序设计》第三版谭浩强著清华大学出版社

参考文献《数据结构》（C语言版）严蔚敏著清华大学出版社

《数据结构及应用》沈华等编著机械工业出版社

指导教师签字：

审查意见

教研室主任签字：

一、需求分析

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

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

3）存储结构：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单位处就是最优解。

2运行环境

VisualStdioC++6.0

WindowsVista/2003/XP

3概要设计

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

的最短路径问题。设G=(V,E,w)是一个带权有向图，其边V={vl,v2,…,vn}。

对于kWn,考虑其结点V的一个子集。对于V中任何两个结点vi、vj,考虑从vi

到Vj的中间结点都在vk中的所有路径，设该路径是其中最短的，并设它的路径长

度为最短路径长度。如果结点vk不在从vi到Vj的最短路径上，则；反之则可以

把分为两段，其中一段从Vi到vk,另一段从vk到vj,这样便得到表达式。上述

讨论可以归纳为如下递归式：

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

开始

流程图

Main()

/输入基本信息/

GreatMgraph(Gh)

------►

建立邻接矩阵的存储结构

Floyd算法

N

A[i][j]==INF,i!=j

i到j不存在路

Floyed(Gh)

4详细设计

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

的值作的新值，完成后得到A(l),如此进行下去，当第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(nT)[i][j]表示从i到j的最短路径长度。

4.1头文件和变量设定

ttinclude<string.h>

#include<stdio.h>

ttinclude<stdlib.h>

ttinclude<time.h>

ttincludemalloc.h

ttinclude<iostream.h>

ttdefineTURE1

ttdefineFALSE0

ttdefineOK1

ttdefineERROR0

ttdefineOVERFLOW-1

ttdefineINF32767

constintMAXVEX=100;

typedefcharVextype;

4.2结构体的定义

typedefstruct

(

Vextypevexs[MAXVEX][MAXVEX];〃单位名称（顶点信

息)；

intadj[MAXVEX][MAXVEX];〃单位之间的相通情

况(是否有边)；

intdis[MAXVEX][MAXVEX];〃单位间距离（边的

长度)；

intf[MAXVEX];〃各单位去

超市的频率；

intn;〃顶点

数和边数；

inte;

}Mgraph;

4.3变量的输入

voidCreatMgraph(Mgraph*G)

inti,j,k;

printf(”请输入单位个数:\n");

scanf&(G->n));

printf(”请输入单位间的路径数:\n");

scanf&(G->e));

printf(”请输入单位名称：\n");

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

{

printf("请输入第%d个单位名称：\n",i);

scanf("%s”,&G->vexs[i]);

)

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

的初始化；

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

(

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

G->disEi][j]=0;

G->f[i]=O;

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

(

printf("请输入相通的两单位(输入格式:i,j):\n");

scanf(/z%d,%d",&i,&j);〃在距离上体现为无向；

printf("请输入相同两个单位间的距离(格式：dis)：\n");

scanf("%d”,&(G->dis[i][j]));

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

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

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

)

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

(

printf("请输入第%d个单位去超市的相对频率:\n”,k);

scanf&(G->f[k]));

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

离和频率之积作为权值；

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

(

G->disEi][j]*=G->fEi];〃最终权值非完全无向;

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

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

)

)

4.4带权有向图求最短路径floyd算法

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□□数组

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

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

path[i][j]=-l;

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[iHj]>(A[i][k]+A[k][j]))〃从i经j到k的一条路径更短

A[i][j]=A[i][k]+A[k][j];

path[i][j]=k;

cout«endl«/zFloyed算法求解如下："〈〈endl;

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

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

{

if(i!=j)

{

cout<<"

if(A[iHj]==INF)

(

if(i!=j)

cout«”不存在路径;

)

else

(

cout«”路径长度为:“<<A[i][j"<"\n";

cout<<“路径为：

pre=path[i][j];

while(pre!=-l)

cout«pre<<//\n//;

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

countEi]=l;

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

if(count[ij)

{

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

if(i!=j)A[i][i]+=A[j][i];

)

k=0;

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

(

if(count[ij)

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

k=i;

)

cout(<”超市的最佳地址为:z/<<G->vexs[k]<<endl;

4.5主函数模块

voidmain()

Mgraph*Gh=NULL;

Gh=(Mgraph*)malloc(sizeof(Mgraph));

CreatMgraph(Gh);

Floyed(Gh);

system("pause");

)

5调试分析

5.1本题目的关键点之一：

有两个权值：各单位到超市的距离及各单位人去超市的频度。这使得图的建

立出现了困