旅游区导游图_景区导游图

旅游区导游图由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“景区导游图”。

旅游区导游图

题目内容： 问题描述：

设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m

以(Vi ,Vj ,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi和Vj表示两个不同的旅游景点,d表示这两个景点之间的道路距离；该旅游景点图采用邻接链表存储结构。实现要求：

⑴ 旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。⑵ 相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。

⑶ 景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。

⑷ 景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。

⑸ 最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。⑹ 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。

代

码

如

下： ································

#include“stdio.h” #include“malloc.h” #include “string.h” #define INFINITY

32767

/* 图的最大权值,32767是整数表示的最大值*/ #define MAX_VEX 30

/* 最大顶点数目

*/

#define MAX_VALUE 999999999

typedef int InfoType;typedef char VexType;typedef enum{DG=1, AG=2, WDG=3,WAG=4}GraphKind;/*枚举常量定义旅游景点对应的图类型*/

typedef struct Path { int vertex[MAX_VEX];int value;int count;}GPath;

typedef struct MGraph { char vexs[MAX_VEX];

/*存放图的邻接矩阵的的顶点,顶点向量

*/ int arcs[MAX_VEX][MAX_VEX];

/*存放图的邻接矩阵的边

*/ int vexnum,arcnum;

/*图的当前顶点数和弧数

*/ }MGraph;

/*图的邻接链表转换为矩阵后,图的结构定义 */

/*图的邻接矩阵存储结构中结点结构体的定义*/ //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// typedef struct Linknode { char adjvex;

/*邻接点在头结点数组中的位置（邻接边的弧头顶点序号）*/ InfoType info;

/*与边或弧相关的信息, 如权值

*/ struct Linknode *nextarc;

/*指向下一个表结点

*/ }LinkNode;

/*邻接边单链表的结点结构体

*/ ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// typedef struct VexNode { char data;

/*数据域存储顶点信息

*/ int indegree;

/*顶点的度, 有向图是入度或出度或没有

*/ LinkNode *firstarc;

/*链域指向第一个表结点（邻接边头指针）*/ }VexNode;

/*顶点结点类型定义

*/ //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// typedef struct {

GraphKind kind;

/*图的种类标志

*/

int vexnum;

/*顶点个数

*/ VexNode AdjList[MAX_VEX];

/*邻接表数组

*/ }ALGraph;

/*图的结构定义

*/

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// typedef struct { VexType vex1, vex2;

/*弧或边所依附的两个顶点

*/ InfoType info;

/*与边或弧相关的信息, 如权值

*/ }ArcType;

/*弧或边的结构定义

*/ //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void Init_Graph(ALGraph * G)

/*图的初始化

*/ { do {

printf(“请确认旅游景点的类型(1：无向图。2：有向图。3：带权有向图。4：带权无向图):n”);

} scanf(“%d”, &G->kind);if(G->kind==4)printf(“旅游区导游图的类型:带权无向图n”);else {

} printf(“

●您选择的图的类型不对●n”);

while(G->kind!=4);G->vexnum=0;

/* 初始化顶点个数为0

*/ } ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// int LocateVex(ALGraph *G, VexType vp)

/*图的顶点定位（图的顶点定位实际上是确定一个顶点在AdjList数组中的某个元素的data域内容。）*/ {

int k;for(k=0;kvexnum;k++)if(G->AdjList[k].data==vp)return(k);

/*如果存在此顶点返回顶点数组下标值

return(-1);

/*如果没有则返回-1(图中无此顶点)

*/

*/ } //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// int AddVertex(ALGraph *G, char vp)

/*向图中增加顶点（向图中增加一个顶点的操作，在AdjList数组的末尾增加一个数据元素。）*/ { int k;if(G->vexnum>=MAX_VEX){ } if(LocateVex(G,vp)!=-1){ printf(“所要添加的顶点已存在!n”);printf(“图中顶点数已达到最多!n”);

return(-1);return(-1);} G->AdjList[G->vexnum].data=vp;G->AdjList[G->vexnum].indegree=0;G->AdjList[G->vexnum].firstarc=NULL;k=++G->vexnum;return k;} /////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// int AddArc(ALGraph *G, ArcType *arc)/*向图中增加一条边(弧)（根据给定的弧或边所依附的顶点，修改单链表：无向图修改两个单链表；）*/ {

int k,j;LinkNode *p,*q;k=LocateVex(G,arc->vex1);j=LocateVex(G,arc->vex2);if(k==-1||j==-1)

/*先判断是否两个顶点重复或者是否存在这两个顶点*/

{ printf(“该两个景点为一点或两景点都不存在,错误!n”);

return(-1);} p=(LinkNode *)malloc(sizeof(LinkNode));p->adjvex=arc->vex1;p->info=arc->info;p->nextarc=NULL;

/* 边的起始表结点赋值

*/ q=(LinkNode *)malloc(sizeof(LinkNode));q->adjvex=arc->vex2;q->info=arc->info;

q->nextarc=NULL;

/* 边的末尾表结点赋值

*/ q->nextarc=G->AdjList[k].firstarc;

G->AdjList[k].firstarc=q;p->nextarc=G->AdjList[j].firstarc;G->AdjList[j].firstarc=p;

/* 是无向图, 用头插入法插入到两个单链表

*/ return(1);

/*无向图，把p和q互相连接到彼此的边点上

*/ } ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ALGraph *Create_ALGraph()/*采用邻接链表作为图的存储结构建立带权有向图*/ {

char stack1[MAX_VEX],stack2[MAX_VEX],vex,k1,k2;int weight;ALGraph *G;ArcType *p;printf(“首先对旅游区导游图进行初始化:nn”);G=(ALGraph *)malloc(sizeof(ALGraph));//申请动态结点空间

Init_Graph(G);printf(“n请输入旅游区导游图的各个旅游景点代码(以字符的形式出入),当输入0时作为结束标志n”);while(1){

scanf(“%s”,stack1);/*以字符串的形式输入存储旅游区景点,一次一个的存储输入的景点存到数组中之后又在图中插入该顶点，当输入0时结束*/

vex=stack1[0];

/*用字符串可以区别结束标识，用字符存到数组中不易设置结束标志*/

} if(vex=='0')break;else AddVertex(G,vex);p=(ArcType *)malloc(sizeof(ArcType));printf(“n 从键盘输入以(Vi ,Vj ,d)的形式建立该旅游区的旅游景点图,n 其中: Vi和Vj表示两个不同的旅游景点, d表示这两个景点之间的道路距离;n 该旅游景点图采用邻接链表存储结构(当输入第一个顶点是0时表示结束):n”);

while(1){

scanf(“%s”,stack1);k1=stack1[0];

if(k1=='0')

/* 输入第一个顶点,0结束

*/ break;

else {

scanf(“%s”,stack2);scanf(“%d”,&weight);

/* 输入第二个顶点和权值

*/ k2=stack2[0];p->vex1=k1;p->vex2=k2;p->info=weight;

AddArc(G,p);printf(“n请继续输入下一条道路！n”);} } return(G);} ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void output_ALGraph(ALGraph *G)

// 2:输出图的邻接链表

{

int j;LinkNode *p;

printf(“n旅游区导游图的邻接链表景点输出表示如下:n”);for(j=0;jvexnum;j++){

printf(“%c”,G->AdjList[j].data);

p=G->AdjList[j].firstarc;

while(p!=NULL)

//输出一个邻接链表的景点之后，继续输出他的其他邻接景点

} {

} printf(“-> ”);printf(“<%c,%d>”,p->adjvex,p->info);p=p->nextarc;printf(“nn”);} //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void output_Find_ALGraph(ALGraph *G)

// 4:相邻景点查询并输出

{

int j;LinkNode *p;

//定义邻接边单链表结点p printf(“请输入您要查询的景点(顶点数组下标值):n”);

//从输入的景点开始找和其相邻的景点并输出权值

scanf(“%d”,&j);

p=G->AdjList[j].firstarc;

//定义邻接边头指针 while(p!=NULL){ printf(“景点%c到景点%c的距离是%d(两景点之间有相连的道路)n”,G->AdjList[j].data,p->adjvex,p->info);//第j个景点和他下一个相邻的景点和权值

p=p->nextarc;

//指向下一个结点的地址，使全部与G->AdjList[j].data直接连通的顶点全部输出，NULL时截止 } printf(“nn”);} //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void ListToMat(ALGraph G, MGraph &g)

/*将邻接链表转换成邻接矩阵

*/ { int k,i,j;

LinkNode *p;for(i=0;i

/*g.arcs[i][j]赋初值INFINITY

for(j=0;j

g.arcs[i][j]=INFINITY;for(i=0;i

/*把链表的数组顶点保存到数组vexs[i]} for(i=0;i

p=G.AdjList[i].firstarc;while(p!=NULL)

{

k=LocateVex(&G,p->adjvex);

/*取和p相邻的顶点下标值用于邻接*/

中*/

矩阵的下标值

*/

g.arcs[i][k]=g.arcs[k][i]=p->info;/*把权值赋值给二维数组用于矩阵输出

*/

*/

} } p=p->nextarc;

/*指向下一个邻接表结点

} g.vexnum=G.vexnum;///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void display(ALGraph *G,MGraph g)

/*3:输出邻接矩阵

*/ { int i,j;ListToMat(*G, g);

/*将邻接链表转换成邻接矩阵

*/ printf(“

”);for(i=0;ivexnum;i++)printf(“%-8c”,G->AdjList[i].data);

/*输出矩阵横向顶点值

*/ printf(“n”);for(i=0;i

printf(“%c

”,G->AdjList[i].data);

/*输出矩阵竖向顶点值，每输出一行输出一次顶点*/

}

} for(j=0;j

if(g.arcs[i][j]==INFINITY)

printf(“∞

”);else printf(“%-8d”, g.arcs[i][j]);

/*每个权值占有8个字符，负号表示左端对齐

*/ } printf(“n”);//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void dijkshort_One(ALGraph F, MGraph G,int v0,int distance[], int path[])/* 带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标path*/ //带权图F从下标v0到其他顶点的最短距离diatance和最短路径下标path,path中存放了从输入的v0到其他各个顶点的最短路径的前一个顶点的下标 //基于狄克斯特拉函数的设计

{

int *S=(int *)malloc(sizeof(int)*G.vexnum);int minDis,i,j,u,p;

ListToMat(F, G);printf(“你所要开始查询的景点是:%cn”,F.AdjList[v0].data);for(i=0;i

distance[i]=G.arcs[v0][i];S[i]=0;if(distance[i]

path[i]=-1;} S[v0]=1;

//标记顶点v0已从集合T加入到集合S中（以v0为下标值的顶点）for(i=0;i

minDis=INFINITY;for(j=0;j

{

minDis=distance[j];

u=j;} } S[u]=1;

//标记顶点u已从集合T加入到集合S中（以u为下标值的顶点）

for(j=0;j

// /修改从v0到其他顶点的最短距离和最短路径

if(S[j]==0&&G.arcs[u][j]distance[u]+G.arcs[u][j]){ distance[j]=distance[u]+G.arcs[u][j];//顶点v0经顶点u到其他顶点的最短距 path[j]=u;离和最短路径

} }

//顶点v0到其他所有的顶点的最短距离已经保存在数组distance中 printf(“查询结果是:n”);for(j=0;j

if(path[j]!=-1){

printf(“从景点%c到景点%c”,F.AdjList[v0].data,G.vexs[j]);

p=path[j];

printf(“的最短距离是: %d”,distance[j]);//输出顶点v0到其他所有的顶点的最短printf(“ 途中经过的景点有:”);while(p!=-1){ printf(“ %c”,G.vexs[p]);

路径

}

p=path[p];} printf(“n”);

} else if(j!=v0)

printf(“n%c到%c : 没有通路!”,G.vexs[j],G.vexs[v0]);/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void dijkshort_Two(ALGraph F, MGraph G,int v0,int distance[], int path[])/*带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标path*/ {

int w;int S[30],i,j,k,p,min,d;ListToMat(F, G);printf(“你所要开始查询的开始景点是:%cnn”,F.AdjList[v0].data);for(i=0;i

{

distance[i]=G.arcs[v0][i];S[i]=0;if(distance[i]

//顶点v0已加入到集合S中 for(i=0;i

min=INFINITY;for(j=0;j

if(!S[j]&&distance[j]

{

} min=distance[j];k=j;} S[k]=1;

///将找到的顶点加入到集合S中 for(w=0;w

// /修改集合T中顶点的距离值

if(!S[w]&&distance[w]>distance[k]+G.arcs[k][w]){ distance[w]=distance[k]+G.arcs[k][w];} path[w]=k;}

printf(“输入你要查询的另外一个景点(下标值):”);scanf(“%d”,&d);printf(“你要查询的另外一个景点是:%cn”,G.vexs[d]);printf(“n查询结果:n”);//输出结果

if(path[d]!=-1){

printf(“从景点%c到景点%c”,F.AdjList[v0].data,G.vexs[d]);

p=path[d];printf(“的最短距离是: %d”,distance[d]);printf(“ 途中经过的景点有:”);while(p!=-1){ printf(“ %c”,G.vexs[p]);p=path[p];} printf(“n”);} } ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void dfs_path(ALGraph *g,int src,int cur,int vis[],GPath *cur_path,GPath * min_path){

LinkNode * 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;vis[index]=0;if(vis[src]){

} if(cur_path->count==g->vexnum){

if(cur_path->valuevalue){ memcpy(min_path,cur_path,sizeof(GPath));/*由cur_path所指内存区域复制return;sizeof(GPath)个字节到min_path所指内存区域*/ } } return;} //////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// void best_path(ALGraph *g,int src){ int vis[MAX_VEX];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=MAX_VALUE;dfs_path(g,src,src,vis,&cur_path,&min_path);if(min_path.value!=MAX_VALUE){

int i=0;printf(“n最佳旅游路线景点下标值是:n”);for(i=0;i

printf(“%d->”,min_path.vertex[i]);} printf(“n”);printf(“n最佳旅游路线景点是:n”);

for(i=0;i

{

printf(“%c-> ”,g->AdjList[min_path.vertex[i]].data);

} } printf(“n”);}else { printf(“建立的图中没有最佳路径n”);}

//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// /*------------菜单------------*/ void main(){

int n,v0;MGraph g;int distance[MAX_VEX],path[2*MAX_VEX];ALGraph *G;

printf(“

============================n”);

printf(“

!欢迎使用旅游区导游系统

!n”);printf(“

============================n”);do { printf(“n请选择对该旅游区导游图的操作→nn”);

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(“

┗━━━━━━━━━━━━━━━━━━━━━┛n”);do { } scanf(“%d”,&n);while(n9);switch(n){ case 1:

{

G=(ALGraph *)malloc(sizeof(ALGraph));/*动态申请图G的内存空间*/ G=Create_ALGraph();printf(“nn”);break;

} case 2:

{

} {

printf(“n旅游导游图的邻接链表表示如下所示:n”);output_ALGraph(G);printf(“nn”);break;case 3:

printf(“n旅游区导游图的邻接矩阵表示如下所示:n”);printf(“n∞表示两景点之间不存在连通的路线n”);printf(“n数值表示两景点之间的路线长度n”);display(G,g);printf(“nn”);break;

}

case 4:

{

}

case 5:

{

}

case 6:

{

}

case 7:

{

}

} } while(n!=8);} output_Find_ALGraph(G);printf(“nn”);break;printf(“输入你要查询的景点(下标值):”);scanf(“ %d”,&v0);dijkshort_One(*G,g,v0,distance,path);break;printf(“输入你要查询的开始景点(下标值):”);scanf(“ %d”,&v0);dijkshort_Two(*G,g,v0,distance,path);break;printf(“输入你要查询的开始景点(下标值):”);scanf(“%d”,&v0);printf(“景点是%c ”,G->AdjList[v0].data);best_path(G,v0);break;