【正文】 畢 業(yè) 設(shè) 計(jì) 課 程 名 稱： 專 業(yè) 班 級(jí) ： 1 學(xué) 生 姓 名 ： 學(xué) 號(hào) ： 6 任 課 教 師 ： 計(jì)算機(jī)應(yīng)用技術(shù) 專業(yè)課程設(shè)計(jì)任務(wù)書 學(xué)生姓名 專業(yè)班級(jí) 學(xué)號(hào) 題 目 校園導(dǎo)航系統(tǒng) 課題性質(zhì) 工程設(shè)計(jì) 課題來(lái)源 自擬課題 指導(dǎo)教師 同組姓名 主要內(nèi)容 用無(wú)向網(wǎng)表示你所在學(xué)校的校園景點(diǎn)平面圖，圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的 編號(hào)、名稱、簡(jiǎn)介等信息，圖中的邊表示景點(diǎn)間的道路，存放路徑長(zhǎng)度等信息。要求能夠回答有關(guān)景點(diǎn)介紹、游覽路徑等問題。 （ 1） 查詢各景點(diǎn)的相關(guān)信息； （ 2） 查詢圖中任意兩個(gè)景點(diǎn)間的最短路徑。 （ 3） 查詢圖中任意兩個(gè)景點(diǎn)間的所有路徑。 （ 4） 增加、刪除、更新有關(guān)景點(diǎn)和道路的信息。 （ 5） 求多個(gè)景點(diǎn)的最佳（最短）游覽路徑。 任務(wù)要求 1．研究應(yīng)用圖的存儲(chǔ)與基本算法 2．應(yīng)用數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)知識(shí)進(jìn)行實(shí)際問題求解與分析； 3．編程實(shí)現(xiàn)算法 4．具有良好的界面，操作方便靈活、簡(jiǎn)潔高效。 5．按要求撰寫課程設(shè)計(jì)報(bào) 告和設(shè)計(jì)總結(jié)。 參考文獻(xiàn) 1． 《 數(shù)據(jù)結(jié)構(gòu)（ C 語(yǔ)言版）》，嚴(yán)蔚敏、吳偉民，清華大學(xué)出版社，1997. 2． 《 Visual C++實(shí)用教程（第一版）》，張榮梅、梁曉林，冶金工業(yè)出版社， 2020. 審查意見 指導(dǎo)教師簽字： 教研室主任 簽字： 年 月 日 1 需求分析 1 設(shè)計(jì)學(xué)校的校園平面圖。選取若干個(gè)有代表性的景點(diǎn)抽象成一個(gè)無(wú)向帶權(quán)圖（無(wú)向網(wǎng)），以圖中頂點(diǎn)表示校內(nèi)各景點(diǎn)，邊上的權(quán)值表示兩景點(diǎn)之間的距離。 2存放景點(diǎn)代號(hào)、名稱、簡(jiǎn)介 等信息供用戶查詢。 3為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。 4為來(lái)訪客人提供圖中任意景點(diǎn)之間的問路查詢。 5可以為校園平面圖增加或刪除景點(diǎn)或邊，修改邊上的權(quán)值等。 2 概要設(shè)計(jì) 主界面設(shè)計(jì) 為了實(shí)現(xiàn)校園導(dǎo)航系統(tǒng)各功能的管理，首先設(shè)計(jì)一個(gè)含有多個(gè)菜單項(xiàng)的主控菜單子程序以鏈接系統(tǒng)的各項(xiàng)子功能，方便用戶使用本系統(tǒng)。 存儲(chǔ)結(jié)構(gòu)設(shè)計(jì) 本系統(tǒng)采用圖結(jié)構(gòu)類型（ mgraph）存儲(chǔ)抽象校園圖的信息。其中：各景點(diǎn)間的鄰接關(guān)系用圖的鄰接矩陣類型（ adjmatrix）存儲(chǔ)；景點(diǎn)（頂點(diǎn) ）信息用結(jié)構(gòu)數(shù)組（ vexs）存儲(chǔ)，其中每個(gè)數(shù)組元素是一個(gè)結(jié)構(gòu)變量，包含景點(diǎn)編號(hào)、景點(diǎn)名稱及景點(diǎn)介紹三個(gè)分量；圖的頂點(diǎn)個(gè)數(shù)及邊的個(gè)數(shù)由分量 vexnum、 arum 表示，它們是整型數(shù)據(jù)。 此外，本系統(tǒng)還設(shè)置了三個(gè)全局變量： visited[ ] 數(shù)組用于存儲(chǔ)頂點(diǎn)是否被訪問標(biāo)志； d[ ]數(shù)組用于存放邊上的權(quán)值或存儲(chǔ)查找路徑頂點(diǎn)的編號(hào)； campus是一個(gè)圖結(jié)構(gòu)的全局變量。 系統(tǒng)功能設(shè)計(jì) 本系統(tǒng)除了要完成圖的初始化功能外還設(shè)置了 8 個(gè)子功能菜單。圖的初始化由函數(shù) initgraph( )實(shí)現(xiàn)。依據(jù)讀入的圖的頂點(diǎn) 個(gè)數(shù)和邊的個(gè)數(shù)，分別初始化圖結(jié)構(gòu)中圖的頂點(diǎn)向量數(shù)組和圖的鄰接矩陣。 8個(gè)子功能的設(shè)計(jì)描述如下。 (1)學(xué)校景點(diǎn)介紹 學(xué)校景點(diǎn)介紹由函數(shù) browsepus( )實(shí)現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)即能輸出學(xué)校全部景點(diǎn)的信息：包括景點(diǎn)編號(hào)、景點(diǎn)名稱及景點(diǎn)簡(jiǎn)介。 （ 2）查看瀏覽路線 查看瀏覽路線由函數(shù) shortestpath_dij( )實(shí)現(xiàn)。該功能采用迪杰斯特拉（ Dijkstra）算法實(shí)現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)能根據(jù)用戶輸入的起始景點(diǎn)編號(hào)，求出從該景點(diǎn)到其它景點(diǎn)的最短路徑線路及距離。 （ 3）查看兩景點(diǎn)間最短路徑 查看兩景點(diǎn)間最短路徑由函數(shù) shortestpath_floyd( )實(shí)現(xiàn)。該功能采用弗洛伊德（ Floyd）算法實(shí)現(xiàn)。當(dāng)用戶選擇該功能，系統(tǒng)能根據(jù)用戶輸入的起始景點(diǎn)及目的地景點(diǎn)編號(hào)，查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的最短路徑線路及距離。 （ 4）景點(diǎn)信息查詢 景點(diǎn)信息查詢由函數(shù) seeabout( )實(shí)現(xiàn)。該功能根據(jù)用戶輸入的景點(diǎn)編號(hào)輸出該景點(diǎn)的相關(guān)信息。例如，景點(diǎn)編號(hào)、名稱等。 （ 5）更改圖的信息 更改圖的信息功能由主調(diào)函數(shù) changegraph( )及若干個(gè)子函數(shù)完成，可以實(shí)現(xiàn)圖的若干基本操作。例如：增加新的景點(diǎn)、刪除邊 、重建圖等。 （ 6）查詢景點(diǎn)間可行路徑 該功能是查詢兩景點(diǎn)間所有可行路徑，由函數(shù) allpath( )和函數(shù) path( )實(shí)現(xiàn)，其中 path( )函數(shù)是直接遞歸函數(shù)。由于是無(wú)向網(wǎng)，如果網(wǎng)中的邊數(shù)很多，任意兩個(gè)景點(diǎn)間的所有路徑也會(huì)有限多，但很多路徑是無(wú)實(shí)際意義的（有近路，為什么去走遠(yuǎn)路呢？）。所以，本算法在求得的兩景點(diǎn)間所有可行路徑中，限制只輸出路徑長(zhǎng)度不超過 8個(gè)景點(diǎn)的路線。 （ 7）退出 即退出校園導(dǎo)游系統(tǒng)，由 exit(0)函數(shù)實(shí)現(xiàn)。 本程序包含 3 個(gè)模塊：主程序模塊、工作區(qū)模塊和無(wú)向網(wǎng)操作模塊。 調(diào)用關(guān)系如圖所示。 主程序模塊 工作區(qū)模塊 無(wú)向網(wǎng)操作模塊 模塊調(diào)用示意圖 本系統(tǒng)共設(shè)置 18個(gè)子程序，各子程序的函數(shù)名及功能說明如下。 （ 1） mgraph initgraph( ) // 圖的初始化 （ 2） int locatevex(mgraph c, int v) // 查找景點(diǎn)在圖中的序號(hào) （ 3） void path(mgraph c, int m,int n,int k) // 打印序號(hào)為 m,n 景點(diǎn)間的長(zhǎng)度不超過 8個(gè)景點(diǎn)的路徑 （ 4） int allpath(mgraph c) // 打印兩景點(diǎn)間的景點(diǎn)個(gè)數(shù)不超過8 的所有路徑。調(diào)用 (3) （ 5） void shortestpath_dij(mgraph c) // 用 Dijkstra 算法，求一個(gè)景點(diǎn)到其他景點(diǎn)間的最短路徑，并打印 以下編號(hào)（ 6）－（ 11）是圖的基本操作。包括：重建圖、更新信息、刪除、增加結(jié)點(diǎn)和邊等。 （ 6） int creatgragh(mgraph amp。c) // 建圖。以圖的鄰接矩陣存儲(chǔ)圖 （ 7） int newgraph(mgraph amp。c) // 更新圖的部分信息。返回值：1 （ 8） int enarc(mgraphamp。c) // 增加一條邊。返回值： 1 （ 9） int envex(mgraphamp。c) // 增加一個(gè)結(jié)點(diǎn)。返回值： 1 （ 10） int delvex(mgraphamp。c) // 刪除圖的一個(gè)頂點(diǎn)。返回值：1 （ 11） int delarc(mgraphamp。c) // 刪除圖的一條邊。返回值：1 （ 12） int changegraph(mgraph amp。c) // 圖操作的主調(diào)函數(shù)。返回值： 1 （ 13） void shortestpath_floyd(mgraph c) // 用 Floyd 算法求任意兩景點(diǎn)間的最短路徑，并輸出 （ 14） void seeabout(mgraph c) // 查詢景點(diǎn)的信息 （ 15） void browsepus(mgraph c) // 顯示所有景點(diǎn)信息 （ 16） void mainwork( ) // 工作區(qū)函數(shù)。操作區(qū) 用戶界面 （ 17） void main( ) // 主函數(shù)。設(shè)定界面的顏色和大小，調(diào)用工作區(qū)模塊函數(shù)