校園問(wèn)路系統(tǒng)設(shè)計(jì)

C++課程設(shè)計(jì)[題目]:第3.1題:校園導(dǎo)游咨詢問(wèn)題實(shí)驗(yàn)內(nèi)容:設(shè)計(jì)學(xué)校的校園平面圖,建立一個(gè)訪問(wèn)校園各個(gè)景點(diǎn)的問(wèn)路系統(tǒng).2.實(shí)驗(yàn)的目的:把校園內(nèi)的各個(gè)景點(diǎn)的聯(lián)系設(shè)計(jì)成一個(gè)無(wú)向網(wǎng),求任意一個(gè)景點(diǎn)到其它任意一個(gè)景點(diǎn)的最短簡(jiǎn)單路徑并提供一定的相關(guān)信息.3.實(shí)驗(yàn)的要求:(1)設(shè)計(jì)學(xué)校的校園平面圖，所含景點(diǎn)不少于10個(gè)，以圖中頂點(diǎn)表示學(xué)校各景點(diǎn)，存放景點(diǎn)名稱、代號(hào)、簡(jiǎn)介等信息；以邊表示路徑，存放路徑長(zhǎng)度等相關(guān)信息。(2)為來(lái)訪客人提供圖中任意景點(diǎn)的問(wèn)路查詢，即查詢?nèi)我鈨蓚€(gè)景點(diǎn)之間的一條最短的簡(jiǎn)單路徑。(3)為來(lái)訪的客人提供圖中任意景點(diǎn)相關(guān)信息的查詢。4.程序的設(shè)計(jì)思想:(1)存儲(chǔ)結(jié)構(gòu):a.構(gòu)造一個(gè)無(wú)向圖G并用鄰接矩陣來(lái)存儲(chǔ)。b.利用迪杰斯特拉算法來(lái)計(jì)算出起點(diǎn)到各個(gè)頂點(diǎn)之間的最短路徑用二維數(shù)組p[i][]來(lái)記錄，最短路徑長(zhǎng)度就用一維數(shù)組d[i]存放；i的范圍：0～20。一維數(shù)組have[]是用來(lái)記錄最短路徑出現(xiàn)頂點(diǎn)的順序。c.根據(jù)起點(diǎn)和終點(diǎn)輸出最短路徑和路徑長(zhǎng)度。(2).主要算法的根本思想:由于導(dǎo)游程序在實(shí)際執(zhí)行時(shí)，需要根據(jù)用戶的臨時(shí)輸入求最短路徑。因此，雖然Dijkstra算法的時(shí)間復(fù)雜度比Floyd算法低，但要求每一條最短路徑都必須重新搜索一遍，在頻繁查詢時(shí)會(huì)導(dǎo)致查詢效率降低，而Floyd算法只需要一次，即可求得每一對(duì)頂點(diǎn)之間的最短路徑，雖然時(shí)間復(fù)雜度為O(n),但以后每次查詢只要查表即可，極大地提高了查詢效率，而且，F(xiàn)loyd算法還支持帶負(fù)權(quán)的圖的最短路徑的計(jì)算。因此在本程序中選用Floyd算法搜索。是否敲回車是否敲回車FT1234TTFF輸出選項(xiàng)1、查詢景點(diǎn)名稱；2、輸出景點(diǎn)信息；3、查詢路徑；4、退出；判斷選擇相應(yīng)選項(xiàng)輸出10個(gè)景點(diǎn)名稱輸出景點(diǎn)相關(guān)信息輸入查詢景點(diǎn)起點(diǎn)編號(hào)退出輸出：請(qǐng)敲回車返回輸出：請(qǐng)敲回車返回輸入查詢景點(diǎn)的起點(diǎn)編號(hào)X判斷0<X<11輸入查詢景點(diǎn)的終點(diǎn)編號(hào)Y判斷0<Y<11輸出X號(hào)景點(diǎn)與其他9個(gè)景點(diǎn)的距離、X號(hào)景點(diǎn)到T景點(diǎn)的距離路徑輸出你的輸入錯(cuò)誤并提示結(jié)束開(kāi)始輸出景點(diǎn)信息5.源程序清單:文件search.c#include<conio.h>#include<graphics.h>#include<stdio.h>#include<stdlib.h>#include<dos.h>#include<string.h>#include"word.h"/*調(diào)用漢字庫(kù)文件*/#defineR20/*設(shè)置鼠標(biāo)大小*/#defineCOLOR_15/*設(shè)置字體顏色*/#defineMAX50/*景點(diǎn)個(gè)數(shù)最大值*/#defineERROR0/****************定義數(shù)據(jù)結(jié)構(gòu)********************//*采用矩陣存貯方式，一維數(shù)組表示景點(diǎn)信息，二維數(shù)組表示路徑,此程序中景點(diǎn)數(shù)為12個(gè)*/typedefstruct{charname[20];/*景點(diǎn)名稱*/chardaihao[15];/*景點(diǎn)代號(hào)*/charjianjie[100];/*景點(diǎn)簡(jiǎn)介*/}Elemtype;typedefstruct{intnum;/*頂點(diǎn)編號(hào)*/Elemtypedate;/*頂點(diǎn)信息*/}Vertex;/*定義頂點(diǎn)*/typedefstruct{Vertexvex[MAX];/*存放頂點(diǎn)的一維數(shù)組,數(shù)組第零個(gè)單元沒(méi)有用上*/unsignedintedge[MAX][MAX];/*存放路徑的長(zhǎng)度*/}adjmax;adjmaxadj;/*全局變量,定義adj為adjmax類型*/charA[20];intshortest[MAX][MAX];/*定義全局變量存貯最小路徑*/intpath[MAX][MAX];/*定義存貯路徑*//****************定義數(shù)據(jù)結(jié)構(gòu)********************/#include"infor.h"/********************開(kāi)始模式***********************/voidinitgr(void)/*BGI初始化*/{intgd=DETECT,gm=0;registerbgidriver(EGAVGA_driver);initgraph(&gd,&gm,"");}voiddrawmat(char*mat,intmatsize,intx,inty,intcolor)/*字模指針、點(diǎn)陣大小、起始坐標(biāo)(x,y)、顏色*/{inti,j,k,n;n=(matsize-1)/8+1;for(j=0;j<matsize;j++)for(i=0;i<n;i++)for(k=0;k<8;k++)if(mat[j*n+i]&(0x80>>k))/*測(cè)試為1的位那么顯示*/putpixel(x+i*8+k,y+j,color);/*在指定的位置畫一個(gè)象素*/}voidword(){inti;for(i=0;i<6;i++){drawmat(hz_1[i],32,200+40*i,200,COLOR_1);}}/*寫漢字*/voidmydelay(intx){inti;for(i=0;i<x;i++){delay(2000);}}voidclew() /*提示信息*/{while(!kbhit()){setcolor(RED);outtextxy(250,250,"pressanykey....");mydelay(75);setcolor(BLACK);outtextxy(250,250,"pressanykey....");mydelay(75);}}voidscreen(){hanzi();clew();}/********************開(kāi)始模式***********************//******************鼠標(biāo)驅(qū)動(dòng)************************/voidgetmouse(int*x,int*y,int*key){unionREGSinregs,outregs;inregs.x.ax=3;/*獲取鼠標(biāo)位置和狀態(tài)*/int86(0x33,&inregs,&outregs);/*中斷調(diào)用*/*x=outregs.x.cx;/*cx存放器中存的是橫坐標(biāo)*/*y=outregs.x.dx;/*dx存放器中存的是列坐標(biāo)*/*key=outregs.x.bx;/*bx存放器是按鍵狀態(tài)*/}voidmouse(int*x,int*y,int*z)/*畫鼠標(biāo)是利用將一個(gè)空矩形存入內(nèi)存中,然后再在該空矩形中畫鼠標(biāo)形狀*/{inta=0,b=0,c=0,a_old=0,b_old=0;/*a,b的值可以隨便*/int*ball;/*定義指向內(nèi)存的存儲(chǔ)圖形的指針*/ball=(int*)malloc(sizeof(imagesize(a,b,a+R,b+R)));/*返回矩形區(qū)域的大小，并且申請(qǐng)空間*/getimage(a,b,a+R,b+R,ball);/*第一次將圖形(一個(gè)空矩形)存入到內(nèi)存中,內(nèi)存中存入的是一個(gè)空矩形*/while(c==0)/*直到按鍵后才返回,不按鍵一直循環(huán)*/{getmouse(&a,&b,&c);/*a,為橫坐標(biāo),b,為列坐標(biāo),c為按鍵狀態(tài)*/if(a<0)a=0;/*保證鼠標(biāo)左邊不出界*/if(b<0)b=0;/*保證上面不出界*/if(a>getmaxx()-R)a=getmaxx()-R;/*保證右邊不出界*/if(b>getmaxy()-R)b=getmaxy()-R;/*保證下邊不出界*/if(a!=a_old||b!=b_old)/*當(dāng)鼠標(biāo)移動(dòng)時(shí)*/{putimage(a_old,b_old,ball,0);/*在a_old,b_old輸出圖形,用來(lái)擦掉原來(lái)的鼠標(biāo)*/getimage(a,b,a+R,b+R,ball);/*這條語(yǔ)句是將目前鼠標(biāo)所在位置的圖形存貯到ball里面試著看著有無(wú)這條語(yǔ)句的區(qū)別*//*不需要在獲取了*/setcolor(11);setlinestyle(0,0,1);line(a,b,a+R,b+R/2);line(a,b,a+R/2,b+R);line(a+R,b+R/2,a+R/2,b+R);line(a+R*3/4,b+R*3/4,a+R,b+R);/*畫鼠標(biāo)*/}a_old=a;b_old=b;}/*endwhile*/*x=a;*y=b;*z=c;/*返回按鍵后鼠標(biāo)的位置*/putimage(a,b,ball,0);/*將鼠標(biāo)擦掉,因?yàn)榇嬖赽all里面的是一個(gè)背景為缺省狀態(tài)下的一個(gè)空矩形*/free(ball);}/******************鼠標(biāo)驅(qū)動(dòng)************************//******************主題模式********************/voidcls(intx1,inty1,intx2,inty2)/*去除局部屏幕*/{setfillstyle(1,BLACK);bar(x1,y1,x2,y2);}voidbutton(intx1,inty1,intx2,inty2)/*畫三維按鈕*/{setfillstyle(1,8);bar3d(x1,y1,x2,y2,5,1);}voidfigure(){inti;cls(0,0,getmaxx(),getmaxy());/*去除整個(gè)屏幕*/setbkcolor(BLACK);setcolor(11);setlinestyle(0,0,1);settextstyle(0,0,1);line(0,75,getmaxx(),75);setcolor(WHITE);rectangle(19,24,101,51);rectangle(559,24,621,51);rectangle(199,24,281,51);rectangle(379,24,461,51);setfillstyle(1,8);button(20,25,100,50);/*景點(diǎn)查詢對(duì)應(yīng)的位置*/button(200,25,280,50);/*景點(diǎn)一覽對(duì)應(yīng)的位置*/button(380,25,460,50);/*路徑查詢對(duì)應(yīng)的位置*/button(560,25,620,50);/*退出對(duì)應(yīng)的位置*/for(i=0;i<4;i++){drawmat(hz_2[i],24,21+18*i,26,COLOR_1);/*景點(diǎn)查詢*/}for(i=0;i<2;i++){drawmat(hz_3[i],24,381+18*i,26,COLOR_1);}drawmat(cha24K,24,417,26,COLOR_1);drawmat(xun24K,24,435,26,COLOR_1);/*路徑查詢*/for(i=0;i<2;i++){drawmat(hz_2[i],24,201+18*i,26,COLOR_1);}for(i=2;i<4;i++){drawmat(hz_4[i-2],24,201+18*i,26,COLOR_1);}/*景點(diǎn)一覽*/for(i=0;i<2;i++){drawmat(hz_6[i],24,561+35*i,26,COLOR_1);/*退出*/}}voidzhwg(){inti;int*buf;char*str='\0';buf=(int*)malloc(sizeof(imagesize(200,250,420,300)));getimage(200,250,420,300,buf);setfillstyle(1,GREEN);bar(200,250,420,300);for(i=0;i<5;i++){drawmat(hz_5[i],24,220+30*i,255,11);}for(i=5;i>=1;i--){sprintf(str,"%d",i);outtextxy(280,290,"count");outtextxy(340,290,str);sleep(1);setfillstyle(1,GREEN);bar(280,290,350,295);}/*endfor*/putimage(200,250,buf,COPY_PUT);}/******************主題模式********************//*****************初始化界面******************/voidinit(){initgr();/*BGI初始化*/screen();figure();zhwg();read(&adj);/*讀取信息文件*/}/*****************初始化界面******************/voidalldisplay()/*全部顯示*/{inti;cls(0,77,getmaxx(),getmaxy());setlinestyle(0,0,1);settextstyle(0,0,1);for(i=1;i<=T;i++)/*總共有12個(gè)信息*/{setcolor(11);outtextxy(200,80+30*i,adj.vex[i].);}}/*景點(diǎn)一覽*/voiddisplay_1(inti){cls(0,77,getmaxx(),getmaxy());settextstyle(0,0,1);setlinestyle(0,0,1);setcolor(WHITE);drawmat(ming24K,24,40,185,WHITE);drawmat(cheng24K,24,70,185,WHITE);drawmat(dai24K,24,40,235,WHITE);drawmat(hao24K,24,70,235,WHITE);outtextxy(100,200,adj.vex[i].);outtextxy(100,250,adj.vex[i].date.daihao);outtextxy(0,300,adj.vex[i].date.jianjie);}voiddisplay_2(){cls(0,77,getmaxx(),getmaxy());setcolor(11);setlinestyle(0,0,3);settextstyle(0,0,2);outtextxy(150,250,"notfindthemessage");}/*******************查找函數(shù)******************/intsearch(){inti=1;while(i<=T&&strcmp(adj.vex[i].,A)!=0){i=i+1;}if(i==T+1){return(ERROR);}/*查找失敗*/else{return(adj.vex[i].num);}/*查找成功*/}/*******************查找函數(shù)******************/voidget(intx,inty,intn)/*從終端輸入字符*/{intj=0;while(1){setlinestyle(0,0,1);settextstyle(0,0,1);A[j]=getch();if(A[j]==13){A[j]='\0';break;}/*回車鍵結(jié)束輸入*/if(A[j]==8)/*刪除*/{setcolor(BLACK);outtextxy(x+8*(j-1),y,&A[j-1]);if(j==0){j=0;}else{j=j-1;}A[j]='\0';}else{A[j+1]='\0';setcolor(WHITE);outtextxy(x+8*j,y,&A[j]);if(j<n){j++;}else{j=n-1;}}}}voidinput()/*輸入函數(shù)*/{inti;setfillstyle(1,GREEN);bar(180,150,500,250);for(i=0;i<2;i++){drawmat(hz_7[i],24,185+80*i,160,11);}for(i=0;i<2;i++){drawmat(hz_2[i],24,185+80*(i+2),160,11);}/*輸入景點(diǎn)*/setfillstyle(1,BLACK);bar(200,210,480,230);get(201,214,20);}voiddemand(){inti;cls(0,77,getmaxx(),getmaxy());input();i=search();if(i==ERROR){display_2();}else{display_1(i);}}/*景點(diǎn)查詢*//********************搜索算法*********************/voidfloyd(){inti,j,k;for(i=1;i<=T;i++){for(j=1;j<=T;j++){shortest[i][j]=adj.edge[i][j];path[i][j]=0;}}/*初始化數(shù)組*/for(k=1;k<=T;k++){for(i=1;i<=T;i++){for(j=1;j<=T;j++){if(shortest[i][j]>(shortest[i][k]+shortest[k][j])){shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;/*記錄經(jīng)過(guò)的路徑*/}}}}for(i=1;i<=T;i++){shortest[i][i]=0;/*自己到自己的設(shè)置路程為零*/}}voidoutputPath(inti,intj,intk){/*輸出i到j(luò)的路徑的實(shí)際代碼*/if(i==j)return;if(path[i][j]==0){sleep(2);outtextxy(300,190+20*k,adj.vex[j].);}else{outputPath(i,path[i][j],++k);outputPath(path[i][j],j,++k);}}/*輸出最短路徑*/voidPrintPath(inti,intj){/*輸出從i到j(luò)的最短路徑*/if(shortest[i][j]==MAXCOST){setcolor(GREEN);setlinestyle(0,0,1);settextstyle(0,0,1);outtextxy(100,200,"Thereisnopath");return;}settextstyle(0,0,1);setcolor(GREEN);setlinestyle(0,0,1);outtextxy(300,170,adj.vex[i].);outputPath(i,j,0);}/********************搜索算法*********************//*********************路徑查找函數(shù)*****************/voidpath(){inti,j,k;char*str='\0';cls(0,77,getmaxx(),getmaxy());input();if(search()==ERROR){cls(0,77,getmaxx(),getmaxy());display_2();return;}else{i=search();input();if(search()==ERROR){cls(0,77,getmaxx(),getmaxy());display_2();return;}else{j=search();}/*endif*/}/*endif*/floyd();/*floyd算法*/if(shortest[i][j]!=MAXCOST){cls(0,77,getmaxx(),getmaxy());setlinestyle(0,0,1);settextstyle(0,0,1);setcolor(GREEN);outtextxy(10,100,adj.vex[i].);for(k=0;k<100;k++){line(150,100,200+k,100);delay(9000);}line(290,90,305,100);line(290,110,305,100);outtextxy(360,100,adj.vex[j].);outtextxy(100,130,"theshortest'swaylengthis:");sprintf(str,"%d",shortest[i][j]);/*將shortest[i][j]整型轉(zhuǎn)換稱字符型存放到數(shù)組str中*/outtextxy(350,130,str);/*在屏幕上輸出shortest[i][j]的內(nèi)容整型*/outtextxy(380,130,"M");outtextxy(150,150,"thewayis:");PrintPath(i,j);}else{cls(0,77,getmaxx(),getmaxy());setlinestyle(0,0,3);settextstyle(0,0,1);setcolor(GREEN);outtextxy(200,100,"havenowaytoconectthetwostation");}/*endif*/}/*********************路徑查找函數(shù)*****************//******************鼠標(biāo)處理事件*******************/voidjifa(){intx,y,z;while(1){mouse(&x,&y,&z);if(x>200&&x<280&&y>25&&y<50){alldisplay();}/*單擊景點(diǎn)一覽*/if(x>560&&x<620&&y>25&&y<50){closegraph();exit(0);}if(x>20&&x<100&&y>25&&y<50){demand();}/*單擊景點(diǎn)查詢*/if(x>380&&x<460&&y>25&&y<50){path();}/*單擊路徑查詢*/}}/******************鼠標(biāo)處理事件*******************//********************主函數(shù)********************/voidmain(void){init();jifa();}/********************主函數(shù)********************/文件infor.h#defineMAXCOST1000/*定義路徑的無(wú)窮大*/#defineT12/*目前的景點(diǎn)個(gè)數(shù)*/chushihua(adjmax*adj){inti,j;adj->vex[1].num=1;strcpy(adj->vex[1].,"NorthGate");strcpy(adj->vex[1].date.daihao,"000001");strcpy(adj->vex[1].date.jianjie,"thisistheenteranceofschool,therehavesomepolicementoprotectschool.");adj->vex[2].num=2;strcpy(adj->vex[2].,"Library");strcpy(adj->vex[2].date.daihao,"000002");strcpy(adj->vex[2].date.jianjie,"Libraryistheabigbulidinganditshavealotofbooks.");adj->vex[3].num=3;strcpy(adj->vex[3].,"Teaching-building");strcpy(adj->vex[3].date.daihao,"000003");strcpy(adj->vex[3].date.jianjie,"Teaching-buildingatthecenterofschoolbeautyful.");adj->vex[4].num=4;strcpy(adj->vex[4].,"28#Building");strcpy(adj->vex[4].date.daihao,"000004");strcpy(adj->vex[4].date.jianjie,"28#Buildingisboy'sdormandcanaccommodate2000boys.");adj->vex[5].num=5;strcpy(adj->vex[5].,"Hotelofschool");strcpy(adj->vex[5].date.daihao,"000005");strcpy(adj->vex[5].date.jianjie,"thisisthemainincomeofschooltheserviceisverywell.");adj->vex[6].num=6;strcpy(adj->vex[6].,"10thRestaurant");strcpy(adj->vex[6].date.daihao,"000006");strcpy(adj->vex[6].date.jianjie,"itssupplymostoffood,andthepricenotveryhighisgoodforstudents.");adj->vex[7].num=7;strcpy(adj->vex[7].,"Hospital");strcpy(adj->vex[7].date.daihao,"000007");strcpy(adj->vex[7].date.jianjie,"ifyouillpleaseincomethereverythingwillbefine.");adj->vex[8].num=8;strcpy(adj->vex[8].,"Playground");strcpy(adj->vex[8].date.daihao,"000008");strcpy(adj->vex[8].date.jianjie,"intheregrassverygreen,peoplecanplayandreadbookonthatground.");adj->vex[9].num=9;strcpy(adj->vex[9].,"MainBuilding");strcpy(adj->vex[9].date.daihao,"000009");strcpy(adj->vex[9].date.jianjie,"teachallintheretheystudyandcommunicatedeachotheratthere.");adj->vex[10].num=10;strcpy(adj->vex[10].,"WC");strcpy(adj->vex[10].date.daihao,"000010");strcpy(adj->vex[10].date.jianjie,"WCnearthereverofshcoolyoucanfinditeasily.");adj->vex[11].num=11;strcpy(adj->v