Question

急求求大仙帮忙！C语言数据结构课程设计，关于旅游图。

问题描述：
设某个旅游区共有n个旅游景点（n≥10）,每个旅游景点都和相邻的m个旅游景点（m≥2，m<n）有直接的道路（有对应的距离）相通，请设计一个简易的旅游区导游系统。
以(Vi,Vj ,d)的形式从键盘输入建立该旅游区的旅游景点图，其中：Vi和Vj表示两个不同的旅游景点，d表示这两个景点之间的道路距离；该旅游景点图采用邻接矩阵存储结构。
实现要求：
⑴ 旅游景点图的输出：分别以邻接矩阵、邻接链表的方式输出该旅游景点图。
⑵ 相邻景点查询：假设对于每个景点，设置有简易的信息查询，要求能给出与该景点相邻的所有景点(有直接的道路相通)及对应的距离。
⑶ 景点路线查询：假设对于每个景点，设置有景点路线查询，要求能给出从该景点出发到任一其它景点的最短简单路径及距离。
⑷ 景点路线综合查询：对于该旅游区的任意两个景点，找出它们之间的最短简单路径及距离。
⑸ 最佳旅游路线确定：假设该旅游区的入口也是出口，请确定一条最佳的旅游线路，该线路必须经过所有的旅游景点（有些景点可以重复经过）且走的路最短。⑹ 设计一个菜单，上述操作要求都作为菜单中的主要菜单项。

Answer 1

#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
{
intvertex[MAX_VEX];
intvalue;
intcount;
}GPath;

typedef struct MGraph
{
charvexs[MAX_VEX]; /*存放图的邻接矩阵的的顶点,顶点向量 */
intarcs[MAX_VEX][MAX_VEX]; /*存放图的邻接矩阵的边 */
intvexnum,arcnum; /*图的当前顶点数和弧数 */
}MGraph; /*图的邻接链表转换为矩阵后,图的结构定义 */
/*图的邻接矩阵存储结构中结点结构体的定义*/
typedef struct Linknode
{
charadjvex; /*邻接点在头结点数组中的位置（邻接边的弧头顶点序号）*/
InfoTypeinfo; /*与边或弧相关的信息, 如权值 */
structLinknode *nextarc; /*指向下一个表结点 */
}LinkNode; /*邻接边单链表的结点结构体 */
typedef struct VexNode
{
char data; /*数据域存储顶点信息 */
int indegree ; /*顶点的度, 有向图是入度或出度或没有 */
LinkNode *firstarc; /*链域指向第一个表结点（邻接边头指针）*/
}VexNode; /*顶点结点类型定义 */
typedef struct
{
GraphKind kind; /*图的种类标志 */
intvexnum; /*顶点个数 */
VexNodeAdjList[MAX_VEX]; /*邻接表数组 */
}ALGraph; /*图的结构定义 */
typedef struct
{
VexType vex1, vex2; /*弧或边所依附的两个顶点 */
InfoTypeinfo; /*与边或弧相关的信息, 如权值 */
}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;k<G->vexnum;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)
{
printf("图中顶点数已达到最多!\n");
return(-1);
}
if(LocateVex(G,vp)!=-1)
{
printf("所要添加的顶点已存在!\n");
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()/*采用邻接链表作为图的存储结构建立带权有向图*/
{
charstack1[MAX_VEX],stack2[MAX_VEX],vex,k1,k2;
intweight;
ALGraph*G;
ArcType*p;
printf("首先对旅游区导游图进行初始化:\n\n");
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;j<G->vexnum;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("\n\n");
}}
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("\n\n");
}
void ListToMat(ALGraph G, MGraph&g) /*将邻接链表转换成邻接矩阵 */
{
intk,i,j;
LinkNode*p;
for
(i=0;i<G.vexnum;i++)
/*g.arcs[i][j]赋初值INFINITY */
for(j=0;j<G.vexnum;j++)
g.arcs[i][j]=INFINITY;
for(i=0;i<G.vexnum;i++)
{
g.vexs[i]=G.AdjList[i].data; /*把链表的数组顶点保存到数组vexs[i]中*/
}
for(i=0;i<G.vexnum;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:输出邻接矩阵 */
{
inti,j;
ListToMat(*G,g); /*将邻接链表转换成邻接矩阵 */
printf(" ");
for(i=0;i<G->vexnum;i++)
printf("%-8c",G->AdjList[i].data);/*输出矩阵横向顶点值 */
printf("\n");
for(i=0;i<g.vexnum;i++)
{
printf("%c ",G->AdjList[i].data ); /*输出矩阵竖向顶点值，每输出一行输出一次顶点*/
for(j=0;j<g.vexnum ;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,intv0,int distance[], int path[])/* 带权图G从顶点v0到其他定点的最短距离distance和最短路径前驱结点的下标path*/
//带权图F从下标v0到其他顶点的最短距离diatance和最短路径下标path,path中存放了从输入的v0到其他各个顶点的最短路径的前一个顶点的下标
//基于狄克斯特拉函数的设计
{

int*S=(int *)malloc(sizeof(int)*G.vexnum);
intminDis,i,j,u,p;
ListToMat(F,G);
printf("你所要开始查询的景点是:%c\n",F.AdjList[v0].data);
for(i=0;i<G.vexnum;i++)//初始化
{
distance[i]=G.arcs[v0][i];
S[i]=0;
if(distance[i]<INFINITY)
path[i]=v0;
else
path[i]=-1;
}
S[v0]=1; //标记顶点v0已从集合T加入到集合S中（以v0为下标值的顶点）
for(i=0;i<G.vexnum;i++)
{
minDis=INFINITY ;
for(j=0;j<G.vexnum;j++)
{
if(S[j]==0&&distance[j]<minDis)
{
minDis=distance[j];
u=j;
}
}
S[u]=1; //标记顶点u已从集合T加入到集合S中（以u为下标值的顶点）
for(j=0;j<G.vexnum;j++) // /修改从v0到其他顶点的最短距离和最短路径
if(S[j]==0&&G.arcs[u][j]<INFINITY&&distance[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<G.vexnum;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");
}
elseif(j!=v0)
printf("\n%c到%c : 没有通路!",G.vexs[j],G.vexs[v0]);}

Answer 2

你这个应该是图论编程的大作业吧
(1) 图的邻接矩阵和邻接表表示, easy

(2) 直接从图的邻接表表示就可以得结果，easy
(3) Dijkstra算法，求最短路径，不难。

(4) Floyd算法，求任意2点间最短路径，中等难度。

(5) 这个属于旅行商问题(TSP)，非常难的问题，百度一下，有很多专门的算法。

(6) 设计菜单，不会

追问

能求完整代码吗？

Answer 3

ggh那

Answer 4

留下邮箱...

追问

764953546@qq.com。求帮忙，谢谢！

追答

已发送 ，请查收