第1页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第1页共18页HUBEINORMALUNIVERSITY课程设计论文Course’sThesis课程名称数据结构专业通信工程班级0803班学生蔡兵学号2008115020301设计题目校园导游咨询指导教师孙玉霞老师时间2011年3月22日年度2011年第二学期第2页共18页第1页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第2页共18页目录一、课程目的二、基本要求三、实验内容及步骤1、概要设计2、详细设计（1）建立模型（逻辑结构）（2）建立模块之间的关系（存储结构）（3）算法四、源程序清单五、测试结果六、课程设计总结及心得体会第3页共18页第2页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第3页共18页实验题目：校园导游咨询一、课程目的为用户提供路径咨询和景点查询，根据用户指定的始点和终点输出相应路径或者根据用户指定的景点输出景点的信息。二、基本要求（1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。附加要求：a、界面友好，函数功能要划分好b、总体设计应画一流程图c、程序要加必要的注释d、要提供程序测试方案三、实验内容及步骤1、概要设计：第4页共18页第3页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第4页共18页在设计这个校园导游系统前考虑到整个信息的结点和操作，可以通过邻接矩阵借助图的相关知识来完成。按照要求分为三个模块，图的信息的初始化，图各个景点信息的查询和景点间的最短路径查询功能voidintroduce()//用来查询各景点的相关信息intshortestdistance()//用来查询任意两个景点之间的最短路径和经过的景点voidfloyed()//用来计算任意两个景点之间的最短路径voiddisplay(inti,intj)//用来显示任意景点之间的最短路径和经过的景点/*包含头文件*/#include/*定义符号常量*/#defineINT_MAX10000#definen10/*定义全局变量*/intcost[n][n];/*边的值*/intshortest[n][n];/*两点间的最短距离*/intpath[n][n];/*经过的景点*/第5页共18页第4页共18页17823459610732151111112222编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第5页共18页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的结点，此时该路径第6页共18页第5页共18页编号：时间：2021年x月x日书山有路勤为径，学海无涯苦作舟页码：第6页共18页长度与从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度相同；另一种情况是该路径经过结点序号k+1的结点，此时该路径可分为两段，一段是从结点Vi到结点Vk+1的最短路径，另一段是从结点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;}}四、源程序清单#include第7页...
