数据结构-校园导游程序(附源码)

石家庄铁道大学实习报告4/10实习报告实验名称：校园导游程序日期：2017年7月7日姓名：李琛学号：20153204班级：信1501-2指导教师：陈娜1．实验题目校园导游程序[问题描述]用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。2．需求分析游客通过终端可询问：（1）从某一景点到另一景点的最短路径。（2）游客从公园进入，选取一条最佳路线。（3）使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边）。[基本要求]（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离．为此图选择适当的数据结构。（2）把各种路径都显示给游客，由游客自己选择浏览路线。（3）画出景点分布图于屏幕上。3．概要设计数据类型定义#include<iostream>#include<string>//图的邻接矩阵存储表示#defineMaxInt32767//极大值#defineMVNum100//最大顶点数//顶点类型为字符型typedefintArcType;//边的权值为整型usingnamespacestd;inti,j;intS[100],D[100],min,Path[100];intN=49;intbestcost=MaxInt;//记录目前最少运费或代价intcurrentcost;//当前运费或代价intcurrent[MaxInt];//当前路径intbest[MaxInt];//记录最佳路径structAMGraphd{ stringvexs[MVNum];//顶点表 intarcs[MVNum][MVNum];//邻接矩阵 intvexnum;//图的当前点数 intarcnum;//边数 stringinfo[MVNum];//景点介绍}G;主函数调用其它函数4．详细设计#include<iostream>#include<string>//图的邻接矩阵存储表示#defineMaxInt32767//极大值#defineMVNum100//最大顶点数//顶点类型为字符型typedefintArcType;//边的权值为整型usingnamespacestd;inti,j;intS[100],D[100],min,Path[100];intN=49;intbestcost=MaxInt;//记录目前最少运费或代价intcurrentcost;//当前运费或代价intcurrent[MaxInt];//当前路径intbest[MaxInt];//记录最佳路径structAMGraphd{ stringvexs[MVNum];//顶点表 intarcs[MVNum][MVNum];//邻接矩阵 intvexnum;//图的当前点数 intarcnum;//边数 stringinfo[MVNum];//景点介绍}G; G.vexs[20]="三实验楼";G.info[20]="第三实验楼"; G.vexs[21]="超市";G.info[21]="学校超市，银行都在这"; G.vexs[22]="九栋";G.info[22]="最大的学生宿舍楼"; G.vexs[23]="学一";G.info[23]="学一餐厅，地上两层，地下一层，共三层"; G.vexs[24]="西操";G.info[24]="学校西边的操场，塑胶操场，比较大"; G.vexs[25]="机械楼";G.info[25]="机械学院的楼"; G.vexs[26]="九实验楼";G.info[26]="第九实验楼，主要是计算机上机"; G.vexs[27]="交通楼";G.info[27]="交通学院的楼"; G.vexs[28]="1栋";G.info[28]="学生第一宿舍楼"; G.vexs[29]="10/11栋";G.info[29]="学生宿舍"; G.vexs[30]="土木楼";G.info[30]="土木学院的楼"; G.vexs[31]="招待所";G.info[30]="铁道大学的招待所"; G.vexnum=32; G.arcnum=49; for(i=0;i<G.vexnum;++i)//权值初始化为最大值 for(j=0;j<G.arcnum;++j) { G.arcs[i][j]=MaxInt; } G.arcs[0][2]=1;G.arcs[1][2]=2;G.arcs[1][6]=1;G.arcs[2][7]=1;G.arcs[2][3]=2;G.arcs[3][8]=1;G.arcs[3][4]=1;G.arcs[4][9]=1;G.arcs[4][5]=3;G.arcs[5][10]=1; G.arcs[2][0]=1;G.arcs[2][1]=2;G.arcs[6][1]=1;G.arcs[7][2]=1;G.arcs[3][2]=2;G.arcs[8][3]=1;G.arcs[4][3]=1;G.arcs[9][4]=1;G.arcs[5][4]=3;G.arcs[10][5]=1; G.arcs[6][7]=2;G.arcs[6][12]=1;G.arcs[7][13]=1;G.arcs[7][8]=2;G.arcs[8][15]=1;G.arcs[8][9]=1;G.arcs[9][16]=1;G.arcs[9][10]=3;G.arcs[10][17]=1;G.arcs[10][11]=2; G.arcs[7][6]=2;G.arcs[12][6]=1;G.arcs[13][7]=1;G.arcs[8][7]=2;G.arcs[15][8]=1;G.arcs[9][8]=1;G.arcs[16][9]=1;G.arcs[10][9]=3;G.arcs[17][10]=1;G.arcs[11][10]=2; G.arcs[11][18]=2;G.arcs[12][13]=2;G.arcs[12][19]=1;G.arcs[13][20]=1;G.arcs[13][14]=1;G.arcs[14][15]=1;G.arcs[15][27]=2;G.arcs[15][16]=1;G.arcs[16][21]=1;G.arcs[16][17]=1; G.arcs[18][11]=2;G.arcs[13][12]=2;G.arcs[19][12]=1;G.arcs[20][13]=1;G.arcs[14][13]=1;G.arcs[15][14]=1;G.arcs[27][15]=2;G.arcs[16][15]=1;G.arcs[21][16]=1;G.arcs[17][16]=1; G.arcs[17][22]=1;G.arcs[17][18]=1;G.arcs[18][23]=1;G.arcs[19][20]=2;G.arcs[19][25]=1;G.arcs[20][26]=1;G.arcs[21][28]=1;G.arcs[21][22]=2;G.arcs[22][29]=1;G.arcs[22][23]=2; G.arcs[22][17]=1;G.arcs[18][17]=1;G.arcs[23][18]=1;G.arcs[20][19]=2;G.arcs[25][19]=1;G.arcs[26][20]=1;G.arcs[28][21]=1;G.arcs[22][21]=2;G.arcs[29][22]=1;G.arcs[23][22]=2; G.arcs[24][25]=1;G.arcs[25][26]=2;G.arcs[26][30]=1;G.arcs[26][27]=2;G.arcs[27][28]=1;G.arcs[28][29]=2;G.arcs[24][30]=5;G.arcs[0][31]=2;G.arcs[4][31]=3; G.arcs[25][24]=1;G.arcs[26][25]=2;G.arcs[30][26]=1;G.arcs[27][26]=2;G.arcs[28][27]=1;G.arcs[29][28]=2;G.arcs[30][24]=5;G.arcs[31][0]=2;G.arcs[31][4]=3; return0;}voidfind(){ intff; stringss; cout<<"请输入景点"<<endl; cin>>ss; ff=LocateVex(G,ss);//起点 cout<<ss<<"的简介为："<<endl; cout<<G.info[ff]<<endl; cout<<endl;}voidshow(){ cout<<"土木楼"<<endl; cout<<"||"<<endl; cout<<"西操机械楼九实验楼交通楼1栋10/11栋"<<endl; cout<<"|||||"<<endl; cout<<"游泳馆三实验楼|超市九栋学一"<<endl; cout<<"||||||"<<endl; cout<<"体育馆图书馆信息楼五教基教4/5/7/8栋学二"<<endl; cout<<"||||||"<<endl; cout<<"三教沁园翠园大礼堂泽园综餐"<<endl; cout<<"|||||"<<endl; cout<<"二教一教四教校医院春晖楼"<<endl; cout<<"||"<<endl; cout<<"正门招待所"<<endl;}voidxuanze(){ stringa; stringb; cout<<"请输入当前位置："; cin>>a; cout<<"请输入终点位置："; cin>>b; inti,n,v,v0,w,z; v0=LocateVex(G,a);//起点 z=LocateVex(G,b);//终点 n=G.vexnum; for(v=0;v<n;v++) { S[v]=false; D[v]=G.arcs[v0][v]; if(D[v]<MaxInt) Path[v]=v0; else Path[v]=-1; } S[v0]=true; D[v0]=0; for(i=1;i<n;i++) { min=MaxInt; for(w=0;w<n;w++) { if(!S[w]&&D[w]<min) { v=w; min=D[w]; } } S[v]=true; for(w=0;w<n;w++) { if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])) { D[w]=D[v]+G.arcs[v][w]; Path[w]=v; } } } cout<<endl; cout<<"路线为："<<endl; ints=z; cout<<G.vexs[z]<<"<--"; while(Path[s]!=v0) { cout<<G.vexs[Path[s