c語(yǔ)言校園導(dǎo)游系統(tǒng)課程設(shè)計(jì)

1、<p>　　課程名稱(chēng) 數(shù)據(jù)結(jié)構(gòu)（基于C語(yǔ)言）課程設(shè)計(jì) </p><p>　　題 目 校園導(dǎo)游程序的設(shè)計(jì)與實(shí)現(xiàn) </p><p>　　院 系 ＿ 信息科學(xué)技術(shù)學(xué)院＿＿＿＿</p><p><b>　　軟件專(zhuān)題訓(xùn)練任務(wù)書(shū)</b></p><p>　　校園導(dǎo)游程序

2、 </p><p><b>　　一、簡(jiǎn)介</b></p><p>　　1．設(shè)計(jì)目的：通過(guò)校園導(dǎo)游程序的設(shè)計(jì)與實(shí)現(xiàn)，熟練掌握?qǐng)D型結(jié)構(gòu)在實(shí)際問(wèn)題中的應(yīng)用。</p><p>　　2．問(wèn)題的描述：設(shè)計(jì)一個(gè)校園模擬導(dǎo)游程序，為新生或來(lái)訪(fǎng)的客人通過(guò)與機(jī)器的“對(duì)話(huà)“提供最短路徑的信息查詢(xún)服務(wù)。 1．任意選取n個(gè)場(chǎng)所，構(gòu)成一

3、個(gè)無(wú)向帶權(quán)圖，圖中頂點(diǎn)表示場(chǎng)所，邊上的權(quán)值表示兩點(diǎn)間的距離，圖的存儲(chǔ)結(jié)構(gòu)可采用帶權(quán)的鄰接矩陣。</p><p>　　2．咨詢(xún)以用戶(hù)和計(jì)算機(jī)的對(duì)話(huà)方式進(jìn)行，由用戶(hù)輸入起始點(diǎn)和終點(diǎn)，輸出信息：最短路徑是多少？并指出所經(jīng)過(guò)的場(chǎng)所。</p><p>　　3、計(jì)算并記錄從校門(mén)口到各個(gè)場(chǎng)所的最短路徑，即求單源點(diǎn)到其它各個(gè)場(chǎng)所的最短路徑。</p><p>　　4、提供校園中任意場(chǎng)

4、所的問(wèn)路查詢(xún)，即求任意兩點(diǎn)之間的最短路徑。</p><p>　　二、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：</p><p>　　由于各個(gè)場(chǎng)所通過(guò)校園中的道路相連，各個(gè)場(chǎng)所和連接它們的道路構(gòu)成了整個(gè)校園的地理環(huán)境，所以使用圖這種數(shù)據(jù)結(jié)構(gòu)對(duì)他們?nèi)ミM(jìn)行描述。以圖中的頂點(diǎn)表示校園內(nèi)各個(gè)場(chǎng)所，應(yīng)包含場(chǎng)所名稱(chēng)、代號(hào)、簡(jiǎn)介等信息；以邊表示連接各個(gè)場(chǎng)所的道路，應(yīng)包含路徑的長(zhǎng)度等信息；頂點(diǎn)和邊均使用結(jié)構(gòu)體定義，整個(gè)圖的數(shù)據(jù)結(jié)構(gòu)采

5、用教材中介紹的帶權(quán)的鄰接矩陣方法。</p><p>　　二、數(shù)據(jù)結(jié)構(gòu)的設(shè)計(jì)：</p><p>　　typedef struct ArCell</p><p><b>　　{</b></p><p>　　int adj; //路徑長(zhǎng)度</p><p>　　}ArCell,AdjMatrix[

6、MAX_VERTEX_NUM][MAX_VERTEX_NUM];</p><p>　　typedef struct //圖中頂點(diǎn)表示主要景點(diǎn)，存放景點(diǎn)的序號(hào)、名稱(chēng)、介紹等信息，</p><p><b>　　{</b></p><p>　　char name[30];</p><p><b>　　int nu

7、m;</b></p><p>　　char introduction[100];//簡(jiǎn)介</p><p>　　}infotype;</p><p>　　typedef struct</p><p><b>　　{</b></p><p>　　infotype vexs[MAX_VERT

8、EX_NUM];</p><p>　　AdjMatrix arcs;</p><p>　　int vexnum,arcnum;</p><p><b>　　}MGraph;</b></p><p><b>　　MGraph b;</b></p><p>　　void cmd(

9、void)</p><p><b>　　{</b></p><p><b>　　int i;</b></p><p>　　b=InitGraph();</p><p><b>　　Menu();</b></p><p>　　scanf("%d&

10、quot;,&i);</p><p>　　while(i!=4)</p><p><b>　　{</b></p><p><b>　　switch(i)</b></p><p><b>　　{</b></p><p>　　case 1:Brows

11、er(&b);Menu();break;</p><p>　　case 2:ShortestPath_DIJ(&b);Menu();break;</p><p>　　case 3:Floyd(&b);Menu();break;</p><p>　　case 4:exit(1);break;</p><p>　　defa

12、ult: printf("輸入序號(hào)不存在,請(qǐng)重新輸入");break;</p><p><b>　　}</b></p><p>　　scanf("%d",&i);</p><p><b>　　}</b></p><p>　　MGraph InitGra

13、ph(void)</p><p><b>　　{</b></p><p><b>　　MGraph G;</b></p><p><b>　　int i,j;</b></p><p>　　G.vexnum=10;</p><p>　　G.arcnum=1

14、4;</p><p>　　for(i=0;i<G.vexnum;i++)</p><p>　　G.vexs[i].num=i;</p><p>　　strcpy(G.vexs[0].name,"海南大學(xué)北門(mén)");</p><p>　　strcpy(G.vexs[0].introduction,"高大威武&q

15、uot;);</p><p>　　strcpy(G.vexs[1].name,"文化柱");</p><p>　　strcpy(G.vexs[1].introduction,"海大學(xué)子健康成長(zhǎng)，激情飛揚(yáng)的地方");</p><p>　　strcpy(G.vexs[2].name,"圖書(shū)樓");</p&

16、gt;<p>　　strcpy(G.vexs[2].introduction,"藏書(shū)豐富，設(shè)施良好，知識(shí)的搖籃");</p><p>　　strcpy(G.vexs[3].name,"3號(hào)教學(xué)樓");</p><p>　　strcpy(G.vexs[3].introduction,"海大學(xué)子努力學(xué)習(xí)，堅(jiān)持向上的場(chǎng)所 "

17、;);</p><p>　　strcpy(G.vexs[4].name,"第一田徑場(chǎng)");</p><p>　　strcpy(G.vexs[4].introduction,"標(biāo)準(zhǔn)化跑道，適宜鍛煉身體的場(chǎng)所");</p><p>　　strcpy(G.vexs[5].name,"男生宿舍樓");</p&

18、gt;<p>　　strcpy(G.vexs[5].introduction,"房間設(shè)施良好，標(biāo)準(zhǔn)六人間");</p><p>　　strcpy(G.vexs[6].name,"海大餐廳");</p><p>　　strcpy(G.vexs[6].introduction,"廳內(nèi)衛(wèi)生整潔，環(huán)境宜人");</p&

19、gt;<p>　　strcpy(G.vexs[7].name,"聯(lián)誼館");</p><p>　　strcpy(G.vexs[7].introduction,"內(nèi)有乒乓球館，排球館，室內(nèi)籃球館等設(shè)施");</p><p>　　strcpy(G.vexs[8].name,"女生宿舍樓");</p><

20、;p>　　strcpy(G.vexs[8].introduction,"房間設(shè)施良好，標(biāo)準(zhǔn)六人間");</p><p>　　strcpy(G.vexs[9].name,"海大東門(mén)");</p><p>　　strcpy(G.vexs[9].introduction,"外有建設(shè)銀行");</p><p>

21、;　　for(i=0;i<G.vexnum;i++)</p><p>　　for(j=0;j<G.vexnum;j++)</p><p>　　G.arcs[i][j].adj=INFINITY;</p><p>　　G.arcs[0][1].adj=100;</p><p>　　G.arcs[0][2].adj=80;</p

22、><p>　　G.arcs[0][6].adj=100;</p><p>　　G.arcs[1][7].adj=120;</p><p>　　G.arcs[2][3].adj=50;</p><p>　　G.arcs[3][6].adj=110;</p><p>　　G.arcs[3][4].adj=150;</p&

23、gt;<p>　　G.arcs[4][5].adj=60;</p><p>　　G.arcs[4][9].adj=280;</p><p>　　G.arcs[5][9].adj=250;</p><p>　　G.arcs[6][7].adj=190;</p><p>　　G.arcs[6][9].adj=180;</p&g

24、t;<p>　　G.arcs[7][8].adj=130;</p><p>　　G.arcs[8][9].adj=100;</p><p>　　for(i=0;i<G.vexnum;i++)</p><p>　　for(j=0;j<G.vexnum;j++)</p><p>　　G.arcs[j][i].adj=G.

25、arcs[i][j].adj;</p><p><b>　　return G;</b></p><p>　　}//InitGraph end</p><p>　　用的是一個(gè)switch語(yǔ)句實(shí)現(xiàn)輸入不同的序號(hào)操作選項(xiàng)，調(diào)用不同的函數(shù)進(jìn)入不同的操作板塊</p><p>　　// 迪杰斯特拉算法計(jì),v0為始點(diǎn)</p>

26、;<p>　　void ShortestPath_DIJ(MGraph * G)</p><p><b>　　{</b></p><p>　　int v,w,i,min,t=0,x,flag=1,v0;</p><p>　　int final[20], D[20], p[20][20];</p><p>　

27、　while(flag)</p><p><b>　　{</b></p><p>　　printf("請(qǐng)輸入起始點(diǎn)序號(hào):");</p><p>　　scanf("%d",&v0);</p><p>　　if(v0<0||v0>G->vexnum)</

28、p><p><b>　　{</b></p><p>　　printf("輸入錯(cuò)誤，景點(diǎn)序號(hào)不存在!請(qǐng)?jiān)俅屋斎刖包c(diǎn)序號(hào):");</p><p>　　scanf("%d",&v0);</p><p><b>　　}</b></p><p&g

29、t;　　if(v0>=0&&v0<G->vexnum)</p><p><b>　　flag=0;</b></p><p><b>　　}</b></p><p>　　for(v=0;v<G->vexnum;v++)</p><p><b>　

30、　{</b></p><p>　　final[v]=0;</p><p>　　D[v]=G->arcs[v0][v].adj;</p><p>　　for(w=0;w<G->vexnum;w++)</p><p>　　p[v][w]=0;</p><p>　　if(D[v]<INFI

31、NITY)</p><p><b>　　{</b></p><p>　　p[v][v0]=1;p[v][v]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　D[v0]=0;final[v0]=1

32、;</p><p>　　for(i=1;i<G->vexnum;i++)</p><p><b>　　{</b></p><p>　　min=INFINITY;</p><p>　　for(w=0;w<G->vexnum;w++)</p><p>　　if(!final[w

33、])</p><p>　　if(D[w]<min){v=w;min=D[w];}</p><p>　　final[v]=1;</p><p>　　for(w=0;w<G->vexnum;w++)</p><p>　　if(!final[w]&&(min+G->arcs[v][w].adj<D[w]

34、))</p><p><b>　　{</b></p><p>　　D[w]=min+G->arcs[v][w].adj;</p><p>　　for(x=0;x<G->vexnum;x++) </p><p>　　p[w][x]=p[v][x];</p><p>　　p[w][w

35、]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(v=0;v<G->vexnum;v++)</p><p><b>　　{</b></p><p>　　if(v0!=v) p

36、rintf("%s",G->vexs[v0].name);</p><p>　　for(w=0;w<G->vexnum;w++)</p><p><b>　　{</b></p><p>　　if(p[v][w]&&w!=v0) printf("-->%s",G-&

37、gt;vexs[w].name);</p><p><b>　　t++;</b></p><p><b>　　}</b></p><p>　　if(t>G->vexnum-1&&v0!=v)printf(" 總路線(xiàn)長(zhǎng)%dm\n\n",D[v]);</p>

38、;<p><b>　　}</b></p><p>　　}//ShortestPath_DIJ end</p><p>　　void Floyd(MGraph *G)</p><p><b>　　{</b></p><p>　　int v,u,i,w,k,j,flag=1,p[10][

39、10][10],D[10][10];</p><p>　　for(v=0;v<G->vexnum;v++)</p><p>　　for(w=0;w<G->vexnum;w++)</p><p><b>　　{</b></p><p>　　D[v][w]=G->arcs[v][w].adj;&

40、lt;/p><p>　　for(u=0;u<G->vexnum;u++)</p><p>　　p[v][w][u]=0;</p><p>　　if(D[v][w]<INFINITY)</p><p><b>　　{</b></p><p>　　p[v][w][v]=1;p[v][w]

41、[w]=1;</p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　for(u=0;u<G->vexnum;u++)</p><p>　　for(v=0;v<G->vexnum;v++)</p><p>　

42、　for(w=0;w<G->vexnum;w++)</p><p>　　if(D[v][u]+D[u][w]<D[v][w])</p><p><b>　　{</b></p><p>　　D[v][w]=D[v][u]+D[u][w];</p><p>　　for(i=0;i<G->vexn

43、um;i++)</p><p>　　p[v][w][i]=p[v][u][i]||p[u][w][i];</p><p><b>　　}</b></p><p>　　while(flag)</p><p><b>　　{</b></p><p>　　printf("

44、請(qǐng)輸入始點(diǎn)和終點(diǎn)的序號(hào):");</p><p>　　scanf("%d%d",&k,&j);</p><p>　　if(k<0||k>G->vexnum||j<0||j>G->vexnum)</p><p><b>　　{</b></p><p

45、>　　printf("景點(diǎn)序號(hào)錯(cuò)誤!請(qǐng)?jiān)俅屋斎胧键c(diǎn)和終點(diǎn)的序號(hào):");</p><p>　　scanf("%d%d",&k,&j);</p><p><b>　　}</b></p><p>　　if(k>=0&&k<G->vexnum&&am

46、p;j>=0&&j<G->vexnum)</p><p><b>　　flag=0;</b></p><p><b>　　}</b></p><p>　　printf("%s",G->vexs[k].name);</p><p>　　for

47、(u=0;u<G->vexnum;u++)</p><p>　　if(p[k][j][u]&&k!=u&&j!=u)</p><p>　　printf("-->%s",G->vexs[u].name);</p><p>　　printf("-->%s",G->

48、vexs[j].name);</p><p>　　printf(" 總路線(xiàn)長(zhǎng)%dm\n",D[k][j]);</p><p>　　}//Floyd end</p><p>　　int LocateVex(MGraph *G,char* v)</p><p><b>　　{ </b></

49、p><p>　　int c=-1,i;</p><p>　　for(i=0;i<G->vexnum;i++)</p><p>　　if(strcmp(v,G->vexs[i].name)==0)</p><p>　　{c=i;break;}</p><p><b>　　return c;<

50、/b></p><p><b>　　}</b></p><p>　　MGraph * CreatUDN(MGraph *G)</p><p><b>　　{</b></p><p>　　int i,j,k,w;</p><p>　　char v1[20],v2[20];

51、</p><p>　　printf("輸入圖的頂點(diǎn)數(shù),弧數(shù):");</p><p>　　scanf("%d%d",&G->vexnum,&G->arcnum);</p><p>　　printf("輸入景點(diǎn)的編號(hào):、名稱(chēng)、介紹:\n");</p><p>

52、　　for(i=0;i<G->vexnum;i++)</p><p><b>　　{</b></p><p>　　printf("景點(diǎn)序號(hào):");</p><p>　　scanf("%d",&G->vexs->num);</p><p>　　prin

53、tf("景點(diǎn)名稱(chēng):");</p><p>　　scanf("%s",G->vexs[i].name);</p><p>　　printf("景點(diǎn)介紹:");</p><p>　　scanf("%s",G->vexs->introduction);</p>

54、<p><b>　　}</b></p><p>　　for(i=0;i<G->vexnum;i++)</p><p>　　for(j=0;j<G->vexnum;j++)</p><p>　　G->arcs[i][j].adj=INFINITY;</p><p>　　printf(

55、"請(qǐng)輸入路徑長(zhǎng)度:\n");</p><p>　　for(k=0;k<G->arcnum;k++)</p><p><b>　　{</b></p><p>　　printf("第%d條邊:\n",k+1);</p><p>　　printf("景點(diǎn)對(duì)(x,y)

56、:");</p><p>　　scanf("%s",v1);</p><p>　　scanf("%s",v2);</p><p>　　printf("路徑長(zhǎng)度:");</p><p>　　scanf("%d",&w);</p>&l

57、t;p>　　i=LocateVex(G,v1);</p><p>　　j=LocateVex(G,v2);</p><p>　　if(i>=0&&j>=0)</p><p><b>　　{</b></p><p>　　G->arcs[i][j].adj=w;</p>

58、<p>　　G->arcs[j][i]=G->arcs[i][j];</p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　return G;</b></p><p><b>　　}</

59、b></p><p>　　void print(MGraph *G)</p><p><b>　　{</b></p><p>　　int v,w,t=0;</p><p>　　for(v=0;v<G->vexnum;v++)</p><p>　　for(w=0;w<G-&g

60、t;vexnum;w++)</p><p>　　{ if(G->arcs[v][w].adj==INFINITY)</p><p>　　printf("∞ ");</p><p>　　else printf("%-7d",G->arcs[v][w].adj);</p><p>

61、;<b>　　t++;</b></p><p>　　if(t%G->vexnum==0)</p><p>　　printf("\n");</p><p><b>　　}</b></p><p><b>　　}</b></p><p&

62、gt;　　旅客進(jìn)行查詢(xún)：1. 查看校園各景點(diǎn)2. 查看所有游覽線(xiàn)路； 3. 選擇始點(diǎn)和終點(diǎn) 4. 退出程序</p><p>　　三、功能（函數(shù)）設(shè)計(jì)：</p><p>　　一．本程序從總體上分為四個(gè)功能模塊，分別為： (1)查看校園各景點(diǎn)，這一功能主要為來(lái)客提供要查的信息。（2） 查看所有游覽線(xiàn)路,這一功能主要提供來(lái)客所要到達(dá)目的地的所有的線(xiàn)路，方便選擇最短的的路線(xiàn)。（3）選擇始點(diǎn)和終點(diǎn)

63、，這一功能的實(shí)現(xiàn)為了找出所走線(xiàn)路中的最短路徑（4）. 退出程序</p><p><b>　　二，流程圖如下</b></p><p>　　程序功能介紹和操作提示模塊</p><p>　?。?）查看所有游覽線(xiàn)路</p><p><b>　　帶權(quán)最少的路徑</b></p><p>

64、<b>　　選擇始點(diǎn)和終點(diǎn)</b></p><p><b>　　四、界面設(shè)計(jì)：</b></p><p>　　本程序界面本著易于操作簡(jiǎn)單整潔而不失美觀的理念，采用數(shù)字對(duì)應(yīng)功能選項(xiàng)，結(jié)合詳細(xì)的操作提示，使得操作方便快捷，界面清晰明朗。</p><p>　　函數(shù)MGraph InitGraph():初始化圖。</p>

65、<p>　　函數(shù)void Menu()：創(chuàng)建菜單。</p><p>　　函數(shù)void Browser(MGraph *G)：瀏覽全景。</p><p>　　函數(shù)void Search(MGraph *G)：查詢(xún)某點(diǎn)信息。</p><p>　　函數(shù)void Floyd(MGraph *G)：查詢(xún)?nèi)我鈨牲c(diǎn)之間的最短路徑。</p><p&

66、gt;　　函數(shù)void ShortestPath_DIJ(MGraph * G)：查詢(xún)校門(mén)口到其他各點(diǎn)之間的最短路徑</p><p><b>　　六、運(yùn)行與測(cè)試：</b></p><p>　　1、測(cè)試的數(shù)據(jù)及其結(jié)果：</p><p>　?。?）瀏覽各景點(diǎn)選項(xiàng)功能</p><p>　　（2）選擇查看校門(mén)口到各個(gè)景點(diǎn)的最短路

67、徑</p><p>　?。?）從各個(gè)景點(diǎn)中任意選擇兩景點(diǎn)之間的最短距離</p><p>　?。?）查詢(xún)完畢，退出程序</p><p>　　2、運(yùn)行與測(cè)試期間遇到的問(wèn)題及其解決辦法。</p><p>　　1. 對(duì)文件的輸入、輸出打開(kāi)方式不夠熟悉，導(dǎo)致輸入輸出信息有誤，后參照教材等材料進(jìn)行修改，使得程序正常進(jìn)行； </p><

68、p>　　2. 刪除函數(shù)中循環(huán)使用不當(dāng)，導(dǎo)致運(yùn)行結(jié)果及寫(xiě)入文件結(jié)果錯(cuò)誤，經(jīng)修改后恢復(fù)正常；</p><p>　　3. 經(jīng)過(guò)反復(fù)修改測(cè)試運(yùn)行，程序功能基本實(shí)現(xiàn)，基本完成題目要求。 。</p><p><b>　　七、設(shè)計(jì)后的思考：</b></p><p>　　1.首先經(jīng)過(guò)這一個(gè)星期的緊張而又充實(shí)的課程設(shè)計(jì)，是我對(duì)數(shù)據(jù)結(jié)構(gòu)這一門(mén)課程的相關(guān)知識(shí)

69、有了全面深刻的認(rèn)識(shí)，尤其是對(duì)圖這一數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識(shí)掌握的更加全面和牢固，特別是對(duì)迪杰斯特拉算法的思想和具體實(shí)現(xiàn)更是經(jīng)歷了從不知所云到熟練運(yùn)用的學(xué)習(xí)過(guò)程，同時(shí)也全面而又系統(tǒng)的復(fù)習(xí)了C++相關(guān)知識(shí)。 2.此次課程設(shè)計(jì)最大的收獲可以說(shuō)是全面掌握了數(shù)據(jù)結(jié)構(gòu)圖的相關(guān)知識(shí)。雖說(shuō)圖這一章也是數(shù)據(jù)結(jié)構(gòu)的終點(diǎn)，但是由于考試只考一些算法的思想，對(duì)具體的實(shí)現(xiàn)沒(méi)有做要求，因此課程設(shè)計(jì)之前我對(duì)迪杰斯特拉算法可以說(shuō)是一竅不通，更談不上了解。經(jīng)過(guò)幾天的探索和同學(xué)的

70、指點(diǎn)，終于可以運(yùn)用迪杰斯特拉算法實(shí)現(xiàn)對(duì)無(wú)向網(wǎng)中各頂點(diǎn)間的最小路徑和具體路徑的求解。 3.經(jīng)過(guò)此次課程設(shè)計(jì)，使我懂得任何一門(mén)計(jì)算機(jī)語(yǔ)言學(xué)習(xí)，都是應(yīng)該理論與實(shí)際的結(jié)合，光有理論知識(shí)是不行的。在以前的學(xué)習(xí)中，我往往知識(shí)以備考為目的，只注重對(duì)教材理論知識(shí)的學(xué)習(xí)，不注重實(shí)踐，平時(shí)很少主動(dòng)去寫(xiě)一些代碼，從以前的C語(yǔ)言到C++語(yǔ)言包括現(xiàn)在的數(shù)據(jù)結(jié)構(gòu)都是這樣一個(gè)情況。雖然在期末考試中往往有不錯(cuò)的表現(xiàn)，但是真正到要我自己動(dòng)手去編寫(xiě)一個(gè)程序時(shí)，往往都是困難