校園導(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） 了解二叉樹特性、存儲(chǔ)及其操作實(shí)現(xiàn)，在計(jì)算機(jī)領(lǐng)域運(yùn)用二叉樹編譯代碼實(shí)現(xiàn)一件簡(jiǎn)單實(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ì)用鄰接

2、鏈表和鄰接數(shù)組兩種方法來(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)單

3、路徑； （最短路徑長(zhǎng)度中轉(zhuǎn)次數(shù)最少） 2>任意兩個(gè)地點(diǎn)之間的一條最佳訪問(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 功能模塊圖：校園導(dǎo)游系統(tǒng)main()創(chuàng)建新地圖Create() 1. 查看西郵地圖功能菜單 3. 查詢路線基本狀況 2. 顯示基本信息 4. 添加新路線 6. 增加新景點(diǎn) 5. 撤銷舊路線 7. 撤銷舊景點(diǎn) 8. 最短路徑查詢 9. 最短連通路徑查詢 12. 查看所有簡(jiǎn)單路徑 0. 退出系統(tǒng) 13.查看中轉(zhuǎn)次數(shù)最少路徑 11. 查看所有景點(diǎn)

4、名稱 10. 查看所有景點(diǎn)詳情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)名稱以及編號(hào)和各景點(diǎn)之間的距離，方便更直觀的了解本校的景點(diǎn)分布；2. 顯示基本信息，顯示每一個(gè)景點(diǎn)可直達(dá)的景點(diǎn)路徑和距離；3. 查詢路線基本狀況，查詢從任意一個(gè)景點(diǎn)出發(fā)到

5、其余各景點(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è)廢棄或拆遷的景點(diǎn)并將刪除后的信息保存到文件里面；8. 最短路徑查詢，只需要從鍵盤輸入起點(diǎn)和終點(diǎn)的景點(diǎn)編號(hào)，就可以找出這兩點(diǎn)之間的最短路徑；9. 最短連通路徑查詢，從鍵

6、盤輸入起始景點(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)系圖；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è)景點(diǎn)的名稱和詳情輸入G->arcnum條路線將景點(diǎn)信息和路線存入文件i+2.輸出所有景點(diǎn)詳情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.添加新景點(diǎn)No=Locate(G，place)開始輸入景點(diǎn)名稱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.兩點(diǎn)之間的所有簡(jiǎn)單路徑和中轉(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.刪除景點(diǎn)開始輸入待刪除景點(diǎn)No刪除鄰接矩陣中第No行第No列的有路的路徑，G->arcnum減去相應(yīng)值從鄰接矩陣第No行第No列開始，將數(shù)據(jù)前移(G->vexnum)-3重點(diǎn)設(shè)計(jì)及編碼。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個(gè)結(jié)點(diǎn)pathjt+1=0; 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é)束了），第二

12、組為其余未確定最短路徑的頂點(diǎn)集合（用U表示），按最短路徑長(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

13、=1;i<=G->vexnum;i+)for(j=1;j<=G->vexnum;j+)fprintf(fp,"%d ",G->arcij);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í)候就不用再次輸入一連串繁瑣的信息了，可以直接打開所需的文件直接讀取便可，如此一來(lái)便省去了不

14、少事。五 測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果1.正常測(cè)試數(shù)據(jù)（3組）及運(yùn)行結(jié)果； 最短路徑查詢（權(quán)值最?。?兩點(diǎn)之間所有簡(jiǎn)單路徑查詢 兩點(diǎn)之間中轉(zhuǎn)次數(shù)最小路徑查詢2非正常測(cè)試數(shù)據(jù)（2組）及運(yùn)行結(jié)果。 兩點(diǎn)之間最短路徑查詢（所查景點(diǎn)不存在） 增加新路線（該路線已存在）六調(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è)較大漏洞，直接導(dǎo)致程序運(yùn)行的錯(cuò)誤，在此記錄下來(lái)作

15、為之后自省。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ù)那里，剛開始編寫的代碼第一次查詢的時(shí)候還能夠正確輸出，但是第二次第三次就會(huì)出