//shortest_path.c #include<stdio.h> #include<stdlib.h>//用file #include<string.h>//可用gets(),puts() #include"shortest_path.h" #define MAX 32767 #define MENU "欢迎进入导航系统！\n==========菜单===========\n0、载入北外地图\n1、建立地图\n2、查询最短路径\n3、退出\n==========菜单===========\n" struct stmap map;//无向网 const char *filepath1="D:\\spots.dat"; const char *filepath2="D:\\paths.dat"; int load1() {  FILE *fp;  int i;  fp=fopen(filepath1,"r");  if(fp==NULL){printf("spots文件打开异常，读取失败");return -1;}  fread(&map.spotnum,sizeof(int),1,fp);  for(i=0;i<map.spotnum;i++)  {   fread(map.spot[i].name,sizeof(char),10,fp);   fread(map.spot[i].intro,sizeof(char),20,fp);  }  fclose(fp);  return 0; } int load2() {  FILE *fp;  int i,j;  fp=fopen(filepath2,"r");  if(fp==NULL){printf("paths文件打开异常，读取失败");return -1;}  fread(&map.pathmatrix,sizeof(int),1,fp);  for(i=0;i<map.spotnum;i++)   for(j=0;j<map.spotnum;j++)    fread(&map.pathmatrix[i][j],sizeof(int),1,fp);  fclose(fp);  return 0; } void loadmap() {  if(load1()==0)   printf("spot读入成功\n");  else   printf("spot读入失败\n");  if(load2()==0)   printf("path读入成功\n");  else   printf("path读入失败\n");  } void drawmap()//直接输入 {  int i;  int a,b;  char s1[10],s2[10];  printf("共有几个景点？(<=20)");//map.spotmun  fflush(stdin);  scanf("%d",&map.spotnum);  printf("共有几条景点与景点之间直接相连的路径？");//map.pathnum  fflush(stdin);//清空键盘缓冲区，在"stdio.h"中  scanf("%d",&map.pathnum);  for(a=0;a<map.spotnum;a++)//initialize map   for(b=0;b<map.spotnum;b++)   {    if(a==b)map.pathmatrix[a][b]=0;    else map.pathmatrix[a][b]=MAX;   }  for(i=0;i<map.spotnum;i++){   printf("请输入第%d个景点的名称（<=10letters）",i+1);   fflush(stdin);   gets(map.spot[i].name);   printf("请输入第%d个景点的介绍（<=20letters）",i+1);   fflush(stdin);   gets(map.spot[i].intro);  }//输入景点名字和简介map.spot[].name;map.spot[].intro  for(i=0;i<map.pathnum;i++){   do{    printf("请输入第%d条路径的起点",i+1);    fflush(stdin);    gets(s1);    for(a=0;a<map.spotnum;a++)     if(!strcmp(map.spot[a].name,s1))break;//查找景点编号    if(a==map.spotnum)printf("不存在此景点，请重新输入。\n");   }while(a==map.spotnum);   do{    printf("请输入第%d条路径的终点",i+1);    fflush(stdin);    gets(s2);    for(b=0;b<map.spotnum;b++)     if(!strcmp(map.spot[b].name,s2))break;    if(b==map.spotnum)printf("不存在此景点，请重新输入。\n");   }while(b==map.spotnum);   printf("请输入第%d条路径的长度",i+1);   fflush(stdin);   scanf("%d",&map.pathmatrix[a][b]);   map.pathmatrix[b][a]=map.pathmatrix[a][b];//输入路径长度  } } void shortestpath()//最短路径，输入起点终点输出路径和路程 {  struct stspath spath[20];  int s,t,v,w,min;  char s1[10],s2[10];  int pathorder[20];  struct stspath *p;//pathorder  do{   printf("请输入起点");//查找起点的景点编号   fflush(stdin);   gets(s1);   for(s=0;s<map.spotnum;s++)    if(!strcmp(map.spot[s].name,s1))break;   if(s==map.spotnum)printf("不存在此景点，请重新输入。\n");  }while(s==map.spotnum);   do{   printf("请输入终点");//查找终点的景点编号   fflush(stdin);   gets(s2);   for(t=0;t<map.spotnum;t++)    if(!strcmp(map.spot[t].name,s2))break;   if(t==map.spotnum)printf("不存在此景点，请重新输入。\n");  }while(t==map.spotnum);  for(v=0;v<map.spotnum;v++)//initialize spath  {   spath[v].length=MAX;   spath[v].in=0;  }  spath[s].in=1;  spath[s].length=0;  spath[s].pior=NULL;  v=s;  while(v!=t){   for(w=0;w<map.spotnum;w++)    if((!spath[w].in)&&(spath[w].length>spath[v].length+map.pathmatrix[v][w])){     spath[w].length=spath[v].length+map.pathmatrix[v][w];     spath[w].pior=&spath[v];    }   min=MAX;   for(w=0;w<map.spotnum;w++)    if((!spath[w].in)&&(spath[w].length<min)){     min=spath[w].length;     v=w;    }   spath[v].in=1;  }  printf("最短路径长度为%d,最短路径为：\n",spath[t].length);//print path  for(v=0,p=&spath[t];p->pior!=NULL;p=p->pior)  {   pathorder[v]=p-spath;   v++;  }  pathorder[v]=s;  for(;v>=0;v--)   printf("s",map.spot[pathorder[v]].name); } void main() {  int menu=1;  printf(MENU);  while(menu!=3)  {   printf("\n请输入您的选项（数字）\n");   fflush(stdin);   scanf("%d",&menu);   switch (menu)   {   case 0: loadmap();printf("\n北外地图载入完成\n");break;   case 1: drawmap();printf("\n新建完成\n");break;   case 2: shortestpath();printf("\n查询完成完成\n");break;   }  }  printf("谢谢使用！"); } 2. [文件] shortest_path.h ~ 430B     下载(2)     #ifndef _SHORTEST_PATH_H_ #define _SHORTEST_PATH_H_ struct stspot{//景点的顶点  char name[11];//景点名称no more than 10  char intro[20];//景点介绍no more than 20 }; struct stmap{//整个无向网  stspot spot[20];//点，景点向量  int pathmatrix[20][20];//边，路径的邻接矩阵  int spotnum;  int pathnum; }; struct stspath//求最短路径时的景点数组 {  stspath * pior;  int in;// can be boolen  int length; }; #endif