超市選址課程設計報告

1、計算機科學與技術(shù)學院課程設計成績單課程名稱：數(shù)據(jù)結(jié)構(gòu)課程設計 指導教師：李順新姓名彭偉華性別男學號2班級計科1103綜合成績成績等級 程序運行情況（占總成績20%）能正確運行 基本能正確運行 能運行但結(jié)果不完善（20分） （15分） （10分）程序功能的完善程度（占總成績10%）完善 基本完善 不完善（10分） （8分） （5分）程序結(jié)構(gòu)的合理性（占總成績10%）合理 基本合理 不太合理（10分） （8分） （5分）對問題的答辯情況（占總成績40%）概念正確有創(chuàng)新 能正確回答所有問題 基本能正確回答（40分） （35分） （30分）部分問題回答概念不清晰（20分）學生的工作態(tài)度與獨立工作能力（

2、占總成績10%）工作態(tài)度認真能獨立完成任務 工作態(tài)度認真但獨立性較差（10分） （8分）工作態(tài)度基本認真但缺乏獨立性（5分）設計報告的規(guī)范性（占總成績10%） 符合規(guī)范 基本符合規(guī)范 規(guī)范性較差（10分） （8分） （5分）優(yōu)秀：90分100分 良好：80分89分 中等：7079分 及格：6069分 不及格0分59分 武漢科技大學計算機科學與技術(shù)學院制表 計算機科學與技術(shù)學院課 程 設 計 報 告課程名稱： 數(shù)據(jù)結(jié)構(gòu)課程設計 專 業(yè)： 計算機科學與技術(shù) 班 級： 2011級03班 學 號： 2 姓 名： 彭 偉 華 指導老師： 李 順 新 2013年9月20日計算機科學與技術(shù)專業(yè)課程設計任務書

3、設計題目小區(qū)便利店選址問題學生姓名彭偉華所在院系計算機科學與技術(shù)專業(yè)、班級計科1103主要內(nèi)容：對于某一小區(qū)便利店，其他各棟樓到其的距離不同，同時各棟樓的居民數(shù)也各不相同，不考慮各居民去超市的頻率，請為便利店選址，要求實現(xiàn)總體最優(yōu)，方便更多的住戶購物。 【提示】1）便利店無論選址何處，八棟樓的居民均可直接到達，即八棟樓與便利店均相鄰，且距離為直線距離；2）八棟樓的居民人數(shù)為權(quán)重，應該方便大多數(shù)人，實現(xiàn)總體最優(yōu)。學生應完成的工作：l 設計友好的用戶界面l 數(shù)據(jù)設計合理，模塊劃分清晰l 程序能正確無錯誤地運行，提交完整源代碼l 寫出符合要求的課程設計報告書參考文獻閱讀：1 數(shù)據(jù)結(jié)構(gòu)（C語言版） 嚴

4、蔚敏 清華大學出版社.2 數(shù)據(jù)結(jié)構(gòu)題集（C語言版） 嚴蔚敏 清華大學出版社.3 c語言程序設計 譚浩強 清華大學出版社. 4數(shù)據(jù)結(jié)構(gòu)與算法分析 張銘   電子工業(yè)出版社 5 DATA STRUCTURE WITH C+ William Ford,William Topp 清華大學出版社工作計劃：第1-2天：課題分析與總體設計第3-7天：程序設計，調(diào)度與測試第8-9天：設計總結(jié)，完成課程設計報告書第10天： 檢查考核任務下達日期：2013 年 9 月 10 日任務完成日期：2013 年 9 月 20 日 學生（簽名）： 便利店選址摘要：該課題是為小區(qū)內(nèi)的某一便利店選址，要求實現(xiàn)總體最優(yōu)

5、，這是帶權(quán)的最小生成樹的問題，小區(qū)平面圖采用鄰接矩陣表示，設計小區(qū)的平面圖是一有向網(wǎng)，邊表示各單位到便利店的路徑，邊上的權(quán)值表示路徑的長度。關鍵詞：權(quán) 鄰接矩陣 有向網(wǎng)1 引 言1.1課題背景便利店的選址問題是一個很復雜的決策過程，既需要定性分析，又需要定量計算。選址問題主要取決于店鋪位置的地形特點及其周圍的人口狀況、城市設施狀況、交通條件、地租成本和競爭環(huán)境等，正確的選址決策能在減少投資運行成本的同時提高經(jīng)濟效益。近幾年，由于選址數(shù)據(jù)的愈加復雜以及計算機技術(shù)的迅速發(fā)展，人們開始利用計算機的強大計算能力對選址數(shù)據(jù)進行分析計算，從而決定最佳的選址方案。1.2課程設計目的數(shù)據(jù)結(jié)構(gòu)是計算機學科實踐性

6、很強的一門核心課程。課程設計是加強學生實踐能力的一個強有力手段，要求學生掌握數(shù)據(jù)結(jié)構(gòu)的應用、算法的編寫、類C語言的算法轉(zhuǎn)換成C（C+）程序并上機調(diào)試的基本方法，還要求學生在完成程序設計的同時能夠?qū)懗霰容^規(guī)范的設計報告。嚴格實施課程設計這一環(huán)節(jié)，對于學生基本程序設計素養(yǎng)的培養(yǎng)和軟件工作者工作作風的訓練，將起到顯著的促進作用。1.3 課程設計任務對于某一小區(qū)便利店，其他各棟樓到其的距離不同，同時各棟樓的居民數(shù)也各不相同，不考慮各居民去超市的頻率，請為便利店選址，要求實現(xiàn)總體最優(yōu)，方便更多的住戶購物。 【提示】1）便利店無論選址何處，八棟樓的居民均可直接到達，即八棟樓與便利店均相鄰，且距離為直線距離

7、；2）八棟樓的居民人數(shù)為權(quán)重，應該方便大多數(shù)人，實現(xiàn)總體最優(yōu)。通過該題目的設計過程，可以加深理解圖數(shù)據(jù)結(jié)構(gòu)，掌握某些基本運算的實現(xiàn)，進一步理解和熟練掌握課本中所學的各種數(shù)據(jù)結(jié)構(gòu)，學會如何把學到的知識用于解決實際問題，培養(yǎng)學生的動手能力。1.4 系統(tǒng)開發(fā)平臺1、題目：便利店選址2、開發(fā)工具： Microsoft Visual C+6.03、操作系統(tǒng)：Windows 72 系統(tǒng)結(jié)構(gòu)分析2.1需求分析核心問題: 求最短路徑(選址的要求就是便利店到各單位權(quán)值之和最少)數(shù)據(jù)模型（邏輯結(jié)構(gòu)）: 帶權(quán)有向圖 (權(quán)值計算: 距離*人數(shù))存儲結(jié)構(gòu): typedef struct string vexsMAX_V

8、ERTEX_SIZE; int arcsMAX_VERTEX_SIZEMAX_VERTEX_SIZE; int vexnum;/ ,arcnum;MGraph; 核心算法: Floyd算法(弗洛伊德算法-每一對頂點之間的最短路徑) 輸入數(shù)據(jù): 單位個數(shù)、各單位地址、各單位人數(shù)輸出數(shù)據(jù): 便利店地址值總體思路:如果便利店所選地址為（x,y），那么先求出各單位到該地址的含參直線距離，在保證總體最優(yōu)（權(quán)值最?。┑那闆r下計算出便利店地址的精確值。 2.2方案選擇 1）直角距離選址模型使總體最優(yōu)的的便利店選址問題可表述為：minZ=CjQj（|X-Xa|+|Y-Ya|）可將問題分解成兩個單獨最小化問題：

9、minZ= minZ1+ minZ2minZ1=minCjQj|X-Xa|minZ2=minCjQj|Y-Ya|2)歐式距離選址模型兩點之間的歐式距離定義如下：Dj=(X-Xa)*(X-Xa)+(Y-Ya)*(Y-Ya)使總體最優(yōu)的便利店選址問題可表述為：minZ=CjQj(X-Xa)* (X-Xa)+(Y-Ya)* (Y-Ya)分別求Z對Xa和Ya的偏導數(shù)，令所得方程等于零，求Xa和Ya的值：Xa=(CjQjXj/Dj)/ (CjQj/Dj)Ya=(CjQjYj/Dj)/ (CjQj/Dj)3)修正距離選址模型在方案2）所得結(jié)果的基礎上，采用迭代法求解更精確的結(jié)果。Dj=k(X-Xa)* (

10、X-Xa)+(Y-Ya)* (Y-Ya) minZ=kCjQj(X-Xa)* (X-Xa)+(Y-Ya)* (Y-Ya)由于本課題所給數(shù)據(jù)比較簡單，通過綜合比較分析，本課題決定采用方案1）。3 應用程序設計3.1流程圖設計開始Main（）輸入基本信息GreatMgraph（Gh）建立鄰接矩陣的存儲結(jié)構(gòu)Floyd算法NYAij=INF,i!=ji到j不存在路徑輸出i->j的路徑和路徑長度Floyed（Gh）輸出超市的最佳地址：i結(jié)束3.2源程序#include <iostream> #include <cmath> using namespace std; stru

11、ct building double x; double y; double value; ; building bd1000; int n;/n棟樓 double minx,maxx,miny,maxy;/記錄各棟樓的區(qū)域 double midx,mmidx,midy,mmidy; double result_x,result_y,sum = 100000;/最后結(jié)果 double dis(double x,double y)/計算距離 double sum= 0; for(int i = 0;i < n;i+) sum += sqrt(x - bdi.x)*(x - bdi.x) +

12、 (y - bdi.y)*(y - bdi.y)*bdi.value; return sum; void D_Divide()/三分法求位置 midx = (minx + maxx)/2; mmidx = (midx + maxx)/2; midy = (miny + maxy)/2; mmidy = (midy + maxy)/2; while(maxx-minx) > 0.01) while(maxy-miny)>0.01) if(dis(midx,midy) > dis(midx,mmidy) miny = midy; else maxy = mmidy; midy =

13、 (miny + maxy)/2; mmidy = (midy + maxy)/2; ; if(dis(midx,midy) > dis(mmidx,midy) minx = midx; else maxx = mmidx; midx = (minx + maxx)/2; mmidx = (midx + maxx)/2; ; result_x = midx; result_y = midy; sum = dis(result_x,result_y); int main() cout<<"請輸入樓的數(shù)量:" cin>>n; cout<<

14、;"n請輸入各樓x y 權(quán)值"<<endl; minx = maxx = miny = maxy = 0; for(int i = 0;i < n;i+) cin>>bdi.x>>bdi.y>>bdi.value; if(bdi.x < minx) minx = bdi.x; if(bdi.x > maxx) maxx = bdi.x; if(bdi.y < minx) miny = bdi.y; if(bdi.y > maxx) maxy = bdi.y; D_Divide(); cout<

15、;<"n便利店選址坐標為:"<<endl; cout<<"x: "<<result_x<<" "<<"y: "<<result_y<<endl; cout<<"n最優(yōu)解為: "<<sum<<endl; return 0; 4 測試與結(jié)果通過測試可以發(fā)現(xiàn)程序設計中存在的很多問題，通過解決一個個的問題，可以更好的完善程序功能。4.1測試過程截圖4.2調(diào)試分析（1）調(diào)試中遇到的

16、問題及對問題的解決遇到的問題：在調(diào)試時發(fā)現(xiàn)，寫入程序是產(chǎn)生的數(shù)據(jù)、函數(shù)定義不當、函數(shù)調(diào)用不當?shù)葐栴}。還有一些在輸入數(shù)據(jù)時產(chǎn)生的輸入值、輸入范圍不相匹配的錯誤。解決方法：對于前一問題，在程序調(diào)試中根據(jù)系統(tǒng)提示找到相應出錯行。細心分析、多方求證，最終得到順利解決。對于后一問題，可根據(jù)事先程序中寫入的相關提示就可以解決，如無提示就返回相關實現(xiàn)的算法程序中查找。（2）算法的時間復雜度以及空間復雜度 時間復雜度為：O（n3）,空間復雜度為：O（1）5 總 結(jié)本次課程設計的題目是小區(qū)便利店的選址問題，要求實現(xiàn)總體最優(yōu)。在編寫程序的過程中遇到了許多的問題，在解決問題的同時對鄰接矩陣，最小生成樹，有向網(wǎng)等進一步加深了了解，強化了在上課學的知識，對自己提高很大,同時了解到自己專業(yè)基礎知識的不足，所以我還要通過不斷的學習，不斷的充電自己。通過該題目的設計過程，初步掌握數(shù)據(jù)結(jié)構(gòu)的基本理論和方法，及用C語言設計編寫程序的技巧，提高了解決實際問題的能力。通過對本次課程設計的總結(jié)，我也有如下經(jīng)驗教訓：1、程序代碼工作開始之前，一定要首先進行需求的具體分析，只有對于需求有了全面客觀的掌握，才能確定程序所應實現(xiàn)的功