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

1、西安垂B院數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：校園導(dǎo)游系統(tǒng)系部名稱：計(jì)算機(jī)系專業(yè)名稱：軟件工程班級(jí)：0604班學(xué)號(hào)：04065139學(xué)生姓名：高孟迪指導(dǎo)教師：王春梅2008年6月1日至2008年6月8日1 .實(shí)驗(yàn)?zāi)康? .對(duì)自己學(xué)過(guò)的知識(shí)進(jìn)一步的加深理解，對(duì)數(shù)據(jù)結(jié)構(gòu)的算法思想要有更深的理解。2 .通過(guò)課程設(shè)計(jì)，學(xué)會(huì)通過(guò)系統(tǒng)分析、系統(tǒng)設(shè)計(jì)、編程調(diào)試，寫實(shí)驗(yàn)報(bào)告等環(huán)節(jié)，進(jìn)一步掌握應(yīng)用系統(tǒng)設(shè)計(jì)的方法和步驟，靈活運(yùn)用并深刻理解典型數(shù)據(jù)結(jié)構(gòu)在軟件開發(fā)中的應(yīng)用。3 .學(xué)會(huì)綜合運(yùn)用數(shù)據(jù)結(jié)構(gòu)課程中學(xué)到的幾種典型數(shù)據(jù)結(jié)構(gòu)，如鏈表，棧，隊(duì)列，以及程序設(shè)計(jì)語(yǔ)言（C語(yǔ)言），自行實(shí)現(xiàn)一個(gè)較為完整的應(yīng)用系統(tǒng)的設(shè)計(jì)與開發(fā)。2 .課程

2、設(shè)計(jì)內(nèi)容基本要求：校園平面圖（景點(diǎn)、路徑等信息）存儲(chǔ)選取校園或某景區(qū)中多個(gè)具有代表性景點(diǎn)，抽象成無(wú)向帶權(quán)圖?？刹捎绵徑颖砘蜞徑佣嘀乇泶鎯?chǔ)。查詢圖中任意景點(diǎn)的相關(guān)信息查詢道路信息（道路類別、沿途景色等）查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑利用迪杰斯特拉或弗洛伊德算法確定最短路徑從某個(gè)景點(diǎn)出發(fā)給出訪問(wèn)所有景點(diǎn)的最佳行走方案利用深度優(yōu)先和廣度優(yōu)先搜索遍歷圖查詢?nèi)我鈨删包c(diǎn)之間的所有路徑（選做）3 .需求分析現(xiàn)在大多數(shù)的學(xué)校由于不斷的擴(kuò)張，這也就使得學(xué)校不得不建立的更大。這也就為人們拜訪學(xué)校造成了很大的不便。人們往往不熟悉學(xué)校，找個(gè)東西，或某處帶來(lái)了極大的不便。往往要花很多時(shí)間在這一方面。然而要是有

3、一個(gè)學(xué)校導(dǎo)游系統(tǒng)這將給乘客帶來(lái)極大的方便，使人們一下就能了解到這個(gè)學(xué)校的大致的情況。功能：這個(gè)系統(tǒng)給用戶提供查詢景點(diǎn)，瀏覽路徑，尋找最佳的方案到達(dá)目的地，還提供了最佳路徑。實(shí)現(xiàn)的目標(biāo)：實(shí)現(xiàn)對(duì)某一個(gè)學(xué)校的校園導(dǎo)游系統(tǒng)。4 .概要設(shè)計(jì).系統(tǒng)結(jié)構(gòu)圖系統(tǒng)分析：用的圖的算法進(jìn)行構(gòu)造，用鄰接表建立圖，然后再用深度優(yōu)先遍歷進(jìn)行搜索，查找所需的路徑。再用迪杰特斯拉算法求出兩個(gè)景點(diǎn)之間的最佳路徑。結(jié)構(gòu)圖：.功能模塊說(shuō)明創(chuàng)建圖(InitGraph):建立無(wú)向圖，把學(xué)校的景點(diǎn)及景點(diǎn)的信息，連接起來(lái)建立鄰接表采用鏈?zhǔn)郊禹樖酱鎯?chǔ)。瀏覽學(xué)校的全景(Browser)：列出學(xué)校的所有的景點(diǎn)。尋找最佳路徑(DFSTravers

4、e：):輸入一個(gè)景點(diǎn)，會(huì)吧所有都瀏覽一邊，并找出最佳的路徑。最短路徑(ShortPath):求出起點(diǎn)和終點(diǎn)的最佳路徑，并求出最佳路徑的長(zhǎng)度。遍歷出某一起點(diǎn)到終點(diǎn)的所有路徑(SearchAllPath)：找出所有路徑，利用深度優(yōu)先遍歷。五.詳細(xì)設(shè)計(jì)創(chuàng)建圖：結(jié)束瀏覽學(xué)校全景用數(shù)組存放這個(gè)學(xué)校的全部景點(diǎn)，在通過(guò)遍歷數(shù)組打印出學(xué)校的所有景點(diǎn)及其信息。尋找最佳路徑(DFSTraverse):利用深度優(yōu)先的思想，遍歷圖找出一條最佳最佳的的路徑，讓它遍歷所有景點(diǎn)。利用遞歸的思想，往下遍歷，訪問(wèn)標(biāo)志位，若訪問(wèn)過(guò)在下次就不用訪問(wèn)。若找完一個(gè)分支在下次重新遍歷。開始visitedv=0;/初始化標(biāo)志位一二二二土二

5、_L_iiif(visitedv=0)'DFS(g,v,visited);/對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFv+;count+;一y一二二lcount<=n結(jié)束最短路徑(ShortPath):利用迪杰特斯拉算法，求v0到其余頂點(diǎn)的最短路徑path,distance口是用來(lái)存放各路徑的權(quán)值，借助輔助數(shù)組s標(biāo)志，是否當(dāng)前頂點(diǎn)屬于S(1,屬于)。遍歷出某一起點(diǎn)到終點(diǎn)的所有路徑(SearchAllPath):利用圖的深度優(yōu)先遍歷，利用訪問(wèn)標(biāo)志位。path記錄路徑，visited設(shè)訪問(wèn)標(biāo)志,v起點(diǎn),des終點(diǎn),length，代表的是訪問(wèn)景點(diǎn)的長(zhǎng)度。若碰見死路或者不同的路，則從上一個(gè)景點(diǎn)，從新掃描。

6、運(yùn)行結(jié)果:主界面:學(xué)校全景:函H:tuiDebug®.exe路有佳地所;|最的的&<目點(diǎn)和息氏II起點(diǎn)信個(gè)圖游園一發(fā)點(diǎn)一園統(tǒng)建出創(chuàng)瀏尋查12345678國(guó)“D:200TC課程設(shè)計(jì)、十111。©1111名圖.excJn|x|10111213正門基礎(chǔ)教學(xué)樓實(shí)驗(yàn)樓行政樓卜噴泉圖書館大學(xué)生活動(dòng)中心人工湖體育館操場(chǎng)食堂宿舍某一起點(diǎn)的最佳路徑I西安郵電學(xué)院正門I供學(xué)生平時(shí)上課用I培訓(xùn)學(xué)生的地方I管理學(xué)生的地方I最能吸引人的地方I包藏各類圖書I大學(xué)生活動(dòng)中心I約會(huì)的好地方I體育館I操場(chǎng)I食堂I學(xué)生宿舍國(guó)“D:200TC課程設(shè)計(jì)、十111。©1111式圖.ckc黃M

7、KMMMKMMMKMMM逐攵洶使校：園導(dǎo)卡呈序M：*MMM：*MMM：*MM：*-n景點(diǎn)名稱；景點(diǎn)描述£££££££££££££eeeeeeeeeeeee門礎(chǔ)驗(yàn)政蠶學(xué)工加堂窿實(shí)本圖大人體操食宿東>>>>>>>>>>>>>12345678901231111動(dòng)活館生總一番菖甌包；約體操食空門用方活正課方方地生院上地地的書善學(xué)時(shí)的的人圖大地電孟生量好舍瞿必奉吸各的館宿會(huì)命堂生一請(qǐng)輸入你寰開始的景

8、點(diǎn);2基礎(chǔ)教學(xué)科噴泉-濯書館-人工湖-東門-大學(xué)生活動(dòng)中心行政樓正門實(shí)驗(yàn)樓體育館食堂蓿舍-操場(chǎng)請(qǐng)按任意鍵繼續(xù).一個(gè)起點(diǎn)的所有路徑:國(guó)“D:200TC課程設(shè)計(jì)、十111。©1111名圖.excJn|x|一圖書館一實(shí)驗(yàn)才婁一體育館一食堂一宿舍一一圖書錯(cuò)一實(shí)驗(yàn)樓一操場(chǎng)一傳胃館一置堂一宿舍一B圖書館一實(shí)驗(yàn)樓5一圖書館一噴泉一【一宿吉一實(shí)驗(yàn)樓二體育館一.*茅陵一2登門一一大正門一君政樓一東門一人工湖一圖書館一噴泉一基礎(chǔ)教學(xué)樓一實(shí)驗(yàn)樓一體育館一食堂一宿舍-正門一行政樓一東門一人工湖一圖書館一噴泉一基礎(chǔ)教學(xué)樓一實(shí)驗(yàn)樓一操場(chǎng)一體育植一食堂-宿舍一4正門一行政樓一東門一人工湖一圖書館一噴泉一基礎(chǔ)教學(xué)樓

9、一實(shí)驗(yàn)樓一操場(chǎng)一食堂一宿舍一1一噴是一基礎(chǔ)1一噴臬一基鼬1一噴臬一基鼬:一噴臬一基鼬小樓一實(shí)驗(yàn)樓一體育館一操場(chǎng)一食甄一實(shí)驗(yàn)樓一體育館一食堂一蓿舍一學(xué)”.婁一密驗(yàn)堂-宿舍一場(chǎng)一體育館一食堂一宿舍一學(xué)校的圖:館一實(shí)驗(yàn)樓-館一實(shí)驗(yàn)樓-一舉堂一宿舍一操場(chǎng)一食堂一后舍一-體育館一食堂一宿舍一濰揚(yáng)-使直館-？食堂-宿舍-.一圖書館一實(shí)驗(yàn)樓一寸果履一食堂一宿舍一請(qǐng)按任意鍵繼續(xù)六、調(diào)試情況，設(shè)計(jì)技巧及體會(huì)這次課程設(shè)計(jì)給我的感觸很多，課程設(shè)計(jì)沒開始之前我總是在想今年的課程設(shè)計(jì)會(huì)不會(huì)象去年那樣辛苦，但是這兩周下來(lái)我當(dāng)然也感到累，也有心情煩躁的時(shí)候，體會(huì)到調(diào)試成功使的那種喜悅。課程設(shè)計(jì)之前老師讓我們自己先將設(shè)計(jì)思路

10、寫好，都做了哪些模塊，第一天要檢查。我當(dāng)時(shí)是在電腦上寫了，那天下午編了一下午，沒什么成就弄得我很心煩，再想到快要考試，那種急于求成的心更迫切，自己很難平靜。第二天老師檢查時(shí)我什麼都沒有看到同學(xué)的程序我開始著急了，但那會(huì)我只有一個(gè)念頭我得從新開始，由于對(duì)圖不是很了解，我就從讀寫模塊開始，就使用簡(jiǎn)單的C語(yǔ)知識(shí)，那天早上將那兩個(gè)模塊給拿下了。下機(jī)后我在寢室開始編程，開始進(jìn)入真正的圖部分，邊思考怎樣可以將它們聯(lián)系起來(lái)，邊進(jìn)行調(diào)試。對(duì)編程興趣很濃，直到晚上十點(diǎn)我已經(jīng)將老師的要求完成差不多。這些日子是很辛苦，但我學(xué)到了很多東西，和同學(xué)一起分享調(diào)試成功的那種喜悅，我完成的早，同學(xué)有問(wèn)題會(huì)讓我?guī)椭趲退麄兊?/p>

11、過(guò)程中我也學(xué)會(huì)了很多種不同的思想，讓我對(duì)圖有了更深刻的理解。當(dāng)然，我要感謝我們的程序設(shè)計(jì)老師，是她給了我們一個(gè)相對(duì)輕松有趣的環(huán)境，讓我們感到在設(shè)計(jì)中沒有壓力，在她的幫助下，我終于完成了本次課程設(shè)計(jì)的任務(wù)七、參考文獻(xiàn)C語(yǔ)言程序設(shè)計(jì)王曙燕等科學(xué)出版社數(shù)據(jù)結(jié)構(gòu)一一使用C語(yǔ)言陳一華等電子科技大學(xué)出版社數(shù)據(jù)結(jié)構(gòu)一一C語(yǔ)言描述耿國(guó)華高等教育出版社數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版嚴(yán)蔚敏，吳偉民清華大學(xué)出版社葭程序源代碼#include"stdio.h"#include"stdlib.h"#include"string.h"#include"iostre

12、am.h"#defineMAX40#defineMAXEDGE500typedefstructArcNodeintdata;/該弧所得指向的頂點(diǎn)的位置ArcNode*nextarc;/指向下一條弧的指針ArcNode,*ArcLink;typedefstructVNode/頂點(diǎn)信息(charname30;intnum;charintroduction100;指向第一條依附該頂點(diǎn)的弧的指針ArcLinkfirstarc;/VNode,AdjListMAX+1;typedefstructALGraph(AdjListvdata;intvexnum,arcnum;/圖的頂點(diǎn)數(shù)和弧數(shù)ALGr

13、aph;intEdgeMAXMAX;/用來(lái)存放路徑的權(quán)值intn,e;voidCreateGraph(AdjList&g)/創(chuàng)建圖/從文件讀入圖的信息，包括景點(diǎn)信息，和路的信息FILE*fp;intnum;charname20;charinformation100;inti=1;inta,b,weight;ArcLinkp,q;/定義一條邊的兩個(gè)端點(diǎn)的臨時(shí)指針fp=fopen("tuxinxi.txt","r");/打開圖信息文件if(fp=NULL)printf("圖信息文件不能打開.”)；exit(0);for(i=1;i<=

14、n;i+)/對(duì)路的權(quán)值進(jìn)行初始化for(intj=1;j<=n;j+)if(i=j)Edgeij=0;/主對(duì)角線上的(自己對(duì)自己付為零);elseEdgeij=MAXEDGE;for(i=1;i<=n;i+)/初始化鄰接表，gi.firstarc=NULL;for(i=1;i<=n;i+)/從文件讀入頂點(diǎn)的信息fscanf(fp,"%d",&num);gi.num=num;fscanf(fp,"%s",name);strcpy(,name);fscanf(fp,"%s",information)

15、;strcpy(roduction,information);for(intj=1;j<=e;j+)/從文件中讀入邊的信息fscanf(fp,"%d",&a);fscanf(fp,"%d",&b);fscanf(fp,"%d",&weight);Edgeab=weight;Edgeba=weight;p=(ArcLink)malloc(sizeof(ArcNode);/為頂點(diǎn)申請(qǐng)空間p->data=a;p->nextarc=gb.firstarc;gb.firstarc=p;/把p

16、插進(jìn)來(lái)q=(ArcLink)malloc(sizeof(ArcNode);q->data=b;q->nextarc=ga.firstarc;ga.firstarc=q;fclose(fp);voidBrowser(AdjListG)/瀏覽整個(gè)景點(diǎn)intv;printf("111n");printf("|編號(hào)|景點(diǎn)名稱|簡(jiǎn)介In");for(v=1;v<=n;v+)printf("|%-4d|%-16s|%-56s|n",Gv.num,G,Groduction);printf("1111

17、n");intGetWeight(intv1,intv2)/得到兩個(gè)景點(diǎn)之間的路的權(quán)值if(v1<0|v1>n|v2<0|v2>n)printf("該地點(diǎn)不存在！")；return0;returnEdgev1v2;voidDIJ(AdjListG,intv0,intdistance,intpath)/迪杰特斯拉算法/求v0到其余頂點(diǎn)的最短路徑path,distance是用來(lái)存放各路徑的權(quán)值/借助輔助數(shù)組s口標(biāo)志，是否當(dāng)前頂點(diǎn)屬于S(1,屬于)int*s=newintn;intminDis=0,i=0,j=0,u=0;for(i=1;i<

18、;=n;i+)/初始化distance,s,pathdistancei=GetWeight(v0,i);si=0;if(i!=v0&&distance。卜MAXEDGE)pathi=v0;elsepathi=-1;/v0至Uv0為-1sv0=1;/v0入s集distancev0=0;/v0至Uv0的距離為零for(i=1;i<n;i+)/開始主循環(huán)，每次求得v0到某個(gè)頂點(diǎn)v的最短距離，并將v并入s中minDis=MAXEDGE;/當(dāng)前所知v0頂點(diǎn)的最近距離，并設(shè)初值為MAXEGDEintu=v0;/把v0給ufor(j=1;j<=n;j+)if(!sj&&a

19、mp;distancej<minDis)/查找屬于s并且求最小的路徑(u=j;/在s一直往下找minDis=distancej;/賦給最小路徑su=1;/離v0最近的景點(diǎn)，入sfor(j=1;j<=n;j+)/更新當(dāng)前最短路徑及距離(if(!sj&&GetWeight(u,j)<MAXEDGE)(intnewdist=distanceu+GetWeight(u,j);if(newdist<distancej)(distancej=newdist;pathj=u;/記錄下尋找最短的路voidShortPath(AdjListg)/求兩點(diǎn)的最短路徑(intq

20、idian,zhongdian;intdistanceMAX;intpathMAX;intminPath=0;intwayMAX;intq=0;intpre=0;printf("n");printf("請(qǐng)輸入要查詢的景點(diǎn)的起點(diǎn)，終點(diǎn)：")；scanf("%d,%d”,&qidian,&zhongdian);DIJ(g,qidian,distance,path);intw=zhongdian;while(w!=qidian)/遍歷path口并把到終點(diǎn)的路存放在way口中(q+;wayq=pathw;w=pathw;printf(&

21、quot;路徑為:");/輸出路徑for(intj=q;j>=1;j-)(printf("%s->",);printf("%s",);printf("n");printf("最短路徑為d",distancezhongdian);printf("n");voidSerach(AdjListG)/查詢景點(diǎn)信息intk,flag=1;while(flag)(printf("請(qǐng)輸入要查詢的景點(diǎn)編號(hào)：")；scan

22、f("%d",&k);if(k<0|k>n)(printf("景點(diǎn)編號(hào)不存在！請(qǐng)重新輸入景點(diǎn)編號(hào)：")；scanf("%d",&k);if(k>=0&&k<=n)flag=0;printf("111n");printf("|編號(hào)|景點(diǎn)名稱|簡(jiǎn)介In");printf("|%-4d|%-16s|%-56s|n",Gk.num,G,Groduction);printf("1111n"

23、);voidDFS(AdjListg,intv,intvisited口)/從v個(gè)頂點(diǎn)深度優(yōu)先搜索(ArcLinkp;intw;visitedv=1;/做上訪問(wèn)過(guò)的標(biāo)記printf("%s->",);p=gv.firstarc;/取該頂點(diǎn)鏈表while(p)/遍歷該鏈表(w=p->data;if(visitedw=0)DFS(g,w,visited);p=p->nextarc;voidDFSTraverse(AdjListg)/深度優(yōu)先遍歷(intvisitedMAX+1;intv;intnum,count=1;for(v=1;v<=n;

24、v+)(visitedv=0;/初始化標(biāo)志位printf("請(qǐng)輸入你要開始的景點(diǎn):");scanf("%d",&num);while(count<=n)v=num;if(visitedv=0)DFS(g,v,visited);/v+;對(duì)尚未訪問(wèn)的頂點(diǎn)調(diào)用DFScount+;)voidPrintPath(AdjListg,intpath,intlength)/打印路徑(for(inti=0;i<length;i+)(printf("%s->",);)printf("n"

25、);)voidSearchAllPath(AdjListG,intpath,intvisited,intv,intdes,intlength)/利用深度優(yōu)先遍歷，path記錄路徑，visited設(shè)訪問(wèn)標(biāo)志，v起點(diǎn)，des終點(diǎn)，length,代表的是訪問(wèn)景點(diǎn)的長(zhǎng)度if(visitedv)return;/若所有的景點(diǎn)都訪問(wèn)過(guò)，則終止pathlength-1=v;/開始記錄路徑if(v=des)/若找到終點(diǎn)則，打印路徑PrintPath(G,path,length);)elsevisitedv=1;for(inti=1;i<=n;i+)if(GetWeight(v,i)!=MAXEDGE&am

26、p;&!visitedi)兩個(gè)景點(diǎn)之間有路，并且還未訪問(wèn)過(guò)，則深度遍歷SearchAllPath(G,path,visited,i,des,length+1);)visitedv=0;)voidInitGraph(AdjList&g)/初始化圖的景點(diǎn)printf("請(qǐng)輸入圖中的頂點(diǎn)數(shù)：")；scanf("%d",&n);printf("請(qǐng)輸入道路的數(shù)目：")；scanf("%d",&e);printf("n");printf("用戶可以自己寫文件創(chuàng)建圖的

27、信息.")；CreateGraph(g);)charMenu()/主菜單charc;intflag;doprintf("n西安郵電學(xué)院導(dǎo)游圖n");printf("1n");printf("|1.創(chuàng)建導(dǎo)游系統(tǒng)|n");printf("I2.瀏覽校園全景In");printf("I3.尋找某一起點(diǎn)的最佳路徑In");printf("|4.選擇出發(fā)點(diǎn)和目的地In");printf("I5.查看景點(diǎn)信息In");printf("I6.瀏覽出一

28、個(gè)起點(diǎn)的所有路徑In");printf("|7.瀏覽校園圖In");printf("|8.退出系統(tǒng)In");n");printf("1printf("請(qǐng)選擇(1-8)-:");scanf("%c",&c);if(c='1'|c='2'|c='3'|c='4'|c='5'|c='6'|c='7'|c='8')flag=0;if(flag)printf(&

29、quot;輸入錯(cuò)誤，請(qǐng)重新選擇.");getchar();while(flag);returnc;voidnarrate(AdjListg)/*說(shuō)明函數(shù)*/(inti,k=0;printf("ntt*歡迎使用校園導(dǎo)游程序*»);printf("tn");printf("tt景點(diǎn)名稱tt|t景點(diǎn)描述n");printf("t|n");for(i=1;i<=n;i+)(printf("t%c(%2d)%-10stt|t%-25s%cn”,2,i,,roduction,

30、2);/*輸出景點(diǎn)列表*/k=k+1;printf("t|n"voidPrintTU()printf（"西安郵電學(xué)院圖"）;printf("n");printf("正門");printf("n");printf("/|");printf("n");printf("/|仃政樓");printf("n");printf("/噴泉|");printf("n");printf(&quo

31、t;基礎(chǔ)教學(xué)樓|");printf("n");printf("|");printf("n");printf("|");printf("n");printf("|");printf("n");printf（"實(shí)驗(yàn)樓|大學(xué)生活動(dòng)中心|"）;printf("n");printf("|");printf("n");printf("|");printf(&q

32、uot;n");printf("|=圖書館=人工湖|");printf("n");printf("|");printf("n");printf("|");printf("n");printf("|")；printf("n");printf("|=東門");printf("n");printf("|");printf("n");printf(&quo

33、t;|");printf("n");printf("操場(chǎng)=體育館");printf("n");printf("|");printf("n");printf("|");printf("n");printf("|");printf("n");printf("|");printf("n");printf("|");printf("n"

34、);printf("|");printf("n");printf("|");printf("n");printf("=食堂");printf("n");printf("|");printf("n");printf("|");printf("n"););printf("|=宿舍printf("n");)voidmain()/主函數(shù)(AdjListg;intv0,v1,i;intvisitedMA