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

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

2、種方法來(lái)實(shí)現(xiàn)數(shù)據(jù)的存儲(chǔ)與讀取；（ 4） 鞏固文件的存儲(chǔ)與讀取部分，以便能夠加深對(duì)文件讀寫的理解和更好的更熟練的實(shí)際應(yīng)用；（ 5） 學(xué)會(huì)用計(jì)算機(jī)解決實(shí)際問(wèn)題，將生活中的問(wèn)題數(shù)據(jù)化，然后輸入到計(jì)算機(jī)中以便更快的解決，提高自己的實(shí)踐能力以及自身的學(xué)習(xí)能力，加深對(duì)課本知識(shí)的理解和掌握。二.設(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)的問(wèn)路查詢：1任意兩個(gè)地點(diǎn)之間的一條最短的簡(jiǎn)單路徑；（最短路徑長(zhǎng)度中轉(zhuǎn)次數(shù)最少）2任意兩個(gè)地點(diǎn)之間

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

4、號(hào)和各景點(diǎn)之間的距離，方便更直觀的了解本校的景點(diǎn)分布；2. 顯示基本信息，顯示每一個(gè)景點(diǎn)可直達(dá)的景點(diǎn)路徑和距離；3. 查詢路線基本狀況，查詢從任意一個(gè)景點(diǎn)出發(fā)到其余各景點(diǎn)之間距離最短的路徑，提供給旅客最簡(jiǎ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)編號(hào)，就可以找出這兩點(diǎn)之間的最短路徑；9. 最短連通路徑查詢，從鍵盤輸入起始景點(diǎn)的編號(hào)，就可以找出一條最短連通路，方便旅客找出一條參觀所有景點(diǎn)的最佳路徑；10. 查看所有景點(diǎn)詳情，可以輸出所有景點(diǎn)的編號(hào)、名稱以及該景點(diǎn)的詳細(xì)介紹，供旅客選擇自己喜歡的地方；11. 查看所有景點(diǎn)名稱，輸出所有景點(diǎn)名稱，讓旅客知道本校的所有景點(diǎn)；12. 查看兩個(gè)景點(diǎn)的所有簡(jiǎn)單路徑，輸出兩個(gè)景點(diǎn)之間的所有簡(jiǎ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)之間的所有簡(jiǎ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、表示)，按最短路徑長(zhǎng)度的遞增次序依次把第二組的頂點(diǎn)加入S中。在加入的過(guò)程中，總保持從源點(diǎn)v到S中各頂點(diǎn)的最短路徑長(zhǎng)度不大于從源點(diǎn)v到U中任何頂點(diǎn)的最短路徑長(zhǎng)度。此外，每個(gè)頂點(diǎn)對(duì)應(yīng)一個(gè)距離，S中的頂點(diǎn)的距離就是從v到此頂點(diǎn)的最短路徑長(zhǎng)度，U中的頂點(diǎn)的距離，是從v到此頂點(diǎn)只包括S中的頂點(diǎn)為中間頂點(diǎn)的當(dāng)前最短路徑長(zhǎng)度。2>文件存儲(chǔ)功能的部分代碼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");文件存儲(chǔ)是先存入景點(diǎn)數(shù)和路線條數(shù)，然后再存入所有的景點(diǎn)名稱和景點(diǎn)詳細(xì)介紹以及所有的路線，路線是以鄰接矩陣的形式存入文件的，鄰接矩陣?yán)锩娴拿恳粋€(gè)數(shù)據(jù)都對(duì)應(yīng)兩個(gè)景點(diǎn)，有路的存路徑長(zhǎng)度，沒(méi)有路的默認(rèn)為一個(gè)極大值,這樣一來(lái)方便路線的讀取。將信息存入文件，以便下一次運(yùn)行程序的時(shí)候就不用再次輸入一連串繁瑣的信息了，可以直接打開(kāi)所需的文件直接讀取便可，如此一來(lái)便省去了不少事。五.測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1.正常測(cè)試數(shù)據(jù)（

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

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

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