數(shù)據(jù)結(jié)構(gòu)1236newVIP

1、 課程設(shè)計(jì)說(shuō)明書（論文） 第 I 頁(yè) 交通咨詢系統(tǒng)的開(kāi)發(fā)摘 要 此次課程設(shè)計(jì)主要運(yùn)用圖的知識(shí)，借助弗洛伊德算法實(shí)現(xiàn)最短路徑的求解，完成了時(shí)間復(fù)雜度的計(jì)算,并依此實(shí)現(xiàn)交通系統(tǒng)的開(kāi)發(fā)。首先對(duì)算法進(jìn)行分析，即弗洛伊德思路算法思想的闡述，然后編寫最短路程序。在算法設(shè)計(jì)是，首先生成鄰接矩陣，然后再進(jìn)行逐點(diǎn)比較，最后算出任意兩點(diǎn)之間的最短路徑。完成程序設(shè)計(jì)后，并舉例完成交通咨詢系統(tǒng)的開(kāi)發(fā)。最后并擴(kuò)展算法的應(yīng)用即工程安排、設(shè)備更新等實(shí)際問(wèn)題 。關(guān)鍵詞：弗洛伊德，最短路徑，算法，圖，交通咨詢系統(tǒng)課程設(shè)計(jì)說(shuō)明書（論文） 第 II 頁(yè) 目 錄1 緒 論.12 課題描述 .13 算法時(shí)間復(fù)雜度 .14 弗洛伊德算法

2、的思路 .25 弗洛伊德算法設(shè)計(jì) .26 具體實(shí)例 .47 實(shí)例分析 .6總 結(jié).9參考文獻(xiàn).10課程設(shè)計(jì)說(shuō)明書（論文） 第 1 頁(yè) 1 緒 論 自 1946 年第一臺(tái)計(jì)算機(jī)問(wèn)世以來(lái)，計(jì)算機(jī)產(chǎn)業(yè)的飛速發(fā)展已遠(yuǎn)遠(yuǎn)超出人們對(duì)它的預(yù)料，在某些生產(chǎn)線上，甚至一秒鐘就能生產(chǎn)出一臺(tái)微型計(jì)算機(jī)，產(chǎn)量猛增，價(jià)格低廉，這就使得它的應(yīng)用范圍迅速擴(kuò)展。如今，計(jì)算機(jī)已深入到人類社會(huì)的各個(gè)領(lǐng)域。計(jì)算機(jī)的應(yīng)用已不再局限于科學(xué)計(jì)算，而更多的用于控制、管理及數(shù)據(jù)處理等非數(shù)值計(jì)算的處理工作。于此相應(yīng)，計(jì)算機(jī)加工處理的對(duì)象由純粹的數(shù)值發(fā)展到字符、表格和圖像等各種具有一定結(jié)構(gòu)的數(shù)據(jù)，這就給程序設(shè)計(jì)帶來(lái)一些新的問(wèn)題。為了編寫出一個(gè)“

3、好”的程序，必須分析待處理的對(duì)象的特性以及各種處理對(duì)象之間存在的關(guān)系。這就是“數(shù)據(jù)結(jié)構(gòu)”這門學(xué)科的形成和發(fā)展的背景。2 課題描述最短路問(wèn)題 short-path problem，若網(wǎng)絡(luò)中的每條邊都有一個(gè)數(shù)值 (長(zhǎng)度、成本、時(shí)間等)，則找出兩節(jié)點(diǎn) (通常是源節(jié)點(diǎn)和阱節(jié)點(diǎn) )之間總權(quán)和最小的路徑就是最短路問(wèn)題。最短路問(wèn)題是網(wǎng)絡(luò)理論解決的典型問(wèn)題之一，可用來(lái)解決交通咨詢、管路鋪設(shè)、線路安裝、廠區(qū)布局和 設(shè)備更新等實(shí)際問(wèn)題 。3 算法時(shí)間復(fù)雜度算法來(lái)決定的。整個(gè)算法的執(zhí)行時(shí)間與該基本操作（乘法）重復(fù)執(zhí)行的次數(shù) n3成正比，故時(shí)間復(fù)雜度為 。3( )()T nO n4 弗洛伊德算法的思路 UYI VEW

4、RWE 次算法是從帶權(quán)鄰接矩陣 cost 出發(fā)，其基本思想如下： 假設(shè)求從定點(diǎn)到的最短路徑，如果從到有弧，則從到存在一條長(zhǎng)度為ivjvivjvivjvarcsijd 的路徑，該路徑不一定是最短路徑，尚需進(jìn)行 n 次試探。首先考慮路徑（vi, ,）是否存在(即判斷弧（,） ，和（, ）是否存在)。如果存在，則0vjviv0v0vjv比較（，）和（， , ）的路徑長(zhǎng)度取長(zhǎng)度較短者為從到的中間頂點(diǎn)的ivjviv0vjvivjv序號(hào)不大于 0 的最短路徑。加入在路徑上再增加一個(gè)頂點(diǎn)，也就是說(shuō)，如果1v課程設(shè)計(jì)說(shuō)明書（論文） 第 2 頁(yè) （,v1）和（v1, ）分別是當(dāng)前找到的中間頂點(diǎn)的序號(hào)不大于 0

5、的最短路徑，ivjv那么， （vi,v1,., ）就有可能是從到的中間頂點(diǎn)的序號(hào)不大于 1 的最短路jvivjv徑。將它和已經(jīng)得到的從到中間頂點(diǎn)序號(hào)不大于 0 的最短路徑相比較，從中選出ivjv中間頂點(diǎn)不大于 1 的最短路徑之后，再增加一個(gè)頂點(diǎn)，繼續(xù)進(jìn)行試探。依次類推。2v在一般情況下，若（, ）和(, )分別是從到的中間頂點(diǎn)的序號(hào)不ivkvkvjvivjv大于的最短路徑，則將（, , ）和已經(jīng)得到的從到且序號(hào)不大1k ivkvjvivjv于的最短路徑相比較，取長(zhǎng)度較短者便是從到的中間頂點(diǎn)的序號(hào)不大于的1k ivjvk最短路徑。這樣在經(jīng)過(guò) n 次比較后，最后求得的必是從到的最短路徑。ivjv5

6、 弗洛伊德算法設(shè)計(jì) 弗洛伊德算法最短路程序如下：#define n 6#define MaxNum 1000 /*定義一個(gè)最大數(shù)*/#include/* 定義鄰接矩陣類型 */typedef int adjmatrixnn; /* 建立圖的鄰接矩陣 */void CreatMatrix(adjmatrix G)int i,j,k,e,arcnum; printf(圖中有%d 個(gè)頂點(diǎn)n,n); for(i=0;in;i+) for(j=0;jn;j+) if(i=j) Gij=0; /*對(duì)角線的值置為 0*/ else Gij=MaxNum; /*其它位置的值初始化為一個(gè)最大數(shù)*/ printf

7、(請(qǐng)輸入邊的個(gè)數(shù)(5-30):);課程設(shè)計(jì)說(shuō)明書（論文） 第 3 頁(yè) scanf(%d,&arcnum); printf(請(qǐng)輸入邊的信息,按照起點(diǎn),終點(diǎn),權(quán)值的形式輸入:n); for(k=0;karcnum;k+) scanf(%d,%d,%d,&i,&j,&e); Gj-1i-1=Gi-1j-1=e; /*弗洛伊德算法*/void Floyd(int Gnn, int Ann, int Pnn) int i, j, k; for (i=0; in; i+) for(j=0;jn;j+) Aij=Gij;Pij=0; for (k=0; kn; k+) for

8、 (i=0; in; i+) for (j=0; jn; j+) if(Aik +AkjAij) Pij=k+1;Aij=Aik+Akj; void main() int i,j; adjmatrix G,A,P; CreatMatrix(G); Floyd(G, A, P); printf(原圖的臨界矩陣n); for(i=0;in;i+) for(j=0;jn;j+) printf(t%d,Gij); printf(nn);課程設(shè)計(jì)說(shuō)明書（論文） 第 4 頁(yè) printf(兩點(diǎn)間的距離n); for(i=0;in;i+) for(j=0;jn;j+) printf(t%d,Aij); pr

9、intf(nn); printf(兩點(diǎn)間路徑的中介點(diǎn)n); for(i=0;in;i+) for(j=0;jn;j+)printf(t%d,Pij); printf(nn);6 具體實(shí)例舉個(gè)簡(jiǎn)單的例子,假設(shè)有六座城市，現(xiàn)在有一個(gè)游客要從城市 到城市觀光旅游，ij他向交通咨詢系統(tǒng)咨詢乘座哪一路車劃算，即花費(fèi)最少。現(xiàn)在我們幫旅客解決這個(gè)問(wèn)題。比如這六座城市的地理位置的布局，其中權(quán)值代表兩座城市之間的距離（） 。kmA111B2C3D4F6654535403016802220課程設(shè)計(jì)說(shuō)明書（論文） 第 5 頁(yè) 運(yùn)行上面設(shè)計(jì)的程序，運(yùn)行結(jié)果：圖中有 6 個(gè)頂點(diǎn)請(qǐng)輸入邊的個(gè)數(shù)（5-30） ； 101,2

10、,452,3,653,5,805,6,566,1,404,1,204,2,224,3,354,5,304,6,16原圖的臨界矩陣 兩點(diǎn)間的距離 04510002010004045065221000100010006503580100020223503016100010008030056401000100016560042552050364205722523855570356551202235030165052653004636385116460E556課程設(shè)計(jì)說(shuō)明書（論文） 第 6 頁(yè) 兩點(diǎn)間路徑的中介點(diǎn) 040444400444440444000000440004440440結(jié)果分析：A 城

11、市到 B、C、D、E、F 的最短距離依次為 42、55、20、50、36，中間經(jīng)過(guò)4、0、4、4、4；B 到 C、D、E、F 的最短距離依次為 57、22、52、38，中間經(jīng)過(guò)0、4、4、4；C 到 D、E、F 的最短距離依次為 35、65、51，中間經(jīng)過(guò) 4、4、4；D 到 E、F 的最短距離依次為 30、16，中間不經(jīng)過(guò)任何城市；E 到 F 的最短路徑為 46，中經(jīng)過(guò)城市 4。 （其中 0 代表不經(jīng)過(guò)任何城市。 ）由以上分析可知城市 4 是中心城市?，F(xiàn)實(shí)生活中的交通網(wǎng)是很復(fù)雜的，我們只需調(diào)整其中的節(jié)點(diǎn) n 即可，即可以完成大型的交通咨詢系統(tǒng)的開(kāi)發(fā)。課程設(shè)計(jì)說(shuō)明書（論文） 第 7 頁(yè) 總 結(jié)

12、此次數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，歷經(jīng)一周時(shí)間，雖然時(shí)間緊任務(wù)重，但是還是按時(shí)完成了課程設(shè)計(jì)。由于前期沒(méi)有開(kāi)設(shè) C 語(yǔ)言，數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)一直都很吃力，在授課期間，葉老師給我們適當(dāng)?shù)难a(bǔ) C 語(yǔ)言的必要知識(shí)，這給我們的學(xué)習(xí)帶來(lái)了很大的幫助。這次課程設(shè)計(jì)我選作的是基于左端路徑問(wèn)題的交通咨詢系統(tǒng)的開(kāi)發(fā)，并列舉實(shí)例，進(jìn)行此算法的應(yīng)用。算法實(shí)現(xiàn)使用的是弗洛伊德算法，闡述了弗洛伊德的算法的設(shè)計(jì)思想和程序?qū)崿F(xiàn)。完成最短路徑設(shè)計(jì)后，并對(duì)算法的應(yīng)用進(jìn)行擴(kuò)展比如解決交通咨詢、管路鋪設(shè)、線路安裝、廠區(qū)布局和設(shè)備更新等實(shí)際問(wèn)題 ，并且對(duì)工程安排、設(shè)備更新等進(jìn)行了詳細(xì)的闡述。在做課程設(shè)計(jì)的過(guò)程中，我遇到了很多困難。比如不知道如何定義結(jié)構(gòu)等，知道算法的思想但不知道用語(yǔ)言如何實(shí)現(xiàn)，這些困難困惑了我很久，對(duì)虧了葉老師的耐心指導(dǎo)，使我的課程設(shè)計(jì)能夠得以順利的完成。通過(guò)這次