超市選址課程設計報告

1、<p>　　計算機科學與技術學院</p><p>　　課 程 設 計 報 告</p><p>　　課程名稱： 數(shù)據(jù)結構課程設計 </p><p>　　專 業(yè)： 計算機科學與技術 </p><p>　　班 級： 2011級03班 </p><p>　　學 號： <

2、;/p><p>　　姓 名： </p><p>　　指導老師： </p><p>　　2013年9月20日</p><p>　　計算機科學與技術專業(yè)課程設計任務書</p><p><b>　　便利店選址</b></p><p><

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

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

5、發(fā)展，人們開始利用計算機的強大計算能力對選址數(shù)據(jù)進行分析計算，從而決定最佳的選址方案。</p><p><b>　　1.2課程設計目的</b></p><p>　　數(shù)據(jù)結構是計算機學科實踐性很強的一門核心課程。課程設計是加強學生實踐能力的一個強有力手段，要求學生掌握數(shù)據(jù)結構的應用、算法的編寫、類C語言的算法轉換成C（C++）程序并上機調試的基本方法，還要求學生在完成程

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

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

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

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

10、構: 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算法(弗洛伊德算法-每一對頂點之間的最短路徑) </p><p>　　輸入數(shù)據(jù): 單位個數(shù)、各單位地址、各單位人數(shù)</p><p>　　輸出數(shù)據(jù): 便利店地址值</p><p>　　總體

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

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

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

15、;/p><p>　　Ya=(∑CjQjYj/Dj)/ (∑CjQj/Dj)</p><p>　　3)修正距離選址模型</p><p>　　在方案2）所得結果的基礎上，采用迭代法求解更精確的結果。</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ù)比較簡單，通過綜合比較分析，本課題決定采用方案1）。</p><p><b>　　3 應用程序設計</b></p><p><b>　　3.1流程圖設計</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、后結果 </p><p>　　double dis(double x,double y)//計算距離 </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<<"請輸入樓的數(shù)量:"; </p><p><b>　　cin>&

29、gt;n; </b></p><p>　　cout<<"\n請輸入各樓x y 權值"<<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便利店選址坐標為:"<<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 測試與結果</b></p><p>　　通過測試可以發(fā)現(xiàn)程序設計中存在的很多問題，通過解決一個個的問題，可以更好的完善程序功能。</p><p><b>　　4.1測試過程截圖</b></p><p><b>

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

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

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

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

39、t;/p><p><b>　　附：參考文獻</b></p><p>　　[1] 《數(shù)據(jù)結構（C語言版）》 嚴蔚敏 清華大學出版社.</p><p>　　[2] 《數(shù)據(jù)結構題集（C語言版）》 嚴蔚敏 清華大學出版社.</p><p>　　[3] 《c語言程序設計》 譚浩強 清華大學出版社.