醫(yī)院選址 《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)報(bào)告.doc

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目: 醫(yī)院選址 姓名： 李恒 學(xué)號： 2115110289 專業(yè)： 物聯(lián)網(wǎng)工程 院系： 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 班級： 1506 指導(dǎo)教師： 高秀梅 2017年 1月 6日 摘要醫(yī)院是一個(gè)為人民服務(wù)的服務(wù)機(jī)構(gòu)，對于醫(yī)院選址的問題則關(guān)乎其利民程度，一個(gè)好的醫(yī)院選址則可以更好的服務(wù)的百姓。本系統(tǒng)的功能就是醫(yī)院選址。通過Floyd算法，實(shí)現(xiàn)該功能。在課程設(shè)計(jì)中，系統(tǒng)開發(fā)平臺為Windows 7，程序設(shè)計(jì)設(shè)計(jì)語言采用Visual Studio 2010，設(shè)計(jì)簡單目的明確，簡易操作。關(guān)鍵詞 程序設(shè)計(jì)；數(shù)據(jù)結(jié)構(gòu)；Floyd算法；醫(yī)院選址英文摘要The hospital is a service for people service for hospital location problem is related to the benefit degree, can better service the location of a good hospital of the people. The function of this system is hospital location. Through the Floyd algorithm, the realization of the function. In the curriculum design, the system development platform for Windows 7, programming design language using Visual Studio 2010, the design of simple and clear, simple operation. Key words ：programming; data structure; Floyd algorithm; hospital location 目 錄摘要.1英文摘要.2問題描述.4需求分析.4概要設(shè)計(jì).4數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì).4算法設(shè)計(jì).5程序設(shè)計(jì)與實(shí)現(xiàn).8調(diào)試分析.10遇到的問題及解決方法.11心得體會.11源代碼.11一、問題描述1.題目內(nèi)容：問題描述：有n個(gè)村莊，現(xiàn)要從這n個(gè)村莊中選擇一個(gè)村莊新建一所醫(yī)院，使其余的村莊到這所醫(yī)院的距離總和來說較短。（n6）2.基本要求：輸入各個(gè)村莊的距離（即圖各結(jié)點(diǎn)直接弧長） 3.使用Floyd算法求最短路徑4.求到所有結(jié)點(diǎn)路徑最短的結(jié)點(diǎn)及其到其余結(jié)點(diǎn)的路徑長度二、需求分析1.本程序的功能主要實(shí)現(xiàn)圖的最短路徑，2.輸出最短路徑的的起點(diǎn)，3.Floyd算法的實(shí)現(xiàn)。三、概要設(shè)計(jì)由于設(shè)計(jì)功能簡單所有并未采用多文件結(jié)構(gòu)處理；1.#define HUGE 1000000;/設(shè)最大弧長，用于最后的選擇比較算法2.int n;/村莊數(shù)目 在函數(shù)外聲明n 定義村莊數(shù)目的聲明。3.void Shortest(int arcs1010) /用Floyd算法求出最短距離的矩陣4.int select(int arcs1010) / 選出使距離最長的那個(gè)村莊四、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1 元素類型#define HUGE 1000000;/設(shè)最大弧長，用于最后的選擇比較算法int n;/村莊數(shù)目 在函數(shù)外聲明n 定義村莊數(shù)目的聲明。void Shortest(int arcs1010) /用Floyd算法求出最短距離的矩陣int select(int arcs1010) / 選出使距離最長的那個(gè)村莊int v,w,u; v,w用于村莊標(biāo)號同樣用于計(jì)數(shù) u用于計(jì)數(shù) int arcs1010;數(shù)組用于存儲村莊之間的距離（即結(jié)點(diǎn)直接的弧長）五、算法設(shè)計(jì) 1、算法分析1).Floyd算法是一個(gè)經(jīng)典的動(dòng)態(tài)規(guī)劃算法。用通俗的語言來描述的話，首先我們的目標(biāo)是尋找從點(diǎn)i到點(diǎn)j的最短路徑。從動(dòng)態(tài)規(guī)劃的角度看問題，我們需要為這個(gè)目標(biāo)重新做一個(gè)詮釋從任意節(jié)點(diǎn)i到任意節(jié)點(diǎn)j的最短路徑不外乎2種可能，1是直接從i到j(luò)，2是從i經(jīng)過若干個(gè)節(jié)點(diǎn)k到j(luò)。所以，我們假設(shè)Dis(i,j)為節(jié)點(diǎn)u到節(jié)點(diǎn)v的最短路徑的距離，對于每一個(gè)節(jié)點(diǎn)k，我們檢查Dis(i,k) + Dis(k,j) Dis(i,j)是否成立，如果成立，證明從i到k再到j(luò)的路徑比i直接到j(luò)的路徑短，我們便設(shè)置Dis(i,j) = Dis(i,k) + Dis(k,j)，這樣一來，當(dāng)我們遍歷完所有節(jié)點(diǎn)k，Dis(i,j)中記錄的便是i到j(luò)的最短路徑的距離。2).算法描述：a.從任意一條單邊路徑開始。所有兩點(diǎn)之間的距離是邊的權(quán)，如果兩點(diǎn)之間沒有邊相連，則權(quán)為無窮大。 b.對于每一對頂點(diǎn) u 和 v，看看是否存在一個(gè)頂點(diǎn) w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。 2、算法實(shí)現(xiàn) void Shortest(int arcs1010) /用Floyd算法求出最短距離的矩陣int u,v,w;cout=請輸入相應(yīng)初始指標(biāo)=endl;coutn;coutn;if(n6)system(cls);coutPlease input the number more than 6!endl;Shortest(arcs);for(v=1;v=n;v+)for(w=v;w=n;w+)if(v!=w)cout村莊v與村莊warcsvw;coutn;else arcsvw=0;for(v=1;v=n;v+)for(w=1;w=v;w+)arcsvw=arcswv;for(u=1;u=n;u+)for(v=1;v=n;v+)for(w=0;wn;w+)if(arcsvu+arcsuwarcsvw)arcsvw=arcsvu+arcsuw;3、算法流程圖在本題中假設(shè)輸入弧長入下圖所示六、程序測試與實(shí)現(xiàn)1、函數(shù)之間的調(diào)用關(guān)系 主函數(shù)調(diào)用算法函數(shù)2、主程序 void main()int w,arcs1010,m;Shortest(arcs);m=select(arcs);coutn-nendl;cout相應(yīng)結(jié)果:選取村莊m作為醫(yī)院endl;for(w=1;w=n;w+)if(w!=m) cout醫(yī)院到村莊w最短距離為：arcsmwendl;coutn;coutn-nendl;3、測試數(shù)據(jù)4、測試結(jié)果七、調(diào)試分析1調(diào)試過程主要是運(yùn)行編制好的程序，然后遇到錯(cuò)誤根據(jù)系統(tǒng)的提示，找到相關(guān)的問題所在。運(yùn)行完程序一次有錯(cuò)誤提示，是因?yàn)橥涥P(guān)閉上次調(diào)試的操作界面所導(dǎo)致的，這個(gè)問題經(jīng)常出現(xiàn)，基本是粗心所導(dǎo)致的2算法的時(shí)空分析：時(shí)間復(fù)雜度:O(n3)；空間復(fù)雜度:O(n2)Floyd算法適用于APSP(All Pairs Shortest Paths，多源最短路徑)，是一種動(dòng)態(tài)規(guī)劃算法，稠密圖效果最佳，邊權(quán)可正可負(fù)。此算法簡單有效，由于三重循環(huán)結(jié)構(gòu)緊湊，對于稠密圖，效率要高于執(zhí)行|V|次Dijkstra算法，也要高于執(zhí)行V次SPFA算法。優(yōu)點(diǎn)：容易理解，可以算出任意兩個(gè)節(jié)點(diǎn)之間的最短距離，代碼編寫簡單。缺點(diǎn)：時(shí)間復(fù)雜度比較高，不適合計(jì)算大量數(shù)據(jù)。八、遇到的問題及解決辦法主要問題就是Floyd算法的使用，通過參考教材及網(wǎng)上資料講解，進(jìn)一步認(rèn)知Floyd算法通過不斷編譯將其實(shí)現(xiàn)。九、心得體會對于算法的使用和掌握必須通過踐行和反復(fù)嘗試才能正確調(diào)試，耐心和認(rèn)真都是完成項(xiàng)目的重要關(guān)鍵。/源代碼如下：#includeusing namespace std;#define HUGE 1000000; /弧長int n;/村莊數(shù)目void Shortest(int arcs1010) /用Floyd算法求出最短距離的矩陣int u,v,w;cout=請輸入相應(yīng)初始指標(biāo)=endl;coutn;coutn;if(n6)system(cls);coutPlease input the number more than 6!endl;Shortest(arcs);for(v=1;v=n;v+)for(w=v;w=n;w+)if(v!=w)cout村莊v與村莊warcsvw;coutn;else arcsvw=0;for(v=1;v=n;v+)for(w=1;w=v;w+)arcsvw=arcswv;for(u=1;u=n;u+)for(v=1;v=n;v+)for(w=0;wn;w+)if(arcsvu+arcsuwarcsvw)arcsvw=arcsvu+arcsuw;int select(int arcs1010) / 選出使距離最長的那個(gè)村莊int v, w,i,max10; double Min=HUGE;int minmark;for(i=1;i=n;i+) maxi=0;for(v=1;v=n;+v)for(w=1;wmaxv) maxv=arcsvw;for(i=1;i=n;i+) if(maxiMin) Min=ma