校園導(dǎo)游咨詢程序

太原理工大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院PAGE2012年01月實(shí)驗(yàn)三：校園導(dǎo)游咨詢?cè)O(shè)計(jì)方案簡(jiǎn)介設(shè)計(jì)一個(gè)校園導(dǎo)游程序，為來(lái)訪的客人提供各種信息查詢服務(wù)。1）設(shè)計(jì)你所在學(xué)校的校園平面圖，2）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。3）為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。設(shè)計(jì)題目實(shí)現(xiàn):實(shí)際需求1）設(shè)計(jì)你所在學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)。以圖中頂點(diǎn)表示校園內(nèi)各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息：以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。2）為來(lái)訪客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。3）為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。2）概要設(shè)計(jì)校園全景一覽圖、顯示出校園的平面圖。提供校園中任意景點(diǎn)問(wèn)路查詢，即求任意兩個(gè)景點(diǎn)之間的所有路徑。3、提供校園圖中多個(gè)景點(diǎn)的最佳訪問(wèn)路線查詢，即求途徑這過(guò)個(gè)景點(diǎn)的最佳（短）路徑。1．功能模塊圖；voidMap();//校園地圖voidCreateGraph();//創(chuàng)建圖voidOutputPlace();//輸出景點(diǎn)列表voidSearchPlace();//查詢景點(diǎn)信息voidSearchPath();//查詢最短路徑voidShortpath(inti);//計(jì)算最短路徑voidOutput(intsight1,intsight2);//輸出函數(shù)2．各個(gè)模塊詳細(xì)的功能描述。Map();//顯示校園整體的地圖、包含學(xué)校各景點(diǎn)的詳細(xì)位置CreateGraph();//創(chuàng)建圖、主要用來(lái)保存各景點(diǎn)信息OutputPlace();//輸出景點(diǎn)列表、供選擇景點(diǎn)信息查詢時(shí)使用SearchPlace();//查詢景點(diǎn)信息、景點(diǎn)的名稱及介紹SearchPath();//查詢最短路徑、兩景點(diǎn)間最短距離Shortpath(inti);//計(jì)算兩景點(diǎn)間最短路徑Output(intsight1,intsight2);//輸出兩景點(diǎn)最短路徑及信息四．詳細(xì)設(shè)計(jì)Main()1．功能函數(shù)的調(diào)用關(guān)系圖Main()CreateGraph()gate:;//標(biāo)號(hào)，可以作為goto語(yǔ)句跳轉(zhuǎn)的位置path[a][sight1]=0;for(b=0;b<NUM;b++){ if(G.arc[d][b].length<MAX&&path[a][b])//如果景點(diǎn)一和它的一個(gè)臨界點(diǎn)之間存在路徑且最短路徑 { printf(">%s",G.vertex[b].name);//輸出此節(jié)點(diǎn)的名稱 q=q+1;//計(jì)數(shù)變量加一，滿8控制輸出時(shí)的換行 path[a][b]=0; d=b;//將b作為出發(fā)點(diǎn)進(jìn)行下一次循環(huán)輸出，如此反復(fù) if(q%14==0)printf("\n"); gotogate; }} } printf("\n\n\t\t\t\t\t\t最短距離為%dm.\n\n\t",D[a]); } }五．測(cè)試數(shù)據(jù)及運(yùn)行結(jié)果系統(tǒng)主界面學(xué)校平面圖學(xué)校景點(diǎn)圖最短路徑信息查詢異常信息設(shè)計(jì)評(píng)述:設(shè)計(jì)者對(duì)本設(shè)計(jì)的評(píng)述及通過(guò)設(shè)計(jì)的收獲體會(huì)改進(jìn)方案系統(tǒng)還有部分漏洞未能修復(fù)、不夠絕對(duì)的穩(wěn)定、還需改進(jìn)！求最短路徑時(shí)可以采用比較簡(jiǎn)單的哈密爾頓算法。本次課程設(shè)計(jì)僅完成了要求的基本功能、由于平時(shí)掌握的不夠好以及時(shí)間關(guān)系未能完成選作功能、這是一大缺陷！另外通過(guò)本次課程設(shè)計(jì)也更好的掌握了平時(shí)所學(xué)的知識(shí)、通過(guò)實(shí)踐學(xué)到了許多課本上沒(méi)有的知識(shí)！體會(huì)以后要加強(qiáng)動(dòng)手時(shí)間能力、多與同學(xué)交流算法精髓！在編寫程序中盡量做到獨(dú)立完成、對(duì)于自己想要完成的問(wèn)題要主動(dòng)編程完成、這樣自己是一個(gè)很大的提升、也能學(xué)到很多的知識(shí)、熟練編程！報(bào)告最后有兩部分附錄附錄一：參考資料1、C語(yǔ)言程序設(shè)計(jì)（譚浩強(qiáng)版）2、數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）編著：嚴(yán)蔚敏、吳偉民清華大學(xué)出版社附錄二：源程序（將所有的源程序附在最后的附錄中）//查詢景點(diǎn)信息.cpp:Definestheentrypointfortheconsoleapplication.//#include"stdafx.h"#include"stdio.h"#include<string.h>#include<stdio.h>#include<malloc.h>#include<stdlib.h>#include<conio.h>#defineNUM20#defineMAX100000#defineFALSE0#defineTURE1typedefstructArcNode{intlength;//路徑長(zhǎng)度}ArcNode,*ArcLink;//邊結(jié)點(diǎn)的定義typedefstructVertexNode{intnumber;//景點(diǎn)的編號(hào)char*name;//景點(diǎn)的名稱char*info;//景點(diǎn)的簡(jiǎn)介}VertexNode;//頂點(diǎn)結(jié)點(diǎn)的定義typedefstructGraph{VertexNodevertex[NUM];ArcNodearc[NUM][NUM];intvexnum,arcnum;//圖的頂點(diǎn)數(shù)，邊數(shù)}Graph;//圖的定義GraphG;intpath[NUM][NUM];intD[NUM];voidCreateGraph();//創(chuàng)建圖voidMap();//學(xué)校地圖voidoutputplace();//輸出校園景點(diǎn)名稱voidsearchplace();//查詢景點(diǎn)信息voidsearchpath();//查詢最短路徑voidshortestpath_DIJ(intnum);//迪杰斯特拉算法最短路徑voidoutput(intsight1,intsight2);//輸出函數(shù)voidCreateGraph()//創(chuàng)建圖{ inti,j; G.vexnum=12; G.arcnum=17; for(i=1;i<NUM;i++) G.vertex[i].number=i; G.vertex[1].name="太原理工大學(xué)正門"; G.vertex[1].info="學(xué)校正門位于學(xué)校的正南方向、是進(jìn)入學(xué)校前的第一道亮麗\n\t\t的風(fēng)景線!\n"; G.vertex[2].name="電機(jī)館"; G.vertex[2].info="電機(jī)館是數(shù)學(xué)系，電子信息系，自動(dòng)化，通訊等學(xué)院的學(xué)院樓!\n"; G.vertex[3].name="科學(xué)樓"; G.vertex[3].info="科學(xué)樓是我?？蒲袡C(jī)構(gòu)場(chǎng)所，也是山西省網(wǎng)關(guān)所在地!\n"; G.vertex[4].name="多學(xué)科樓"; G.vertex[4].info="科學(xué)樓是計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，軟件學(xué)院，電子信息學(xué)院，\n\t\t土木，建筑的學(xué)院樓，也是我校最好的學(xué)院樓!\n"; G.vertex[5].name="圖書館"; G.vertex[5].info="太原理工圖書館經(jīng)歷了初創(chuàng)時(shí)期，發(fā)展時(shí)期，面向現(xiàn)代化的轉(zhuǎn)型時(shí)期。\n\t\t如今，她已經(jīng)發(fā)展成為資源豐富，現(xiàn)代化，綜合性，開(kāi)放式的圖書館!\n"; G.vertex[6].name="機(jī)械館"; G.vertex[6].info="機(jī)械館是我校百年高校最有力的體現(xiàn)!\n\t\t是歐式風(fēng)格建筑，外觀宏偉氣派\n\t\t為機(jī)械學(xué)院的學(xué)院樓!\n"; G.vertex[7].name="籃球場(chǎng)"; G.vertex[7].info="籃球場(chǎng)全橡膠場(chǎng)，每天這里打球人員特多，我?；@球隊(duì)\n\t\t在歷年的CUBA聯(lián)賽上取得佳績(jī)，是我們引以為豪的校隊(duì)!\n"; G.vertex[8].name="清澤餐廳"; G.vertex[8].info="清澤餐廳是我校最現(xiàn)代化的食堂，提供各種美食!\n"; G.vertex[9].name="學(xué)生宿舍"; G.vertex[9].info="這里是我校學(xué)生宿舍集中所在地，包括本科生，研究生宿舍，\n\t\t是我們?cè)趯W(xué)校的家!\n"; G.vertex[10].name="文體中心"; G.vertex[10].info="文體中心包括體育館，體育場(chǎng)，各種體育娛樂(lè)場(chǎng)所，供學(xué)生\n\t\t體育鍛煉的地方!\n"; G.vertex[11].name="國(guó)際交流中心"; G.vertex[11].info="國(guó)際交流中心是外國(guó)留學(xué)生居住學(xué)習(xí)科研的場(chǎng)所!\n"; for(i=0;i<NUM;++i) for(j=0;j<NUM;++j) G.arc[i][j].length=MAX; G.arc[1][2].length=G.arc[2][1].length=60; G.arc[1][3].length=G.arc[3][1].length=30; G.arc[1][6].length=G.arc[6][1].length=70; G.arc[2][3].length=G.arc[3][2].length=10; G.arc[2][4].length=G.arc[4][2].length=50; G.arc[2][6].length=G.arc[6][2].length=100; G.arc[4][5].length=G.arc[5][4].length=20; G.arc[5][6].length=G.arc[6][5].length=40; G.arc[5][7].length=G.arc[7][5].length=10; G.arc[7][8].length=G.arc[8][7].length=15; G.arc[8][9].length=G.arc[9][8].length=400; G.arc[8][10].length=G.arc[10][8].length=120; G.arc[9][10].length=G.arc[10][9].length=500; G.arc[10][11].length=G.arc[11][10].length=80; G.arc[11][5].length=G.arc[5][11].length=100; G.arc[11][6].length=G.arc[6][11].length=500;}voidMap()//學(xué)校地圖{ printf("\n\n"); system("cls"); printf("\t┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┒\n"); printf("\t┃太原理工大學(xué)校園圖┃\n"); printf("\t┃注：此圖按正門布局而畫,方位并非上北下南左西右東!┃\n"); printf("\t┃━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n"); printf("\t┃┏————┒\n"); printf("\t┃┃學(xué)生宿舍┃\n"); printf("\t┃::┗--┛┃\n"); printf("\t┃┏┒┏┒┃\n"); printf("\t┃┃文體中心┃┃清澤餐廳┃┃\n"); printf("\t┃┗┛┗┛┃\n"); printf("\t┃::┃\n"); printf("\t┃::┃\n"); printf("\t┃:┍┒┃\n"); printf("\t┃:┃籃球場(chǎng)┃┃\n"); printf("\t┃:┗┛┃\n"); printf("\t┃::┃\n"); printf("\t┃::┃\n"); printf("\t┃┍┒┏┒┏┒┃\n"); printf("\t┃┃國(guó)際交流┃┃圖書館┃┃多學(xué)科樓┃┃\n"); printf("\t┃┗┛┗┛┗┛┃\n"); printf("\t┃:::┃\n"); printf("\t┃:::┃\n"); printf("\t┃:┏┒:┏┒:┃\n"); printf("\t┃:...┃機(jī)械館┃┃電機(jī)館┃:┃\n"); printf("\t┃┗┛:┗-┛:┃\n"); printf("\t┃:::┃\n"); printf("\t┃::┏┒┃\n"); printf("\t┃::┃科學(xué)樓┃┃\n"); printf("\t┃::┗┛┃\n"); printf("\t┃┏┒:┋┃\n"); printf("\t┃┃太原理工大學(xué)大門┃'''''''''''''┃\n"); printf("\t┃┗┛┎┓┃\n"); printf("\t┃┃北┃\n"); printf("\t┃┃西╋東┃\n"); printf("\t┃┃南┃\n"); printf("\t┃┗┛┃\n"); printf("\t┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━\n");}voidoutputplace()//輸出校園景點(diǎn)名稱{ printf("\t┎━━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf("\t┃太原理工大學(xué)學(xué)校景點(diǎn)一覽表┃\n"); printf("\t┠━━━━━━━━━━━━━┲━━━━━━━━━━┃\n"); printf("\t┃1.學(xué)校正門┃2.電機(jī)館┃\n"); printf("\t┠━━━━━━━━━━━━━╂━━━━━━━━━━┃\n"); printf("\t┃3.科學(xué)樓┃4.多學(xué)科樓┃\n"); printf("\t┠━━━━━━━━━━━━━╂━━━━━━━━━━┃\n"); printf("\t┃5.圖書館┃6.機(jī)械館┃\n"); printf("\t┠━━━━━━━━━━━━━╂━━━━━━━━━━┃\n"); printf("\t┃7.籃球場(chǎng)┃8.清澤餐廳┃\n"); printf("\t┠━━━━━━━━━━━━━╂━━━━━━━━━━┃\n"); printf("\t┃9.學(xué)生宿舍┃10.文體中心┃\n"); printf("\t┠━━━━━━━━━━━━━╂━━━━━━━━━━┃\n"); printf("\t┃11.國(guó)際交流中心┃┃\n"); printf("\t┗━━━━━━━━━━━━━┸━━━━━━━━━━┛\n");}voidsearchplace()//查詢景點(diǎn)信息{ inti,num; charc='y'; while(c=='y'){ system("cls"); outputplace(); printf("\t\t請(qǐng)輸入您要查找的景點(diǎn)編號(hào)："); scanf("%d",&num); getchar(); system("cls"); if(num>0&&num<=G.vexnum)//判定信息輸入正確 { for(i=1;i<=G.vexnum;i++) if(num==G.vertex[i].number) { printf("\n\t\t景點(diǎn)編號(hào):%d\n",i); printf("\t\t景點(diǎn)名稱:%s\n",G.vertex[i].name); printf("\t\t景點(diǎn)簡(jiǎn)介:%s\n\n",G.vertex[i].info); } } else printf("\t\t信息輸入有誤!\n"); num=0; printf("\n\t\t是否繼續(xù)查詢景點(diǎn)信息(y/n):"); c=getchar(); getchar();}system("cls");}voidsearchpath()//查詢最短路徑{ inti,j;charc='y';while(c=='y'){ system("cls"); outputplace(); printf("\n\n\t\t初始景點(diǎn)編號(hào)(1->11):"); scanf("%d",&i); printf("\t\t最終景點(diǎn)編號(hào)(1->11):"); scanf("%d",&j); getchar(); if(i>G.vexnum||i<=0||j>G.vexnum||j<0||i==j) printf("\t\t輸入信息錯(cuò)誤!\n\n"); else { shortestpath_DIJ(i); output(i,j); } printf("\n\t\t是否繼續(xù)查詢最短路徑(y/n):"); c=getchar(); getchar();}system("cls");}voidshortestpath_DIJ(intnum)//迪杰斯特拉算法最短路徑{ intv,w,i,t;//i、w和v為計(jì)數(shù)變量//t表示景點(diǎn)個(gè)數(shù) intfinal[NUM];//標(biāo)志數(shù)組、用來(lái)存放頂點(diǎn)的信息 intmin;//記錄權(quán)值、最終輸出路徑 for(v=0;v<NUM;v++) { final[v]=FALSE;//假設(shè)從頂點(diǎn)num到頂點(diǎn)v沒(méi)有最短路徑 D[v]=G.arc[num][v].length;//將num到其余頂點(diǎn)的最短路徑長(zhǎng)度初始化為權(quán)值 for(w=0;w<NUM;w++) path[v][w]=FALSE;//初始化從v到w的路徑值 if(D[v]<MAX)//存在路徑 { path[v][num]=TURE;//存在標(biāo)志置為一 path[v][v]=TURE;//自身到自身 } } D[num]=0;//初始化新路徑 final[num]=TURE;//初始化num頂點(diǎn)屬于final集合 //開(kāi)始主循環(huán),每一次求得num到某個(gè)頂點(diǎn)的最短路徑，并將其加入到final集合 for(i=0;i<NUM;++i)//其余G.vexnum-1個(gè)頂點(diǎn) { min=MAX;//當(dāng)前所知離頂點(diǎn)num的最近距離 for(w=0;w<NUM;++w) if(!final[w])//w頂點(diǎn)在v-s中 if(D[w]<min)//w頂點(diǎn)離num頂點(diǎn)更近 { v=w; min=D[w]; } final[v]=TURE;//離num頂點(diǎn)更近的v加入到s集合 for(w=0;w<NUM;++w)//更新當(dāng)前最短路徑極其距離 if(!final[w]&&((min+G.arc[v][w].length)<D[w]))//不在s集合，并且比以前所找到的路徑都短就更新當(dāng)前路徑 { D[w]=min+G.arc[v][w].length;//更新路徑 for(t=0;t<NUM;t++) path[w][t]=path[v][t]; path[w][w]=TURE; } } }voidoutput(intsight1,intsight2)//輸出函數(shù){ inta,b,c,d,q=0;//a、b、c和d為計(jì)數(shù)變量//q控制計(jì)數(shù)變量、用于換行 a=sight2;//將景點(diǎn)二賦值給a if(a!=sight1)//如果景點(diǎn)二不和景點(diǎn)一輸入重合，則進(jìn)行... { printf("\t\t從%s到%s的最短路徑是:\n\n\t\t",G.vertex[sight1].name,G.vertex[sight2].name);//輸出提示信息 //輸出sight1到sight2的最短路徑長(zhǎng)度，存放在D[]數(shù)組中 printf("%s",G.vertex[sight1].name);//輸出景點(diǎn)一的名稱 d=sight1;//將景點(diǎn)一的編號(hào)賦值給d for(c=0;c<NUM;++c) {gate:;//標(biāo)號(hào)，可以作為goto語(yǔ)句跳轉(zhuǎn)的位置path[a][sight1]=FALSE;for(b=0;b<NUM;b++){ if(G.arc[d][b].length<MAX&&path[a][b])//如果景點(diǎn)一和它的一個(gè)臨界點(diǎn)之間存在路徑且最短路徑 { printf(">%s",G.vertex[b].name);//輸