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

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

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

3、的一條最佳訪問路線；（帶權(quán)（公里數(shù)）最短路徑長度）3任意兩個(gè)地點(diǎn)之間的所有簡單路徑。（4）提供圖中所有地點(diǎn)的最佳布網(wǎng)方案；（5）增加新地點(diǎn)和路線、撤銷舊地點(diǎn)和路線。三概要設(shè)計(jì)1.功能模塊圖:2各個(gè)模塊詳細(xì)的功能描述。該導(dǎo)游系統(tǒng)能為來訪者提供包括景點(diǎn)介紹、景點(diǎn)查詢、仿真地圖、最短路徑之類的快捷指導(dǎo)。最短路徑查詢和景點(diǎn)概況主要運(yùn)用了Dijstra算法來實(shí)現(xiàn)，其他功能都是通過一些簡單的算法來編寫的。所謂系統(tǒng)，也不盡然，只是一個(gè)小小的信息提示。其中主要運(yùn)用到的程序、算法也較簡單。除了可以創(chuàng)建一個(gè)新的地圖外，其主要功能還有以下幾點(diǎn)：1. 查看西郵地圖，自制的西安郵電大學(xué)方針地圖，地圖上標(biāo)有景點(diǎn)名稱以及編

4、號和各景點(diǎn)之間的距離，方便更直觀的了解本校的景點(diǎn)分布；2. 顯示基本信息，顯示每一個(gè)景點(diǎn)可直達(dá)的景點(diǎn)路徑和距離；3. 查詢路線基本狀況，查詢從任意一個(gè)景點(diǎn)出發(fā)到其余各景點(diǎn)之間距離最短的路徑，提供給旅客最簡單的路線介紹；4. 添加新路線，在原有路線的基礎(chǔ)之上，新增一條路線并保存到文件里面（該功能中新增路線的兩端只能是目前地圖上已有景點(diǎn)）；5. 撤銷舊路線，在原有路線的基礎(chǔ)之上，刪除一條廢棄不用的路線并將刪除后的信息保存到文件里面；6. 增加新景點(diǎn)，在原有景點(diǎn)的基礎(chǔ)之上，添加一個(gè)新的景點(diǎn)并保存到文件里面，添加景點(diǎn)包括景點(diǎn)名稱和景點(diǎn)詳細(xì)介紹；7. 撤銷舊景點(diǎn)，就是在原有景點(diǎn)的基礎(chǔ)之上，刪除一個(gè)廢棄或

5、拆遷的景點(diǎn)并將刪除后的信息保存到文件里面；8. 最短路徑查詢，只需要從鍵盤輸入起點(diǎn)和終點(diǎn)的景點(diǎn)編號，就可以找出這兩點(diǎn)之間的最短路徑；9. 最短連通路徑查詢，從鍵盤輸入起始景點(diǎn)的編號，就可以找出一條最短連通路，方便旅客找出一條參觀所有景點(diǎn)的最佳路徑；10. 查看所有景點(diǎn)詳情，可以輸出所有景點(diǎn)的編號、名稱以及該景點(diǎn)的詳細(xì)介紹，供旅客選擇自己喜歡的地方；11. 查看所有景點(diǎn)名稱，輸出所有景點(diǎn)名稱，讓旅客知道本校的所有景點(diǎn)；12. 查看兩個(gè)景點(diǎn)的所有簡單路徑，輸出兩個(gè)景點(diǎn)之間的所有簡單路徑供給旅客選擇；13. 查看中轉(zhuǎn)次數(shù)最少路徑，輸出兩個(gè)景點(diǎn)之間途徑地方最少的一條路徑。四詳細(xì)設(shè)計(jì)1.功能函數(shù)的調(diào)用關(guān)

6、系圖;2.各功能函數(shù)的數(shù)據(jù)流程圖;1創(chuàng)建新地圖2.輸出所有景點(diǎn)詳情3.顯小圖信息i+j+4.添加新景點(diǎn)6.兩點(diǎn)之間的所有簡單路徑和中轉(zhuǎn)次數(shù)最少路徑7刪除路線(G->arcnum)-8.刪除景點(diǎn)3.重點(diǎn)設(shè)計(jì)及編碼1>Dijkatra算法的修改路徑部分的代碼for(j=1;j<=G->vexnum;j+)if(!path皿0&&G->arckj<INFINITY&&distk+G->arckj<distj)distj=distk+G->arckj;t=1;while(pathkt!=0)path皿t=pathkt

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

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

9、;i+)for(j=1;j<=G->vexnum;j+)fprintf(fp,"%d",G->arc皿);fprintf(fp,"n");文件存儲是先存入景點(diǎn)數(shù)和路線條數(shù)，然后再存入所有的景點(diǎn)名稱和景點(diǎn)詳細(xì)介紹以及所有的路線，路線是以鄰接矩陣的形式存入文件的，鄰接矩陣?yán)锩娴拿恳粋€(gè)數(shù)據(jù)都對應(yīng)兩個(gè)景點(diǎn)，有路的存路徑長度，沒有路的默認(rèn)為一個(gè)極大值,這樣一來方便路線的讀取。將信息存入文件，以便下一次運(yùn)行程序的時(shí)候就不用再次輸入一連串繁瑣的信息了，可以直接打開所需的文件直接讀取便可，如此一來便省去了不少事。五.測試數(shù)據(jù)及運(yùn)行結(jié)果1.正常測試數(shù)據(jù)（

10、3組）及運(yùn)行結(jié)果；兩點(diǎn)之間所有簡單路徑查詢iWnCT«up5.買噓E吊丸謁幅上昨中心ti.igfi12.籃算場心盤廣場槐腌is.W襦域點(diǎn)的景睛號：u麟域域景糕號需士摭場T籃涉場T美食廣場-淵沖瑛犍土操場"范富榛"測日施一潛育恰一潛育須一>圖書館一>大帶中心T噴泉T行政橫T學(xué)校正門T教學(xué)樓一琪驗(yàn)樓按任意鍍返幽兩點(diǎn)之間中轉(zhuǎn)次數(shù)最小路徑查詢i-wn2.行牌5.實(shí)驗(yàn)片6.審熱心13.W®14就睢請輸Ai2點(diǎn)的景點(diǎn)編號442.非正常測試數(shù)據(jù)（2組）及運(yùn)行結(jié)果兩點(diǎn)之間最短路徑查詢（所查景點(diǎn)不存在）6為辯心8.洗洛中心"體制i組腦物土就12.籃球

11、場13溪新14晅聯(lián)1S.公寓模請輸入起始景點(diǎn)編號：1終點(diǎn)鐳編號:1915 .公寓楂增加新路線（該路線已存在）場梨電后- 3 15 9 1* « 0 4 2 6 11*餃景點(diǎn)不存在,Pre除anykeytocontinue請輸入新瑁路線的起點(diǎn)編碼：1終點(diǎn)名稱:2距禺：12六.調(diào)試情況，設(shè)計(jì)技巧及體會1 .對自己的設(shè)計(jì)進(jìn)行評價(jià)，指出合理和不足之處，提出改進(jìn)方案;（1）本程序參考課本上的導(dǎo)游系統(tǒng)編寫而成。期間或自我摸索，或查找資料，或請教同學(xué)，最終實(shí)現(xiàn)了該系統(tǒng)的成功運(yùn)行。編程過程不斷出現(xiàn)各種各樣的，均能設(shè)法將其化解，算是在實(shí)踐中學(xué)得編譯運(yùn)行調(diào)試指法。以下是編寫過程中出現(xiàn)過的幾個(gè)較大漏洞，直

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