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

　　

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