公園導游圖數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

PAGEPAGE2課程名稱：數(shù)據(jù)結(jié)構(gòu)湖南涉外經(jīng)濟?學院本科學生課程?設(shè)計（論文）題目公園導游圖姓名學號學部計算機科學與?技術(shù)專業(yè)、年級指導教師湖南涉外經(jīng)濟?學院本科學生?課程設(shè)計（論文）

摘要隨著中國經(jīng)濟?不斷的發(fā)展，城市發(fā)展的越?來越好，越來越多的人?融入了城市生?活。公園成為人們?散心，娛樂的場所，公園也隨即也?在不斷的擴張?，變得越來越全?面，但是這不利于?逛公園的人尋?找自己想要去?的地方，尤其是對公園?陌生的游客，更是不知道如?何走，才能更好的游?玩公園，達到的最好經(jīng)?濟效益。所以針對這種?現(xiàn)象，為了方便游客?，開發(fā)這么一款?公園導游系統(tǒng)?軟件。系統(tǒng)是用C語?言實現(xiàn)，基于visu?alc++6.0開發(fā)的，采用圖這么一?種數(shù)據(jù)結(jié)構(gòu)，采用鄰接矩陣?的存儲方式，用一個二維數(shù)?組來記錄所有?的邊，為了實現(xiàn)地圖?的隨時更新，采用了靜態(tài)鏈?表實現(xiàn)對圖的?接點的添加，刪除。本系統(tǒng)設(shè)計基?于圖的結(jié)構(gòu)，創(chuàng)建一個無向?圖，針對游客的需?求，將涉外公園的?景點編號、名稱、介紹等信息放?入到圖的頂點?當中并保存景?點文本文件中?，將兩個景點的?編號和它們之?間的距離當權(quán)?值也保存在相?同的文本文件?中，利用迪杰特斯?拉算法來求從?一個景點到另?一個景點的最?短距離，利用Sera?ch（）；查找景點，本顯示他的信?息，從而解決了要?查找景點信息?和兩個景點之?間的最短路徑?的問題，最后按照顯示?屏上的提示進?行相關(guān)的操作?。關(guān)鍵詞：公園導游；圖；鄰接矩陣；二維數(shù)組；靜態(tài)鏈

目錄HYPERL?INK第一章前言 PAGERE?F_Toc31?300454?7\h1HYPERL?INK1.1課題的研究?背景、要求和意義 PAGERE?F_Toc31?300454?8\h1HYPERL?INK1.2課題的目標?、研究范圍 PAGERE?F_Toc31?300454?9\h1HYPERL?INK1.3理論技術(shù)方?案的選取 PAGERE?F_Toc31?300455?0\h2HYPERL?INK1.4研究方法 PAGERE?F_Toc31?300455?1\h2HYPERL?INK1.5結(jié)構(gòu)與安排? PAGERE?F_Toc31?300455?2\h2HYPERL?INK第二章系統(tǒng)功能分析? PAGERE?F_Toc31?300455?3\h4HYPERL?INK2.1可行性分析 PAGERE?F_Toc31?300455?4\h4HYPERL?INK2.1.1技術(shù)可行性? PAGERE?F_Toc31?300455?5\h4HYPERL?INK2.1.2工具可行性 PAGERE?F_Toc31?300455?6\h4HYPERL?INK2.1.3經(jīng)濟可行性 PAGERE?F_Toc31?300455?7\h4HYPERL?INK2.1.4操作可行性 PAGERE?F_Toc31?300455?8\h5HYPERL?INK2.2需求分析 PAGERE?F_Toc31?300455?9\h5HYPERL?INK2.2.1功能需求 PAGERE?F_Toc31?300456?0\h5HYPERL?INK2.2.2輸入輸出的要?求 PAGERE?F_Toc31?300456?1\h5HYPERL?INK第三章總體設(shè)計 PAGERE?F_Toc31?300456?2\h6HYPERL?INK3.1程序模塊 PAGERE?F_Toc31?300456?3\h6HYPERL?INK3.2系統(tǒng)涉及的數(shù)?據(jù)結(jié)構(gòu) PAGERE?F_Toc31?300456?4\h6HYPERL?INK3.2.1程序數(shù)據(jù)結(jié)構(gòu)? PAGERE?F_Toc31?300456?5\h7HYPERL?INK3.2.2具體數(shù)據(jù)類型?定義 PAGERE?F_Toc31?300456?6\h7HYPERL?INK第四章詳細設(shè)計 PAGERE?F_Toc31?300456?7\h9HYPERL?INK4.1創(chuàng)建圖（Fprint?-Link） PAGERE?F_Toc31?300456?8\h9HYPERL?INK4.2尋找最佳路徑?（DFSTra?verse） PAGERE?F_Toc31?300456?9\h9HYPERL?INK4.3最短路徑（ShortP?ath） PAGERE?F_Toc31?300457?0\h10HYPERL?INK4.4遍歷出某一起?點到終點的所?有路徑（Search?AllPat?h） PAGERE?F_Toc31?300457?1\h12HYPERL?INK4.5導入新文件（Loadne?wmap） PAGERE?F_Toc31?300457?2\h13HYPERL?INK第五章系統(tǒng)實現(xiàn) PAGERE?F_Toc31?300457?3\h14HYPERL?INK5.1程序執(zhí)行之前?的準備 PAGERE?F_Toc31?300457?4\h14HYPERL?INK5.2主界面 PAGERE?F_Toc31?300457?5\h14HYPERL?INK5.3游客界面 PAGERE?F_Toc31?300457?6\h15HYPERL?INK5.4系統(tǒng)用戶界面? PAGERE?F_Toc31?300457?7\h15HYPERL?INK5.5瀏覽公園全景?簡圖 PAGERE?F_Toc31?300457?8\h16HYPERL?INK5.6尋找某一起點?的最佳路徑和?指定起點、終點的最短路?徑 PAGERE?F_Toc31?300457?9\h16HYPERL?INK5.7尋找指定起點?、終點的所有路?徑 PAGERE?F_Toc31?300458?0\h17HYPERL?INK5.8刪除，添加結(jié)點，保存和導入新?地圖 PAGERE?F_Toc31?300458?1\h17HYPERL?INK第六章解決的關(guān)鍵問?題 PAGERE?F_Toc31?300458?2\h18HYPERL?INK6.1如何實現(xiàn)尋找?最短路徑功能? PAGERE?F_Toc31?300458?3\h18HYPERL?INK6.2如何實現(xiàn)深度?優(yōu)先搜索 PAGERE?F_Toc31?300458?4\h18HYPERL?INK6.3如何修改地圖? PAGERE?F_Toc31?300458?5\h18HYPERL?INK6.4如何導入其?他文件信息 PAGERE?F_Toc31?300458?6\h18HYPERL?INK第七章結(jié)論 PAGERE?F_Toc31?300458?7\h19HYPERL?INK結(jié)束語 PAGERE?F_Toc31?300458?8\h20HYPERL?INK參考文獻 PAGERE?F_Toc31?300458?9\h21公園導游圖第一章前言PAGE3公園導游圖第一章前言PAGE1第一章前言1.1課題的研究?背景、要求和意義現(xiàn)代公園范圍?的廣闊，內(nèi)容不斷的增?加，使得公園整個?系統(tǒng)變得復雜?。使用電腦對游?客進行導游成?為發(fā)展的趨勢?，以達到更好的?為游客服務(wù)的?目的。對于公園的游?客來說，他們要求：能夠瀏覽整個?公園的信息、查詢每一個景?點的信息、從任意景點遍?歷全部的景點?、能夠查找最短?路徑。對于系統(tǒng)用戶?來說，他們要求：刪除地點、添加地點、添加路徑、刪除路徑、保存修改、導入文件數(shù)據(jù)?。采用圖這么一?種數(shù)據(jù)結(jié)構(gòu)，采用鄰接表的?存儲方式，用一個二維數(shù)?組來記錄所有?的邊，為了實現(xiàn)地圖?的隨時更新，采用了靜態(tài)鏈?表實現(xiàn)對圖的?接點的添加，刪除。應(yīng)用文件的讀?寫來進行文件?操作。查找最短路徑?采用迪杰特斯?拉算法實現(xiàn)，從任意景點遍?歷全部的景點?采用深度優(yōu)先?遍歷實現(xiàn)。對于界面設(shè)計?，游客不能進行?地圖的修改，更換，所以首先要驗?證身份，再出現(xiàn)對應(yīng)的?界面。1.2課題的目標?、研究范圍實現(xiàn)的目標：實現(xiàn)對某一個?公園導游及地?圖的修改與更?新的系統(tǒng)。通過系統(tǒng)分析?、系統(tǒng)設(shè)計、編程調(diào)試，寫實驗報告等?環(huán)節(jié)，進一步掌握應(yīng)?用系統(tǒng)設(shè)計的?方法和步驟，靈活運用并深?刻理解典型數(shù)?據(jù)結(jié)構(gòu)在軟件?開發(fā)中的應(yīng)用?。綜合運用數(shù)據(jù)?結(jié)構(gòu)課程中學?到的幾種典型?數(shù)據(jù)結(jié)構(gòu)，如鏈表，棧，隊列，以及程序設(shè)計?語言（C語言），自行實現(xiàn)一個?較為完整的應(yīng)?用系統(tǒng)的設(shè)計?與開發(fā)，對自己學過的?知識進一步的?加深理解，對數(shù)據(jù)結(jié)構(gòu)的?算法思想要有?更深的理解。圖（Graph）是一種較線性?表和樹更為復?雜的數(shù)據(jù)結(jié)構(gòu)?。在線性表中，數(shù)據(jù)元素之間?僅有線性關(guān)系?，每個數(shù)據(jù)元素?只有一個直接?前驅(qū)和一個直?接后繼；在樹形結(jié)構(gòu)中?，數(shù)據(jù)元素之間?有著明顯的層?次關(guān)系，并且每一層上?的數(shù)據(jù)元素可?能和下一層中?多個元素（即其該子結(jié)點?）相關(guān)，但只能和上一?層中一個元素?（即其雙親結(jié)點?）相關(guān)，而在圖形結(jié)構(gòu)?中，結(jié)點之間的關(guān)?系可以是任意?的，圖中任意兩個?數(shù)據(jù)元素之間?都可能相關(guān)。由此，圖的應(yīng)用極為?廣泛，特別是近年來?的迅速發(fā)展，已滲入到諸如?語言學、邏輯學、物理、化學、電訊工程、計算機科學以?及數(shù)學的其他?分支中。1.3理論技術(shù)方?案的選取鄰接矩陣存儲?結(jié)構(gòu)對圖的構(gòu)?造操作的實現(xiàn)?框架，他根據(jù)圖G的?種類調(diào)用具體?構(gòu)造算法。如果G是無向?圖，則構(gòu)造一個具?有n個頂點和?e條邊的無向?網(wǎng)G的時間復?雜度是O（n2+e*n），其中對鄰接矩?陣G.arcs的初?始化耗費了O?（n2）的時間。這個存儲結(jié)構(gòu)?上易于實現(xiàn)課?題所需的基本?操作，在建立鄰接表?或逆鄰接表，時間復雜度為?（n+e），需要通過查找?才能得到頂點?圖中位置，時間復雜度為?O（n*e）。在鄰接表上容?易找到任一頂?點的的第一個?鄰接點和下一?鄰接點，但要判定任意?兩個頂點（vi和vj）之間是否有邊?或弧相連，則需要搜索第?i個或第j個?鏈表，因此，不及鄰接矩陣?方便。1.4研究方法基于Visu?alC++6.0平臺編程是?當今程序者的?青睞，它有著強大的?性能、完全豐富的工?具及高速的處?理速度和完備?的兼容性。不僅可以簡化?編程的設(shè)計并?且算法應(yīng)用靈?活，使應(yīng)用程序的?開發(fā)更為簡便?。C++是為開發(fā)大型?程序而研制的?，它比C語言困?難得多，它功能豐富、表達能力強、使用靈活方便?、應(yīng)用面廣、目標程序效率?高、可移植性好，既具有高級語?言的優(yōu)點，又具有低級語?言的許多特點?，完全適合于編?寫系統(tǒng)軟件；本人就利用上?述C++開發(fā)軟件編寫?了《公園導游系統(tǒng)?》，采用人機互動?的操作模式，系統(tǒng)經(jīng)過顯示?主界面功能，然后用戶的需?要操作。1.5結(jié)構(gòu)與安排?首先“前言”對研究背景和?研究目的作了?簡單的介紹；其次“系統(tǒng)功能分析?”對本系的說明?和講解；再次“總體設(shè)計”對本系統(tǒng)做了?一個簡要引導?，并且通過“總體設(shè)計”對該系統(tǒng)的運?行懂得差不多?了；“詳細設(shè)計”就是對系統(tǒng)有?了詳細的設(shè)計?過程，更進一步知道?設(shè)計原理；“排序算法的改?進”介紹傳統(tǒng)算法?的不足，經(jīng)過設(shè)想對原?算法加以改進?“系統(tǒng)實現(xiàn)”不但讓我們知?道了系統(tǒng)的界?面和一些操作?的實施，讓你知道整個?算法的設(shè)計并?且加以理解。公園導游圖第二章系統(tǒng)功能分析?PAGE5第二章系統(tǒng)功能分析?2.1可行性分析所謂可行性分?析就是用最小?的代價在盡可?能短的時間內(nèi)?確定問題是否?能夠解決。這步工作的主?要是要進行一?次大大壓縮簡?化了的系統(tǒng)分?析和設(shè)計的過?程，也就是在較高?層次上以比較?抽象的方式進?行系統(tǒng)分析和?設(shè)計的過程?？尚行匝芯康?最根本任務(wù)是?對以后的行動?方針提出建議?，以避免時間、資源、人力和金錢的?浪費，推薦一個較好?的解決方案，并且為工程制?定一個初步的?計劃。2.1.1技術(shù)可行性?查找最短路徑?以及查詢?nèi)我?兩景點之間的?所有路徑采用?迪杰特斯拉算?法或弗洛伊德?算法實現(xiàn)。解決這個問題?的一個方法是?：每次以一個頂?點為源點，重復執(zhí)行迪杰?斯特拉算法n?次。這樣，便可求得每一?對頂點之間的?最短路徑?？偟膱?zhí)行時間?為O（n3）。雖然弗洛伊德?算法時間復雜?度也是O（n3），但形式簡單些?。從任意景點遍?歷全部的景點?采用深度優(yōu)先?遍歷或廣度優(yōu)?先搜索遍歷圖?實現(xiàn)。所謂可行性分?析就是用最小?的代價在盡可?能短的時間內(nèi)?確定問題是否?能夠解決。這步工作的主?要是要進行一?次大大壓縮簡?化了的系統(tǒng)分?析和設(shè)計的過?程，也就是在較高?層次上以比較?抽象的方式進?行系統(tǒng)分析和?設(shè)計的過程?？尚行匝芯康?最根本任務(wù)是?對以后的行動?方針提出建議?，以避免時間、資源、人力和金錢的?浪費，推薦一個較好?的解決方案，并且為工程制?定一個初步的?計劃。本系統(tǒng)采用人?機操作進行管?理，用visua?lC++6.0進行前臺設(shè)?計、系統(tǒng)隨機產(chǎn)生?數(shù)據(jù)，用戶通過界面?操作，系統(tǒng)自動給予?合理分析，由于visu?alC++6.0功能強大、使用的靈活、良好的可擴展?性、以及廣泛實際?應(yīng)用，充分說明本系?統(tǒng)在技術(shù)方面?的可行性。2.1.2工具可行性軟件方面：信息時代對于?軟件的應(yīng)用已?不是人們的難?題，人們在日常辦?公中用的計算?機操作的系統(tǒng)?等都屬于軟件?部分。硬件方面：計算機普及到?今天，人們對于它的?擁有已不少見?，它的硬件設(shè)備?完全能夠滿足?人們的需求，而價格也能被?人們所接受。2.1.3經(jīng)濟可行性線在大多數(shù)的?公園景點及內(nèi)?容不斷的增多?和豐富，這也就使得整?個公園系統(tǒng)不?得不建立的更?大。這也就為人們?逛公園造成了?很大的不便。人們往往不熟?悉公園，找個東西，或某處帶來了?極大的不便。往往要花很多?時間在這一方?面。然而要是有一?個公園導游系?統(tǒng)這將給乘客?帶來極大的方?便，使人們一下就?能了解到這個?公園的大致的?情況。這是個超小型?的性能分析系?統(tǒng)，從投入的人力?，財力與物力來?講是非常之小?的，只要一臺電腦?，一臺打印機，這個系統(tǒng)就可?以搞起來，考慮到學校里?有電腦，現(xiàn)只要購置一?臺打印機就可?以了。從節(jié)省人力方?面，可以讓管理人?員從繁與復雜?的工作中解脫?出來，做更多的工作?，可以給讀者提?高到更深的一?個層次。2.1.4操作可行性本系統(tǒng)設(shè)計清?晰，有良好的用戶?接口，操作簡潔，完全可以給用?戶解決，并達到操作過?程中的直觀、方便、實用、安全等要求，因此操作方面?具有可行性。2.2需求分析2.2.1功能需求對于游客，系統(tǒng)功能需求?如下：能夠瀏覽整個?公園的信息、查詢每一個景?點的信息、從任意景點遍?歷全部的景點?、能夠查找最短?路徑。對于系統(tǒng)后臺?操作功能需求?如下：刪除地點、添加地點、添加路徑、刪除路徑、保存修改、導入文件數(shù)據(jù)?。2.2.2輸入輸出的要?求程序執(zhí)行是需?要有描述地圖?的文件，并放在相應(yīng)的?位置。文件中開始位?置存放景點個?數(shù)，圖存在多少條?邊；接著是存放景?點序號、名稱、相關(guān)信息；對后是存放著?各個景點之間?的距離矩陣。執(zhí)行程序先要?先要進行選擇?。修改地圖是要?驗證密碼。查找任意兩個?景點的最短路?徑時，輸入查找最短?路徑的兩個點?。運行各個小過?程要求要輸出?的暫時的結(jié)果?。公園導游圖第三章總體設(shè)計PAGE8第三章總體設(shè)計3.1程序模塊從文件中對出?數(shù)據(jù)(Fprint?-Link())：通過調(diào)用Up?date(L,g)，先將鏈表L的?信息賦值給鄰?接數(shù)組g中，進行更新。建立無向圖，把公園的景點?及景點的信息?，連接起來建立?鄰接表采用鏈?式加順式存儲?。瀏覽學校的全?景（Browse?r）：列出學校的所?有的景點。尋找最佳路徑?（DFSTra?verse：）：輸入一個景點?，會吧所有都瀏?覽一邊，并找出最佳的?路徑。最短路徑（ShortP?ath）:求出起點和終?點的最佳路徑?，并求出最佳路?徑的長度。遍歷出某一起?點到終點的所?有路徑（Search?AllPat?h）：找出所有路徑?，利用深度優(yōu)先?遍歷。刪除地點、添加地點、添加路徑、刪除路徑、保存修改、導入文件數(shù)據(jù)?。對應(yīng)代碼函數(shù)?如下：Delete?Adv(L,g)、Insert?Adv(L,g)、Insert?Edge()、Delete?Edge()、SaveMa?p(g)、Loadne?wmap(p,g)?？傮w結(jié)構(gòu)設(shè)計?如圖3-1所示。刪刪除地點主模塊系統(tǒng)用戶游客模塊添加地點添加路徑刪除路徑保存存修改入文件數(shù)據(jù)任意景點遍歷?查詢景點信息?和瀏覽公園簡?圖查詢?nèi)我鈨蓚€景點?最短的路徑遍歷輸出任意?一個景點的所?有路徑圖3-SEQ圖3-\*ARABIC?1系統(tǒng)框架圖3.2系統(tǒng)涉及的數(shù)?據(jù)結(jié)構(gòu)3.2.1程序數(shù)據(jù)結(jié)構(gòu)?程序主要用了?圖和靜態(tài)鏈表?兩種數(shù)據(jù)結(jié)構(gòu)?，采用矩陣來保?存圖形結(jié)構(gòu)的?地圖，用數(shù)組來保存?遍歷經(jīng)過的結(jié)?點用以遍歷回?溯，以及存儲最最?終路徑。圖的抽象數(shù)據(jù)?類型：ADTGraph{數(shù)據(jù)對象V：V是具有相同?特性的數(shù)據(jù)元?素的集合，稱為頂點集。數(shù)據(jù)關(guān)系：R={VR} VR=｛<v,w>|v,w∈v且P(v,w)表示從v到w?的弧，謂詞P（v,w）定義了弧<v,w>的意義或信息?｝基本操作P：PrintM?ap(g) Serach?(g)DFSTra?verse(g)ShortP?ath(g)。｝ADTGraph線性鏈表的抽?象數(shù)據(jù)類型：ADTList｛ 數(shù)據(jù)對象：D=｛ai|ai∈ElemSe?t，i=1，2，…,n,n≥0｝數(shù)據(jù)關(guān)系：R1=｛<ai-1,ai>|ai-1,ai∈D,i=2,…,n｝基本操作:Delete?Adv(L,g)Insert?Adv(L,g)Insert?Edge()Delete?Edge()SaveMa?p(g)Loadne?wmap(p,g)｝ADTList。3.2.2具體數(shù)據(jù)類型?定義typede?fstruct?LNode{ charname[30]; intnum; charintrod?uction?[100]; struct?LNode*next;}LNode,*Link;typede?fstruct?ArcNod?e{intdata;//該弧所得指向?的頂點的位置? ArcNod?e*nextar?c;//指向下一條弧?的指針}ArcNod?e,*ArcLin?k;typede?fstruct?VNode//頂點信息{ charname[30]; intnum;charintrod?uction?[100]; ArcLin?kfirsta?rc;//指向第一條依?附該頂點的弧?的指針}VNode,AdjLis?t[MAX+1];typede?fstruct?ALGrap?h{AdjLis?tvdata;intvexnum?,arcnum?;//圖的頂點數(shù)和?弧數(shù)}ALGrap?h;intEdge[MAX][MAX];//用來存放路徑?的權(quán)值intn,e;//存放結(jié)點數(shù)和?邊數(shù)讀取文件信息?代碼如下： for(i=1;i<=n;i++) {fscanf?(fp,"%d",&num);fscanf?(fp,"%s",name); fscanf?(fp,"%s",inform?ation);ListIn?sert(L,num,name,inform?ation); } Update?(L,g); for(j=1;j<=e;j++)//從文件中讀入?邊的信息{ fscanf?(fp,"%d",&a); fscanf?(fp,"%d",&b); fscanf?(fp,"%d",&weight?); Edge[a][b]=weight?; Edge[b][a]=weight?; p=(ArcLin?k)malloc?(sizeof?(ArcNod?e));//為頂點申請空?間 p->data=a; p->nextar?c=g[b].firsta?rc; g[b].firsta?rc=p;//把p插進來 q=(ArcLin?k)malloc?(sizeof?(ArcNod?e)); q->data=b; q->nextar?c=g[a].firsta?rc; g[a].firsta?rc=q;公園導游圖第四章詳細設(shè)計PAGE13第四章詳細設(shè)計4.1創(chuàng)建圖（Fprint?-Link）從文件中讀出?數(shù)據(jù)，函數(shù)流程圖4?-1所示。結(jié)束結(jié)束j++開始讀入n,eArcLin?kp,q;初始化鏈表，鄰接表，Eage[][]i=1,j=1，p=q=(ArcLin?k)malloc?(sizeof?(ArcNod?e));i<=n讀入結(jié)點，插入到鏈表L?i++YN讀入邊信息起?點a,終點b，長度weig?ht。Eage[a][b]=weight?，Eage[b][a]=weight?p->nextar?c=g[b].firsta?rc;g[b].firsta?rc=p;//把p插進來q?->nextar?c=g[a].firsta?rc;g[a].firsta?rc=q;j<=eYNUpdate?(L,g);//給g賦值圖4-SEQ圖4-\*ARABIC?1Fprint?-Link函數(shù)?流程圖4.2尋找最佳路徑?（DFSTra?verse）利用深度優(yōu)先?的思想，遍歷圖找出一?條最佳最佳的?的路徑，讓它遍歷所有?景點。利用遞歸的思?想，往下遍歷，訪問標志位，若訪問過在下?次就不用訪問?。若找完一個分?支在下次重新?遍歷，函數(shù)流程如圖?4-2所示。開始開始初始化vis?it[v]=0//初始化標志位?If（visit[v]==0） DFS(g,v,visite?d);v++Count++Count<=n結(jié)束YN圖4-SEQ圖4-\*ARABIC?2尋找最佳路徑?流程圖4.3最短路徑（ShortP?ath）利用迪杰特斯?拉算法，求v0到其余?頂點的最短路?徑path[],distan?ce[]是用來存放各?路徑的權(quán)值，借助輔助數(shù)組?s[]標志,是否當前頂點?屬于S(1,屬于)函數(shù)流程圖4-3所示。開始開始初始化dis?tence[]，s[],path[]開始主循環(huán)，每次求得v0?到某頂點v的最短距離，并將v并入中?minDis?=MAXEDG?E;//當前所知v0?的最短距離并?設(shè)初值為MA?XEAGE，inti=1,j=1,u=v0;!s[j]&&distan?ce[j]<minDis?u=j;//在s[]下一直往下找?minDis?=distan?ce[j];j<=nj=0;更新當前最短?路徑及距離；newDis?t=distan?ce[u]+GetWei?ght[u]distan?ce[j]=newDis?t;path[j]=u;//記錄尋找的最?短的路徑i<=n結(jié)束If(newDis?t<distan?ce[j])j<=nYNYNYYN圖4-SEQ圖4-\*ARABIC?3尋找最短路徑?流程圖4.4遍歷出某一起?點到終點的所?有路徑（Search?AllPat?h）利用圖的深度?優(yōu)先遍歷，利用訪問標志?位。path[]記錄路徑，visite?d[]設(shè)訪問標志，v起點，des終點，length?，代表的是訪問?景點的長度。若碰見死路或?者不同的路，則從上一個景?點，從新掃描，search?AllPat?h()流程如圖4-4所示。IIf（visite?d[V]）reture?n;//若所有景點都?訪問過，則終止v==desPrintf?Path(G,path,length?);visite?d[v]=1;GetWei?ght(v,i)!=MAXEDG?&&!visite?d[i]Search?AllPat?h(G,path,visite?d,i,des,length?+1)i++i<=n結(jié)束開始NYvisite?d[v]=0;NY圖4-SEQ圖4-\*ARABIC?4search?AllPat?h()流程圖4.5導入新文件（Loadne?wmap） 將指定文件導?入到鄰接表中?，再保存到zh?eke1.txt中,具體實現(xiàn)如圖?4-5所示。開始開始初始化Lin?kp，輸入文件名f?ilenam?e[20]Fprint?-Link(p，g，filena?me)SaveMa?p(g) L=P;結(jié)束圖4-SEQ圖4-\*ARABIC?5導入新文件結(jié)?構(gòu)示圖公園導游圖第五章系統(tǒng)實現(xiàn)PAGE15第五章系統(tǒng)實現(xiàn)5.1程序執(zhí)行之前?的準備首先在zhe?ke1.txt中保存?內(nèi)容圖5-1所示北門北門理工天堂汽車展覽中心?微瀾湖東門餐廳哲科技術(shù)中心?靜心湖體育中心愛情博物館涉外花園華天大酒店巾幗紀念堂56715710456553555765南門圖5-SEQ圖5-\*ARABIC?1涉外公園簡圖?在zheke?2.txt中保存?內(nèi)容圖5-2所示3長沙市3長沙市邵陽市衡陽市隆回縣710126825株洲市圖5-SEQ圖5-\*ARABIC?2城市連通圖5.2主界面表5-SEQ表5-\*ARABIC?1主界面5.3游客界面表5-SEQ表5-\*ARABIC?2游客界面5.4系統(tǒng)用戶界面?公園導游圖第六章解決的關(guān)鍵問?題PAGE18表5-SEQ表5-\*ARABIC?3系統(tǒng)用戶登錄?界面表5-SEQ表5-\*ARABIC?4系統(tǒng)用戶界面?5.5瀏覽公園全景?簡圖表5-5涉外公園簡?圖表5-6詳細信息表?5.6尋找某一起點?的最佳路徑和?指定起點、終點的最短路?徑表5-7查詢最佳路徑?表5-8查詢最短路徑?5.7尋找指定起點?、終點的所有路?徑表5-9輸入兩點之間?的所有路徑5.8刪除，添加結(jié)點，保存和導入新?地圖表5-10刪除結(jié)點表5-10導入新的地圖?第六章解決的關(guān)鍵問?題6.1如何實現(xiàn)尋找?最短路徑功能?我在網(wǎng)上查了?很多資料，在考慮好用鄰?接表做系統(tǒng)后?，我一直在尋找?一種合適的算?法來實現(xiàn)查找?最短路徑的功?能。最終我決定采?用迪杰特斯拉?算法。解決了這一難?題。6.2如何實現(xiàn)深度?優(yōu)先搜索系統(tǒng)采用一個?數(shù)組來做訪問?過的標記，如果正在訪問?結(jié)點的下一個?結(jié)點沒有訪問?，就采用函數(shù)的?遞歸來實現(xiàn)深?度優(yōu)先搜索。6.3如何修改地圖?通過對鏈表中?結(jié)點的修改，就能對鄰接表?中結(jié)點的修改?，在刪除結(jié)點時?，通過將后面結(jié)?點的邊信息將?次結(jié)點的信息?覆蓋，即Edge[i]