课程设计报告课程设计题目：校园导航专业：计算机科学与技术班级：1230701学号：2学生姓名：胡玖龙指导教师：刘志锋2014年6月19日1 / 17实验题目:校园导航系统实验时间：2014/6/16-2014/6/19实验地点：软件楼402实验目的：综合运用所学的数据结构知识解决一个关于学校导航系统的问题，侧重对图的相关内容特别是求最短路径的应用，使得能进一步熟悉掌握数据结构的基础知识，进一步提升自己的解决问题和编程调试能力，为后续专业课程的学习打下基础。

实验要求：设计学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从某个场所到达另一场所的最佳路径。

求最短路径用Dijkstra或Floryd算法实现。

2 / 17实现思路：先分析需求，本程序的主要目的是提供本学校地点的路径查询,并提供其他各种信息查询服务。

需求：1、提供校园平面图，使得能直观的了解学校。

2、提供地点信息查询，为各地点提供简短的介绍。

3、提供任意两地点间最短路径查询，并计算总路程。

根据要求，先将校园平面图信息抽象为无向网，用邻接矩阵存储。

需求1：定义map()函数，功能是输出校园的平面图。

可简单的通过printf()函数实现。

需求2：定义Query()函数，功能是查询输出地点信息。

可直接输出无向网中的顶点信息。

需求3：根据输入的起点和终点，运用Floryd算法，求出最短路径，计算路径长度并输出。

考虑到使用者并不一定需要使用所有的功能，所以开始时需要一个选择菜单。

定义Menu()函数，功能是提供功能选择。

输入1，选择查看学校平面图输入2，选择查看各地点信息输入3，选择查找两地点间最短路径输入4，退出程序3 / 17总流程图：4 / 17平面图模块流程图：地点信息查询模块流程图：5 / 17求最短路径模块流程图：实现过程：从学校的平面图中选取出12个比较重要的地点，将其抽象成无向带权网并用邻接矩阵来表示。

以图中的顶点代表地点，存放地点名称、编号、简介等信息，权值代表两地之间的距离。

最短路径用Floyd算法求出。

地点间距离用地图软件测出。

6 / 17将得到的信息绘制成无向网：程序用到的函数：MGraph InitGraph(MGraph &G) //构造校园图void Menu() //初始菜单void Map() //校园平面图V oid Number() //输出地点编号，在其他操作中会用到void Query(MGraph G) //查找函数，可以输出地点名称和介绍void floyd(MGraph G) //floyd算法void shortestPath_Floyd(MGraph &G) //求最短路径void main(); //主函数（1）图的存储结构：typedef struct{char name[30]; //地点名称int num; //地点编号char introduction[200]; //地点介绍1.体育馆2.北区宿舍3.图书馆4.樱花广场5.三教6.东门7.青春广场8.西区食堂9.西区宿舍10.南区食堂11.南区宿舍12.南门7 / 17}VertexType;typedef struct{VertexType vexs[MAX]; //地点int arcs[MAX][MAX]; //存储图的邻接矩阵int vexNum,arcNum; //地点数，路径数}MGraph;（2）构造校园图：MGraph InitGraph(MGraph &G) //构造校园图{int i,j;G.vexNum=12;G.arcNum=16;for(i=1;i<=G.vexNum;i++)G.vexs[i].num=i;strcpy(G.vexs[1].name,"体育馆");strcpy(G.vexs[1].introduction,"有田径场及各种体育活动场馆");strcpy(G.vexs[2].name,"北区宿舍");strcpy(G.vexs[2].introduction,"学校北区的宿舍");strcpy(G.vexs[3].name,"图书馆");strcpy(G.vexs[3].introduction,"有着丰富的藏书，是学习、自习的好地方");strcpy(G.vexs[4].name,"樱花广场");strcpy(G.vexs[4].introduction,"有很多樱花树，适合早读");strcpy(G.vexs[5].name,"三教");strcpy(G.vexs[5].introduction,"学校的教学区");strcpy(G.vexs[6].name,"东门");strcpy(G.vexs[6].introduction,"学校的正门");strcpy(G.vexs[7].name,"青春广场");strcpy(G.vexs[7].introduction,"经常有各种各样的社团活动");strcpy(G.vexs[8].name,"西区食堂");strcpy(G.vexs[8].introduction,"西区的食堂，饭菜很好吃");strcpy(G.vexs[9].name,"西区宿舍");strcpy(G.vexs[9].introduction,"学校西区的宿舍，既有男生宿舍也有女生宿舍");strcpy(G.vexs[10].name,"南区食堂");strcpy(G.vexs[10].introduction,"南区食堂，饭菜很好吃");strcpy(G.vexs[11].name,"南区宿舍");strcpy(G.vexs[11].introduction,"学校南区的宿舍，全是男生宿舍");strcpy(G.vexs[12].name,"南门");strcpy(G.vexs[12].introduction,"学校的南门，比较小");for(i=0;i<G.vexNum;i++)8 / 17for(j=0;j<G.vexNum;j++){G.arcs[i][j]=INFINITY; //不存在的路径长度设为无穷大G.arcs[0][1]=170;G.arcs[1][2]=200;G.arcs[1][4]=150;G.arcs[2][3]=30;G.arcs[2][4]=150;G.arcs[2][5]=300;G.arcs[3][4]=30;G.arcs[4][6]=170;G.arcs[4][7]=160;G.arcs[5][6]=500;G.arcs[5][10]=570;G.arcs[6][7]=100;G.arcs[7][8]=160;G.arcs[8][9]=180;G.arcs[9][10]=100;G.arcs[10][11]=20;}for(i=0;i<G.vexNum;i++) //无向网的邻接矩阵关于对角线对称for(j=0;j<G.vexNum;j++)G.arcs[j][i]=G.arcs[i][j];return G;}（3）菜单模块：void Menu() //初始菜单{printf("\n\n 东华理工大学校园导游系统\n");printf(" ┏━━┳━━━━━━━━━━━━━━━━━━━━━━━━━━┓\n");printf(" ┃编号┃功能┃\n");printf(" ┣━━╋━━━━━━━━━━━━━━━━━━━━━━━━━━┫\n");printf(" ┃1 ┃查看学校平面图┃\n");printf(" ┃2 ┃查看地点信息┃\n");printf(" ┃3 ┃查找两地点间最短路径┃\n");printf(" ┃4 ┃退出┃\n");printf(" ┗━━┻━━━━━━━━━━━━━━━━━━━━━━━━━━┛\n");printf("输入你的选择：");}9 / 17（4）平面图模块：void Map() //校园平面图{printf("\n");printf(" ┏━━━━━━━┓\n");printf(" ┃┃ \n");printf(" ┃ 1.体育馆┃\n");printf(" ┃┃\n");printf(" ┗━━━┳━━━┛\n");printf(" ┃\n");printf(" ┏━━━┻━━━┓\n");printf(" ┃┃\n");printf(" ┏━━━━━━━━━┳━━━┫ 2.北区宿舍┣━━━┓\n");printf(" ┃┃┃┃┃\n");printf(" ┃┃┗━━━━━━━┛┃\n");printf(" ┃┏━━━━━━━┓┃┃\n");printf(" ┃┃┃┃┃\n");printf(" ┏━━┓┃┃┃┃┣┓\n");printf(" ┃┣╋┫ 3.图书馆┣┫┃┃6. \n");printf(" ┃4. ┃┃┃┃┃┃┃东\n");printf(" ┃樱┃┃┃┃┣━━━━━━━━━━━━━━━┫┃门\n");printf(" ┃花┃┃┗━━━━━━━┛┃┃┃\n");printf(" ┃广┃┃┏━━━━━━━┓┃┃┃\n");printf(" ┃场┃┃┃┃┃┣┛\n");printf(" ┃┃┃┃┃┃┃\n");printf(" ┃┣┻┫ 5.三教┣┫┃\n");printf(" ┗━━┛┃┃┃┃\n");printf(" ┃┃┃┃\n");printf(" ┗━━━━━━━┛┣━━━━┳━━━━━━━━━━┫\n");printf(" ┃┏━━━┻━━━┓┃\n");printf(" ┏━━━━━━━┓┃┃┃┃\n");printf(" ┃┃┃┃┃┃\n");printf(" ┃┃┃┃7.青春广场┃┃\n");printf(" ┃8.西区食堂┣╋┫┃┃\n");printf(" ┃┃┃┃┃┃\n");printf(" ┃┃┃┃┃┃\n");printf(" ┗━━━━━━━┛┃┗━━━━━━━┛┃\n");printf(" ┃┃\n");printf(" ┏━━━━━━━┓┃┃\n");printf(" ┃┃┃┃\n");printf(" ┃┃┃┃\n");printf(" ┃9. ┃┃┃\n");printf(" ┃西┃┃┃\n");printf(" ┃区┣┫┃\n");10 / 17printf(" ┃宿┃┃┃\n");printf(" ┃舍┃┃┃\n");printf(" ┃┃┃┃\n");printf(" ┃┃┃┃\n");printf(" ┃┃┃┃\n");printf(" ┗━━━━━━━┛┃┃\n");printf(" ┃┃\n");printf(" ┃┏━━━━━━━━━━━┓┃\n");printf(" ┏━━━━━━━┓┃┃┃┃\n");printf(" ┃┃┃┃┃┃\n");printf(" ┃┃┃┃┃┏┻┓\n");printf(" ┃10.南区食堂┣┻┫11.南区宿舍┣━┫┃\n");printf(" ┃┃┃┃┗━┛\n");printf(" ┃┃┃┃12.南门\n");printf(" ┗━━━━━━━┛┃┃\n");printf(" ┗━━━━━━━━━━━┛\n");printf("请按任意键继续!");getch();}（5）地点编号函数：V oid Number() //输出地点编号，在其他操作中会用到{int v;printf("\n\n┏━━┳━━━━━━┓\n");printf("┃编号┃地点名称┃\n");for(v=1;v<=G.vexNum;v++){printf("┃%-4d┃%-12s┃\n",G.vexs[v].num,G.vexs[v].name);}printf("┗━━┻━━━━━━┛\n");}（6）地点信息查询模块：void Query(MGraph G) //查找函数，可以输出地点名称和介绍{int k,i=1;Number();while(i){printf("请输入要查询的地点编号,输入0退出:");scanf("%d",&k);if(k<0||k>G.vexNum){printf("地点编号不存在!请重新输入地点编号:");scanf("%d",&k);}printf("%d.%s %-62s\n\n",G.vexs[k].num,G.vexs[k].name,G.vexs[k].introduction);if(k==0)i=0;}}（7）Floyd算法求最短路径：int D[MAX][MAX],Path[MAX][MAX];void floyd(MGraph G) //Floyd算法{int i,j,k;for(i=0;i<G.vexNum;i++)for(j=0;j<G.vexNum;j++){D[i][j]=G.arcs[i][j];if(i!=j&&G.arcs[i][j]<INFINITY) Path[i][j]=i;else Path[i][j]=-1;}for(k=0;k<G.vexNum;k++)for(i=0;i<G.vexNum;i++)for(j=0;j<G.vexNum;j++)if(D[i][k]+D[k][j]<D[i][j]){D[i][j]=D[i][k]+D[k][j];Path[i][j]=Path[k][j];}}void shortestPath_Floyd(MGraph &G) //求最短路径{int i,j,p,m,k;int b[100];floyd(G);Number();do{printf("请输入起点编号:");scanf("%d",&i);printf("请输入终点编号:");scanf("%d",&j);if(i==j)printf("起点和终点一样，请重新输入\n");else if(i>12||i<0||j>12||j<0)printf("输入错误，请重新输入\n");}while(i==j||i>12||i<0||j>12||j<0);i=i-1;j=j-1;if(i!=j){printf("起点：%s，终点：%s\n最短路径：",G.vexs[i+1].name,G.vexs[j+1].name);p=Path[i][j];if(p==-1) printf("empty\n");else{m=0;b[m++]=j;while(p!=i){b[m++]=p; p=Path[i][p];}b[m]=i;for(k=m;k>0;k--) printf("%s->",G.vexs[b[k]+1].name);printf("%s,路程为%d米\n",G.vexs[b[0]+1].name,D[i][j]);}}printf("\n\n按任意键继续\n\n");getch();}（8）主函数：void main() //主函数{InitGraph(G);int i;Menu(G);scanf("%d",&i); //输入选择while(i!=4) //输入4，则退出{switch(i){ //每次选择后会调用清屏函数，使界面美观case 1:system("CLS");Map();Menu(G);break; //若输入1，则输出平面图case 2:system("CLS");Query(G);Menu(G);break; //若输入2，则查找并输出地点名称和介绍case 3:system("CLS");shortestPath_Floyd(G);Menu(G);break; //若输入3，则找出最短路径case 4:;break;default:printf("输入错误,清重新输入\n");}scanf("%d",&i);}}运行结果：图1：初始菜单，输入1查看学校平面图，输入2查看地点信息，输入3查找两地点间最短路径，输入4退出。