基于无向图的校园导游系统_数据结构课程设计报告(编辑修改稿)

基于无向图的校园导游系统_数据结构课程设计报告(编辑修改稿)内容摘要：

{ if(k 5 == 0) { coutendl。 cout39。 \t39。 [k].name。 } else { cout39。 \t39。 [k].name。 } }将景点的名称打印在显示屏上，最后是一个 switch()。 的选择语句，提示游客根据选择来进入到相关的操作界面实现程序的基本功能。 查找介绍函数的详细设计 当游客选择了要查找景点的信息的介绍这一项功能的时候，程序就会调用DisIntroduction(G)。 函数进入到查找景点的介绍的界面，当游客输入了需要查找的景点的名称的时候，程序利用 for()。 循环语句来查找是否有这个景点for(int i=0。 i。 i++) { int m = strcmp([i].name,n1)。 if(m==0) { v1=i。 count1=count1+1。 } 重庆科技学院 本科生课程设计 详细设计 6 }，找到将它的编号返回，并输出它的介绍，没有找到这输出错误提示，提醒游客进行相关的操作进入正确的操作过程当中。 查找最短路径函数的详细设计 当游客选择了要查找两个景点之间的最短距离这一项功能的时候，程序就会调用 DisPath(G)；函数进入到查找两个景点之间的最短距离的操作界面当中，当游客输入了两个景点的名称过 后，程序会调用 strcmp()。 函数查看是否有这两个景点，如果有则返回他们各自的编号，并调用 ShortPath_DIJ(G,v1,v2)。 函数进入到查找最短路径问题的程序当中。 for(v=0。 v。 v++)//各对节点之间初始已知路径及距离 { final[v]=FALSE。 //从 V出发的最短路径的空集合 D[v]=[v0][v]。 //从 V 出发到图上其余各个定点 v0 可能到达的最短路径的初始值 for(w=0。 w。 w++) { P[v][w]=FALSE。 //设空路径 } if(D[v]MAXNUM) { P[v][v0]=TRUE。 P[v][v]=TRUE。 } } D[v0]=0。 final[v0]=TRUE。 int a[20]。 for(i=0。 i。 i++)//对 Path[i][j]进行初始化，使其值全部为 1000，便于后期的判断 { for(j=0。 j。 j++) { Path[i][j]=1000。 } } for(i=0。 i。 i++)//对数组进行初始化，以便对 Path[i][j]进行描述 { a[i]=1。 重庆科技学院 本科生课程设计 详细设计 7 } for(v=0。 v。 v++)//各条路线的初始节点为 v0 { Path[v][0]=v0。 } //开始主循环，每次求解得到 v0 到某个 v 顶点的最短路径，并加入到 S 集合中 for(i=1。 i。 i++)//其余 1个顶点 { m=MAXNUM。 //当前所知的离 v0最近的距离 for(w=0。 w。 w++) { if(!final[w])//w 顶点在 VS中 { if(D[w]m)//w 顶点离 v0顶点更近 { v=w。 m=D[w]。 } } } Path[v][a[v]]=v。 //离 v0 顶点最近的 v 加入 s集合 final[v]=TRUE。 for(w=0。 w。 w++)//更新当前最短路径及距离 { if((!final[w])amp。 amp。 (m+[v][w]D[w])) { D[w]=m+[v][w]。 //修改当前的最短路径的值 int k0=1。 a[w]=1。 while(Path[v][k0]!=1000) //如果上述条件成立， Path[w]路径需要改变，因为从 v0 到 w 的路径显然经过了 v0 和 v 之间的所有的点（包括 v） { Path[w][k0]=Path[v][k0]。 k0++。 a[w]++。 } } } } cout两个景点之间的最短路径为 :39。 \t39。 int k=0。 while(Path[v2][k]!=1000) 重庆科技学院 本科生课程设计 详细设计 8 { int m=Path[v2][k]。 cout[m].name39。 \t39。 k++。 } coutendl。 cout两个景点之间的最短距离为 : D[v2]Mendl。 cout请选择要进行的操作 (I:查询景点信息， P:查询两个景点之间的最短路径， Q:退出 )endl。 (1)假设用带权的邻接矩阵 arcs 来表示带权的有向图， arcs[i][j]表示弧（ vi,vj）上的权值。 若 (vi,vj)不存在，则置 arcs[i][j]为无穷大。 S为已找到从 v 出发的最短路径的终点集合，它的初始状态为空集。 那么，从 v 出发到图上其余各个定点 vi可能到达的最短路径长度的初始值为： D[i] = arcs[v][i]。 (2)选择 vj,使得 D[j] = Min{D[i] | vi ∈ V – S}vj 就是当前求得的一条从 v 出发的最短路径的终点。 令 S = S ∪ {j}。 (3)修改从 v 出发到集合 V – S 上任意顶点 vk可到达的最短路径的长度。 如果 D[j] + arcs[j][k] D[k]则修改 D[k]为 D[k] = D[j]+arcs[j][k]。 (4)重复操作 (2)、 (3)共 n – 1 次，由此求得从 v 到图上其余各个顶点的最短路径是依路径长度递增的序列。 从而求得了从一个景点到另一个景点的最短路径的问题。 退出函数的详细设计 对于退出函数，当游客选择了退出这一个操作的时候，程序就会调用 Exit()。 函数从而进入到退出函数的界面 void Exit() //退出 { cout欢迎下次继续使用 !endl。 exit(0)。 }程序会提示游客感谢使 用，欢迎下次继续使用的提示语，然后调用 exit(0)。 函数实现退出主函数的功能。 数据结构的详细设计 本软件的数据结构包括 3 个部分： 1. 邻接矩阵 重庆科技学院 本科生课程设计 详细设计 9 typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。 定义一个 邻接矩阵 ，用 邻接矩阵 来定义和储存边的相关信息。 2. 顶点的结构体 typedef struct Vertex//定义图中顶点的数据类型 { int num。 //景点编号 char name[14]。 //景点名称 char introduction[100]。 //景点介绍 }Vertex。 定义一个顶点的结构体，用来储存景点的编号、景点得名称和景点的介绍等关于景点的信息。 typedef struct //定义图的数据类型 { Vertex vexs[MAX_VERTEX_NUM]。 //顶点的结构体 AdjMatrix arcs。 //边的 邻接矩阵 int vexnum,arum。 //顶点的个数，边的个数 }MGraph。 定义一个图的结构体，用来储存顶点的信息、边的信息、顶点的个数和边的个数等相关的信息便于我们以后在用的时候能够方便快捷的调用。 定义好这些结构体后，当我们以后需要调用的时候，我们就能够方便快捷的调用这些结构体，从而使得我们在运行程序的时候能够更加的快速能够提高我们的程序的运行效率，大大的节省了我们的时间还使得程序变得更加的简单。 重庆科技学院 本科生课程设计 软件测试 10 4 软件 测试。