數(shù)據(jù)結(jié)構(gòu)課程設(shè)計-超市選址問題

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

數(shù)據(jù)結(jié)構(gòu)

課程設(shè)計報告

設(shè)計題目：學(xué)校超市選址問題

專業(yè)計算機(jī)科學(xué)與技術(shù)

班級

學(xué)生

學(xué)號

聯(lián)系方式

年學(xué)期

1

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

問題描述

對于某一學(xué)校超市，其他各單位到其的距離不同，同時各單位人員去超市的頻度也不同。請

為超市選址，要求實現(xiàn)總體最優(yōu)。

1、需求分析

核心問題：求最短路徑（選址的要求就是超市到各單位權(quán)值之和至少）

數(shù)據(jù)模型（邏輯結(jié)構(gòu)）：帶權(quán)有向圖（權(quán)值計算：距離*頻度）

存儲結(jié)構(gòu)：typedefstruct

（

stringvexs[MAX_VERTEX_SIZE];

intarcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];

intvexnum;//,arcnum;

}MGraph;

核心算法：Floyd算法（弗洛伊德算法-每一對頂點之間的最短路徑）

輸入數(shù)據(jù)：各單位名稱，距離，頻度，單位個數(shù).

輸出數(shù)據(jù)：所選單位名稱.

總體思路：如果超市是要選在某個單位，那末先用floyd算法得出各頂點間的最短距

離/最小權(quán)值。

假設(shè)頂點個數(shù)有n個，那末就得到n*n的一張表格，arcs（i,j）表示i單位到j(luò)單位的最短

距離/最小權(quán)值，這張表格中和最小的那一行（假設(shè)為第t行），那末超市選在t單位處就

是最優(yōu)解。

運行環(huán)境

DEV-C++

2、概要設(shè)計

Floyd算法利用動態(tài)規(guī)劃思想，通過把問題分解為子問題來解決任意兩點見的最短路徑問

題。設(shè)G=（V,E,w）是一個帶權(quán)有向圖，其邊V={vl,v2,…，vn}。對于k〈n,考慮其結(jié)

點V的一個子集。對于V中任何兩個結(jié)點vi、vj,考慮從vi到vj的中間結(jié)點都在vk中的

所有路徑，設(shè)是其中最短的，并設(shè)的路徑長度為。如果結(jié)點vk不在從vi到vj的最短路徑

上，則；反之則可以把分為兩段，其中一段從vi到vk,另一段從vk到vj,這樣便得到表

達(dá)式。上述討論可以歸納為如下遞歸式：

原問題轉(zhuǎn)化為對每一個i和j求，或者說求矩陣

2

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

流程圖

第一步，讓所有路徑加之中間頂點1,取與中較小的值作

的新值，完成后得到A(1),如此進(jìn)行下去，當(dāng)?shù)趉步完成后，A(k)表示從i到就且

路徑上的中間頂點的路徑的序號小于或者等于k的最短路徑長度。當(dāng)?shù)趎-1步完成后，得到

A(n-1),A(n-1)即所求結(jié)果。A(n-1)表示從i到j(luò)且路徑上的中點頂點的序號

小于或者等于n-1的最短路徑長度，即表示從i到j(luò)的最短路徑長度。

代碼表示如下：

voidFloyed(Mgraph*G)〃帶權(quán)有向圖求最短路徑floyd算法

3

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

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

inti,j,k,pre;

intcount[MAXVEX];

for(i=0;i<G->n;i++)//初始化A叩和path加數(shù)組

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īng)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;

)

)

)

〃以下為選擇總體最優(yōu)過程，然后確址；

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

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

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、調(diào)試分析

測試數(shù)據(jù)：

輸入：

單位個數(shù)

4

單位間的路徑數(shù)

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

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

輸出：相通兩單位之間的路徑和他的長度

結(jié)果：

S3D:\李凌鋒-O8O30D8094-踩程設(shè)一.._□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

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

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;〃頂點數(shù)和邊數(shù)；

inte;

JMgraph;

voidCreatMgraph(Mgraph*G)

(

int

請輸入單位個數(shù)

請輸入單位間的路徑數(shù)

請輸入單位名稱

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

(

請輸入第%(1個單位名稱

for(i=0;i<G->n;i++)〃結(jié)構(gòu)體的初始化;

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++)

(

請輸入相通的兩單位(輸入格式

在距離上體現(xiàn)為無向；

請輸入相同兩個單位間的距離(格式：dis)：

7

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

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++)〃以距離和頻率之積作為權(quán)值;

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

(

G->dis[i][j]*=G->f[i];//最終權(quán)值非徹底無向；

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

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

)

)

voidFloyed(Mgraph*G)〃帶權(quán)有向圖求最短路徑floyd算法

(

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

inti,j,k,pre;

intcount[MAXVEX];

for(i=0;i<G->n;i++)//初始化A叩和path加數(shù)組

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īng)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

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計

if(i!=j)

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

(

if(i!=j)

不存在路徑

)

else

(

路徑長度為

路徑為

pre=path[i][j];