數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)學(xué)校超市選址問(wèn)題

1、WORD格式學(xué)校超市選址問(wèn)題學(xué)生*專業(yè)班級(jí)學(xué)號(hào)題目學(xué)校超市選址問(wèn)題課題性質(zhì)工程設(shè)計(jì)課題來(lái)源自選課題指導(dǎo)教師同組*無(wú)對(duì)于某一學(xué)校超市，其他各單位到其的距離不同，專業(yè)資料整理WORD格式主要內(nèi)容任務(wù)要求參考文獻(xiàn)審查意見(jiàn)同時(shí)各單位人員去超市的頻度也不同。請(qǐng)為超市選址，要*現(xiàn)總體最優(yōu)。1. 實(shí)現(xiàn)公司到超市距離，頻率最優(yōu)。2. 確定超市位置，要*現(xiàn)總體最優(yōu)。 C程序設(shè)計(jì)"第三版譚浩強(qiáng) 著 清華大學(xué)"數(shù)據(jù)構(gòu)造" C 語(yǔ)言版嚴(yán)蔚敏著清華大學(xué)"數(shù)據(jù)構(gòu)造及應(yīng)用"沈華等編著機(jī)械工業(yè)指導(dǎo)教師簽字：教研室主任簽字：專業(yè)資料整理WORD格式一、需求分析1 核心問(wèn)題 :

2、求最短路徑 ( 選址的要求就是超市到各單位權(quán)值之和最少 )2數(shù)據(jù)模型邏輯構(gòu)造 : 帶權(quán)有向圖 ( 權(quán)值計(jì)算 : 距離 * 頻度 )3存儲(chǔ)構(gòu)造 : typedef structstring vexsMAX_VERTEX_SIZE;int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE;int vexnum;/ ,arcnum;MGraph;核心算法 : Floyd算法 ( 弗洛伊德算法 - 每一對(duì)頂點(diǎn)之間的最短路徑)輸入數(shù)據(jù) :各單位名稱，距離，頻度，單位個(gè)數(shù)輸出數(shù)據(jù) :所選單位名稱總體思路 :如果超市是要選在某個(gè)單位，那么先用floyd算法得出各頂點(diǎn)間的最短距離 / 最小

3、權(quán)值。假設(shè)頂點(diǎn)個(gè)數(shù)有n 個(gè)，那么就得到n*n 的一X表格， arcs(i,j)表示 i 單位到 j單位的最短距離 / 最小權(quán)值 ,這X表格中和最小的那一行( 假設(shè)為第 t 行) ，那么超市選在 t 單位處就是最優(yōu)解。2 運(yùn)行環(huán)境Visual Stdio C+6.0Windows Vista/2003/XP3 概要設(shè)計(jì)Floyd 算法利用動(dòng)態(tài)規(guī)劃思想， 通過(guò)把問(wèn)題分解為子問(wèn)題來(lái)解決任意兩點(diǎn)見(jiàn)的最短路徑問(wèn)題。設(shè) G=(V, E, w)是一個(gè)帶權(quán)有向圖，其邊 V=v1, v2, , vn 。對(duì)于 kn，考慮其結(jié)點(diǎn) V 的一個(gè)子集。對(duì)于 V 中任何兩個(gè)結(jié)點(diǎn) vi 、vj ，考慮從vi 到 vj 的中間

4、結(jié)點(diǎn)都在 vk 中的所有路徑，設(shè)該路徑是其中最短的，并設(shè)它的路徑長(zhǎng)度為最短路徑長(zhǎng)度。如果結(jié)點(diǎn) vk 不在從 vi 到 vj 的最短路徑上，那么；反之那么可以把分為兩段，其中一段從 vi 到 vk，另一段從 vk 到 vj ，這樣便得到表專業(yè)資料整理WORD格式1專業(yè)資料整理WORD格式達(dá)式。上述討論可以歸納為如下遞歸式：原問(wèn)題轉(zhuǎn)化為對(duì)每個(gè)i 和 j 求，或者說(shuō)求矩陣流程圖開(kāi)場(chǎng)Main 輸入根本信息GreatMgraphGh 建立鄰接矩陣的存儲(chǔ)構(gòu)造Floyd 算法NYAij=INF,i!=ji 到 j 不存在路FloyedGh 輸出 i->j 的路徑和路徑長(zhǎng)度輸出超市的最正確地址：i完畢4

5、 詳細(xì)設(shè)計(jì)第一步，讓所有路徑加上中間頂點(diǎn)1，取 Aij與 Ai1+A1j中較小的值作 Aij的新值，完成后得到 A(1), 如此進(jìn)展下去， 當(dāng)?shù)?k 步完成后， A專業(yè)資料整理WORD格式2專業(yè)資料整理WORD格式 k ij表示從 i 到就且路徑上的中間頂點(diǎn)的路徑的序號(hào)小于或等于k 的最短路徑長(zhǎng)度。當(dāng)?shù)趎-1 步完成后，得到 A n-1 ，An-1 即所求結(jié)果。 An-1 ij表示從 i 到 j且路徑上的中點(diǎn)頂點(diǎn)的序號(hào)小于或等于n-1 的最短路徑長(zhǎng)度，即 A(n-1)ij表示從 i 到 j 的最短路徑長(zhǎng)度。4.1 頭文件和變量設(shè)定#include <string.h>#includ

6、e <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 32767const int MAXVEX=100;typedef char Vextype;4.2 構(gòu)造體的定義typedef structVextype vexsMAXVEXMAX

7、VEX;/單位名稱頂點(diǎn)信息；int adjMAXVEXMAXVEX;/ 單位之間的相通情況是否有邊；int disMAXVEXMAXVEX;/ 單位間距離邊的長(zhǎng)度 ；int fMAXVEX;/ 各單位去超市的頻率；專業(yè)資料整理WORD格式3專業(yè)資料整理WORD格式int n;/ 頂點(diǎn)數(shù)和邊數(shù)；int e;Mgraph;4.3 變量的輸入void CreatMgraph(Mgraph *G)int i,j,k;printf("請(qǐng)輸入單位個(gè)數(shù) :n");scanf("%d",&(G->n);printf("請(qǐng)輸入單位間的路徑數(shù) :n&

8、quot;);scanf("%d",&(G->e);printf("請(qǐng)輸入單位名稱 :n");for(i=0;i<G->n;i+)printf("請(qǐng)輸入第 %d個(gè)單位名稱 :n",i);scanf("%s",&G->vexsi);for(i=0;i<G->n;i+)/ 構(gòu)造體的初始化； for(j=0;j<G->n;j+)G->adjij=0;G->disij=0;G->fi=0;for(k=0;k<G->e;k+)pri

9、ntf("請(qǐng)輸入相通的兩單位( 輸入格式 :i,j):n");scanf("%d,%d",&i,&j);/在距離上表達(dá)為無(wú)向；專業(yè)資料整理WORD格式4專業(yè)資料整理WORD格式printf("請(qǐng)輸入一樣兩個(gè)單位間的距離( 格式： dis) ： n");scanf("%d",&(G->disij);G->adjij=1;G->adjji=1;G->disji=G->disij;for(k=0;k<G->n;k+)printf(" 請(qǐng)輸入第 %

10、d個(gè)單位去超市的相對(duì)頻率 :n",k); scanf("%d",&(G->fk);for(i=0;i<G->n;i+)/以距離和頻率之積作為權(quán)值；for(j=0;j<G->n;j+)G->disij*=G->fi;/最終權(quán)值非完全無(wú)向；if(G->adjij=0&&i!=j)G->disij=INF;4.4 帶權(quán)有向圖求最短路徑floyd算法void Floyed(Mgraph *G)/帶權(quán)有向圖求最短路徑floyd算法int AMAXVEXMAXVEX,pathMAXVEXMAXVEX

11、;int i,j,k,pre;int countMAXVEX;for(i=0;i<G->n;i+)/初始化 A和 path專業(yè)資料整理WORD格式5專業(yè)資料整理WORD格式數(shù)組for(j=0;j<G->n;j+)/置初值；Aij=G->disij;pathij=-1;counti=0;for(k=0;k<G->n;k+)/k代表運(yùn)算步驟for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij>(Aik+Akj)/從 i 經(jīng) j 到 k 的一條路徑更短Aij=Aik+Akj;pathij=k;co

12、ut<<endl<<"Floyed算法求解如下 :"<<endl;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(i!=j)cout<<" "<<i<<"->"<<j<<""if(Aij=INF)if(i!=j)cout<<" 不存在路徑 "<<"n"<<endl;專業(yè)資料整理WORD格

13、式6專業(yè)資料整理WORD格式elsecout<<" 路徑長(zhǎng)度為 :"<<Aij<<"n"cout<<" 路徑為 :"<<i<<"*"pre=pathij;while(pre!=-1)cout<<pre<<"n"pre=pathprej;cout<<j<<endl;/ 以下為選擇總體最優(yōu)過(guò)程，然后確址；for(i=0;i<G->n;i+)for(j=0;j<G-

14、>n;j+)if(Aij=INF)counti=0;elsecounti=1;for(i=0;i<G->n;i+)if(counti)for(j=0;j<G->n;j+)if(i!=j)Aii+=Aji;專業(yè)資料整理WORD格式7專業(yè)資料整理WORD格式k=0;for(i=0;i<G->n;i+)if(counti)if(Akk>Aii)k=i;cout<<" 超市的最正確地址為 :"<<G->vexsk<<endl;4.5 主函數(shù)模塊void main()Mgraph *Gh=NUL

15、L;Gh=(Mgraph *)malloc(sizeof(Mgraph);CreatMgraph(Gh);Floyed(Gh);system("pause");5 調(diào)試分析5.1 此題目的關(guān)鍵點(diǎn)之一：有兩個(gè)權(quán)值：各單位到超市的距離及各單位人去超市的頻度。這使得圖的建立出現(xiàn)了困難，經(jīng)過(guò)分析這兩個(gè)值可以合并為一個(gè)權(quán)值即distance*frequency；這樣就使得圖的建立輕而易舉。專業(yè)資料整理WORD格式8專業(yè)資料整理WORD格式5.2 此題目的關(guān)鍵點(diǎn)之二：利用 floyd算法求出每一對(duì)頂點(diǎn)之間的最短路徑。5.3 此題目的關(guān)鍵點(diǎn)之三：選出最短路徑， 即最正確地點(diǎn)應(yīng)使其到其他單

16、位權(quán)值最小。注意：每比較一次 path 應(yīng)清 0 一次 Path=0。6 設(shè)計(jì)程序如下：#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 32767const int M

17、AXVEX=100;typedef char Vextype;typedef structVextype vexsMAXVEXMAXVEX;/ 單位名稱頂點(diǎn)信息 ；int adjMAXVEXMAXVEX;/單位之間的相通情況是否有邊；int disMAXVEXMAXVEX;/單位間距離邊的長(zhǎng)度；int fMAXVEX;/各單位去超市的頻率；int n;/頂點(diǎn)數(shù)和邊數(shù)；int e;Mgraph;void CreatMgraph(Mgraph *G)int i,j,k;printf(" 請(qǐng)輸入單位個(gè)數(shù):n");scanf("%d",&(G->n

18、);printf(" 請(qǐng)輸入單位間的路徑數(shù):n");scanf("%d",&(G->e);printf(" 請(qǐng)輸入單位名稱:n");for(i=0;i<G->n;i+)專業(yè)資料整理WORD格式9專業(yè)資料整理WORD格式printf(" 請(qǐng)輸入第 %d 個(gè)單位名稱 :n",i);scanf("%s",&G->vexsi);for(i=0;i<G->n;i+)/構(gòu)造體的初始化；for(j=0;j<G->n;j+)G->adjij=

19、0;G->disij=0;G->fi=0;for(k=0;k<G->e;k+)printf(" 請(qǐng)輸入相通的兩單位(輸入格式 :i,j):n");scanf("%d,%d",&i,&j);/在距離上表達(dá)為無(wú)向；printf(" 請(qǐng)輸入一樣兩個(gè)單位間的距離(格式： dis)： n");scanf("%d",&(G->disij);G->adjij=1;G->adjji=1;G->disji=G->disij;for(k=0;k<G-&

20、gt;n;k+)printf(" 請(qǐng)輸入第 %d 個(gè)單位去超市的相對(duì)頻率:n",k);scanf("%d",&(G->fk);for(i=0;i<G->n;i+)/以距離和頻率之積作為權(quán)值；for(j=0;j<G->n;j+)G->disij*=G->fi;/ 最終權(quán)值非完全無(wú)向；if(G->adjij=0&&i!=j)G->disij=INF;void Floyed(Mgraph *G)/ 帶權(quán)有向圖求最短路徑floyd 算法int AMAXVEXMAXVEX,pathMAX

21、VEXMAXVEX;int i,j,k,pre;int countMAXVEX;for(i=0;i<G->n;i+)/初始化 A 和 path 數(shù)組for(j=0;j<G->n;j+)/置初值；Aij=G->disij;pathij=-1;專業(yè)資料整理WORD格式10專業(yè)資料整理WORD格式counti=0;for(k=0;k<G->n;k+)/k 代表運(yùn)算步驟for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(Aij>(Aik+Akj)/ 從 i 經(jīng) j 到 k 的一條路徑更短Aij=Aik+A

22、kj;pathij=k;cout<<endl<<"Floyed算法求解如下:"<<endl;for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if(i!=j)cout<<" "<<i<<"->"<<j<<""if(Aij=INF)if(i!=j)cout<<" 不存在路徑 "<<"n"<<end

23、l;elsecout<<" 路徑長(zhǎng)度為 :"<<Aij<<"n"cout<<" 路徑為 :"<<i<<"*"pre=pathij;while(pre!=-1)cout<<pre<<"n"pre=pathprej;cout<<j<<endl;/ 以下為選擇總體最優(yōu)過(guò)程，然后確址； for(i=0;i<G->n;i+)for(j=0;j<G->n;j+)if

24、(Aij=INF)counti=0;專業(yè)資料整理WORD格式11專業(yè)資料整理WORD格式elsecounti=1;for(i=0;i<G->n;i+)if(counti)for(j=0;j<G->n;j+)if(i!=j)Aii+=Aji;k=0;for(i=0;i<G->n;i+)if(counti)if(Akk>Aii)k=i;cout<<" 超市的最正確地址為:"<<G->vexsk<<endl;void main()Mgraph *Gh=NULL;Gh=(Mgraph *)malloc(sizeof(Mgraph);CreatMgraph(Gh);Floyed(Gh);system("pause");/* 測(cè)試數(shù)據(jù)：輸入：?jiǎn)挝粋€(gè)數(shù)4單位間的路徑數(shù)6第 0 個(gè)單位名稱A第 1 個(gè)單位名稱B第 2 個(gè)單位名稱C第 3 個(gè)單位名稱D相通兩單位之間的距離0,121,23專業(yè)資料整理WORD格式12專業(yè)資料整理WORD格式2,340,310,221,33第 0 個(gè)單位去超市的頻率2第 1 個(gè)單位去超市的頻率4第 2 個(gè)單位去超市的頻率3