超市選址課程設(shè)計(jì)報(bào)告

1、<p>　　計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院</p><p>　　課 程 設(shè) 計(jì) 報(bào) 告</p><p>　　課程名稱(chēng)： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p>　　專(zhuān) 業(yè)： 計(jì)算機(jī)科學(xué)與技術(shù) </p><p>　　班 級(jí)： 2011級(jí)03班 </p><p>　　學(xué) 號(hào)： <

2、;/p><p>　　姓 名： </p><p>　　指導(dǎo)老師： </p><p>　　2013年9月20日</p><p>　　計(jì)算機(jī)科學(xué)與技術(shù)專(zhuān)業(yè)課程設(shè)計(jì)任務(wù)書(shū)</p><p><b>　　便利店選址</b></p><p><

3、;b>　　摘要：</b></p><p>　　該課題是為小區(qū)內(nèi)的某一便利店選址，要求實(shí)現(xiàn)總體最優(yōu)，這是帶權(quán)的最小生成樹(shù)的問(wèn)題，小區(qū)平面圖采用鄰接矩陣表示，設(shè)計(jì)小區(qū)的平面圖是一有向網(wǎng)，邊表示各單位到便利店的路徑，邊上的權(quán)值表示路徑的長(zhǎng)度。</p><p>　　關(guān)鍵詞：權(quán) 鄰接矩陣 有向網(wǎng)</p><p><b>　　1 引 言&

4、lt;/b></p><p><b>　　1.1課題背景</b></p><p>　　便利店的選址問(wèn)題是一個(gè)很復(fù)雜的決策過(guò)程，既需要定性分析，又需要定量計(jì)算。選址問(wèn)題主要取決于店鋪位置的地形特點(diǎn)及其周?chē)娜丝跔顩r、城市設(shè)施狀況、交通條件、地租成本和競(jìng)爭(zhēng)環(huán)境等，正確的選址決策能在減少投資運(yùn)行成本的同時(shí)提高經(jīng)濟(jì)效益。近幾年，由于選址數(shù)據(jù)的愈加復(fù)雜以及計(jì)算機(jī)技術(shù)的迅速

5、發(fā)展，人們開(kāi)始利用計(jì)算機(jī)的強(qiáng)大計(jì)算能力對(duì)選址數(shù)據(jù)進(jìn)行分析計(jì)算，從而決定最佳的選址方案。</p><p><b>　　1.2課程設(shè)計(jì)目的</b></p><p>　　數(shù)據(jù)結(jié)構(gòu)是計(jì)算機(jī)學(xué)科實(shí)踐性很強(qiáng)的一門(mén)核心課程。課程設(shè)計(jì)是加強(qiáng)學(xué)生實(shí)踐能力的一個(gè)強(qiáng)有力手段，要求學(xué)生掌握數(shù)據(jù)結(jié)構(gòu)的應(yīng)用、算法的編寫(xiě)、類(lèi)C語(yǔ)言的算法轉(zhuǎn)換成C（C++）程序并上機(jī)調(diào)試的基本方法，還要求學(xué)生在完成程

6、序設(shè)計(jì)的同時(shí)能夠?qū)懗霰容^規(guī)范的設(shè)計(jì)報(bào)告。嚴(yán)格實(shí)施課程設(shè)計(jì)這一環(huán)節(jié)，對(duì)于學(xué)生基本程序設(shè)計(jì)素養(yǎng)的培養(yǎng)和軟件工作者工作作風(fēng)的訓(xùn)練，將起到顯著的促進(jìn)作用。</p><p>　　1.3 課程設(shè)計(jì)任務(wù)</p><p>　　對(duì)于某一小區(qū)便利店，其他各棟樓到其的距離不同，同時(shí)各棟樓的居民數(shù)也各不相同，不考慮各居民去超市的頻率，請(qǐng)為便利店選址，要求實(shí)現(xiàn)總體最優(yōu)，方便更多的住戶購(gòu)物。 </p>

7、<p><b>　　【提示】</b></p><p>　　1）便利店無(wú)論選址何處，八棟樓的居民均可直接到達(dá)，即八棟樓與便利店均相鄰，且距離為直線距離；</p><p>　　2）八棟樓的居民人數(shù)為權(quán)重，應(yīng)該方便大多數(shù)人，實(shí)現(xiàn)總體最優(yōu)。</p><p>　　通過(guò)該題目的設(shè)計(jì)過(guò)程，可以加深理解圖數(shù)據(jù)結(jié)構(gòu)，掌握某些基本運(yùn)算的實(shí)現(xiàn)，進(jìn)一步理解和

8、熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會(huì)如何把學(xué)到的知識(shí)用于解決實(shí)際問(wèn)題，培養(yǎng)學(xué)生的動(dòng)手能力。</p><p>　　1.4 系統(tǒng)開(kāi)發(fā)平臺(tái)</p><p>　　1、題目：便利店選址</p><p>　　2、開(kāi)發(fā)工具： Microsoft Visual C++6.0</p><p>　　3、操作系統(tǒng)：Windows 7</p><

9、;p><b>　　2 系統(tǒng)結(jié)構(gòu)分析</b></p><p><b>　　2.1需求分析</b></p><p>　　核心問(wèn)題: 求最短路徑(選址的要求就是便利店到各單位權(quán)值之和最少)</p><p>　　數(shù)據(jù)模型（邏輯結(jié)構(gòu)）: 帶權(quán)有向圖 (權(quán)值計(jì)算: 距離*人數(shù))</p><p>　　存儲(chǔ)結(jié)

10、構(gòu): typedef struct</p><p><b>　　{</b></p><p>　　string vexs[MAX_VERTEX_SIZE];</p><p>　　int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];</p><p>　　int vexnum;// ,arcn

11、um;</p><p><b>　　}MGraph; </b></p><p>　　核心算法: Floyd算法(弗洛伊德算法-每一對(duì)頂點(diǎn)之間的最短路徑) </p><p>　　輸入數(shù)據(jù): 單位個(gè)數(shù)、各單位地址、各單位人數(shù)</p><p>　　輸出數(shù)據(jù): 便利店地址值</p><p>　　總體

12、思路:　如果便利店所選地址為（x,y），那么先求出各單位到該地址的含參直線距離，在保證總體最優(yōu)（權(quán)值最?。┑那闆r下計(jì)算出便利店地址的精確值。 </p><p><b>　　2.2方案選擇</b></p><p>　　1）直角距離選址模型</p><p>　　使總體最優(yōu)的的便利店選址問(wèn)題可表述為：minZ=∑CjQj（|X-Xa|+|Y-Ya|）

13、</p><p>　　可將問(wèn)題分解成兩個(gè)單獨(dú)最小化問(wèn)題：minZ= minZ1+ minZ2</p><p>　　minZ1=min∑CjQj|X-Xa|</p><p>　　minZ2=min∑CjQj|Y-Ya|</p><p>　　2)歐式距離選址模型</p><p>　　兩點(diǎn)之間的歐式距離定義如下：Dj=√[

14、(X-Xa)*(X-Xa)+(Y-Ya)*(Y-Ya)]</p><p>　　使總體最優(yōu)的便利店選址問(wèn)題可表述為：minZ=∑CjQj√[(X-Xa)* (X-Xa)+(Y-Ya)* (Y-Ya)]</p><p>　　分別求Z對(duì)Xa和Ya的偏導(dǎo)數(shù)，令所得方程等于零，求Xa和Ya的值：</p><p>　　Xa=(∑CjQjXj/Dj)/ (∑CjQj/Dj)<

15、;/p><p>　　Ya=(∑CjQjYj/Dj)/ (∑CjQj/Dj)</p><p>　　3)修正距離選址模型</p><p>　　在方案2）所得結(jié)果的基礎(chǔ)上，采用迭代法求解更精確的結(jié)果。</p><p>　　Dj=k√[(X-Xa)* (X-Xa)+(Y-Ya)* (Y-Ya)]</p><p>　　minZ=∑k

16、CjQj√[(X-Xa)* (X-Xa)+(Y-Ya)* (Y-Ya)]</p><p>　　由于本課題所給數(shù)據(jù)比較簡(jiǎn)單，通過(guò)綜合比較分析，本課題決定采用方案1）。</p><p><b>　　3 應(yīng)用程序設(shè)計(jì)</b></p><p><b>　　3.1流程圖設(shè)計(jì)</b></p><p><b

17、>　　3.2源程序</b></p><p>　　#include <iostream> </p><p>　　#include <cmath> </p><p>　　using namespace std; </p><p>　　struct building </p><

18、p><b>　　{ </b></p><p>　　double x; </p><p>　　double y; </p><p>　　double value; </p><p><b>　　}; </b></p><p>　　building bd[1000

19、]; </p><p>　　int n;//n棟樓 </p><p>　　double minx,maxx,miny,maxy;//記錄各棟樓的區(qū)域 </p><p>　　double midx,mmidx,midy,mmidy; </p><p>　　double result_x,result_y,sum = 100000;//最

20、后結(jié)果 </p><p>　　double dis(double x,double y)//計(jì)算距離 </p><p><b>　　{ </b></p><p>　　double sum= 0; </p><p>　　for(int i = 0;i < n;i++) </p><p&g

21、t;<b>　　{ </b></p><p>　　sum += sqrt((x - bd[i].x)*(x - bd[i].x) + (y - bd[i].y)*(y - bd[i].y))*bd[i].value; </p><p><b>　　} </b></p><p>　　return sum; </

22、p><p><b>　　} </b></p><p>　　void D_Divide()//三分法求位置 </p><p><b>　　{ </b></p><p>　　midx = (minx + maxx)/2; </p><p>　　mmidx = (midx +

23、maxx)/2; </p><p>　　midy = (miny + maxy)/2; </p><p>　　mmidy = (midy + maxy)/2; </p><p>　　while((maxx-minx) > 0.01) </p><p><b>　　{ </b></p><

24、;p>　　while((maxy-miny)>0.01) </p><p><b>　　{ </b></p><p>　　if(dis(midx,midy) > dis(midx,mmidy)) </p><p>　　miny = midy; </p><p><b>　　else

25、</b></p><p>　　maxy = mmidy; </p><p>　　midy = (miny + maxy)/2; </p><p>　　mmidy = (midy + maxy)/2; </p><p><b>　　}; </b></p><p>　　if(dis

26、(midx,midy) > dis(mmidx,midy)) </p><p>　　minx = midx; </p><p><b>　　else </b></p><p>　　maxx = mmidx; </p><p>　　midx = (minx + maxx)/2; </p>&l

27、t;p>　　mmidx = (midx + maxx)/2; </p><p><b>　　}; </b></p><p>　　result_x = midx; </p><p>　　result_y = midy; </p><p>　　sum = dis(result_x,result_y); <

28、;/p><p><b>　　} </b></p><p>　　int main() </p><p><b>　　{ </b></p><p>　　cout<<"請(qǐng)輸入樓的數(shù)量:"; </p><p><b>　　cin>&

29、gt;n; </b></p><p>　　cout<<"\n請(qǐng)輸入各樓x y 權(quán)值"<<endl; </p><p>　　minx = maxx = miny = maxy = 0; </p><p>　　for(int i = 0;i < n;i++) </p><p>

30、<b>　　{ </b></p><p>　　cin>>bd[i].x>>bd[i].y>>bd[i].value; </p><p>　　if(bd[i].x < minx) </p><p>　　minx = bd[i].x; </p><p>　　if(bd[i].

31、x > maxx) </p><p>　　maxx = bd[i].x; </p><p>　　if(bd[i].y < minx) </p><p>　　miny = bd[i].y; </p><p>　　if(bd[i].y > maxx) </p><p>　　maxy = bd[i

32、].y; </p><p><b>　　} </b></p><p>　　D_Divide(); </p><p>　　cout<<"\n便利店選址坐標(biāo)為:"<<endl; </p><p>　　cout<<"x: "<<re

33、sult_x<<" "<<"y: "<<result_y<<endl; </p><p>　　cout<<"\n最優(yōu)解為: "<<sum<<endl; </p><p>　　return 0; </p><p>&

34、lt;b>　　} </b></p><p><b>　　4 測(cè)試與結(jié)果</b></p><p>　　通過(guò)測(cè)試可以發(fā)現(xiàn)程序設(shè)計(jì)中存在的很多問(wèn)題，通過(guò)解決一個(gè)個(gè)的問(wèn)題，可以更好的完善程序功能。</p><p><b>　　4.1測(cè)試過(guò)程截圖</b></p><p><b>

35、　　4.2調(diào)試分析</b></p><p>　　（1）調(diào)試中遇到的問(wèn)題及對(duì)問(wèn)題的解決</p><p>　　遇到的問(wèn)題：在調(diào)試時(shí)發(fā)現(xiàn)，寫(xiě)入程序是產(chǎn)生的數(shù)據(jù)、函數(shù)定義不當(dāng)、函數(shù)調(diào)用不當(dāng)?shù)葐?wèn)題。還有一些在輸入數(shù)據(jù)時(shí)產(chǎn)生的輸入值、輸入范圍不相匹配的錯(cuò)誤。</p><p>　　解決方法：對(duì)于前一問(wèn)題，在程序調(diào)試中根據(jù)系統(tǒng)提示找到相應(yīng)出錯(cuò)行。細(xì)心分析、多方求證，最終

36、得到順利解決。對(duì)于后一問(wèn)題，可根據(jù)事先程序中寫(xiě)入的相關(guān)提示就可以解決，如無(wú)提示就返回相關(guān)實(shí)現(xiàn)的算法程序中查找。</p><p>　?。?）算法的時(shí)間復(fù)雜度以及空間復(fù)雜度</p><p>　　時(shí)間復(fù)雜度為：O（n3）,空間復(fù)雜度為：O（1）</p><p><b>　　5 總 結(jié)</b></p><p>　　本次課程設(shè)計(jì)

37、的題目是小區(qū)便利店的選址問(wèn)題，要求實(shí)現(xiàn)總體最優(yōu)。在編寫(xiě)程序的過(guò)程中遇到了許多的問(wèn)題，在解決問(wèn)題的同時(shí)對(duì)鄰接矩陣，最小生成樹(shù)，有向網(wǎng)等進(jìn)一步加深了了解，強(qiáng)化了在上課學(xué)的知識(shí)，對(duì)自己提高很大,同時(shí)了解到自己專(zhuān)業(yè)基礎(chǔ)知識(shí)的不足，所以我還要通過(guò)不斷的學(xué)習(xí)，不斷的充電自己。</p><p>　　通過(guò)該題目的設(shè)計(jì)過(guò)程，初步掌握數(shù)據(jù)結(jié)構(gòu)的基本理論和方法，及用C語(yǔ)言設(shè)計(jì)編寫(xiě)程序的技巧，提高了解決實(shí)際問(wèn)題的能力。</p>

38、;<p>　　通過(guò)對(duì)本次課程設(shè)計(jì)的總結(jié)，我也有如下經(jīng)驗(yàn)教訓(xùn)：</p><p>　　1、程序代碼工作開(kāi)始之前，一定要首先進(jìn)行需求的具體分析，只有對(duì)于需求有了全面客觀的掌握，才能確定程序所應(yīng)實(shí)現(xiàn)的功能，從而在以后的代碼編寫(xiě)工作中更加全面。</p><p>　　2、代碼編寫(xiě)之前，應(yīng)該全面規(guī)劃項(xiàng)目中的層次結(jié)構(gòu)，具體到變量的名稱(chēng)、方法的引用等等，只有這樣才能在以后的工作中從容不迫。&l

39、t;/p><p><b>　　附：參考文獻(xiàn)</b></p><p>　　[1] 《數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）》 嚴(yán)蔚敏 清華大學(xué)出版社.</p><p>　　[2] 《數(shù)據(jù)結(jié)構(gòu)題集（C語(yǔ)言版）》 嚴(yán)蔚敏 清華大學(xué)出版社.</p><p>　　[3] 《c語(yǔ)言程序設(shè)計(jì)》 譚浩強(qiáng) 清華大學(xué)出版社.