【導(dǎo)讀】本文主要是介紹利用Linux系統(tǒng)和QT制作校園導(dǎo)航系統(tǒng)的設(shè)計方法。個景點的位置、介紹，查看學(xué)校的建筑物，包括建筑物的圖片以及建筑物的描述。景點之間的所有路徑，有助于來往者跟好的選擇路徑。設(shè)計出基本功能并與界面相結(jié)合?？梢圆榭磸脑摻ㄖ锏剿衅渌ㄖ锏穆窂叫畔?。

　　

【正文】 種方案的成本和效益，還應(yīng)該在充分權(quán)衡各種方案的利弊的基礎(chǔ)上 ,推薦一個較好的系統(tǒng) (最佳方案 ),并且制定實現(xiàn)所推薦的系統(tǒng)的詳細計劃。如果用戶 接受分析員推薦的系統(tǒng)，則可以著手完成本階段的另一項主要工作。 上面的工作確定了解決問題的策略以及目標系統(tǒng)需要哪些程序，但是，怎樣設(shè)計這些程序呢？結(jié)構(gòu)設(shè)計的一條基本原理就是程序應(yīng)該模塊化，也就是一個大程序應(yīng)該由許多 規(guī)模適中的模塊按合理的層次結(jié)構(gòu)組織而成?？傮w設(shè)計階段的第二項主要任務(wù)就是設(shè)計軟件的結(jié)構(gòu)，也就是確定程序由哪些模塊組成以及模塊間的關(guān)系。通常用層次 圖或結(jié)構(gòu)圖描繪軟件的結(jié)構(gòu)。 在了解了系統(tǒng)總體設(shè)計的概念及要求后，完成自己的總體設(shè)計，由于這個項目是用于畢業(yè)設(shè)計的，并不是用于其他用途的，所以，就 只有一個方案，沒有顧及成本，只有軟件方面，就是一個人開發(fā)的。 系統(tǒng)總體設(shè)計描述 在對需求分析進行了系統(tǒng)研究后，決定了總體設(shè)計的方案。 首先有一個系統(tǒng)的主界面，在這個主界面上，并沒有關(guān)于導(dǎo)航的其他信息，只有進入導(dǎo)航的入口，和有關(guān)開發(fā)人員的信息（主要包括學(xué)校，所在實訓(xùn)基地，開發(fā)人員的基地指導(dǎo)老師 ,還有開發(fā)人員自己的信息查詢），除此之外，還有系統(tǒng)時間的顯示，查看當(dāng)時的時間，還有學(xué)校名字的顯示。其次，是導(dǎo)航系統(tǒng)的主界面，在主界面中可以查看景點信息，查看路徑，選擇終點和起點，在不需要再使用系統(tǒng)時，可以選擇退 出系統(tǒng)。 系統(tǒng)總體設(shè)計模塊劃分 在了解了需求，分析了需求分析后，劃分出了模塊。主要的模塊由：顯示系統(tǒng)主界面 ，顯示導(dǎo)航系統(tǒng)主界面，查詢導(dǎo)航有關(guān)人員的模塊。 北京郵電大學(xué)畢業(yè)論文設(shè)計 12 在導(dǎo)航系統(tǒng)主界面主界面中有小的模塊，主要的模塊有：退出系統(tǒng)模塊，顯示景點信息模塊，查詢路徑模塊，選擇和更改起始點模塊。 主要模塊劃分圖 在劃分完模塊后，主要的模塊由顯示系統(tǒng)主界面，有顯示校園導(dǎo)航系統(tǒng)主界面，還有查詢相關(guān)等三個主要模塊，得到主要的模塊劃分框圖 ,如圖 41 所示： 圖 41 主要模塊劃分圖 顯示系統(tǒng)主界 面模塊設(shè)計 在我的系統(tǒng)中，首先現(xiàn)實的是整個系統(tǒng)的主界面，并不會直接進入到導(dǎo)航界面，顯得有點突兀，所以有一個整個系統(tǒng)的主界面，在從這個界面中進入到導(dǎo)航系統(tǒng)的主界面，進行過渡一下 ,下面是我的這個界面的框圖。 其中，在選擇進入導(dǎo)航系統(tǒng)時，有兩種選擇： ， 2 在主頁面上，有一張學(xué)校的圖片，點擊圖片也會進入到導(dǎo)航主系統(tǒng)。 如圖 42 所示： 圖 42 系統(tǒng)主界面模塊細分圖 在退出系統(tǒng)時，也可以有多種選擇，可以選擇直接推出，也可以選擇重新使用系統(tǒng)，提供多種選擇。 北京郵電大學(xué)畢業(yè)論文設(shè)計 13 如圖 43 所示： 圖 43 退 出系統(tǒng)模塊劃分圖 查詢導(dǎo)航有關(guān)人員模塊設(shè)計 不論是在系統(tǒng)主界面，還是在導(dǎo)航主界面中，在界面的下端都有一個模塊是用來查詢與該畢業(yè)設(shè)計有關(guān)的人員，有關(guān)的人員主要有所在的學(xué)校、所在的培訓(xùn)基地，開發(fā)者本人，以及開發(fā)者的基地指導(dǎo)老師，相應(yīng)的模塊設(shè)計如下。 如圖 44 所示： 圖 44 查看相關(guān)人員模塊細分圖 導(dǎo)航主界面的模塊的設(shè)計 在這個畢業(yè)設(shè)計中，最重要的是，校園導(dǎo)航系統(tǒng)的實現(xiàn)。在這個系統(tǒng)中，我要實現(xiàn)的功能有查詢兩個景點之間的最短路徑，兩個景點間的所有路徑，每個景點的信息查詢（主要包 括景點描述信息，該景點可以到達的所有其他景點的最短路徑信息），還有在切換起始點和終點的時候，同時出現(xiàn)這兩個景點的圖片，當(dāng)點擊查詢路徑按鈕是，則在該位置上出現(xiàn)的是學(xué)校的總體布局圖。 首先，得到導(dǎo)航系統(tǒng)主界面的主功能圖。如圖 45 所示： 圖 45 校園導(dǎo)航主界面模塊劃分圖 北京郵電大學(xué)畢業(yè)論文設(shè)計 14 在查詢路徑的時候，同時需要干兩件事，在一個地方現(xiàn)實最短路徑及其長度，在另一個地方顯示所有這兩個景點之間的路徑。 如圖 46 所示： 圖 46 路徑查詢模塊細分圖 本章總結(jié) 在本章中，我主要的工作就是，完成總體設(shè)計，得到模塊劃 分圖，和各個模塊的細分圖，在接下來的系統(tǒng)設(shè)計中，以此為基礎(chǔ)來進行詳細設(shè)計。 北京郵電大學(xué)畢業(yè)論文設(shè)計 15 5 詳細設(shè)計 詳細設(shè)計概述 總體設(shè)計階段以比較抽象概括的方式提出了解決問題的辦法。詳細設(shè)計階段的任務(wù)就是把解法具體化，也就是回答下面這個關(guān)鍵問題：“應(yīng)該怎樣具體地實現(xiàn)這個系統(tǒng)呢？”。 這個階段的任務(wù)還不是編寫程序，而是設(shè)計出程序的詳細規(guī)格說明。這種規(guī)格說明的作用很類似于其他工程領(lǐng)域中工程師經(jīng)常使用的工程藍圖，它們應(yīng)該包含必要的細節(jié)，程序員可以根據(jù)它們寫出實際的程序 代碼。 研究一下一般的詳細設(shè)計主要需要完成什么樣的功能。 詳細設(shè)計的主要任務(wù)是設(shè)計每個模塊的實現(xiàn)算法、所需的局部數(shù)據(jù)結(jié)構(gòu)。詳細設(shè)計的目標有兩個：實現(xiàn)模塊功能的算法要邏輯上正確和算法描述要簡明易懂。 基本任務(wù)： (1)為每個模塊進行詳細的算法設(shè)計。用某種圖形、表格、語言等工具將每個模塊處理過程的詳細算法描述出來。 (2)為模塊內(nèi)的數(shù)據(jù)結(jié)構(gòu)進行設(shè)計。對于需求分析、概要設(shè)計確定的概念性的數(shù)據(jù)類型進行確切的定義。 (3)為數(shù)據(jù)結(jié)構(gòu)進行物理設(shè)計，即確定數(shù)據(jù)庫的物理結(jié)構(gòu)。物理結(jié)構(gòu)主要指數(shù)據(jù)庫的存儲記錄格式、存儲記錄安排 和存儲方法，這些都依賴于具體所使用的 數(shù)據(jù)庫系統(tǒng) 。 (4)其他設(shè)計：根據(jù)軟件系統(tǒng)的類型，還可能要進行以下設(shè)計： ① 代碼設(shè)計。為了提高數(shù)據(jù)的輸入、分類、存儲、檢索等操作，節(jié)約內(nèi)存空間，對數(shù)據(jù)庫中的某些數(shù)據(jù)項的值要進行代碼設(shè)計。 ② 輸入 /輸出格式設(shè)計。 ③ 人機對話設(shè)計。對于一個實時系統(tǒng)，用戶與計算機頻繁對話，因此要進行對話方式、內(nèi)容、格式的具體設(shè)計。 (5)編寫詳細設(shè)計說明書。 (6)評審。對處理過程的算法和數(shù)據(jù)庫的物理結(jié)構(gòu)都要評審。 由于該項目是自己實現(xiàn)的，所以就沒有復(fù)雜的流程。 校園導(dǎo)航系統(tǒng)主程序流程圖 在確定了總體設(shè)計后，畫出詳細設(shè)計中，主流程圖。點擊開始就進入了導(dǎo)航主系統(tǒng)，進入到主系統(tǒng)后，就會實例化一系列的類的對象，主要是窗口的實例化，還有圖的實例化，所有的實例化后，就可以進行導(dǎo)航了。 北京郵電大學(xué)畢業(yè)論文設(shè)計 16 如圖 51 所示： 圖 51 程序總體流程圖 單源最短路徑算法介紹 在我的程序中，需要使用到路徑查詢，最重要的就是最短路徑查詢，所以需要設(shè)計一下所使用的算法。 Dijkstra(迪杰斯特拉 )算法 Dijkstra(迪杰斯特拉 )算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。 Dijkstra 算法能保證找到從起點到終點的一條最優(yōu)路徑，只要路徑權(quán)值不會為負。 Dijkstra 一般的表述通常有兩種方式，一種用永久和臨時標號方式，一種是用 OPEN, CLOSE 表的方式，這里均采用永久和臨時標號的方式。注意該算法要求圖中不存在負權(quán)回路 。 北京郵電大學(xué)畢業(yè)論文設(shè)計 17 算法的具體步驟如下： (1)初始化時， S只包含原點，即 S={v}，頂點 v 到自己的距離為 0。 U 包含除v 外的其他頂點， v 到 U 中頂點 u 的距離為邊上的權(quán)或者 INFINITE（無通路）。 (2)從 U中選一點 K，頂點 v 到頂點 k 的距離最小，然后把頂點 k加入 S中（該選定的距離就是 v 到 k 的最短路徑長度）。 代碼實現(xiàn)如下 ： int min = INFINITE。 for(int i=0。 i節(jié)點數(shù) 。 i++) { if(done[i] != 1) continue。 else if(distance[i] min) { min = distance[i]。 no = i。 } } (3)以頂點 k 為新考慮的中間點，修改 v 到 U 各頂點距離：若從源點 v 到頂點u（ u 屬于 U）的距離（經(jīng)過頂點 k）比原來距離（不經(jīng)過 k）短，則修改頂點 u的距離值，修改后的距離值的頂點 k 的距離加上邊 k， u上的權(quán)。 代碼實現(xiàn)如下： for(mapint, int::iterator it = m_edges2[no].begin()。 it!=m_edges2[no].end()。 it++) { if(done[(*it).first] != 1) continue。 else if((distance[no] + (*it).second) distance[(*it).first]) { distance[(*it).first] = distance[no] + (*it).second。 from[(*it).first] = no。 } } (4)重復(fù)（ 2）和（ 3）直到 S 包含所有的頂點。 floyed(弗洛耶德 )算法 FloydWarshall 算法用來找出每對點之間的最短距離。它 需要用鄰接矩陣來儲存邊，這個算法通過考慮最佳子路徑來得到最佳路徑。 注意單獨一條邊的路徑也不一定是最佳路徑。 該算法的思想是： 從任意一條單邊路徑開始。所有兩點之間的距離是邊的權(quán)，或者無窮大，如果兩點 北京郵電大學(xué)畢業(yè)論文設(shè)計 18 之間沒有邊相連。 對于每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。 基本思想是： 求解所有點間的路徑需要進行 n次試探。對于頂點 i 到頂點 j 的路徑長度，首先考慮讓路徑經(jīng)過頂點 1，比較路徑（ i， j）和（ i， 1， j）的長度取其短者為當(dāng)前求得的最短路徑長 度。對每一對頂點的路徑都做這樣的試探，則可求得一個矩陣設(shè)為 A(1)，求 n次即得每對頂點間的最短路徑 A(n)。 弗洛伊德算法仍然使用圖的鄰接矩陣 arcs[n+1][n+1]來存儲帶權(quán)有向圖。算法的基本思想是 :設(shè)置一個 n x n 的矩陣 A(k)，其中除對角線的元素都等于 0 外，其它元素a(k)[i][j]表示頂點 i 到頂點 j 的路徑長度， K 表示運算步驟。開始時，以任意兩個頂點之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時，路徑長度為∞，當(dāng) K=0 時 , A (0)[i][j]=arcs[i][j]，以后逐步嘗試在原路徑中加入 其它頂點作為中間頂點，如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為：第一步，讓所有邊上加入中間頂點 1，取 A[i][j]與 A[i][1]+A[1][j]中較小的值作 A[i][j]的值，完成后得到第一次的查詢。 第二步，讓所有邊上加入中間頂點 2，取 A[i][j]與 A[i][2]+A[2][j]中較小的值，完成后得到 A(2)?，如此進行下去，當(dāng)?shù)?n步完成后，得到 A(n)， A(n)即為我們所求結(jié)果 ,A(n)[i][j]表示頂點 i 到頂點 j 的最短距離。 因此，弗洛伊德算法可以描述為 : A(0)[i][j]=arcs[i][j]。//arcs 為圖的鄰接矩陣 A(k)[i][j]=min{A(k1) [i][j],A(k1) [i][k]+A(k1) [k][j]}。//其中 k=1,2,…,n 定義一個 n 階方陣序列： D(1), D(0), …, D(n1). 其中 D(1) [i][j] = [i][j]； D(k) [i][j] = min { D(k1)[i][j]， D(k1)[i][k] + D(k1)[k][j] }, k = 0,1,…, n 1 D(0) [i][j]是從頂點 vi 到 vj , 中間頂點是 v0 的最短路徑的長度 , D(k) [i][j]是從頂點 vi 到 vj , 中間頂點的序號不大于 k 的最短路徑長度 , D(n1)[i][j]是從頂點 vi 到 vj 的最短路徑長度。 北京郵電大學(xué)畢業(yè)論文設(shè)計 19 C 語言為代碼實現(xiàn)如圖 52 所示： 圖 52 (弗洛耶德 )算法 c語言為代碼 在我的系統(tǒng)中，我使用的是鄰接矩陣的方式來存儲和表示兩個景點之間的距離，所以我打算使用的方法是 floyed(弗洛耶德 )算法。 時間復(fù)雜度： O(|V|^3) 頂點數(shù)的三次方。