校園導(dǎo)航問題

1、安徽建筑大學(xué)課 程 設(shè) 計 報 告 課程名稱： 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計 題 目： 校園導(dǎo)航問題 院 系： 數(shù)理系 專 業(yè)： 信息與計算科學(xué) 班 級： 02班 （專升本） 學(xué) 號： 12207210220 姓 名： 穆海山 課程設(shè)計的目的數(shù)據(jù)結(jié)構(gòu)課程主要是研究非數(shù)值計算的程序設(shè)計問題中所出現(xiàn)的計算機操作對象以及它們之間的關(guān)系和操作的學(xué)科。數(shù)據(jù)結(jié)構(gòu)是介于數(shù)學(xué)、計算機軟件和計算機硬件之間的一門計算機專業(yè)的核心課程，它是計算機程序設(shè)計、數(shù)據(jù)庫、操作系統(tǒng)、編譯原理及人工智能等的重要基礎(chǔ)，廣泛的應(yīng)用于信息學(xué)、系統(tǒng)工程等各種領(lǐng)域。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)是為了將實際問題中所涉及的對象在計算機中表示出來并對它們進行處理。

2、通過課程設(shè)計可以提高學(xué)生的思維能力，促進學(xué)生的綜合應(yīng)用能力和專業(yè)素質(zhì)的提高。通過此次課程設(shè)計主要達到以下目的：n 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力；n 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基本方法和技能；n 提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力；n 訓(xùn)練用系統(tǒng)的觀點和軟件開發(fā)一般規(guī)范進行軟件開發(fā)，培養(yǎng)軟件工作者所應(yīng)具備的科學(xué)的工作方法和作風(fēng)。需求分析設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達另一場所的最佳路徑（最短路徑）。概念設(shè)計1、Floy

3、d算法的原理定義：Dki,j 表示賦權(quán)圖中從結(jié)點vi出發(fā)僅通過v0，v1，vk-1中的某些結(jié)點到達vj的最短路徑的長度，若從vi到vj沒有僅通過v0，v1，vk-1 的路徑，則Di,j= 即 D-1i,j 表示賦權(quán)圖中從結(jié)點vi到vj的邊的長度，若沒有從結(jié)點vi到vj的邊，則Di,j= D0i,j 表示賦權(quán)圖中從結(jié)點vi到vj的”最短”路徑的長度, 這條路上除了可能有v0外沒有其它結(jié)點D1i,j 表示賦權(quán)圖中從結(jié)點vi到vj的”最短”路徑的長度, 這條路上除了可能有v0，v1外沒有其它結(jié)點根據(jù)此定義，Dki,j=min Dk-1i,j , Dk-1i,k-1+Dk-1k-1,j 定義：path

4、i,j表示從結(jié)點vi到vj的“最短”路徑上vi的后繼結(jié)點求每對頂點之間的最短路徑。依次計算矩陣A(0)，A(1)，A(n)。A(0)為鄰接矩陣，計算A(k)時，A(k)(i,j)=minA(k-1)(i,j), （A(k-1)(i,k)+A(k-1)(k,j)）。技巧：計算A(k)的技巧。第k行、第k列、對角線的元素保持不變，對其余元素，考查A(i,j)與A(i,k)+A(k,j) （第k列i“行”元素加上第k行j“列”元素，簡記為“行+列”），如果后者更小則替換A(i,j)，同時修改路徑。程序模塊1. 用Floyd算法求有向網(wǎng)G中各對頂點v和w之間的最短路徑 #define INFINITY

5、 10000 /*定義一個權(quán)值的最大值*/#define Max 10 /* 假設(shè)有向網(wǎng)頂點數(shù)最大為10 */int aMaxMax,PMaxMax;void ShortestPath_Floyd () /*用Floyd算法求有向網(wǎng)G中各對頂點v和w之間的最短路徑P及其帶權(quán)長度a。若Pij=k，則表示k是從i到j(luò)當前求得的最短路徑上的頂點*/ for（i=0；iD；i+） /初始化距離和路徑矩陣,D為頂點個數(shù) for（j=0；j0& aijINFINIFY) /有直接路徑 Pij=i; else Pij=-1; for（k=0； kD； k+） for（i=0； iD； i+） for（j=0

6、；jD；j+） if （aik+akjaij） /從v經(jīng)u到w的一條路徑更短 aij=aik+akj； Pij=k; /* ShortestPath_Floyd*/ void Print_Flod( )2 /打印最短路徑長度及最短路徑 for(int i=0;iD;i+) for(int j=0;j,x);算法的設(shè)計（一）算法描述Step 1 初始化有向圖的成本鄰矩陣D、路徑矩陣path 若從結(jié)點vi到vj有邊，則Di,j= vi到vj的邊的長度，pathi,j= i； 否則Di,j=， pathi,j=-1Step 2 刷新D、path 對k=1,2,n 重復(fù)Step 3和Step 4Ste

7、p 3 刷新行 對 i=1,2,n 重復(fù)Step 4Step 4 刷新Mij 對 j=1,2,n 若Dk-1i,k+Dk-1k,j ,x); printf(-);void Print_Flod( )/打印最短路徑長度及最短路徑 int i,j;for( i=0;iD;i+) for( j=0;jD;j+) if(i!=j) g(i); printf(到); g(j);/printf(from V%d to V%d: ,i,j); printf(: ); dist(i,j); g(j);/printf(V%d,j); printf( (The length is: %d)n,aij);void

8、main() int i,j,k; /*用Floyd算法求有向網(wǎng)G中各對頂點v和w之間的最短路徑P及其帶權(quán)長度a。若Pij=k，則表示k是從i到j(luò)當前求得的最短路徑上的頂點*/ for(i=0;iD;i+) /初始化距離和路徑矩陣,D為頂點個數(shù) for(j=0;j0& aijINFINITY) /有直接路徑 Pij=i; else Pij=-1; for(k=0; kD; k+) for(i=0; iD; i+) for(j=0;jD;j+) if (aik+akjaij) /從v經(jīng)u到w的一條路徑更短 aij=aik+akj; Pij=k; Print_Flod( );測試結(jié)果初始化 “宿舍

9、 ,主教 ,南食堂,超市 ,銀行 ,逸夫樓,圖書館,北食堂,南校門, 北小門之間的鄰接矩陣為： aMaxMax=0, 11, 2, 33, 4, 55 ,6, 75 , 88 ,3,11, 0, 10, 3, 44, 5, 66, 70, 8, 9,2, 10, 0, 3, 4, 1000, 66, 7, 8, 1000,33, 3, 3, 0, 40, 51, 6, 70, 3, 90,4, 44, 4, 40, 0, 50, 6, 7, 8, 9,55,5, 1000,51, 50, 0, 6, 1000, 80, 9,6, 66, 66, 6, 6, 6, 0, 6, 8, 60,75,

10、70, 7, 70, 7, 1000, 6, 0, 10, 100,88,8, 8, 3, 8, 80, 8, 10, 0, 20,3,9, 1000, 90, 9, 9, 60, 100, 20, 0;時間復(fù)雜度Floyd算法中初始化部分由一個循環(huán)組成，其中外循環(huán)運行n次，內(nèi)循環(huán)也運行n次，初始化部分的時間復(fù)雜度為O(n2)。迭代生成矩陣A和路徑nextvex的部分為三個循環(huán)的嵌套，其時間復(fù)雜度為O(n3)Floyd算法的時間復(fù)雜度為O(n3)經(jīng)驗和體會1 經(jīng)驗通過實驗，我覺得在編程過程中要注意盡可能發(fā)揮已有代碼的最大作用，想該實驗中的減法運算，如果在編一個減法運算，又要把加法運算中的很多代

11、碼重復(fù)寫一次，但我們這樣到加法與減法運算的區(qū)別，加入一個type()函數(shù)，就把問題簡化了不少，而且再次用到了原來的加法運算。2 體會我覺得編程過程中，語法的問題一定要注意，如果編寫的過程中注意到了，編譯就很可能會快一些通過，這樣我們有更多的時間來檢查程序中的其它問題。其次編程中我們要考慮很多特殊情況，因為程序往往成功后對大多數(shù)一般的情況都成功，但對少數(shù)特殊情況就可能出現(xiàn)錯誤，在這個程序中體現(xiàn)的非常突出，本來很早就把程序完成了，但對于特殊情況經(jīng)常出錯。我感覺一個好的程序要包括各種特殊情況的處理。參考文獻1 Richard F. Gilberg, Behrouz A. Forouzan. Data Structure.