您所在位置：主题：[原创]求救~！！新手学习数据结构中的公园导游图问题，急。。。
ghostbuster
[专家分：0] 发布于 2007-12-25 16:21:00
[size=3] 这学期没有好好学习数据结构， 导致到学期的课程设计很是头疼，经过几天乱撞，现在已基本上把程序做到如下样子，但是其中的那个两个地方之间最短路径问题实在是不知道怎么解决，希望在这可以碰到热心的大侠给指点一二，帮我度过此劫，先谢谢了~
上面附上所用到的TXT文件，希望大侠给我一并解决，谨在新的一年即将到来之时致以崇高的敬意~~[[/size]size=5][size=3][/size][size=1][/size][size=6][/size][size=5][/size][size=4][/size][size=3]
[size=2]#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "conio.h"
#define OK 1
#define FLASE 0
#define TRUE 1
#define ERROR 0
#define MAXVTXNUM 20 /*图中顶点的最大值*/
#define INFINITY 999
/*顶点，边和图的类型定义*/
typedef struct{
char name[20]; /*该顶点代表的景点的名称*/
char info[50]; /*景点的信息*/
}VertexType; /*顶点类型*/
typedef struct{
int length; /*边的权值，表示路径长度*/
int ivex,jvex; /*边的两端顶点的位置*/
}EdgeType; /*边的类型*/
typedef struct EdgeNode{
EdgeType elem;
struct EdgeNode *ilink,*jlink;
}EdgeNode,*EdgePtr; /*边的结点类型，指向边的指针*/
typedef struct{
VertexType data;
EdgePtr firstEdge; /*指向第一条依附该顶点的边的指针*/
}VNode; /*顶点类型*/
typedef struct{
VNode Adjmulist[MAXVTXNUM]; /*邻接多重表*/
int vexNum,edgeNum; /*图中的顶点数和边数*/
}GraphType; /*图类型*/
/*图的基本操作*/
void InitGraph(GraphType *g); /*初始化邻接多重表，表示一个空图*/
void GetVex(GraphType *g,int i,VertexType *v); /*以v返回邻接多重表中序号为i的顶点*/
EdgePtr FirstEdge(GraphType *g,int vi); /*返回图g中指向依附于顶点vi的第一条边的指针*/
void NextEdge(GraphType *g,int vi,EdgePtr p,int *vj,EdgePtr q); /*以vj返回图g中依附于顶点vi的一条边的另一端点，以q返回图中依附于顶点vi且相对于指针p所指的边的下一条边*/
void InsertVex(GraphType *g,VertexType v,int i); /*在图g的邻接多重表中添加一个顶点v*/
void InsertEdge(GraphType *g,EdgeType e); /*在图g的邻接多重表中添加一条边e*/
void InitGraph(GraphType *g) /*初始化邻接多重表，表示一个空图*/
{
g->vexNum=g->edgeNum=0;
}
void GetVex(GraphType *g,int i,VertexType *v) /*以v返回邻接多重表中序号为i的顶点*/
{
*v=g->Adjmulist[i].data;
}
EdgePtr FirstEdge(GraphType *g,int vi) /*返回图g中指向依附于顶点vi的第一条边的指针*/
{
EdgePtr p;
p=g->Adjmulist[vi].firstEdge;
return p;
}
void NextEdge(GraphType *g,int vi,EdgePtr p,int *vj,EdgePtr q) /*以vj返回图g中依附于顶点vi的一条边的另一端点，以q返回图中依附于顶点vi且相对于指针p所指的边的下一条边*/
{
if(p->elem.ivex==vi)
{
q=p->ilink;
*vj=p->elem.jvex;
}
else
{
q=p->jlink;
*vj=p->elem.ivex;
}
}
void InsertVex(GraphType *g,VertexType v,int i) /*在图g的邻接多重表中添加一个顶点v*/
{
g->Adjmulist[i].data=v;
g->Adjmulist[i].firstEdge=NULL;
}
void InsertEdge(GraphType *g,EdgeType e) /*在图g的邻接多重表中添加一条边e*/
{
EdgePtr p;
p= (EdgePtr) malloc(sizeof(EdgeNode));
p->elem=e;
p->ilink=FirstEdge(g,e.ivex);
p->jlink=FirstEdge(g,e.jvex);
g->Adjmulist[e.ivex].firstEdge=g->Adjmulist[e.jvex].firstEdge=p;
}
/*路径的类型定义*/
typedef struct{
int vx,vy;
}Edge;
typedef struct{
Edge edges[MAXVTXNUM]; /*路径中边的序列*/
int len; /*路径中边的条数*/
}PathType;
typedef struct{
char vertices[MAXVTXNUM][MAXVTXNUM]; /*路径中景点的序列*/
int num;
}PType;
/*路径的相关基本操作*/
void InitPath(PathType *pa); /*初始化pa为一条空路径*/
void CopyPath(PathType *p1,PathType p2); /*复制路径p1=p2*/
void InsertPath(PathType *pa,int v,int w); /*在路径pa中插入一条边(v.w)*/
int PathLength(PathType *pa); /*返回路径pa的长度*/
void OutPath(GraphType *g,PathType pa,PType *vtxes); /*将路径转换为景点名称的序列*/
void ShortestPath(GraphType *g,int st,int nd,int *pathLength,PType *PathInfo); /*求图g中从顶点st到顶点nd的一条最短路径PathInfo及其长度pathLength*/
void PrintScenery(int x,GraphType *g);
void PrintPath(PType *spath,int *pathlen);
void InitPath(PathType *pa) /*初始化pa为一条空路径*/
{
pa->len=0;
}
void CopyPath(PathType *p1,PathType p2) /*复制路径p1=p2*/
{
int i;
for(i=0;i<p2.len;i++)
{
p1->edges[i].vx=p2.edges[i].vx;
p1->edges[i].vy=p2.edges[i].vy;
}
p1->len=p2.len;
}
void InsertPath(PathType *pa,int v,int w) /*在路径pa中插入一条边(v.w)*/
{
pa->edges[pa->len].vx=v;
pa->edges[pa->len].vy=w;
pa->len++;
}
int PathLength(PathType *pa) /*返回路径pa的长度*/
{
return pa->len;
}
void OutPath(GraphType *g,PathType pa,PType *vtxes) /*将路径转换为景点名称的序列*/
{
int i,m=0;
VertexType vtx;
for(i=0;i<pa.len;i++)
{
GetVex(g,pa.edges[i].vx,&vtx);
strcpy(vtxes->vertices[m++],vtx.name);
}
GetVex(g,pa.edges[pa.len].vy,&vtx);
strcpy(vtxes->vertices[m],vtx.name);
vtxes->num=m;
}
int InsetVex(int Vex[],int num,int w)
{
int i;
for(i=0;i<num;i++)
if(Vex[i]==w)
return TRUE;
return FLASE;
}
int minval(int dist[],int num,int Vex[])
{
int i,k;
int min=dist[0];
for(i=1;i<MAXVTXNUM;i++)
if(dist[i]<min&&!InsetVex(Vex,num,i))
{
min=dist[i];
k=i;
}
return k;
}
void ShortestPath(GraphType *g,int st,int nd,int *pathLength,PType *PathInfo) /*求图g中从顶点st到顶点nd的一条最短路径PathInfo及其长度pathLength*/
{
int dist[MAXVTXNUM];
PathType Path[MAXVTXNUM];
int i,found,min,v,w,k;
int count=0;
EdgePtr p,q;
int adjvex;
int Vex[MAXVTXNUM];
for(i=0;i<g->vexNum;i++)
{
dist[i]=INFINITY;
InitPath(&Path[i]);
}
p=FirstEdge(g,st);
while(p)
{
NextEdge(g,st,p,&adjvex,q);
dist[adjvex]=p->elem.length;
InsertPath(&Path[adjvex],st,adjvex);
p=q;
}
found=FLASE;
for(i=0;i<MAXVTXNUM;i++)
{
Vex[i]=0;
}
Vex[count++]=st;
while(!found)
{
min=minval(dist,count,Vex);
if(min==nd) found=TRUE;
else
{
v=min;
Vex[count++]=v;
p=FirstEdge(g,v);
while(p)
{
NextEdge(g,v,p,&w,q);
k=InsetVex(Vex,count,w);
if(!k&&((dist[v]+p->elem.length)<dist[w]))
{
dist[w]=dist[v]+p->elem.length;
CopyPath(&Path[w],Path[v]);
InsertPath(&Path[w],v,w);
}
p=q;
}
}
}
*pathLength=dist[nd];
OutPath(g,Path[nd],PathInfo);
}
void GreatGraph(GraphType *g,FILE *f)
{
int i,j;
VertexType v;
EdgeType e;
InitGraph(g);
fscanf(f,"%d%d",&g->vexNum,&g->edgeNum);
for(i=1;i<=g->vexNum;i++)
{
fscanf(f,"%s%s",v.name,v.info);
InsertVex(g,v,i);
}
for(j=0;j<g->edgeNum;j++)
{
fscanf(f,"%d%d%d",&e.ivex,&e.jvex,&e.length);
if(e.length) InsertEdge(g,e);
}
}
void Initialization(GraphType *g)
{
FILE *fp;
if((fp=fopen("school.txt","r"))==NULL)
{
printf("打开文件出错");
exit(0);
}
GreatGraph(g,fp);
fclose(fp);
}
void ReadCommand(char *cmd)
{
do
{
fflush(stdin);
printf("请选择您所需要的服务:");
scanf("%c",cmd);
}
while(*cmd!='S'&&*cmd!='s'&&*cmd!='V'&&*cmd!='v'&&*cmd!='Q'&&*cmd!='q');
}
void Interpret(char cmd,GraphType *ga)
{ int s,t;
int pathlen;
PType spath;
switch(cmd)
{
case 'S': printf("请输入您要查询的景点编号:");
scanf("%d",&s);
if(s>0&&s<11)
PrintScenery(s,ga);
else
printf("您所查找的景点不存在\n");
break;
case 's': printf("请输入您要查询的景点编号:");
scanf("%d",&s);
if(s>0&&s<11)
PrintScenery(s,ga);
else
printf("您所查找的景点不存在\n");
break;
case 'V': printf("请输入始点:");
scanf("%d",&s);
printf("请输入终点:");
scanf("%d",&t);
ShortestPath(ga,s,t,&pathlen,&spath);
PrintPath(&spath,&pathlen);
break;
case 'v': printf("请输入始点:");
scanf("%d",&s);
printf("请输入终点:");
scanf("%d",&t);
ShortestPath(ga,s,t,&pathlen,&spath);
PrintPath(&spath,&pathlen);
break;
case 'Q': break;
case 'q': break;
}
}
main()
{
char cmd;
GraphType ga;
Initialization(&ga);
do
{ printf("\n");
printf("\n");
printf(" --------------------------------------------------------------\n");
printf(" ----------------------------------------------------------\n");
printf(" ------ 兴庆公园导游系统 ------\n");
printf(" --------------------------------------------------\n");
printf(" ----------------------------------------------\n");
printf("\n");
printf("1. 正门\n");
printf("2. 儿童娱乐区\n");
printf("3. 花卉欣赏区\n");
printf("4. 划船区\n");
printf("5. 假山区\n");
printf("6. 餐饮区\n");
printf("\n");
printf("\n");
printf("S.查询景点信息\n");
printf("V.寻找最短路径\n");
printf("Q.退出系统\n");
ReadCommand(&cmd);
Interpret(cmd,&ga);
}while(cmd!='q'&&cmd!='Q');
}
void PrintScenery(int x,GraphType *g)
{
printf("您所查询的景点信息为:");
printf("%s----",g->Adjmulist[x].data.name);
printf("%s\n",g->Adjmulist[x].data.info);
}
void PrintPath(PType *spath,int *pathlen)
{
int i;
for(i=0;i<spath->num;i++)
printf("%s--",spath->vertices[i]);
printf("\n路径的长度为:%d\n",*pathlen);
} [/size][/size][/size][em33][em33][em33][em33][em33][em33]
上面附上所用到的TXT文件，希望大侠给我一并解决，谨在新的一年即将到来之时致以崇高的敬意~~[[/size]size=5][size=3][/size][size=1][/size][size=6][/size][size=5][/size][size=4][/size][size=3]
[size=2]#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#include "conio.h"
#define OK 1
#define FLASE 0
#define TRUE 1
#define ERROR 0
#define MAXVTXNUM 20 /*图中顶点的最大值*/
#define INFINITY 999
/*顶点，边和图的类型定义*/
typedef struct{
char name[20]; /*该顶点代表的景点的名称*/
char info[50]; /*景点的信息*/
}VertexType; /*顶点类型*/
typedef struct{
int length; /*边的权值，表示路径长度*/
int ivex,jvex; /*边的两端顶点的位置*/
}EdgeType; /*边的类型*/
typedef struct EdgeNode{
EdgeType elem;
struct EdgeNode *ilink,*jlink;
}EdgeNode,*EdgePtr; /*边的结点类型，指向边的指针*/
typedef struct{
VertexType data;
EdgePtr firstEdge; /*指向第一条依附该顶点的边的指针*/
}VNode; /*顶点类型*/
typedef struct{
VNode Adjmulist[MAXVTXNUM]; /*邻接多重表*/
int vexNum,edgeNum; /*图中的顶点数和边数*/
}GraphType; /*图类型*/
/*图的基本操作*/
void InitGraph(GraphType *g); /*初始化邻接多重表，表示一个空图*/
void GetVex(GraphType *g,int i,VertexType *v); /*以v返回邻接多重表中序号为i的顶点*/
EdgePtr FirstEdge(GraphType *g,int vi); /*返回图g中指向依附于顶点vi的第一条边的指针*/
void NextEdge(GraphType *g,int vi,EdgePtr p,int *vj,EdgePtr q); /*以vj返回图g中依附于顶点vi的一条边的另一端点，以q返回图中依附于顶点vi且相对于指针p所指的边的下一条边*/
void InsertVex(GraphType *g,VertexType v,int i); /*在图g的邻接多重表中添加一个顶点v*/
void InsertEdge(GraphType *g,EdgeType e); /*在图g的邻接多重表中添加一条边e*/
void InitGraph(GraphType *g) /*初始化邻接多重表，表示一个空图*/
{
g->vexNum=g->edgeNum=0;
}
void GetVex(GraphType *g,int i,VertexType *v) /*以v返回邻接多重表中序号为i的顶点*/
{
*v=g->Adjmulist[i].data;
}
EdgePtr FirstEdge(GraphType *g,int vi) /*返回图g中指向依附于顶点vi的第一条边的指针*/
{
EdgePtr p;
p=g->Adjmulist[vi].firstEdge;
return p;
}
void NextEdge(GraphType *g,int vi,EdgePtr p,int *vj,EdgePtr q) /*以vj返回图g中依附于顶点vi的一条边的另一端点，以q返回图中依附于顶点vi且相对于指针p所指的边的下一条边*/
{
if(p->elem.ivex==vi)
{
q=p->ilink;
*vj=p->elem.jvex;
}
else
{
q=p->jlink;
*vj=p->elem.ivex;
}
}
void InsertVex(GraphType *g,VertexType v,int i) /*在图g的邻接多重表中添加一个顶点v*/
{
g->Adjmulist[i].data=v;
g->Adjmulist[i].firstEdge=NULL;
}
void InsertEdge(GraphType *g,EdgeType e) /*在图g的邻接多重表中添加一条边e*/
{
EdgePtr p;
p= (EdgePtr) malloc(sizeof(EdgeNode));
p->elem=e;
p->ilink=FirstEdge(g,e.ivex);
p->jlink=FirstEdge(g,e.jvex);
g->Adjmulist[e.ivex].firstEdge=g->Adjmulist[e.jvex].firstEdge=p;
}
/*路径的类型定义*/
typedef struct{
int vx,vy;
}Edge;
typedef struct{
Edge edges[MAXVTXNUM]; /*路径中边的序列*/
int len; /*路径中边的条数*/
}PathType;
typedef struct{
char vertices[MAXVTXNUM][MAXVTXNUM]; /*路径中景点的序列*/
int num;
}PType;
/*路径的相关基本操作*/
void InitPath(PathType *pa); /*初始化pa为一条空路径*/
void CopyPath(PathType *p1,PathType p2); /*复制路径p1=p2*/
void InsertPath(PathType *pa,int v,int w); /*在路径pa中插入一条边(v.w)*/
int PathLength(PathType *pa); /*返回路径pa的长度*/
void OutPath(GraphType *g,PathType pa,PType *vtxes); /*将路径转换为景点名称的序列*/
void ShortestPath(GraphType *g,int st,int nd,int *pathLength,PType *PathInfo); /*求图g中从顶点st到顶点nd的一条最短路径PathInfo及其长度pathLength*/
void PrintScenery(int x,GraphType *g);
void PrintPath(PType *spath,int *pathlen);
void InitPath(PathType *pa) /*初始化pa为一条空路径*/
{
pa->len=0;
}
void CopyPath(PathType *p1,PathType p2) /*复制路径p1=p2*/
{
int i;
for(i=0;i<p2.len;i++)
{
p1->edges[i].vx=p2.edges[i].vx;
p1->edges[i].vy=p2.edges[i].vy;
}
p1->len=p2.len;
}
void InsertPath(PathType *pa,int v,int w) /*在路径pa中插入一条边(v.w)*/
{
pa->edges[pa->len].vx=v;
pa->edges[pa->len].vy=w;
pa->len++;
}
int PathLength(PathType *pa) /*返回路径pa的长度*/
{
return pa->len;
}
void OutPath(GraphType *g,PathType pa,PType *vtxes) /*将路径转换为景点名称的序列*/
{
int i,m=0;
VertexType vtx;
for(i=0;i<pa.len;i++)
{
GetVex(g,pa.edges[i].vx,&vtx);
strcpy(vtxes->vertices[m++],vtx.name);
}
GetVex(g,pa.edges[pa.len].vy,&vtx);
strcpy(vtxes->vertices[m],vtx.name);
vtxes->num=m;
}
int InsetVex(int Vex[],int num,int w)
{
int i;
for(i=0;i<num;i++)
if(Vex[i]==w)
return TRUE;
return FLASE;
}
int minval(int dist[],int num,int Vex[])
{
int i,k;
int min=dist[0];
for(i=1;i<MAXVTXNUM;i++)
if(dist[i]<min&&!InsetVex(Vex,num,i))
{
min=dist[i];
k=i;
}
return k;
}
void ShortestPath(GraphType *g,int st,int nd,int *pathLength,PType *PathInfo) /*求图g中从顶点st到顶点nd的一条最短路径PathInfo及其长度pathLength*/
{
int dist[MAXVTXNUM];
PathType Path[MAXVTXNUM];
int i,found,min,v,w,k;
int count=0;
EdgePtr p,q;
int adjvex;
int Vex[MAXVTXNUM];
for(i=0;i<g->vexNum;i++)
{
dist[i]=INFINITY;
InitPath(&Path[i]);
}
p=FirstEdge(g,st);
while(p)
{
NextEdge(g,st,p,&adjvex,q);
dist[adjvex]=p->elem.length;
InsertPath(&Path[adjvex],st,adjvex);
p=q;
}
found=FLASE;
for(i=0;i<MAXVTXNUM;i++)
{
Vex[i]=0;
}
Vex[count++]=st;
while(!found)
{
min=minval(dist,count,Vex);
if(min==nd) found=TRUE;
else
{
v=min;
Vex[count++]=v;
p=FirstEdge(g,v);
while(p)
{
NextEdge(g,v,p,&w,q);
k=InsetVex(Vex,count,w);
if(!k&&((dist[v]+p->elem.length)<dist[w]))
{
dist[w]=dist[v]+p->elem.length;
CopyPath(&Path[w],Path[v]);
InsertPath(&Path[w],v,w);
}
p=q;
}
}
}
*pathLength=dist[nd];
OutPath(g,Path[nd],PathInfo);
}
void GreatGraph(GraphType *g,FILE *f)
{
int i,j;
VertexType v;
EdgeType e;
InitGraph(g);
fscanf(f,"%d%d",&g->vexNum,&g->edgeNum);
for(i=1;i<=g->vexNum;i++)
{
fscanf(f,"%s%s",v.name,v.info);
InsertVex(g,v,i);
}
for(j=0;j<g->edgeNum;j++)
{
fscanf(f,"%d%d%d",&e.ivex,&e.jvex,&e.length);
if(e.length) InsertEdge(g,e);
}
}
void Initialization(GraphType *g)
{
FILE *fp;
if((fp=fopen("school.txt","r"))==NULL)
{
printf("打开文件出错");
exit(0);
}
GreatGraph(g,fp);
fclose(fp);
}
void ReadCommand(char *cmd)
{
do
{
fflush(stdin);
printf("请选择您所需要的服务:");
scanf("%c",cmd);
}
while(*cmd!='S'&&*cmd!='s'&&*cmd!='V'&&*cmd!='v'&&*cmd!='Q'&&*cmd!='q');
}
void Interpret(char cmd,GraphType *ga)
{ int s,t;
int pathlen;
PType spath;
switch(cmd)
{
case 'S': printf("请输入您要查询的景点编号:");
scanf("%d",&s);
if(s>0&&s<11)
PrintScenery(s,ga);
else
printf("您所查找的景点不存在\n");
break;
case 's': printf("请输入您要查询的景点编号:");
scanf("%d",&s);
if(s>0&&s<11)
PrintScenery(s,ga);
else
printf("您所查找的景点不存在\n");
break;
case 'V': printf("请输入始点:");
scanf("%d",&s);
printf("请输入终点:");
scanf("%d",&t);
ShortestPath(ga,s,t,&pathlen,&spath);
PrintPath(&spath,&pathlen);
break;
case 'v': printf("请输入始点:");
scanf("%d",&s);
printf("请输入终点:");
scanf("%d",&t);
ShortestPath(ga,s,t,&pathlen,&spath);
PrintPath(&spath,&pathlen);
break;
case 'Q': break;
case 'q': break;
}
}
main()
{
char cmd;
GraphType ga;
Initialization(&ga);
do
{ printf("\n");
printf("\n");
printf(" --------------------------------------------------------------\n");
printf(" ----------------------------------------------------------\n");
printf(" ------ 兴庆公园导游系统 ------\n");
printf(" --------------------------------------------------\n");
printf(" ----------------------------------------------\n");
printf("\n");
printf("1. 正门\n");
printf("2. 儿童娱乐区\n");
printf("3. 花卉欣赏区\n");
printf("4. 划船区\n");
printf("5. 假山区\n");
printf("6. 餐饮区\n");
printf("\n");
printf("\n");
printf("S.查询景点信息\n");
printf("V.寻找最短路径\n");
printf("Q.退出系统\n");
ReadCommand(&cmd);
Interpret(cmd,&ga);
}while(cmd!='q'&&cmd!='Q');
}
void PrintScenery(int x,GraphType *g)
{
printf("您所查询的景点信息为:");
printf("%s----",g->Adjmulist[x].data.name);
printf("%s\n",g->Adjmulist[x].data.info);
}
void PrintPath(PType *spath,int *pathlen)
{
int i;
for(i=0;i<spath->num;i++)
printf("%s--",spath->vertices[i]);
printf("\n路径的长度为:%d\n",*pathlen);
} [/size][/size][/size][em33][em33][em33][em33][em33][em33]