数据结构课程设计报告基于无向图的校园导游系统[1](2)

根据主函数中的显示信息和它给我们的相关的提示信息来进行所需要的操作，因此在这次的程序实现的过程当中，首先调用CreateUDN(G);函数创建一个无向图，然后利用一个for();循环语句 for(int k = 0; k < G.vexnum; k++)

{

{ } else { }

cout<<""<<'\t'<<G.vexs[k].name; cout<<endl;

cout<<""<<'\t'<<G.vexs[k].name;

if(k - 5 == 0)

}将景点的名称打印在显示屏上，最后是一个switch();的选择语句，提示游

客根据选择来进入到相关的操作界面实现程序的基本功能。

3.3 查找介绍函数的详细设计

当游客选择了要查找景点的信息的介绍这一项功能的时候，程序就会调用

DisIntroduction(G);函数进入到查找景点的介绍的界面，当游客输入了需要查找的景点的名称的时候，程序利用for();循环语句来查找是否有这个景点for(int i=0;i<G.vexnum;i++)

{

int m = strcmp(G.vexs[i].name,n1); if(m==0) { }

v1=i;

count1=count1+1;

}，找到将它的编号返回，并输出它的介绍，没有找到这输出错误提示，提

醒游客进行相关的操作进入正确的操作过程当中。

3.4 查找最短路径函数的详细设计

当游客选择了要查找两个景点之间的最短距离这一项功能的时候，程序就会

调用DisPath(G)；函数进入到查找两个景点之间的最短距离的操作界面当中，当游客输入了两个景点的名称过后，程序会调用strcmp();函数查看是否有这两个景点，如果有则返回他们各自的编号，并调用ShortPath_DIJ(G,v1,v2);函数进入到查找最短路径问题的程序当中。

for(v=0;v<G.vexnum;v++)//各对节点之间初始已知路径及距离 {

final[v]=FALSE;//从V出发的最短路径的空集合

D[v]=G.arcs[v0][v];//从V出发到图上其余各个定点v0可能到达的最短路径的初始值

for(w=0;w<G.vexnum;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<G.vexnum;i++)//对Path[i][j]进行初始化，使其值全部为1000，便于后期的判断 {

for(j=0;j<G.vexnum;j++) {

Path[i][j]=1000; } }

for(i=0;i<G.vexnum;i++)//对数组进行初始化，以便对Path[i][j]进行描述 {

a[i]=1;

for(v=0;v<G.vexnum;v++)//各条路线的初始节点为v0 {

Path[v][0]=v0; }

//开始主循环，每次求解得到v0到某个v顶点的最短路径，并加入到S集合中

for(i=1;i<G.vexnum;i++)//其余G.vexnum - 1个顶点 {

m=MAXNUM;//当前所知的离v0最近的距离 for(w=0;w<G.vexnum;w++) {

if(!final[w])//w顶点在V-S中 {

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<G.vexnum;w++)//更新当前最短路径及距离 {

if((!final[w])&&(m+G.arcs[v][w]<D[w])) {

D[w]=m+G.arcs[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<<"两个景点之间的最短路径为:"<<'\t'; int k=0;

while(Path[v2][k]!=1000)

int m=Path[v2][k];

cout<<G.vexs[m].name<<'\t'; k++; }

cout<<endl;

cout<<"两个景点之间的最短距离为: "<<D[v2]<<"M"<<endl;

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到图上其余各个顶点的最短路径是依路径长度递增的序列。从而求得了从一个景点到另一个景点的最短路径的问题。

3.5 退出函数的详细设计

对于退出函数，当游客选择了退出这一个操作的时候，程序就会调用Exit();

函数从而进入到退出函数的界面 void Exit() //退出 {

cout<<"欢迎下次继续使用!"<<endl; exit(0);

}程序会提示游客感谢使用，欢迎下次继续使用的提示语，然后调用exit(0);函数实现退出主函数的功能。

3.6 数据结构的详细设计

本软件的数据结构包括3个部分： 1. 邻接矩阵

typedef int AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; 定义一个邻接矩阵，用邻接矩阵来定义和储存边的相关信息。

2. 顶点的结构体

typedef struct Vertex//定义图中顶点的数据类型 {

int num;//景点编号 char name[14];//景点名称 char introduction[100];//景点介绍

}Vertex;

定义一个顶点的结构体，用来储存景点的编号、景点得名称和景点的介绍等关于景点的信息。

3.无向图的结构体

typedef struct //定义图的数据类型 {

Vertex vexs[MAX_VERTEX_NUM];//顶点的结构体 AdjMatrix arcs;//边的邻接矩阵

int vexnum,arcnum;//顶点的个数，边的个数

}MGraph;

定义一个图的结构体，用来储存顶点的信息、边的信息、顶点的个数和边的个数等相关的信息便于我们以后在用的时候能够方便快捷的调用。

定义好这些结构体后，当我们以后需要调用的时候，我们就能够方便快捷的调用这些结构体，从而使得我们在运行程序的时候能够更加的快速能够提高我们的程序的运行效率，大大的节省了我们的时间还使得程序变得更加的简单。

4 软件测试

4.1 菜单的测试

对于菜单函数的测试，首先菜单是一个可示化的界面，它能够提示游客依据

显示屏上出现的提示来进行相关的操作，查看所有的景点从而方便游客进行相关的操作，因而我们在运行程序的时候首先就会进入到菜单函数当中，经过测试其能够实现我们所要实现得基本功能，其效果图如图4.1所示：

图4.1菜单

4.2 查找景点简介的测试

对于查找景点的介绍的测试，首先依据显示屏上的提示首先输入要进行的操

作输入‘i’进入查找景点信息的操作界面，然后输入需要查找的景点的名称即可显示出景点的介绍信息，经过测试可以得出其没有什么 …… 此处隐藏：3025字，全部文档内容请下载后查看。喜欢就下载吧 ……