數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-Floyd算法求解最短路徑

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告撰寫(xiě)要求數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告撰寫(xiě)要求（一）紙張與頁(yè)面要求 1采用國(guó)際標(biāo)準(zhǔn) A4 型打印紙或復(fù)印紙，縱向打印。 2封頁(yè)和頁(yè)面按照下面模板書(shū)寫(xiě)（正文為：小四宋體 1.5 倍行距） 。3圖表及圖表標(biāo)題按照模板中的表示書(shū)寫(xiě)。 （二） 課設(shè)報(bào)告書(shū)的內(nèi)容應(yīng)包括以下各個(gè)部分：（按照以下順序裝訂）1.封頁(yè)(見(jiàn)課設(shè)模版)2、學(xué)術(shù)誠(chéng)信聲明，所有學(xué)生必須本人簽字，否則教師拒絕給予成績(jī)。2.任務(wù)書(shū)(學(xué)生教師均要簽字,信息填寫(xiě)完整)3.目錄4.正文一般應(yīng)包括以下內(nèi)容: （1)題目介紹和功能要求（或描述）課程設(shè)計(jì)任務(wù)的詳細(xì)描述(注意不能直接抄任務(wù)書(shū)),將內(nèi)容做更詳細(xì)的具體的分析與描述；（2) 系統(tǒng)功能

2、模塊結(jié)構(gòu)圖 繪制系統(tǒng)功能結(jié)構(gòu)框圖及主要模塊的功能說(shuō)明； （3) 使用的數(shù)據(jù)結(jié)構(gòu)的描述: 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及用法說(shuō)明;（4) 涉及到的函數(shù)的描述 ; （5) 主要算法描述( 程序流程圖)（6) 給出程序測(cè)試/運(yùn)行的結(jié)果設(shè)計(jì)多組數(shù)據(jù)加以描述（包括輸入數(shù)據(jù)和輸出結(jié)果） （7) 課程設(shè)計(jì)的總結(jié)及體會(huì)（8) 參考文獻(xiàn) 格式要求：1作者，等. 書(shū)名.出版地：出版社，出版年 5.附錄：程序清單 (應(yīng)帶有必要的注釋) 沈陽(yáng)航空航天大學(xué)課課 程程 設(shè)設(shè) 計(jì)計(jì) 報(bào)報(bào) 告告課程設(shè)計(jì)名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：利用弗洛伊德（利用弗洛伊德（Floyd)Floyd)算法求解算法求解最短路徑最短路徑院（

3、系）：計(jì)算機(jī)學(xué)院專(zhuān) 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)(物聯(lián)網(wǎng)方向)班 級(jí)：34010105學(xué) 號(hào)：姓 名： 指導(dǎo)教師： 說(shuō)明：結(jié)論（優(yōu)秀、良好、中等、及格、不及格）作為相關(guān)教環(huán)節(jié)考核必要依據(jù)；格式不符合要說(shuō)明：結(jié)論（優(yōu)秀、良好、中等、及格、不及格）作為相關(guān)教環(huán)節(jié)考核必要依據(jù)；格式不符合要求；數(shù)據(jù)不實(shí)求；數(shù)據(jù)不實(shí),不予通過(guò)。報(bào)告和電子數(shù)據(jù)必須作為實(shí)驗(yàn)現(xiàn)象重復(fù)的關(guān)鍵依據(jù)。不予通過(guò)。報(bào)告和電子數(shù)據(jù)必須作為實(shí)驗(yàn)現(xiàn)象重復(fù)的關(guān)鍵依據(jù)。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 I 學(xué)術(shù)誠(chéng)信聲明 本人聲明本人聲明：所呈交的報(bào)告（含電子版及數(shù)據(jù)文件）是我個(gè)人在導(dǎo)師指導(dǎo)下獨(dú)立進(jìn)行設(shè)計(jì)工作及取得的研究結(jié)果。盡我所知，除了文中特別加以標(biāo)注或

4、致謝中所羅列的內(nèi)容以外，報(bào)告中不包含其他人己經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究結(jié)果，也不包含其它教育機(jī)構(gòu)使用過(guò)的材料。與我一同工作的同學(xué)對(duì)本研究所做的任何貢獻(xiàn)均己在報(bào)告中做了明確的說(shuō)明并表示了謝意。報(bào)告資料及實(shí)驗(yàn)數(shù)據(jù)若有不實(shí)之處，本人愿意接受本教學(xué)環(huán)節(jié)“不及格”和“重修或重做”的評(píng)分結(jié)論并承擔(dān)相關(guān)一切后果。 本人簽名: 日期： 2015 年 1 月 5 日沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 II 沈陽(yáng)航空航天大學(xué)沈陽(yáng)航空航天大學(xué)課課程程設(shè)設(shè)計(jì)計(jì)任任務(wù)務(wù)書(shū)書(shū)課程設(shè)計(jì)名稱(chēng) 數(shù)數(shù)據(jù)據(jù)結(jié)結(jié)構(gòu)構(gòu)課課程程設(shè)設(shè)計(jì)計(jì)專(zhuān)業(yè)計(jì)計(jì)算算機(jī)機(jī)科科學(xué)學(xué)與與技技術(shù)術(shù)（物物聯(lián)聯(lián)網(wǎng)網(wǎng)方方向向）學(xué)生姓名孫思孫思班級(jí)34010105學(xué)號(hào)2013040

5、101204題目名稱(chēng)起止日期2015年1月5日起至2015年1月16日止課設(shè)內(nèi)容和要求：給出一張無(wú)向圖，圖上每一個(gè)頂點(diǎn)表示一個(gè)城市，頂點(diǎn)之間的邊表示城市之間給出一張無(wú)向圖，圖上每一個(gè)頂點(diǎn)表示一個(gè)城市，頂點(diǎn)之間的邊表示城市之間存在路徑，邊上的權(quán)值表示城市間的路經(jīng)長(zhǎng)度。利用弗洛伊德（存在路徑，邊上的權(quán)值表示城市間的路經(jīng)長(zhǎng)度。利用弗洛伊德（FloydFloyd）算法求解）算法求解最短路徑求解任意兩個(gè)城市之間的最短路徑問(wèn)題。最短路徑求解任意兩個(gè)城市之間的最短路徑問(wèn)題。參考資料： 算法與數(shù)據(jù)結(jié)構(gòu)C 語(yǔ)言程序設(shè)計(jì)教教研研室室審審核核意意見(jiàn)見(jiàn)： 教教研研室室主主任任簽簽字字：指導(dǎo)教師（簽名）指導(dǎo)教師（簽名）

6、年月日學(xué)學(xué) 生（簽名）生（簽名）年月日沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 III 目目 錄錄第一章第一章 需求設(shè)計(jì)需求設(shè)計(jì)1.1 題目介紹 .11.2 功能要求 .2第二章第二章 程序設(shè)計(jì)程序設(shè)計(jì).32.1 詳細(xì)設(shè)計(jì) .32.1.1 總體模塊圖.32.1.2 函數(shù)描述.42.2 主要算法描述.5第三章第三章 使用說(shuō)明使用說(shuō)明.63.1 用法說(shuō)明.9第四章第四章 程序測(cè)試程序測(cè)試.114.1 運(yùn)行結(jié)果.114.2 存在的缺陷.12參考文獻(xiàn)參考文獻(xiàn).13附附 錄（關(guān)鍵部分程序清單）錄（關(guān)鍵部分程序清單）.14沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 1 第一章 需求設(shè)計(jì)1.1 題目介紹題目介紹給出一張無(wú)向圖，圖上每

7、一個(gè)頂點(diǎn)表示一個(gè)城市，頂點(diǎn)之間的邊表示城市之間存在路徑，邊上的權(quán)值表示城市間的路經(jīng)長(zhǎng)度。利用弗洛伊德（Floyd）算法求解最短路徑求解任意兩個(gè)城市之間的最短路徑問(wèn)題。將問(wèn)題分解為三個(gè)方面，第一個(gè)方面是對(duì)于無(wú)向圖的存儲(chǔ)問(wèn)題，第二個(gè)方面是實(shí)現(xiàn)弗洛伊德（Floyd）算法求解最短路徑，第三個(gè)方面是將最短路徑輸出。首先對(duì)于圖的建立選擇合適的存儲(chǔ)結(jié)構(gòu)，考慮到之后要用的弗洛伊德算法所以選擇采用鄰接矩陣存儲(chǔ)無(wú)向圖。然后采用弗洛伊德算法，該算法又叫插點(diǎn)法。是利用三重循環(huán)產(chǎn)生一個(gè)存儲(chǔ)每個(gè)結(jié)點(diǎn)最短距離的矩陣，基本思想是設(shè)置一個(gè) n 階矩陣D(k)，D(k)ij表示從 i 到 j 的路徑長(zhǎng)度，k 表示運(yùn)算步驟。用兩個(gè)

8、頂點(diǎn)之間邊的權(quán)值作為路徑長(zhǎng)度，無(wú)邊連接記做無(wú)窮，多次循環(huán)，向原路徑加入新的頂點(diǎn)，若增加的頂點(diǎn)使得路徑比原路徑短，則用新路徑代替原始路徑，將頂點(diǎn)信息存儲(chǔ)在另一個(gè)三維數(shù)組 p 中，pvwu存儲(chǔ)的是由 i 到 j 路徑經(jīng)過(guò)的所有頂點(diǎn)。三重循環(huán)執(zhí)行完畢最短路徑的信息存儲(chǔ)在兩個(gè)數(shù)組中。最后將最短路徑的信息輸出。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 2 1.2 功能要求功能要求一個(gè)無(wú)向圖用每個(gè)頂點(diǎn)代表城市，頂點(diǎn)之間邊的權(quán)重表示城市之間的路徑，將頂點(diǎn)信息和邊的信息輸入程序，即可得到每?jī)蓚€(gè)城市之間的最短路徑長(zhǎng)度值以及這條路徑經(jīng)過(guò)的城市?？梢詾榻ㄖ穯?wèn)題提供參考。設(shè)計(jì)環(huán)境：（1）WINDOWS 7 系統(tǒng)（2）Visual

9、C+開(kāi)發(fā)環(huán)境開(kāi)發(fā)語(yǔ)言：C 語(yǔ)言沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 3 第二章 程序設(shè)計(jì)2.1 詳細(xì)設(shè)計(jì)詳細(xì)設(shè)計(jì) 2.1.1 功能模塊圖功能模塊圖圖圖 2.1 功能模塊圖功能模塊圖用弗洛伊德算法求解最短路徑主函數(shù)輸出最短路徑信息調(diào)用弗洛伊德算法輸入無(wú)向圖頂點(diǎn)及權(quán)值沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 4 2.1.2 函數(shù)描述函數(shù)描述Find：根據(jù)名稱(chēng)得到指定頂點(diǎn)在頂點(diǎn)集合中的下標(biāo)，利用此函數(shù)找到頂點(diǎn)所在位置，進(jìn)而對(duì)無(wú)向圖賦權(quán)值。Create：創(chuàng)建無(wú)向圖的鄰接矩陣，因?yàn)槊織l邊都有權(quán)值，創(chuàng)建的是無(wú)向網(wǎng)的鄰接矩陣，用權(quán)值代替 1，沒(méi)有邊連接則為無(wú)窮。FLOYD：設(shè)置一個(gè) n 階矩陣 D(k)，D(k)ij表示從 i

10、 到 j 的路徑長(zhǎng)度，k 表示運(yùn)算步驟。用兩個(gè)頂點(diǎn)之間邊的權(quán)值作為路徑長(zhǎng)度，無(wú)邊連接記做無(wú)窮，多次循環(huán)，向原路徑加入新的頂點(diǎn)，若增加的頂點(diǎn)使得路徑比原路徑短，則用新路徑代替原始路徑，將頂點(diǎn)信息存儲(chǔ)在另一個(gè)三維數(shù)組 p 中，pvwu存儲(chǔ)的是由 i 到 j 路徑經(jīng)過(guò)的所有頂點(diǎn)。三重循環(huán)執(zhí)行完畢最短路徑的信息存儲(chǔ)在兩個(gè)數(shù)組中。主函數(shù)：在主函數(shù)里定義一個(gè)無(wú)向圖，一個(gè)三維矩陣 p，二維矩陣 D，對(duì)各個(gè)函數(shù)進(jìn)行調(diào)用，實(shí)現(xiàn)無(wú)向網(wǎng)的建立，運(yùn)用弗洛伊德算法求解出最短路徑，將路徑長(zhǎng)度以及經(jīng)過(guò)的頂點(diǎn)信息輸出。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 5 2.2 主要算法描述主要算法描述 開(kāi)始Int u，v，w；V=0；Vvex

11、num;Pvwu=false;+v;uvexnum;Wvexnum記錄相對(duì)路徑和權(quán)重+u；結(jié)束NYNYNY 圖圖 2.2.1 FLOYD 函數(shù)函數(shù)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 6 開(kāi)始Int i；i=0；ivexnum;vexsi=vexReturn 0;i+;結(jié)束YNNY 圖圖 2.2.2 Find 函數(shù)函數(shù)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 7 開(kāi)始創(chuàng)建矩陣Create(G)建立路徑和權(quán)值矩陣；FLOYD();輸出最短路徑；結(jié)束 圖圖 2.2.3 Main 函數(shù)函數(shù)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 8 開(kāi)始輸入邊數(shù)和結(jié)點(diǎn)值邊權(quán)值初始化K=0；kG.arcnumv1=Find(c1,G);arcsv1

12、v2=w;K+；結(jié)束輸入邊和權(quán)重； 圖圖 2.2.4 Create 函數(shù)函數(shù)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 9 第三章 使用說(shuō)明3.1 用法說(shuō)明用法說(shuō)明1.將頂點(diǎn)數(shù)和邊數(shù)輸出，中間用空格隔開(kāi)。圖 3.1.12.輸入頂點(diǎn)信息。圖 3.1.2沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 10 3.依次輸入每條邊連接的兩個(gè)頂點(diǎn)用空格間隔，邊的權(quán)值。圖 3.1.34.得到每?jī)蓚€(gè)頂點(diǎn)城市間的最短距離以及經(jīng)過(guò)的城市。圖 3.1.4.4沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 11 第四章 程序測(cè)試4.1 運(yùn)行結(jié)果運(yùn)行結(jié)果圖 4.1沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 12 4.2 存在的缺陷存在的缺陷 1.無(wú)向圖的頂點(diǎn)信息只能用一個(gè)字符表示。

13、將存儲(chǔ)頂點(diǎn)信息的字符型改為字符數(shù)組就可以完善該缺陷。2.將兩點(diǎn)的最短路徑輸出時(shí)只能顯示經(jīng)過(guò)的頂點(diǎn)有哪些，無(wú)法顯示真實(shí)的路徑順序。3.輸入無(wú)向圖信息只能用手動(dòng)輸入，無(wú)法用文件直接寫(xiě)入。4.輸入不符合要求的數(shù)據(jù)會(huì)使程序自動(dòng)停止。沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 13 參考文獻(xiàn)1 張長(zhǎng)海.C 語(yǔ)言程序設(shè)計(jì)M.北京：高等教育出版社，20062 吳啟武.C 語(yǔ)言課程設(shè)計(jì)案例精編.北京:清華大學(xué)出版社,2011.3 郭翠英.C 語(yǔ)言課程設(shè)計(jì)案例精編.北京:中國(guó)水利水電出版社,2004.4 姜靈芝, 余鍵.C 語(yǔ)言課程設(shè)計(jì)案例精編.北京:清華大學(xué)出版社,2008.5 黃明, 梁旭, 萬(wàn)洪莉.C 語(yǔ)言課程設(shè)計(jì).北

14、京:電子工業(yè)出版社,2006沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 14 附 錄（關(guān)鍵部分程序清單）#include stdio.h#include stdlib.h#define MAX 20#define INFINITY 9999typedef bool PathMatrixMAXMAXMAX;typedef int DistanceMatrixMAXMAX;typedef structint vexnum,arcnum; char vexsMAX; int arcsMAXMAX;MGraph;int Find(char vex, MGraph MG)/根據(jù)名稱(chēng)得到指定頂點(diǎn)在頂點(diǎn)集合中的下標(biāo) ve

15、x表示頂點(diǎn) / return 如果找到則返回下標(biāo)，否則返回 int i; for (i=0;iMG.vexnum;i+) if (MG.vexsi = vex) return i; 沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 15 return 0;void Create(MGraph &G) int i,j,k,v1,v2,w; printf(請(qǐng)輸入頂點(diǎn)數(shù)和邊數(shù):); scanf(%d %d,&G.vexnum,&G.arcnum); getchar(); for(i=0;iG.vexnum;i+) printf(請(qǐng)輸入第%d 個(gè)結(jié)點(diǎn)：,i+1); scanf(%c,&G.

16、vexsi); getchar(); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.arcsij=INFINITY; for(k=0;kG.arcnum;k+) char c1,c2; printf(請(qǐng)輸入與第%d 條邊相連的兩條邊 v1 v2:,k+1); scanf(%c,&c1); getchar(); scanf(%c,&c2); printf(請(qǐng)輸入該邊的權(quán)重：);沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 16 scanf(%d,&w); getchar(); v1=Find(c1,G); v2=Find(c2,G); G.a

17、rcsv1v2=w; G.arcsv2v1=w; void FLOYD(MGraph G,PathMatrix &P,DistanceMatrix &D) int v,w,u,i; for(v=0;vG.vexnum;+v)for(w=0;wG.vexnum;+w) Dvw=G.arcsvw; for(u=0;uG.vexnum;+u)Pvwu=false; if (DvwINFINITY) Pvwv=true; Pvww=true; for(u=0;uG.vexnum;+u)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 17 for(v=0;vG.vexnum;+v)for(w=0;wG.v

18、exnum;+w)if (Dvu+DuwDvw)Dvw=Dvu+Duw;for(i=0;iG.vexnum;+i)Pvwi=Pvui|Puwi;int main() MGraph G; int i,j,k; Create(G); PathMatrix p; DistanceMatrix D; FLOYD(G,p,D); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+)if(i=j)continue;沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 18 elseprintf(%c 到%c 經(jīng)過(guò)的頂點(diǎn)有:,G.vexsi,G.vexsj);for(k=0;kG.vexnum;k+)if(pijk=0)continue;elseprintf(%c ,G.vexsk);printf(最短路徑長(zhǎng)度為: %dnn,Dij); return 0;沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)報(bào)告 19 課程設(shè)計(jì)總結(jié)：課程設(shè)計(jì)總結(jié)：此次課程設(shè)計(jì)中，我了解到了許多以前不太會(huì)的知識(shí)，也在對(duì)程序的不斷的調(diào)試中認(rèn)識(shí)到調(diào)試時(shí)的細(xì)心是很重要的，這些都讓我受益匪淺。譬如，getchar()的使用，用在輸入字