校園導游系統(tǒng)

1、西安郵電大學數(shù)據(jù)結構課程設計報告題 目： 校園導游系統(tǒng)院系名稱： 專業(yè)名稱： 班 級： 學生姓名： 學號（8位）： 指導教師： 設計起止時間：2013年12月16日2013年12月27日一. 設計目的（1） 了解二叉樹特性、存儲及其操作實現(xiàn)，在計算機領域運用二叉樹編譯代碼實現(xiàn)一件簡單實際的操作，熟練掌握二叉樹的三種遍歷遞歸與非遞歸的實現(xiàn)；（2） 掌握圖的兩種遍歷深度優(yōu)先遍歷和廣度優(yōu)先遍歷，了解兩者的區(qū)別和優(yōu)缺點。學習在計算機中表示和處理圖形結構以及繪制簡單的地圖并輸出，熟練掌握圖的邏輯結構和存儲結構，學習用算法來解決實際問題；（3） 掌握鄰接鏈表和鄰接矩陣的存儲結構，以及這兩者的區(qū)別，會用鄰接

2、鏈表和鄰接數(shù)組兩種方法來實現(xiàn)數(shù)據(jù)的存儲與讀取；（4） 鞏固文件的存儲與讀取部分，以便能夠加深對文件讀寫的理解和更好的更熟練的實際應用；（5） 學會用計算機解決實際問題，將生活中的問題數(shù)據(jù)化，然后輸入到計算機中以便更快的解決，提高自己的實踐能力以及自身的學習能力，加深對課本知識的理解和掌握。二. 設計內(nèi)容<1> 設計題目：設計一個校園導游程序，并按各要求進行編程：要求： （1）設計并顯示學校的校園平面圖， 地點（地點名稱、地點介紹）， 路線（公里數(shù)）均不少于10個。 （2）提供圖中任意地點相關信息的查詢。 （3）提供圖中任意地點的問路查詢： 1>任意兩個地點之間的一條最短的簡單

3、路徑； （最短路徑長度中轉次數(shù)最少） 2>任意兩個地點之間的一條最佳訪問路線； （帶權（公里數(shù)）最短路徑長度） 3>任意兩個地點之間的所有簡單路徑。 （4）提供圖中所有地點的最佳布網(wǎng)方案； （5）增加新地點和路線、撤銷舊地點和路線。三概要設計1 功能模塊圖：校園導游系統(tǒng)main()創(chuàng)建新地圖Create() 1. 查看西郵地圖功能菜單 3. 查詢路線基本狀況 2. 顯示基本信息 4. 添加新路線 6. 增加新景點 5. 撤銷舊路線 7. 撤銷舊景點 8. 最短路徑查詢 9. 最短連通路徑查詢 12. 查看所有簡單路徑 0. 退出系統(tǒng) 13.查看中轉次數(shù)最少路徑 11. 查看所有景點

4、名稱 10. 查看所有景點詳情2各個模塊詳細的功能描述。該導游系統(tǒng)能為來訪者提供包括景點介紹、景點查詢、仿真地圖、最短路徑之類的快捷指導。最短路徑查詢和景點概況主要運用了Dijstra算法來實現(xiàn)，其他功能都是通過一些簡單的算法來編寫的。所謂系統(tǒng)，也不盡然，只是一個小小的信息提示。其中主要運用到的程序、算法也較簡單。除了可以創(chuàng)建一個新的地圖外，其主要功能還有以下幾點：1. 查看西郵地圖，自制的西安郵電大學方針地圖，地圖上標有景點名稱以及編號和各景點之間的距離，方便更直觀的了解本校的景點分布；2. 顯示基本信息，顯示每一個景點可直達的景點路徑和距離；3. 查詢路線基本狀況，查詢從任意一個景點出發(fā)到

5、其余各景點之間距離最短的路徑，提供給旅客最簡單的路線介紹；4. 添加新路線，在原有路線的基礎之上，新增一條路線并保存到文件里面（該功能中新增路線的兩端只能是目前地圖上已有景點）；5. 撤銷舊路線，在原有路線的基礎之上，刪除一條廢棄不用的路線并將刪除后的信息保存到文件里面；6. 增加新景點，在原有景點的基礎之上，添加一個新的景點并保存到文件里面，添加景點包括景點名稱和景點詳細介紹；7. 撤銷舊景點，就是在原有景點的基礎之上，刪除一個廢棄或拆遷的景點并將刪除后的信息保存到文件里面；8. 最短路徑查詢，只需要從鍵盤輸入起點和終點的景點編號，就可以找出這兩點之間的最短路徑；9. 最短連通路徑查詢，從鍵

6、盤輸入起始景點的編號，就可以找出一條最短連通路，方便旅客找出一條參觀所有景點的最佳路徑；10. 查看所有景點詳情，可以輸出所有景點的編號、名稱以及該景點的詳細介紹，供旅客選擇自己喜歡的地方；11. 查看所有景點名稱，輸出所有景點名稱，讓旅客知道本校的所有景點；12. 查看兩個景點的所有簡單路徑，輸出兩個景點之間的所有簡單路徑供給旅客選擇；13. 查看中轉次數(shù)最少路徑，輸出兩個景點之間途徑地方最少的一條路徑。四詳細設計1功能函數(shù)的調(diào)用關系圖；Main( ) read()Map( )Serach(&G)Infor(&G)Display(& G)Search_All(&

7、;G,1)Search_All(&G,0)Information(&G)exit(0)Mintree(& G)Del(&G)Shortcut(&G)Delvex(&G)Save(&G)Addvex(&G)Add(&G)Infor(&G)2各功能函數(shù)的數(shù)據(jù)流程圖；1.創(chuàng)建新地圖輸入G->vexnum，G->arcnumi=1i<=G->vexnum輸入第i個景點的名稱和詳情輸入G->arcnum條路線將景點信息和路線存入文件i+2.輸出所有景點詳情i=1開始輸出G->vexi.na

8、mei+i<=G->vexnum輸出G->結束3.顯示圖信息i=1開始輸出iß àj的直達路徑i+i<=G->vexnum結束j+j=1j<=G->vexnumG->arcij=327684.添加新景點No=Locate(G，place)開始輸入景點名稱placei=1i<=G->vexnumreturnG->arciNo=INFINITYG->arcNoi=INFINITY(G->vexnum)+；G->vexNo.num=No;No<=G->vexnumNo

9、>=15.添加新路線開始輸入start 和 endx=1returnG->arcstartend=length G->arcstartend=INFINITY輸入length輸入x(G->arcnum)+G->arcendstart=length6.兩點之間的所有簡單路徑和中轉次數(shù)最少路徑開始輸入start 和 endtop=0Min(G，start，end)Depsearch(G，start，end)cont=INFINITYx=17.刪除路線開始輸入待刪除路線G->arcstartend=INFINITYG->arc endstart=INFINI

10、TY(G->arcnum)-8.刪除景點開始輸入待刪除景點No刪除鄰接矩陣中第No行第No列的有路的路徑，G->arcnum減去相應值從鄰接矩陣第No行第No列開始，將數(shù)據(jù)前移(G->vexnum)-3重點設計及編碼。1> Dijkatra算法的修改路徑部分的代碼for(j=1;j<=G->vexnum;j+)if(!pathj0&&G->arckj<INFINITY&&distk+G->arckj<distj) distj=distk+G->arckj; /當前最小權值t=1;while(pat

11、hkt!=0) /pathkt未結束pathjt=pathkt;t+;pathjt=k; /第k個結點pathjt+1=0; Dijkstra算法是典型最短路算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。Dijkstra算法思想為：設G=(V,E)是一個帶權有向圖，把圖中頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合（用S表示，初始時S中只有一個源點，以后每求得一條最短路徑 , 就將 加入到集合S中，直到全部頂點都加入到S中，算法就結束了），第二

12、組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當前最短路徑長度。2> 文件存儲功能的部分代碼fprintf(fp,"%d %dn",G->vexnum,G->arcnum);for(i=1;i<=G->vexnum;i+)fprintf(fp,PV);for(i

13、=1;i<=G->vexnum;i+)for(j=1;j<=G->vexnum;j+)fprintf(fp,"%d ",G->arcij);fprintf(fp,"n");文件存儲是先存入景點數(shù)和路線條數(shù)，然后再存入所有的景點名稱和景點詳細介紹以及所有的路線，路線是以鄰接矩陣的形式存入文件的，鄰接矩陣里面的每一個數(shù)據(jù)都對應兩個景點，有路的存路徑長度，沒有路的默認為一個極大值，這樣一來方便路線的讀取。將信息存入文件，以便下一次運行程序的時候就不用再次輸入一連串繁瑣的信息了，可以直接打開所需的文件直接讀取便可，如此一來便省去了不

14、少事。五 測試數(shù)據(jù)及運行結果1.正常測試數(shù)據(jù)（3組）及運行結果； 最短路徑查詢（權值最?。?兩點之間所有簡單路徑查詢 兩點之間中轉次數(shù)最小路徑查詢2非正常測試數(shù)據(jù)（2組）及運行結果。 兩點之間最短路徑查詢（所查景點不存在） 增加新路線（該路線已存在）六調(diào)試情況，設計技巧及體會1對自己的設計進行評價，指出合理和不足之處，提出改進方案；（1）本程序參考課本上的導游系統(tǒng)編寫而成。期間或自我摸索，或查找資料，或請教同學，最終實現(xiàn)了該系統(tǒng)的成功運行。編程過程不斷出現(xiàn)各種各樣的，均能設法將其化解，算是在實踐中學得編譯運行調(diào)試指法。以下是編寫過程中出現(xiàn)過的幾個較大漏洞，直接導致程序運行的錯誤，在此記錄下來作

15、為之后自省。a. scanf中缺少“取地址符”，輸入不起作用；b. 源程序所給的“求最短路徑”算法錯誤，參照課Dijkstra算法之后寫出本程序所用的算法，值得肯定；c. 調(diào)用display函數(shù)時錯誤，經(jīng)過同學指點，刪掉五句多余代碼，程序成功運行。（2）書上介紹的弗洛伊德算法只需計算一次，即可求得每一對頂點之間的最短效率，但時間復雜度為O（n3）。迪杰斯特拉算法雖然每求一次最短路徑都必須重新搜索一遍，頻繁查找時會導致效率降低，但是時間復雜度要比弗洛伊德算法低，因此我還是選擇了Dijkstra算法其中編程過程中顯露出來的問題也必須引起高度重視，在今后的學習中必當萬分注意絕不再犯。比如細心問題，有次的一個小小的“取地址符”沒有添加，導致整個程序無法運行，檢查了好久才發(fā)現(xiàn)。所以說，編程是個細活，只有嚴謹?shù)膽B(tài)度，細心的思路以及良好的學習習慣，最終才能收獲成功的喜悅。2對設計及調(diào)試過程的心得體會。 這次課程設計顯然要比去年上手的多，畢竟已經(jīng)是第二次課程設計了，所以心里也沒那么緊張了，但是在編寫過程中還是遇到了種種困難和極難解決的問題。就比如說最少中轉次數(shù)那里，剛開始編寫的代碼第一次查詢的時候還能夠正確輸出，但是第二次第三次就會出