数据结构旅游区导航图课程设计(54页).doc

《数据结构课程设计》报告

题 目 旅游区导游图
专 业 计算机科学与技术
班 级 （2）班
学 生 ###

13 旅游区导游图
题目内容
问题描述：
设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m<n）有直接的道路（有对应的距离）相通，请设计一个简易的旅游区导游系统。
以(Vi ,Vj ,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi和Vj表示两个不同的旅游景点，d表示这两个景点之间的道路距离；该旅游景点图采用邻接矩阵存储结构(数组)。
实现要求：
⑴ 旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。
⑵ 相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。
⑶ 景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。
⑷ 景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。
⑸ 最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。
⑹ 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。
⒈ 本人完成的工作
完成的工作：首先是用邻接矩阵的存储形式建立无向带权图，然后将邻接矩阵转换为邻接链表，最后用狄克斯特拉函数求出后面的三道有关最短路径的小题，设计主函数。
⒉ 所采用的数据结构
邻接矩阵的数据结构，包括（弧/边的结构定义、图的结构定义）
邻接链表的数据结构，包括（弧/边的结点定义、邻接表头结点定义、图的结构定义）
数据结构的定义
//邻接矩阵结构体
typedef struct
{ char vex1, vex2 ; /* 弧或边所依附的两个顶点 */
int ArcVal ; /* 弧或边的权值 */
}ArcType ; /* 弧或边的结构定义 */
typedef struct
{
int vexnum, arcnum ; /* 图的当前顶点数和弧数 */
char vexs[MAXVEX] ; /* 顶点向量 */
int adj[MAXVEX][MAXVEX];
}MGraph ; /* 图的结构定义 */

//邻接链表结构体
typedef struct ANode //弧的结点结构类型
{ int adjvex; //该弧的终点位置
int info; //该弧的相关信息,这里用于存放权值
struct ANode *nextarc; //指向下一条弧的指针
} ArcNode;

typedef struct Vnode //邻接表头结点的类型
{
char data; //顶点信息
ArcNode *firstarc; //指向第一条弧
} VNode;

typedef struct
{
VNode AdjList[MAXVEX];
int vexnum,arcnum; //图中顶点数n和边数e
} ALGraph; //图的邻接表类型

⒊ 所设计的函数
对于每个主要函数必须给出所采用的算法思想和程序框图；
邻接矩阵和邻接链表初始化函数
MGraph *Init_MGraph()
/* 图的初始化 */
{
MGraph *G;
G=(MGraph *)malloc(sizeof(MGraph)) ;
G->vexnum=0 ; G->arcnum=0 ; /* 初始化顶点数、边数 */
return(G) ;
}
ALGraph *Init_ALGraph()
/* 图的初始化 */
{
ALGraph *G;
G=(ALGraph *)malloc(sizeof(ALGraph)) ;
G->vexnum=0 ;
G->arcnum=0; /* 初始化顶点数 */
return(G) ;
}
图中顶点定位的函数，判断顶点是否重复输入了
int LocateVex(MGraph *G, char vp)
/* 图中顶点的定位，若图中有顶点vp，返回其在顶点数组的下标值 */
{
int k ;
for (k=0; k<=G->vexnum; k++)
if (G->vexs[k]==vp) return(k) ;
开始
k=0
返回-1
k<=顶点总数？
G->vexs[k]==vp？
返回k
结束
k++
return(-1) ; /* 图中无此顶点 */
}

N
N Y
Y

往图中增加顶点的函数
void AddVertex(MGraph *G, char vp)
/* 往图的顶点数组中增加顶点 */
{
int k, j ;
if (G->vexnum>=MAXVEX)
printf("图中顶点数已达到最多 !\n");
else
{
if (LocateVex(G, vp)==-1)
{
k=G->vexnum ; G->vexs[G->vexnum++]=vp ;
for (j=0 ; j<G->vexnum ; j++)
{
G->adj[j][k]=INFINITY ;
G->adj[k][j]=INFINITY ;
/* 是带权的有向图或无向图 */
开始
把这个点跟其他所有点建立关系，为INFINITY，表示不存在连通关系
新增加一个顶点
给k赋值=顶点总数
调用函数LocateVex，判断顶点是否有重复
判断顶点数目是否已经超过最大值
结束
}
}
}
}
N
Y

N Y

往图的邻接矩阵中添加边(弧)
void AddArc(MGraph *G , ArcType *arc)
/* 往图的邻接矩阵中添加边(弧) */
{
int k=0, j=0;
k=LocateVex(G, arc->vex1) ;
j=LocateVex(G, arc->vex2) ;
if (k==-1||j==-1)
printf("边或弧的顶点不存在，错误 !\n") ;
else
{
G->arcnum++ ;
G->adj[k][j]=arc->ArcVal ;
G->adj[j][k]=arc->ArcVal ;
/* 是无向图或带权的无向图,需对称赋值 */
开始
给两个顶点之间加上权值
边数加一
判断弧所依托的两个顶点是否存在
结束
}

}

输出图的顶点矩阵和邻接矩阵
void output_graphic(MGraph *G)
/* 输出图的顶点矩阵和邻接矩阵 */
{
int k, j ;
printf("图的顶点如下：\n") ;
for (k=0; k<G->vexnum; k++)
printf("%4c",G->vexs[k]) ;
printf("\n\n") ;
printf("图的邻接矩阵如下：\n") ;
for (k=0; k<G->vexnum; k++)
{
for (j=0; j<G->vexnum; j++)
输出**
判断两个顶点之间是否存在连通
j++
输出权值
开始
结束
j=0
k=0
k++
k=0
输出第k个顶点
判断j是否小于顶点总数

判断k是否小于顶点总数

判断k是否小于顶点总数
k++
if (G->adj[k][j]==INFINITY)
printf("%4s","**") ;
else
printf("%4d",G->adj[k][j]) ;
printf("\n\n") ;
}
}

Y N

Y N

Y

以邻接矩阵作为图的存储结构建立图
MGraph *create_graph()
/* 以邻接矩阵作为图的存储结构建立图 */
{
char inchar[100], enchar[100],fvex,lvex ;
int count=0;
int weight ;
MGraph *G;
ArcType *arc ;
printf("首先进行图的初始化!!\n\n") ;
G=(MGraph *)malloc(sizeof(MGraph)) ;
G=Init_MGraph() ;
arc=(ArcType *)malloc(sizeof(ArcType)) ;
printf("\n请以(顶点,顶点,权值)的形式输入图的边(或弧)，第一个顶点是?表示结束：\n") ;
while(1)
{
scanf("%s",inchar) ;fvex=inchar[0] ; /* 输入第一个顶点，?结束 */
if (fvex=='?') break ;
else
{
AddVertex(G, fvex) ;
scanf("%s",enchar) ;lvex=enchar[0] ;AddVertex(G, lvex) ;
scanf("%d",&weight) ; /* 输入第二个顶点和权值 */
arc->vex1=fvex ; arc->vex2=lvex ;
arc->ArcVal=weight ; AddArc(G, arc) ;
printf("\n请继续输入下一条边(或弧)!!\n") ;
}
}
return(G) ;
}
将邻接矩阵g转换成邻接表G
ALGraph *MGraphToALGraph(MGraph *g,ALGraph *G)
{
int i,j,n=g->vexnum; //n为顶点数
ArcNode *p;
G=(ALGraph *)malloc(sizeof(ALGraph));
G->arcnum = g->arcnum;
G->vexnum = g->vexnum;
for(i=0;i<G->vexnum;i++)
G->AdjList[i].firstarc = NULL;
for (i=0;i<n;i++) //检查邻接矩阵中每个元素
{
for (j=n-1;j>=0;j--)
if (g->adj[i][j]!=INFINITY) //邻接矩阵的当前元素不为
{
p=(ArcNode *)malloc(sizeof(ArcNode)); //创建一个结点*p
G->AdjList[j].data=g->vexs[j];
p->adjvex = g->vexs[j];
p->info=g->adj[i][j];
p->nextarc=G->AdjList[i].firstarc; //将*p链到链表后
G->AdjList[i].firstarc=p;
}
}
return G;
}

j--
给邻接点赋上邻接矩阵对应的顶点
i++
判断两顶点之间是否有连通
头结点数组指针指向相连通的邻接点
给邻接边赋上权值
结束
开始
返回邻接表G
把邻接矩阵的顶点总数赋值给邻接链表的顶点总数

把邻接矩阵的边总数赋值给邻接链表的边总数
把顶点总数赋值给n
j=n-1
i=0
用循环结构把每一个顶点的头指针初始化
j>=0?
i<n?

邻接链表的输出
void output_graphic_c(MGraph *g,ALGraph *G)
{
int i;
ArcNode *p;
for (i=0;i<g->vexnum;i++)
{
printf("%c",G->AdjList[i].data) ;
p=G->AdjList[i].firstarc;
while(p!=NULL)
{
printf("%s","->") ;
printf("(%c,%d)",p->adjvex,p->info) ;
p=p->nextarc ;
}
printf("\n\n");
}
}
相邻景点查询并输出
void output_Find_ALGraph(ALGraph *G)
{ /* 相邻景点查询并输出 */
int j;
ArcNode *p;
printf("请输入你要查询的景点(下标值):\n");
scanf("%d",&j);
p=G->AdjList[j].firstarc;
while(p)
{
printf("景点%c到景点%c的距离是%d (该两个景点之间有直接的道路相通)\n",G->AdjList[j].data,p->adjvex,p->info);
p=p->nextarc;
开始
结束
输出两个顶点之间的距离
把该景点在数组中的邻接边的头指针赋值给p
输入景点对应的下标值
判断邻接边单链表的结点指针是否为空
p指向下一个结点指针
}
printf("\n\n");
}

景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。
void Dijkstra_One(ALGraph *G, MGraph *g,int v0,int distance[], int pre[])
{ // 带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标pre
int w;
int S[30],i,j,k,p,min;
printf("你所要开始查询的景点是:%c\n",G->AdjList[v0].data);
for(i=0;i<g->vexnum;i++)
{
distance[i]=g->adj[v0][i];
S[i]=0;
if(distance[i]< INFINITY)
pre[i]=v0;
else
pre[i]=-1;
}
S[v0]=1; //顶点v0已加入到集合S中
for(i=0;i<g->vexnum;i++)
{
min=INFINITY;
for(j=0;j<g->vexnum;j++)
{
if(!S[j]&&distance[j]<min)
{
min=distance[j];
k=j;
}
}
S[k]=1; ///将找到的顶点加入到集合S中
for(w=0;w<g->vexnum;w++) // /修改集合T中顶点的距离值
if(!S[w]&&distance[w]>distance[k]+g->adj[k][w])
{
distance[w]=distance[k]+g->adj[k][w];
pre[w]=k;
}
}
printf("查询结果:\n");
for(j=0;j<g->vexnum;j++) //输出结果
if(pre[j]!=-1)
{
printf("从景点%c到景点%c",G->AdjList[v0].data,g->vexs[j]);
p=pre[j];
printf("的最短距离是: %d",distance[j]);
printf(" 途中经过的景点有:");
while(p!=-1)
{
printf(" %c",g->vexs[p]);
p=pre[p];
}
printf("\n");
}
else if(j!=v0)
printf("\n%c到%c : no path",g->vexs[j],g->vexs[v0]);
开始
用循环结构实现各数组的初始化
输入要查询景点的下标值
定义最短路径的终点集数组S
置S={v0}
求出当前最小的dist[j]值
w=0
将第j个顶点放入S中
}

结束
从v0到w的最短路径中，
w的前一个顶点是k
判断w是否小于顶点总数
从V0出发中间只经过集合S中的顶点而到达Vw的所有路径中长度最小的路径长度distance[w]是否大于distance[w]+边adj[k][w]的值
从V0出发到w的最短距离distance[w]= 从V0出发到w的最短距离distance[k]+边adj[k][w]的权值
w++
查询结果输出

N
Y

景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。
void Dijkstra_Two(ALGraph *G, MGraph *g,int v0,int distance[], int pre[]){
// 带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标pre

int w;
int S[30],i,j,k,p,min,d;
printf("你所要开始查询的开始景点是:%c\n\n",G->AdjList[v0].data);
for(i=0;i<g->vexnum;i++)
{
distance[i]=g->adj[v0][i];
S[i]=0;
if(distance[i]< INFINITY)
pre[i]=v0;
else
pre[i]=-1;
}
S[v0]=1; //顶点v0已加入到集合S中
for(i=0;i<g->vexnum;i++)
{
min=INFINITY;
for(j=0;j<g->vexnum;j++)
{
if(!S[j]&&distance[j]<min)
{
min=distance[j];
k=j;
}
}
S[k]=1; ///将找到的顶点加入到集合S中
for(w=0;w<g->vexnum;w++) // /修改集合T中顶点的距离值
if(!S[w]&&distance[w]>distance[k]+g->adj[k][w])
{
distance[w]=distance[k]+g->adj[k][w];
pre[w]=k;
}
}

printf("输入你要查询的另外一个景点(下标值):");
scanf("%d",&d);
printf("你要查询的另外一个景点是:%c\n",g->vexs[d]);
printf("\n查询结果:\n"); //输出结果
if(pre[d]!=-1)
{
printf("从景点%c到景点%c",G->AdjList[v0].data,g->vexs[d]);
p=pre[d];
printf("的最短距离是: %d",distance[d]);
printf(" 途中经过的景点有:");
while(p!=-1)
{
printf(" %c",g->vexs[p]);
p=pre[p];
}
开始
用循环结构实现各数组的初始化
输入要查询景点的下标值
定义最短路径的终点集数组S
置S={v0}
printf("\n");
}
}

求出当前最小的dist[j]值
w=0
将第j个顶点放入S中
结束
从v0到w的最短路径中，
w的前一个顶点是k
判断w是否小于顶点总数
从V0出发中间只经过集合S中的顶点而到达Vw的所有路径中长度最小的路径长度distance[w]是否大于distance[w]+边adj[k][w]的值
从V0出发到w的最短距离distance[w]= 从V0出发到w的最短距离distance[k]+边adj[k][w]的权值
w++
输入要查询另外一景点的下标值
查询结果输出

最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。
void dfs_path(ALGraph *g,int src,int cur,int vis[],GPath *cur_path,GPath * min_path)
{

if(vis[src])
{
if(cur_path->count==g->vexnum)
{
if(cur_path->value<min_path->value)
{
memcpy(min_path,cur_path,sizeof(GPath));/*由cur_path所指内存区域复制sizeof(GPath)个字节到min_path所指内存区域*/
return;
}
}
return;
}

ArcNode * node =g->AdjList[cur].firstarc;
for(;node!=NULL; node=node->nextarc)/*起始条件为node =g->AdjList[cur].firstarc*/
{
char adj=node->adjvex;
int index=LocateVex(g,adj);
if(vis[index]==0)
{
cur_path->vertex[cur_path->count++]=index;
cur_path->value+=node->info;
vis[index]=1;
dfs_path(g,src,index,vis,cur_path,min_path);
cur_path->count--;
cur_path->value-=node->info;
结束
判断vp是否存在
弧头顶点数据元素=LocateVexx(g,adj)
最小生成树权值加
递归
开始
把顶点的值vp复制给adj
把邻接表数组的头指针赋值给node
用循环结构复制cur_pat的内存到min_path
判断邻接表指针是否为空
node指向下一个结点
vis[index]=0;
}
}
}

Y N

N Y

void best_path(ALGraph *g,int src)
{
int vis[MAXVEX];
memset(vis,0,sizeof(vis));
GPath cur_path,min_path;
memset(&cur_path,0,sizeof(GPath));/*将cur_path所指向的某一块内存中的每个字节的内容全部设置为0指定的ASCII值,
块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作, 其返回值为指向cur_path的指针。*/
memset(&min_path,0,sizeof(GPath));/*将min_path所指向的某一块内存中的每个字节的内容全部设置为0指定的ASCII值,
块的大小由第三个参数指定,这个函数通常为新申请的内存做初始化工作, 其返回值为指向min_path的指针。*/
min_path.value=INFINITY;
dfs_path(g,src,src,vis,&cur_path,&min_path);
if(min_path.value!=INFINITY)
{
int i=0;
printf("\n最佳旅游路线景点下标值是:\n");
for(i=0; i<min_path.count; i++)
{
printf("%d ->",min_path.vertex[i]);
}
printf("\n");
printf("\n最佳旅游路线景点是:\n");
for(i=0; i<min_path.count; i++)
{

printf("%c-> ",g->AdjList[min_path.vertex[i]].data);
}
printf("\n");
}else
{
printf("建立的图中没有最佳路径\n");
}
}

主函数
void main()
{
int n, opse,v0,i;
int distance[MAXVEX],pre[2*MAXVEX],path[MAXVEX];
ALGraph *G;
MGraph *M;
do
{ printf("\n\n请选择对图的操作要求:\n\n");
for (n=0; n<=30; n++)
printf("* ");
printf("\n* ");
printf("1----建立图的邻接矩阵 ");
printf(" 2----图的邻接矩阵的输出 ");
printf(" *\n");
printf("\n* ");
printf("3----图的邻接链表的输出 ");
printf(" 4----相邻景点查询 ");
printf(" *\n");
printf("\n* ");
printf("5---- 从某点出发到另外所有点最短简单路径及距离 ");
printf(" *\n");
printf("\n* ");
printf("6---- 两个景点之间的最短距离(下标值) ");
printf(" *\n");
printf("\n* ");
printf("7---- 最佳路径 ");
printf("8---- 退出 ");
printf(" *\n");
for (n=0; n<=30; n++)
printf("* ");
printf("\n\n");

do
{ scanf("%d",&opse);
}while (opse<1||opse>8);

switch (opse)
{
case 1:
{ M=(MGraph *)malloc(sizeof(MGraph)) ;
M=create_graph() ;
printf("\n\n");
break ;
}
case 2:
{ printf("\n您所建立的图是：\n") ;
output_graphic(M) ;
break ;
}
case 3:
{ printf(" 图G的邻接矩阵转换成邻接表:\n");

G = MGraphToALGraph(M,G);
output_graphic_c(M,G);
break ;
}
case 4:
{
printf("\n相邻景点是：\n") ;
output_Find_ALGraph(G);
break ;
}
case 5:
{
printf("\n最短简单路径及距离是：\n") ;
scanf(" %d",&v0);
Dijkstra _One(G,M,v0,distance,pre);
break ;
}
case 6:
{
printf("两个景点之间的最短距离(下标值):");
scanf(" %d",&v0);
Dijkstra _Two(G,M,v0,distance,pre);
break;
}
case 7:
{
printf("最佳路径(下标值):");
Dijkstra(M,0,distance,path);

printf("从结点%c到其他各结点的最短距离为:\n",M->vexs[0]);
for(i=1;i<M->vexnum;i++)
printf("到结点%c的最短距离为%d:\n",M->vexs[i],distance[i]);
printf("从结点%c到其他各结点最短路径的前一结点为:\n",M->vexs[0]);
for(i=1;i<M->vexnum;i++)
if(path[i]!=-1)
printf("到结点%c的前一结点为%c:\n",M->vexs[i],M->vexs[path[i]]);

break;
}

}
} while(opse!=8);
}

开始
请选择对图的操作要求
n<=30？
菜单
输出*
n=0
n++
调用create_graph()，建立图
break
break
break
调用MGraphToALGraph()，把邻接矩阵转换为邻接链表
调用output_graphic()邻接矩阵的输出
调用output_graphic_c()邻接矩阵的输出

………
………

结束
调用output_Find_ALGraph()输出相邻景点
break
break
调用dijkshort_Two（）函数，查找两个景点间的最短距离
调用dijkshort_One（）函数，查找最短简单路径和距离
break
break
调用Dijkstra（）函数，查找最佳路径

⒋ 每个题目都必须有运行时的输入数据（随机产生的数据要求输出显示），运行的输出结果。

建立邻接矩阵：

邻接矩阵输出：

邻接链表输出：

相邻景点查询：

从某点出发到另外所有点最短简单路径及距离：

两个景点之间的最短距离：

最佳路径：

⒌ 每个函数中应给出尽可能详细的中文注释。（源程序-全）

#