校园导游咨询

HUBEINORMALUNIVERSITY课程设计论文Course’sThesis课程名称数据结构专业通信工程班级0803班学生蔡兵学号2008115020301设计题目校园导游咨询指导教师孙玉霞老师时间2011年3月22日年度2011年第二学期目录一、课程目的二、基本要求三、实验内容及步骤1、概要设计2、详细设计（1）建立模型（逻辑结构）（2）建立模块之间的关系（存储结构）（3）算法四、源程序清单五、测试结果六、课程设计总结及心得体会实验题目：校园导游咨询一、课程目的为用户提供路径咨询和景点查询，根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。二、基本要求（1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。附加要求：a、界面友好，函数功能要划分好b、总体设计应画一流程图c、程序要加必要的注释d、要提供程序测试方案三、实验内容及步骤1、概要设计：在设计这个校园导游系统前考虑到整个信息的结点和操作，可以通过邻接矩阵借助图的相关知识来完成。按照要求分为三个模块，图的信息的初始化，图各个景点信息的查询和景点间的最短路径查询功能voidintroduce()//用来查询各景点的相关信息intshortestdistance()//用来查询任意两个景点之间的最短路径和经过的景点voidfloyed()//用来计算任意两个景点之间的最短路径voiddisplay(inti,intj)//用来显示任意景点之间的最短路径和经过的景点/*包含头文件*/#includestring/*定义符号常量*/#defineINT_MAX10000#definen10/*定义全局变量*/intcost[n][n];/*边的值*/intshortest[n][n];/*两点间的最短距离*/intpath[n][n];/*经过的景点*/2、详细设计：（1）建立模型（逻辑结构：图）（2）建立模块之间的关系（存储结构：邻接矩阵）（3）算法这个程序的关键代码就利用Floyd算法求最短路径并将路径存放起来。Floyd算法的算法思想：设矩阵cost用来存放带权无向图G的权值，即矩阵元素cost[i][j]中存放着序号为i的结点到序号为j的结点之间的权值，可以通过递推构造一个矩阵序列A0，A1，A2，…，AN来求每对结点之间的最短路径。其中，Ak[i][j]表示从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度。初始时有A0[i][j]=cost[i][j]。当已经求出Ak，要递推求解Ak+1时，可分为两种情况来考虑：一种清楚是该结点序号为k+1的结点，此时该路径长度与从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度相同；另一种情况是该路径经过结点序号k+1的结点，此时该路径可分为两段，一段是从结点Vi到结点Vk+1的最短路径，17823459610732151111112222另一段是从结点Vk+1到结点Vj的最短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况的路径长度较小者，就是要求的从结点Vi到结点Vj的路径上所经过的结点序号不大于k+1的最短路径长度。Floyd具体算法设计voidfloyed(){inti,j,k;for(i=1;i=n;i++)for(j=1;j=n;j++){shortest[i][j]=cost[i][j];path[i][j]=0;}for(k=1;k=n;k++)for(i=1;i=n;i++)for(j=1;j=n;j++)if(shortest[i][j](shortest[i][k]+shortest[k][j])){shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;path[j][i]=k;}}四、源程序清单#includestring#defineINT_MAX10000#definen10intcost[n][n];intshortest[n][n];intpath[n][n];voidintroduce();intshortestdistance();voidfloyed();voiddisplay(inti,intj);voidmain(){inti,j,q;chark;printf(\t----------------欢迎来到湖北师范学院----------------\n\n);printf(\t---按1进入校园导游指示系统，否则请再次输入---\n);PR:printf(\t---------------请输入你的选择----------------\n\t);scanf(%d,&q);if(q!=1){printf(\t-----------------输入错误，请再次输入---------\n);gotoPR;}else{for(i=0;i=n;i++)for(j=0;j=n;j++)cost[i][j]=INT_MAX;cost[1][2]=cost[2][1]=3;cost[2][3]=cost[3][2]=1;cost[3][4]=cost[4][3]=2;cost[4][5]=cost[5][4]=1;cost[5][6]=cost[6][5]=1;cost[3][6]=cost[6][3]=2;cost[1][4]=cost[4][1]=5;cost[1][7]=cost[7][1]=7;cost[4][7]=cost[7][4]=1;cost[7][5]=cost[5][7]=1;cost[7][8]=cost[8][7]=2;cost[8][9]=cost[9][8]=1;cost[5][9]=cost[9][5]=2;cost[8][5]=cost[5][8]=2;cost[8][10]=cost[10][8]=1;cost[1][1]=cost[2][2]=cost[3][3]=cost[4][4]=cost[5][5]=0;cost[6][6]=cost[7][7]=cost[8][8]=cost[9][9]=cost[10][10]=0;while(1){printf(----------------欢迎使用校园导游系统!----------------\n);printf(-----------------湖北师范学院--------------------\n);printf(1.景点信息查询………请按i(introduc)键\n);printf(2.景点最短路径查询…请按s(shortestdistance)键\n);printf(3.退出系统……………请按e(exit)键\n);printf(学校景点列表:\n);printf(1:学校大门\n);printf(2:图书馆\n);printf(3:教育大楼\n);printf(4:科教大厦\n);printf(5:实验楼\n);printf(6:外语楼\n);printf(7:花坛\n);printf(8:篮球场\n);printf(9:足球场\n);printf(10:食堂\n);printf(请选择服务:);scanf(\n%c,&k);switch(k){case'i':printf(进入景点信息查询:);introduce();break;case's':printf(进入最短路径查询:);shortestdistance();break;case'e':exit(0);default:printf(输入信息错误！\n请输入字母i或s或e.\n);break;}}}}voidintroduce(){inta;printf(您想查询哪个景点的详细信息?请输入景点编号:);scanf(%d,&a);printf(\n);switch(a){case1:printf(1:学校大门\n\n学校的正门，气势宏伟。\n\n);break;case2:printf(2:图书馆\n\n学校信息资源中心。\n\n);break;case3:printf(3:教育大楼\n\n学生自学自修的天堂。\n\n);break;case4:printf(4:科教大厦\n\n全校学生公共教学楼。\n\n);break;case5:printf(5:实验楼\n\n计算机机房及各种实验设施。\n\n);break;case6:printf(6:外语楼\n\n外国文化交流中心。\n\n);break;case7:printf(7:花坛\n\n美丽校园的缩影。\n\n);break;case8:printf(8:篮球场\n\n篮球健儿的摇篮。\n\n);break;case9:printf(9:足球场\n\n校内最开阔的地方。\n\n\n);break;case10:printf(10:食堂\n\n学生就餐的地方。\n\n);break;default:printf(景点编号输入错误！请输入1-10的数字编号！\n\n);break;}}intshortestdistance(){inti,j;printf(请输入要查询的两个景点的编号(1-10的数字编号并用','间隔):);scanf(%d,%d,&i,&j);if(in||i=0||jn||j0){printf(输入信息错误！\n\n);printf(请输入要查询的两个景点的编号(1-10的数字编号并用','间隔):\n);scanf(%d,%d,&i,&j);}else{floyed();display(i,j);}return1;}voidfloyed(){inti,j,k;for(i=1;i=n;i++)for(j=1;j=n;j++){shortest[i][j]=cost[i][j];path[i][j]=0;}for(k=1;k=n;k++)for(i=1;i=n;i++)for(j=1;j=n;j++)if(shortest[i][j](shortest[i][k]+shortest[k][j])){shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;path[j][i]=k;}}voiddisplay(inti,intj){inta,b;a=i;b=j;printf(您要查询的两景点间最短路径是:\n\n);if(shortest[i][j]!=INT_MAX){if(ij){printf(%d,b);while(path[i][j]!=0){printf(-%d,path[i][j]);if(ij)j=path[i][j];elsei=path[j][i];}printf(-%d,a);printf(\n\n);printf((%d-%d)最短距离是:%d米\n\n,a,b,shortest[a][b]);}else{printf(%d,a);while(path[i][j]!=0){printf(-%d,path[i][j]);if(ij)j=path[i][j];elsei=path[j][i];}printf(-%d,b);printf(\n\n);printf((%d-%d)最短距离是:%5d米\n\n,a,b,shortest[a][b]);}}elseprintf(输入错误！不存在此路！\n\n);printf(\n);}五、测试结果校园导游的主页面输入1时进入校园导游系统查询景点5的相关信息查询景点1和6之间的最短路径和经过的景点六、课程设计总结及心得体会这次的课程设计题目是校园导游，总的来说还是比较简单的，只运用了Floyd算法和操作。程序设计也比较简单，运行结果正确，