最短路径问题
总路径表没问题，但是0到1，和1到0的距离，为什么不相同呢
程序代码：#include<stdio.h>//标准输入输出函数
#include <stdlib.h>//标准库头文件
#include<string.h>//编译预处理指令
#define OVERFLOW 0//OVERFLOW 溢出
#define MAXSIZE 15
#define MAXINT 9999//最大整数值
#define FALSE 0//错误
#define TRUE 1//正确
typedef struct _path//【path：路径】
{
int adjpark;//邻接点域
int distance;//距离
struct _path *nextpath;//下一个路径
}PathNode,*PList[MAXSIZE];
typedef struct _park//【park：车位】
{
char name[10];//车位名
struct _path *firstpath;//第一个路径
}AdjList[15],parkNode;
typedef struct
{
int parks;//车位数
int paths;//路径数
AdjList list;
}MGraph;
PList head;//列表头
typedef int PathMatrix;//PathMatrix 路径矩阵
typedef int ShortPathTable;//ShortPathTable短路径表
PathMatrix P[MAXSIZE][MAXSIZE];//矩阵p[][]
ShortPathTable D[MAXSIZE];//表d[]
int CreatAdjList(MGraph *G)//创造车位图
{
PathNode *p,*p1,*pre;
int i=0;
printf("请输入车位路径数目\n");
scanf("%d",&G->paths);//存入路径数
printf("请输入车位数目\n");
scanf("%d",&G->parks);//存入车位数
for(i=0; i<G->parks; i++)//在i小于车位之前
{
printf("请输入第%d个车位名称\n",i+1);
getchar();//获取字符getchar有一个int型的返回值.当程序调用getchar时.程序就等着用户按键.用户输入的字符被存放在键盘缓冲区中
//直到用户按回车为止(回车字符也放在缓冲区中).
scanf("%s",G->list[i].name);//%s,字符串，
G->list[i].firstpath=(PathNode *)malloc(sizeof(PathNode));//给指针变量进行相应的地址分配
p=G->list[i].firstpath;
printf("请输入车位第一条路径的邻接车位的位置（-1表示结束）\n");
scanf("%d",&p->adjpark);
printf("请输入车位第一条路径的距离\n");
scanf("%d",&p->distance);
if(p->adjpark==-1)
{
free(p);//释放malloc(或calloc、realloc)函数给指针变量分配的内存空间的函数
//使用后该指针变量一定要重新指向NULL，防止野指针出现，有效 规避误操作。
p=NULL;
G->list[i].firstpath = NULL;//把弧链表的first置为NULL
}
while(p)
{
p->nextpath=(PathNode *)malloc(sizeof(PathNode));
pre=p;
p=p->nextpath;//指针交换指向下一个数据结构体
printf("请输入车位下一条路径的邻接车位（-1表示结束）\n");
scanf("%d",&p->adjpark);
if(p->adjpark==-1)
{
free(p);
p=NULL;
pre->nextpath = NULL;//置pre为弧链表结束的节点
break;
}
printf("请输入车位下一条路径的距离\n");
scanf("%d",&p->distance);
}
}
return 0;
}
int ReadAdjList(MGraph *G)//读取车位图
{
FILE *fp;
int r,i;
PathNode *p,*p1,*pre;
if(( fp=fopen("MGraph.txt","a+"))==NULL)
{
printf("未找到存储文件，已重新创建，请重新打开本程序");
exit(1);
}
r=fscanf(fp,"%d %d ",&G->paths,&G->parks);
if(r==2)
{
for(i=0; i<G->parks; i++)
{
fscanf(fp,"%s",G->list[i].name);
G->list[i].firstpath=(PathNode *)malloc(sizeof(PathNode));
p=G->list[i].firstpath;
fscanf(fp,"%d",&p->adjpark);
if(p->adjpark==-1)
{
free(p);
p=NULL;
G->list[i].firstpath = NULL;//把弧链表的first置为NULL
break;
}
else
fscanf(fp,"%d",&p->distance);
while(1)
{
p->nextpath=(PathNode *)malloc(sizeof(PathNode));
pre = p;
p=p->nextpath;
fscanf(fp,"%d",&p->adjpark);
if(p->adjpark==-1)
{
free(p);
p=NULL;
pre->nextpath = NULL;//置pre为弧链表结束的节点
break;
}
else
fscanf(fp,"%d",&p->distance);
}
}
}
fclose(fp);
return 0;
}
int WriteAdjList(MGraph *G)//读取车位图
{
FILE *fp;
int r,i;
PathNode *p,*p1;
if(( fp=fopen("MGraph.txt","a+"))==NULL)
{
printf("未找到存储文件，已重新创建，请重新打开本程序");
exit(0);
}
fprintf(fp,"%d %d ",G->paths,G->parks);
//fprintf()会根据参数format 字符串来转换并格式化数据, 然后将结果输出到参数stream 指定的文件中, 直到出现字符串结束('\0')为止。
for(i=0; i<G->parks; i++)
{
fprintf(fp,"%s ",G->list[i].name);
p=G->list[i].firstpath;
while(p)
{
fprintf(fp,"%d %d ",p->adjpark,p->distance);
p=p->nextpath;
}
fprintf(fp,"-1 ");
}
fclose(fp);
//fclose是一个函数名，功能是关闭一个流。注意：使用fclose()函数就可以把缓冲区内最后剩余的数据输出到内核缓冲区，并释放文件指针和有关的缓冲区。
return 0;
}
void ADD_PATH(MGraph *G,int ori,int add,PathNode p)//添加路径
{
PathNode *pr;
pr=(PathNode *)malloc(sizeof(PathNode));
pr->adjpark=add;
pr->distance=p.distance;
pr->nextpath=G->list[ori].firstpath;
G->list[ori].firstpath=pr;
}
void ADD_park(MGraph *G)//添加车位
{
int i=0;
PathNode *p,*pre;
if(G->parks>=MAXSIZE) return ;
while(strcmp(G->list[i].name,"0")!=0)
i++;
G->parks++;
printf("请输入%d车位的名称\n",i+1);
getchar();
scanf("%s",G->list[i].name);
G->list[i].firstpath=(PathNode *)malloc(sizeof(PathNode));
p=G->list[i].firstpath;
printf("请输入车位第一条路径的邻接车位的位置（-1表示结束）\n");
scanf("%d",&p->adjpark);
printf("请输入车位第一条路径的距离\n");
scanf("%d",&p->distance);
if(p->adjpark==-1)
{
free(p);
p=NULL;
G->list[i].firstpath = NULL;//把弧链表的first置为NULL
}
else
{
ADD_PATH(G,p->adjpark,i,*p);
}
while(p)
{
p->nextpath=(PathNode *)malloc(sizeof(PathNode));
pre = p;
p=p->nextpath;
printf("请输入车位下一条路径的邻接车位（-1表示结束）\n");
scanf("%d",&p->adjpark);
printf("请输入车位下一条路径的距离\n");
scanf("%d",&p->distance);
if(p->adjpark==-1)
{
free(p);
p=NULL;
pre->nextpath = NULL;//置pre为弧链表结束的节点
}
else
{
ADD_PATH(G,p->adjpark,i,*p);
}
}
}
void UPDATE_park(MGraph *G,int park,char *name)//更新车位
{
strcpy(G->list[park].name,name);
}
int Findpark(MGraph *G,char name[])//寻找车位的序号
{
int i;
for(i=0; i<G->parks; i++)
{
if(strcmp(name,G->list[i].name)==0)
return i;
}
return -1;
}
void UPDATE_PATH(MGraph *G,int left,int right)//更新路径
{
PathNode *p;
int dis;
printf("请输入修改后的路径距离\n");
scanf("%d",&dis);
p=G->list[left].firstpath;
while(1)
{
if(right==p->adjpark)
{
p->distance=dis;
break;
}
p=p->nextpath;
}
p=G->list[right].firstpath;
while(1)
{
if(left==p->adjpark)
{
p->distance=dis;
break;
}
p=p->nextpath;
}
return ;
}
void DELETE_PATH(MGraph *G,int left,int right)//删除车位
{
PathNode *p,*pre;
int dis;
p=G->list[left].firstpath;
pre=p;
while(p)
{
if(right==p->adjpark)
{
break;
}
p=p->nextpath;
}
while(1)
{
if(p==G->list[left].firstpath)
{
G->list[left].firstpath=p->nextpath;
free(p);
break;
}
if(pre->nextpath==p)
{
pre->nextpath=p->nextpath;
free(p);
break;
}
}
p=G->list[right].firstpath;
pre=p;
while(p)
{
if(left==p->adjpark)
{
break;
}
p=p->nextpath;
}
while(1)
{
if(p==G->list[right].firstpath)
{
G->list[right].firstpath=p->nextpath;
free(p);
break;
}
if(pre->nextpath==p)
{
pre->nextpath=p->nextpath;
free(p);
break;
}
}
return ;
}
void DELETE_park(MGraph *G,int park)//删除车位
{
int i;
while(G->list[park].firstpath)
{
DELETE_PATH(G,park,G->list[park].firstpath->adjpark);
}
G->parks--;
for(i=park+1; i<=G->parks; i++)
G->list[i-1]=G->list[i];
}
void menu(int i)
{
switch(i)
{
case 0:
printf("*******************************\n");
printf("******管理员模板请输入 1*******\n");
printf("******客户模板请输入 2*******\n");
printf("******退出系统 3*******\n");
printf("*******************************\n");
break;
case 1:
printf("*****************************\n");
printf("*请输入您要进行的操作********\n");
printf("***初始化车位图 1**********\n");
printf("***更新车位图信息 2**********\n");
printf("***删除车位图信息 3**********\n");
printf("***添加车位图信息 4**********\n");
printf("***创建车位图 5**********\n");
printf("***返回 6**********\n");
printf("*****************************\n");
break;
case 2:
printf("*******************************************\n");
printf("***请输入您要进行的操作: ***\n");
printf("***咨询某车位到其他所有车位的最短路径 1***\n");
printf("***咨询所有车位间的最短路径 2***\n");
printf("***咨询两车位间的最短路径 3***\n");
printf("***浏览地图的邻接表表示 4***\n");
printf("***返回 5***\n");
printf("*******************************************\n");
break;
}
}
void initalize_MGraph(MGraph *G)//初始化
{
int i;
for(i=0; i<MAXSIZE; i++)//#define MAXSIZE 15
{
strcpy(G->list[i].name,"0");
G->list[i].firstpath=NULL;
}
}
void MODE_ADMIN(MGraph *G)//模式管理
{
int i=0,j;
char name[20],name1[20];
PathNode *p;
while(1)
{
menu(1);
scanf("%d",&i);
switch(i)
{
case 1:
initalize_MGraph(G);
printf("初始化完成！\n");
break;
case 2:
printf("1：修改车位名\n2：修改路径距离\n3:返回上一层\n");
scanf("%d",&j);
if(j==1)
{
printf("请输入要修改的车位名称\n");
scanf("%s",&name);
printf("请输入要修改后的车位名称\n");
scanf("%s",&name1);
UPDATE_park(G, Findpark(G,name),name1);
printf("修改完成！\n");
}
else if(j==2)
{
printf("请输入要修改的两个中第一个车位的名称\n");
scanf("%s",&name);
printf("请输入要修改的两个中第二个车位的名称\n");
scanf("%s",&name1);
UPDATE_PATH(G,Findpark(G,name),Findpark(G,name1));
printf("修改完成！\n");
}
else
break;
break;
case 3:
printf("1：删除车位\n2：删除路径\n3:返回上一层\n");
scanf("%d",&j);
if(j==1)
{
printf("请输入要删除的车位名称\n");
scanf("%s",&name);
DELETE_park(G,Findpark(G,name));
printf("删除完成！\n");
}
else if(j==2)
{
printf("请输入要删除的路径中第一个车位的名称\n");
scanf("%s",&name);
printf("请输入要修改的两个中第二个车位的名称\n");
scanf("%s",&name);
DELETE_PATH(G,Findpark(G,name),Findpark(G,name1));
printf("删除完成！\n");
}
else
break;
break;
case 4:
printf("1：添加车位\n2：添加路径\n3:返回上一层\n");
scanf("%d",&j);
if(j==1)
{
ADD_park(G);
printf("添加完成！\n");
}
else if(j==2)
{
p=(PathNode *)malloc(sizeof(PathNode));
printf("请输入要添加的路径中第一个车位的名称\n");
scanf("%s",&name);
printf("请输入要添加的两个中第二个车位的名称\n");
scanf("%s",&name1);
printf("请输入要添加的路径的距离\n");
scanf("%d",p->adjpark);
ADD_PATH(G,Findpark(G,name),Findpark(G,name1),*p);
ADD_PATH(G,Findpark(G,name1),Findpark(G,name),*p);
printf("添加完成！\n");
}
else
break;
break;
case 5:
CreatAdjList(G);
printf("创建完成！\n");
break;
case 6:
return ;
break;
default :
return ;
}
WriteAdjList(G);
}
}
int dis(MGraph *G,int left,int right)//数字化信息系统
{
PathNode *p;
p=G->list[left].firstpath;
while(p)
{
if(right==p->adjpark)
{
return p->distance;
}
p=p->nextpath;
}
return MAXINT;
}
void ShortestPath(MGraph *G,int v0)//ShortestPath最短路径
{
int i,w,min,l=0;
int v=1;
int final[MAXSIZE];//Dijkstra tool
for(v=1; v<=G->parks;++v)//v<=车位数
{
final[v]=FALSE;
D[v]=dis(G,v0,v);
for(w=0; w<G->parks; w++)
P[v][w]=FALSE;
if(D[v]<MAXINT)
{
P[v][v0]=1;
P[v][w]=1;
}
}
D[v0]=0;
final[v0]=TRUE;
for(int i=2; i<=G->parks; i++)
{
min=MAXINT;
int v=v0;
for(int w=1; w<=G->parks; ++w)
{
if(!final[w])
{
if(D[w]<min)
{
v=w;//u=v
min=D[w];//D=dist
}
}
}
final[v]=TRUE;//final=s
for(w=0; w<G->parks; w++)
{
if(!final[w]&&(min+dis(G,v,w)<D[w]))
{
D[w]=min+dis(G,v,w);
strcpy((char*)P[w],(char *)P[v]);
P[w][v]=TRUE;
}
}
}
}
void FindPath(MGraph *G,int v)//寻找路径
{
int i=0;
for(i=0; i<MAXSIZE; i++)
if(P[v][i]==1)
if(dis(G,v,i)<MAXINT)
printf("%s---->",G->list[i].name);
}
void Print1(MGraph *G,int v0)//打印1
{
int i;
PathNode *p,*pre;
for(i=0; i<G->parks; i++)
{
if(i!=v0)
{
printf("%s到%s的最短距离为%d，路径如下：\n",G->list[v0].name,G->list[i].name,D[i]);
printf("%s---->",G->list[v0].name);
P[i][v0]=0;
P[i][i]=0;
FindPath(G,i);
printf("%s\n",G->list[i].name);
}
}
}
void Print2(MGraph *G,int v1,int v2)//打印2
{
printf("%s到%s的最短距离为%d，路径如下：\n",G->list[v1].name,G->list[v2].name,D[v2]);
printf("%s---->",G->list[v1].name);
P[v2][v1]=0;
P[v2][v2]=0;
FindPath(G,v2);
printf("%s\n",G->list[v2].name);
}
void Print3(MGraph *G)//打印3
{
int i;PathNode *p;
for(i=0; i<G->parks; i++)
{
p=G->list[i].firstpath->nextpath;
printf("|%-2d%-12s-->%-12s~%-3d|",
i+1,
G->list[i].name,
G->list[G->list[i].firstpath->adjpark].name,
G->list[i].firstpath->distance);
while(p)
{
printf("-->%-12s~%-3d|",
G->list[p->adjpark].name,
p->distance);
p=p->nextpath;
}
printf("<<");
putchar(10);
}
}
void MODE_CLIENT(MGraph *G)
{
int i,j;
int v0,v1,v2;
char name1[20],name2[20],name[20];
while(1)
{
menu(2);
scanf("%d",&i);
switch(i)
{
case 1:
printf("请输入车位的名称：\n");
scanf("%s",name);
v0=Findpark(G,name);
if(v0==-1)
{
printf("输入有误或者没有该车位！\n");
break;
}
ShortestPath(G,v0);
Print1(G,v0);
break;
case 2:
for(j=0; j<G->parks; j++)
{
ShortestPath(G,j);
Print1(G,j);
}
break;
case 3:
printf("请输入第一个车位的名称：\n");
scanf("%s",name1);
v1=Findpark(G,name1);
printf("请输入第二个车位的名称：\n");
scanf("%s",name2);
v2=Findpark(G,name2);
if(v1==-1||v2==-1)
{
printf("输入有误或者没有该车位！\n");
break;
}
ShortestPath(G,v1);
Print2(G,v1,v2);
break;
case 4:
Print3(G);
getchar();
getchar();
break;
case 5:
return;
default:
return ;
}
}
}
int main()
{
MGraph G;
int password;
initalize_MGraph(&G);
menu(0);
scanf("%d",&password);
ReadAdjList(&G);
while(1)
{
menu(0);
scanf("%d",&password);
if(password==1)
MODE_ADMIN(&G);
if(password==2)
MODE_CLIENT(&G);
if(password==3)
return 0;
}
return 0;
}
~
