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

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