校園導(dǎo)航系統(tǒng)---算法與分析課程設(shè)計(已修改)
2025-06-21 07:43 本頁面
【正文】 算法設(shè)計與分析課程設(shè)計 題目： 校園導(dǎo)航問題 文檔： 物聯(lián)網(wǎng)工程 學(xué)院 物聯(lián)網(wǎng)工程 專業(yè) 學(xué) 號 學(xué)生姓名 班 級 物聯(lián)網(wǎng) 1101 二〇一三 年 十二 月 設(shè)計要求：設(shè)計你的學(xué)校的平面圖，至少包括 10個以上的場所，每兩個場所間可以有不同的路，且路長也可能不同，找出從任意場所到達(dá)另一場所的最佳路（最短路徑）。 本系統(tǒng)為用戶提供以下功能 : (一 )、查詢了解學(xué)校概況，為導(dǎo)游參觀者提供關(guān)于學(xué)校的相關(guān)信息。 (二 )、查詢校園各個場所和景點信息 。 (三 )、為導(dǎo)游者或外來人員參觀人員提供校園交通信息，方便用戶走訪學(xué)校。完成需要操作時，退出系統(tǒng) 校園導(dǎo)航查詢系統(tǒng)的開發(fā)方法總結(jié)如下： (1) 需求分析，了解學(xué)校各個場所與場所或 者是各個景點與景點之間的信息，路徑和距離， 考慮 該如何設(shè)計才能滿足用戶需求。 (2) 概要設(shè)計，對調(diào)查得到的數(shù)據(jù)進行分析，根據(jù)其要求實現(xiàn)的功能分析系統(tǒng)結(jié)構(gòu)和界面將實現(xiàn)的基本功能。 (3) 詳細(xì)設(shè)計，設(shè)計系統(tǒng)界面并編輯實現(xiàn)其各個功能的代碼。 (4) 調(diào)試分析，在設(shè)計完成后，調(diào)試系統(tǒng)運行的狀況，修改完善系統(tǒng) ,然后進行測試。 一、 需求分析 1 學(xué)校以及各景點介紹模塊 采用一維數(shù)組將學(xué)校景點依次排放好編號 [i].number=i 在選擇校園介紹的時候，彈出 [0]校園簡介 。 在選擇各景點信息的時候 ， 可按 編號查詢 2 查詢最短路徑（主要） 查出出發(fā)地到想要到達(dá)的景點的最短路徑，初步構(gòu)想采用最經(jīng)典的迪杰斯特拉算法最短路徑函數(shù) 3 查詢各點距離 將所有景點的距離 顯示出來 。 4 主菜單頁面顯示 提供使用者選擇功能界面，按照提示進行操作。 5 退出 完成需要操作時，退出系統(tǒng) 校園導(dǎo)航系統(tǒng)模式圖 二、 概要設(shè)計 算法設(shè)計說明 校園 導(dǎo)航 模型是由各個景點和景點以及場所和場所之間的路徑組成的，所以這完全可以用數(shù)據(jù)結(jié)構(gòu)中的圖來模擬。用圖的結(jié)點代表景點或場所，用圖的邊代表景點或場所之 間的路徑。所以首先應(yīng)創(chuàng)建圖的存儲結(jié)構(gòu)。結(jié)點值代表景點信息，邊的權(quán)值代表景點間的距離。結(jié)點值及邊的權(quán)值采用圖存儲。本系統(tǒng)需要查詢景點信息和求一個景點到另一個景點的最短路徑長度及路線，為方便操作，所以給每個景點一個代碼，用結(jié)構(gòu)體類型實現(xiàn)。計算路徑長度，最短路線和最佳路徑時可分別用迪杰斯特拉（ Dijkastra）算法和哈密而頓回路算法實現(xiàn)。最后 switch 選擇語句選擇執(zhí)行瀏覽景點信息或查詢最短路徑和距離。 學(xué)校以及各景點介紹模塊 采用了圖的鄰接矩陣存儲結(jié)構(gòu)，首先初始化每一個景點名稱（一維數(shù)組）for(i=1。i。++i) [i].number=i …… 校園導(dǎo)航系統(tǒng) 校園介紹，各景點介紹 查詢校園所有景點路徑 最短路徑查詢 查詢各景點距離 輸入起點與終點 輸出最短路徑 景點介紹功能流程圖 查詢最短路徑（主要） 算法的主要思想是按路徑長度遞增的次序產(chǎn)生最短路徑的算法。中心思想是假設(shè) s 為已求得最短路徑的終點的集合，則下一條最短路徑或者是?。?v,x）或者是中間經(jīng)過 s 中是頂點而最后到達(dá)頂點 x的路徑。 （ 1） arcs 表示弧上的權(quán)值。若不存在，則置 arcs 為 ∞。 S 為已找到從 v 出發(fā)的最短路徑的終點的集合，初始狀態(tài)為空集。那么，從 v 出發(fā)到圖上其余各頂點vi 可能達(dá)到的最短路徑長度的初值為 D=arcs[Locate Vex(G,v),i] vi∈ V （ 2） 選擇 vj，使得 D[j]=Min{D | vi∈ VS} SearchMenu 子菜單 輸入景點編號 編號值 =i Inum 輸出景點介
畢業(yè)設(shè)計相關(guān)推薦
鄂ICP備17016276號-1