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

上傳人：奔*** IP屬地：河北更新時間：2024-03-01 格式：doc 頁數(shù)：17 大小：122.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計---學(xué)校超市選址問題_第1頁

已閱讀1頁，還剩16頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　計算機科學(xué)與技術(shù)專業(yè)課程設(shè)計任務(wù)書　學(xué)生姓名專業(yè)班級學(xué)號　題目學(xué)校超市選址問題　課題性質(zhì)工程設(shè)計課題來源自擬課題　指導(dǎo)教師同組姓名無　主要內(nèi)容對于某一學(xué)校超市，其他各單位到其的距離不同，同時各單位人員去超

2、市的頻度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。　任務(wù)要求1.實現(xiàn)公司到超市距離，頻率最優(yōu)。2. 確定超市位置，要求實現(xiàn)總體最優(yōu)。　參考文獻《C程序設(shè)計》第三版譚浩強著清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)》（C語言版）嚴(yán)蔚敏著清華大學(xué)出版社《數(shù)據(jù)結(jié)構(gòu)與算法》趙文靜祁飛等編著科學(xué)出版社　審查意見指導(dǎo)教

3、師簽字：教研室主任簽字： 　　1 需求分析　　核心問題: 求最短路徑(選址的要求就是超市到各單位權(quán)值之和最少)　　數(shù)據(jù)模型（邏輯結(jié)構(gòu)）: 帶權(quán)有向圖 (權(quán)值計算: 距離*頻度)<p&g

4、t;　　存儲結(jié)構(gòu): typedef struct　　{　　string vexs[MAX_VERTEX_SIZE];　　int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];　　int vexnum;/

5、/ ,arcnum;　　}MGraph; 　　核心算法: Floyd算法(弗洛伊德算法-每一對頂點之間的最短路徑) 　　輸入數(shù)據(jù): 各單位名稱，距離，頻度，單位個數(shù)．　　輸出數(shù)據(jù): 所選單位名稱．<

6、p>　　總體思路:　如果超市是要選在某個單位，那么先用floyd算法得出各頂點間的最短距離/最小權(quán)值。 　　假設(shè)頂點個數(shù)有n個，那么就得到n*n的一張表格，arcs(i,j)表示i單位到j(luò)單位的最短距離/最小權(quán)值 , 這張表格中和最小的那一行(假設(shè)為第t行)，那么超市選在t單位處就是最優(yōu)解。　　2 運行環(huán)境&

7、lt;/p>　　Visual Stdio C++6.0　　Windows Vista/2003/XP　　3 概要設(shè)計　　Floyd算法利用動態(tài)規(guī)劃思想，通過把問題分解為子問題來解決任意兩點見的最短路徑問題。設(shè)G=(V, E, w)是一個帶權(quán)有向圖

8、，其邊V={v1, v2, …, vn}。對于k≤n，考慮其結(jié)點V的一個子集。對于V中任何兩個結(jié)點vi、vj，考慮從vi到vj的中間結(jié)點都在vk中的所有路徑，設(shè)是其中最短的，并設(shè)的路徑長度為。如果結(jié)點vk不在從vi到vj的最短路徑上，則；反之則可以把分為兩段，其中一段從vi到vk，另一段從vk到vj，這樣便得到表達式。上述討論可以歸納為如下遞歸式：　　原問題轉(zhuǎn)化為對每個i和j求，或者說求矩陣&l

9、t;/p>　　流程圖　　4 詳細設(shè)計　　第一步，讓所有路徑加上中間頂點1，取A[i][j]與A[i][1]+A[1][j]中較小的值作A[i][j]的新值，完成后得到A(1),如此進行下去，當(dāng)?shù)趉步完成后，A（k）[i][j]表示從i到就且路徑上的中間

10、頂點的路徑的序號小于或等于k的最短路徑長度。當(dāng)?shù)趎-1步完成后，得到A（n-1），A（n-1）即所求結(jié)果。A（n-1）[i][j]表示從i到j(luò)且路徑上的中點頂點的序號小于或等于n-1的最短路徑長度，即A(n-1)[i][j]表示從i到j(luò)的最短路徑長度。　　4.1頭文件和變量設(shè)定 　　#include <string.h>

11、;　　#include <stdio.h>　　#include <stdlib.h>　　#include <time.h>　　#include "malloc.h"　　#include <

12、iostream.h>　　#define TURE 1　　#define FALSE 0　　#define OK 1　　#define ERROR 0　　#define OVERFLOW -1<

13、p>　　#define INF 32767　　const int MAXVEX=100;　　typedef char Vextype;　　4.2結(jié)構(gòu)體的定義　　typedef struct

14、;　　{　　Vextype vexs[MAXVEX][MAXVEX]; //單位名稱（頂點信息）；　　int adj[MAXVEX][MAXVEX];//單位之間的相通情況（是否有邊）；　　int dis[MAXVEX][MAXVEX];/

15、/單位間距離（邊的長度）；　　int f[MAXVEX];//各單位去超市的頻率；　　int n;//頂點數(shù)和邊數(shù)；　　int e;　　}Mgraph;</p

16、>　　4.3變量的輸入　　void CreatMgraph(Mgraph *G) 　　{　　int i,j,k;　　printf("請輸入單位個數(shù):\n

17、");　　scanf("%d",&(G->n));　　printf("請輸入單位間的路徑數(shù):\n");　　scanf("%d",&(G->e));　　printf("

18、;請輸入單位名稱:\n");　　for(i=0;i<G->n;i++)　　{　　printf("請輸入第%d個單位名稱:\n",i);　　scanf("%s",&

19、G->vexs[i]);　　}　　for(i=0;i<G->n;i++) //結(jié)構(gòu)體的初始化；　　for(j=0;j<G->n;j++)　　{</

20、p>　　G->adj[i][j]=0;　　G->dis[i][j]=0;　　G->f[i]=0;　　}　　for(k=0;k<G->e;k++)<

21、p>　　{　　printf("請輸入相通的兩單位 (輸入格式:i,j):\n");　　scanf("%d,%d",&i,&j);//在距離上體現(xiàn)為無向；　　printf("請輸入相同兩個單位間的距離(格

22、式：dis)：\n");　　scanf("%d",&(G->dis[i][j]));　　G->adj[i][j]=1;　　G->adj[j][i]=1;　　G->dis[j][i]=G->dis[i][j

23、];　　}　　for(k=0;k<G->n;k++)　　{　　printf("請輸入第%d個單位去超市的相對頻率:\n",k);<p&

24、gt;　　scanf("%d",&(G->f[k]));　　}　　for(i=0;i<G->n;i++) //以距離和頻率之積作為權(quán)值；　　for(j=0;j<G->n;j++)

25、　　{　　G->dis[i][j]*=G->f[i]; //最終權(quán)值非完全無向； 　　if(G->adj[i][j]==0&&i!=j)　　G->dis[i][j]=INF;</p&

26、gt;　　}　　}　　4.4帶權(quán)有向圖求最短路徑floyd算法　　void Floyed(Mgraph *G) //帶權(quán)有向圖求最短路徑floyd算法

27、　　{　　int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];　　int i,j,k,pre;　　int count[MAXVEX];　　for(i=0;i<G->n;i++)

28、 //初始化A[][]和path[][]數(shù)組　　for(j=0;j<G->n;j++) //置初值；　　{　　A[i][j]=G->dis[i][j];<p

29、>　　path[i][j]=-1;　　count[i]=0;　　}　　for(k=0;k<G->n;k++) //k代表運算步驟　　{

30、　　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的一條路徑更短　　{<

31、;p>　　A[i][j]=A[i][k]+A[k][j];　　path[i][j]=k;　　}　　}　　cout<<endl<<"Floyed算法求解如下:

32、"<<endl;　　for(i=0;i<G->n;i++)　　for(j=0;j<G->n;j++)　　{　　if(i!=j)

33、　　{　　cout<<" "<<i<<"->"<<j<<";";　　if(A[i][j]==INF)　　{<

34、/b>　　if(i!=j)　　cout<<"不存在路徑"<<"\n"<<endl;　　}　　el

35、se　　{　　cout<<"路徑長度為:"<<A[i][j]<<"\n";　　cout<<"路徑為:"<<i<<"

36、*";　　pre=path[i][j];　　while(pre!=-1)　　{　　cout<<pre<<"\n";　　pre=path[p

37、re][j];　　}　　cout<<j<<endl;　　}　　}　　}&l

38、t;/b>　　//以下為選擇總體最優(yōu)過程，然后確址；　　for(i=0;i<G->n;i++)　　for(j=0;j<G->n;j++)　　{　　if(A[i][

39、j]==INF)　　count[i]=0;　　else　　count[i]=1;　　}　　for(i=0;i<G->n;i++)</p&

40、gt;　　if(count[i])　　{　　for(j=0;j<G->n;j++)　　if(i!=j)A[i][i]+=A[j][i];　　}

41、　　k=0;　　for(i=0;i<G->n;i++)　　{　　if(count[i])　　if(A[k][k]>A[i][i])&

42、lt;p>　　k=i;　　}　　cout<<"超市的最佳地址為:"<<G->vexs[k]<<endl;　　}

43、　　4.5主函數(shù)模塊　　void main()　　{　　Mgraph *Gh=NULL;　　Gh=(Mgraph *)malloc(sizeof(Mgraph));</p

44、>　　CreatMgraph(Gh);　　Floyed(Gh);　　system("pause");　　}　　5 調(diào)試分析&

45、lt;p>　　5.1本題目的關(guān)鍵點之一：　　有兩個權(quán)值：各單位到超市的距離及各單位人去超市的頻度。這使得圖的建立出現(xiàn)了困難，經(jīng)過分析這兩個值可以合并為一個權(quán)值即distance*frequency；這樣就使得圖的建立輕而易舉。　　5.2本題目的關(guān)鍵點之二：　　利用floyd算法求出每一對頂點之間的最短路徑。

46、　　5.3本題目的關(guān)鍵點之三：　　選出最短路徑，即最佳地點應(yīng)使其到其他單位權(quán)值最小。注意：每比較一次path應(yīng)清0一次（Path=0）。　　6 測試結(jié)果　　6.1輸入<

47、;p>　　6.2輸出　　參考文獻：　　1、《C程序設(shè)計》第三版譚浩強著清華大學(xué)出版社　　2、《數(shù)據(jù)結(jié)構(gòu)》（C語言版）嚴(yán)蔚敏著清華大學(xué)出版社　　3、《數(shù)據(jù)結(jié)構(gòu)與算法》趙文

48、靜祁飛等編著科學(xué)出版社　　總結(jié)　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計完成了，對我來說這是一項小小的挑戰(zhàn)，它不僅檢驗了我的學(xué)習(xí)情況，也考驗了我的意志力，收獲非頗豐！　　通過一學(xué)期的學(xué)習(xí)，我知道數(shù)據(jù)結(jié)構(gòu)是一門理論性強、思維抽象、難度較大的課程，是基礎(chǔ)課和專業(yè)課之間的橋梁。之前我們我們

49、已經(jīng)學(xué)習(xí)了C程序設(shè)計、離散數(shù)學(xué)等，以后還要學(xué)操作系統(tǒng)、編譯原理、數(shù)據(jù)庫原理、軟件工程等。通過本門課程的學(xué)習(xí)，我們應(yīng)該能透徹地理解各種數(shù)據(jù)對象的特點，學(xué)會數(shù)據(jù)的組織方法和實現(xiàn)方法，并進一步培養(yǎng)良好的程序設(shè)計能力和解決實際問題的能力，而且該課程的研究方法對我們學(xué)生在校和離校后的學(xué)習(xí)和工作，也有著重要的意義。學(xué)以致用，這才是我的目標(biāo)，課程設(shè)計給了我這個機會。數(shù)據(jù)結(jié)構(gòu)是計算機科學(xué)與技術(shù)專業(yè)的一門核心專業(yè)基礎(chǔ)課程，在我們專業(yè)的課程體

50、系中起著承上啟下的作用，學(xué)好數(shù)據(jù)結(jié)構(gòu)對于提高理論認(rèn)知水平和實踐能力有著極為重要的作用。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的最終目的是為了獲得求解問題的能力。對于現(xiàn)實世界中的問題，應(yīng)該能從中抽象出一個適當(dāng)?shù)臄?shù)學(xué)模型，該數(shù)學(xué)模型在計算機內(nèi)部用相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來表示，然后設(shè)計一個解此數(shù)學(xué)模型的算法，再進行編程調(diào)試，最后獲得問題的解答。通過數(shù)據(jù)結(jié)構(gòu)課程實踐，加上老師的全力指導(dǎo)，無論是理論知識，還是實踐動手能力，我都有了不同程度上的提高。

51、　　#include <string.h>　　#include <stdio.h>　　#include <stdlib.h>　　#include <time.h>　　#include "mal

52、loc.h"　　#include <iostream.h>　　#define TURE 1　　#define FALSE 0　　#define OK 1　　#define ERROR 0

53、　　#define OVERFLOW -1　　#define INF 32767　　const int MAXVEX=100;　　typedef char Vextype;　　typedef struct<

54、;b>　　{　　Vextype vexs[MAXVEX][MAXVEX]; //單位名稱（頂點信息）；　　int adj[MAXVEX][MAXVEX];//單位之間的相通情況（是否有邊）；　　int dis[MAXVEX][MAXVEX];//單位間

55、距離（邊的長度）；　　int f[MAXVEX];//各單位去超市的頻率；　　int n;//頂點數(shù)和邊數(shù)；　　int e;　　}Mgraph;

56、　　void CreatMgraph(Mgraph *G) 　　{　　int i,j,k;　　printf("請輸入單位個數(shù):\n");　　scanf("%d",&a

57、mp;(G->n));　　printf("請輸入單位間的路徑數(shù):\n");　　scanf("%d",&(G->e));　　printf("請輸入單位名稱:\n");　　for(i=0;i<

58、;G->n;i++)　　{　　printf("請輸入第%d個單位名稱:\n",i);　　scanf("%s",&G->vexs[i]);　　}</b

59、>　　for(i=0;i<G->n;i++) //結(jié)構(gòu)體的初始化；　　for(j=0;j<G->n;j++)　　{　　G->adj[i][j]=0;<p&

60、gt;　　G->dis[i][j]=0;　　G->f[i]=0;　　}　　for(k=0;k<G->e;k++)　　{　　pri

61、ntf("請輸入相通的兩單位 (輸入格式:i,j):\n");　　scanf("%d,%d",&i,&j);//在距離上體現(xiàn)為無向；　　printf("請輸入相同兩個單位間的距離(格式：dis)：\n");　　scanf("%d

62、",&(G->dis[i][j]));　　G->adj[i][j]=1;　　G->adj[j][i]=1;　　G->dis[j][i]=G->dis[i][j];　　}

63、;　　for(k=0;k<G->n;k++)　　{　　printf("請輸入第%d個單位去超市的相對頻率:\n",k);　　scanf("%d",&(G->f[k]));

64、;　　}　　for(i=0;i<G->n;i++) //以距離和頻率之積作為權(quán)值；　　for(j=0;j<G->n;j++)　　{

65、　G->dis[i][j]*=G->f[i]; //最終權(quán)值非完全無向； 　　if(G->adj[i][j]==0&&i!=j)　　G->dis[i][j]=INF;　　}<p&

66、gt;　　}　　void Floyed(Mgraph *G) //帶權(quán)有向圖求最短路徑floyd算法　　{　　int A[MAXVEX][MAXVEX],path[MAXVEX][MAXVEX];

67、;　　int i,j,k,pre;　　int count[MAXVEX];　　for(i=0;i<G->n;i++) //初始化A[][]和path[][]數(shù)組　　for(j=0;j<G->n;j++)

68、 //置初值；　　{　　A[i][j]=G->dis[i][j];　　path[i][j]=-1;　　count[i]=0;　　}

69、　　for(k=0;k<G->n;k++) //k代表運算步驟　　{　　for(i=0;i<G->n;i++)　　for(j=0;j<G->n;j++)

70、　　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;

71、;　　}　　}　　cout<<endl<<"Floyed算法求解如下:"<<endl;　　for(i=0;i<G->n;i++)　　for(j=0

72、;j<G->n;j++)　　{　　if(i!=j)　　{　　cout<<" "<<i<<&

73、quot;->"<<j<<";";　　if(A[i][j]==INF)　　{　　if(i!=j)　　cout<<"

74、不存在路徑"<<"\n"<<endl;　　}　　else　　{　　cout<<"路

75、徑長度為:"<<A[i][j]<<"\n";　　cout<<"路徑為:"<<i<<"*";　　pre=path[i][j];　　while(pre!=-1)&l

76、t;p>　　{　　cout<<pre<<"\n";　　pre=path[pre][j];　　}　　cout<<j<<end

77、l;　　}　　}　　}　　//以下為選擇總體最優(yōu)過程，然后確址；　　for(i=0;i<G->n;i++

78、)　　for(j=0;j<G->n;j++)　　{　　if(A[i][j]==INF)　　count[i]=0;　　else

79、;　　count[i]=1;　　}　　for(i=0;i<G->n;i++)　　if(count[i])　　{　　for

80、(j=0;j<G->n;j++)　　if(i!=j)A[i][i]+=A[j][i];　　}　　k=0;　　for(i=0;i<G->n;i++)&

81、lt;p>　　{　　if(count[i])　　if(A[k][k]>A[i][i])　　k=i;　　}

82、　　cout<<"超市的最佳地址為:"<<G->vexs[k]<<endl;　　}　　void main()　　{　　Mgraph *

83、Gh=NULL;　　Gh=(Mgraph *)malloc(sizeof(Mgraph));　　CreatMgraph(Gh);　　Floyed(Gh);　　system("pause");

84、　}　　/*測試數(shù)據(jù)：　　輸入：　　單位個數(shù)　　4<

85、b>　　單位間的路徑數(shù)　　6　　第0個單位名稱　　a　　第1個單位名稱

86、　　b　　第2個單位名稱　　c　　第3個單位名稱　　d</

87、p>　　相通兩單位之間的距離　　0,1 3　　1,2 2　　2,3 2　　0,3

88、 3　　0,2 4　　1,3 1　　第0個單位去超市的頻率 1　　第1個單位去超市的頻率 2　　第2個單位去超市的頻率 4

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

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

文檔簡介

溫馨提示

最新文檔

評論

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

文檔簡介

溫馨提示

最新文檔

評論

免費下載