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

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

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

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

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

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

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

7、達(dá)，即八棟樓與便利店均相鄰，且距離為直線距離；2）八棟樓的居民人數(shù)為權(quán)重，應(yīng)該方便大多數(shù)人，實(shí)現(xiàn)總體最優(yōu)。通過該題目的設(shè)計(jì)過程，可以加深理解圖數(shù)據(jù)結(jié)構(gòu)，掌握某些基本運(yùn)算的實(shí)現(xiàn)，進(jìn)一步理解和熟練掌握課本中所學(xué)的各種數(shù)據(jù)結(jié)構(gòu)，學(xué)會(huì)如何把學(xué)到的知識用于解決實(shí)際問題，培養(yǎng)學(xué)生的動(dòng)手能力。1.4 系統(tǒng)開發(fā)平臺(tái)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)值計(jì)算: 距離*人數(shù))存儲(chǔ)結(jié)構(gòu): typedef s

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

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

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

11、ng namespace std; struct 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)/計(jì)算距離 double sum= 0; for(int i = 0;i < n;i+) sum += sqrt(x

12、- bdi.x)*(x - bdi.x) + (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; els

13、e maxy = mmidy; midy = (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

14、>>n; cout<<"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.

15、y; D_Divide(); cout<<"n便利店選址坐標(biāo)為:"<<endl; cout<<"x: "<<result_x<<" "<<"y: "<<result_y<<endl; cout<<"n最優(yōu)解為: "<<sum<<endl; return 0; 4 測試與結(jié)果通過測試可以發(fā)現(xiàn)程序設(shè)計(jì)中存在的很多問題，通過解決一個(gè)個(gè)的問題，可以更好的完善程序功能。4.1

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