校園導(dǎo)游系統(tǒng)

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

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

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

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

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

6、盤輸入起始景點的編號，就可以找出一條最短連通路，方便旅客找出一條參觀所有景點的最佳路徑；10. 查看所有景點詳情，可以輸出所有景點的編號、名稱以及該景點的詳細(xì)介紹，供旅客選擇自己喜歡的地方；11. 查看所有景點名稱，輸出所有景點名稱，讓旅客知道本校的所有景點；12. 查看兩個景點的所有簡單路徑，輸出兩個景點之間的所有簡單路徑供給旅客選擇；13. 查看中轉(zhuǎn)次數(shù)最少路徑，輸出兩個景點之間途徑地方最少的一條路徑。四詳細(xì)設(shè)計1功能函數(shù)的調(diào)用關(guān)系圖；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->結(jié)束3.顯示圖信息i=1開始輸出iß àj的直達(dá)路徑i+i<=G->vexnum結(jié)束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.兩點之間的所有簡單路徑和中轉(zhuǎn)次數(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減去相應(yīng)值從鄰接矩陣第No行第No列開始，將數(shù)據(jù)前移(G->vexnum)-3重點設(shè)計及編碼。1> Dijkatra算法的修改路徑部分的代碼for(j=1;j<=G->vexnum;j+)if(!pathj0&&G->arckj<INFINITY&&distk+G->arckj<distj) distj=distk+G->arckj; /當(dāng)前最小權(quán)值t=1;while(pat

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

12、組為其余未確定最短路徑的頂點集合（用U表示），按最短路徑長度的遞增次序依次把第二組的頂點加入S中。在加入的過程中，總保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。此外，每個頂點對應(yīng)一個距離，S中的頂點的距離就是從v到此頂點的最短路徑長度，U中的頂點的距離，是從v到此頂點只包括S中的頂點為中間頂點的當(dāng)前最短路徑長度。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ù)，然后再存入所有的景點名稱和景點詳細(xì)介紹以及所有的路線，路線是以鄰接矩陣的形式存入文件的，鄰接矩陣?yán)锩娴拿恳粋€數(shù)據(jù)都對應(yīng)兩個景點，有路的存路徑長度，沒有路的默認(rèn)為一個極大值，這樣一來方便路線的讀取。將信息存入文件，以便下一次運行程序的時候就不用再次輸入一連串繁瑣的信息了，可以直接打開所需的文件直接讀取便可，如此一來便省去了不

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

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