003.cpp

数据结构课程的经典源码。以中国交通图为背景

#include <stdio.h>
#include <conio.h>
#include <string.h>
#define CityNum      25        //最大城市结点数
#define NameLenght   12        //城市名字长度
#define Infinity     10000     //若城市间没有路径距离设定为Infinity

char *CityNameFile="cityname.txt";  //图的顶点--城市名
char *CityPathFile="citypath.txt";  //边--城市间的连接关系
char *MinPathDataFile="minpath.txt";//最短路径数据

/********************************************************/
/*                从文件中读入城市结点数据              */
/* 函数参数：                                           */
/*    char city[][]:存放城市名的数组                    */
/*    int *NodNum:指针变量，指向存放城市个数的变量      */
/* 输入数据：文本数据文件：CityNameFile                 */
/*    文件数据格式：                                    */
/*          <城市个数>                                  */
/*          <城市名>                                    */
/* 输出数据：指从该函数中带回到调用函数的数据，包括：   */
/*           city[][]--城市名称                         */
/*           NodeNum--城市名的个数                      */
/* 返回值：数据读入是否成功的标志                       */  
/*         0--失败    1--成功                           */
/********************************************************/
int InputCityNode(char city[][NameLenght],int *NodeNum)
  { int i,n;
    FILE *fp;
    if(!(fp=fopen(CityNameFile,"r")))
     { printf("城市数据文件不存在\n");
       getch();
       return(0);
     }
    fscanf(fp,"%d",&n);
  if(!n)
    { printf("文件中无城市数据!\n");
      getch();
      return(0);
      }
   for(i=0;i<n;i++) fscanf(fp,"%s",city[i]);
   fclose(fp);
   *NodeNum=n;
   return(1);
   }
/********************************************************/
/*                从文件中读入最短路径数据              */
/* 函数参数：                                           */
/*    int dist[][]:城市间最短路径的值                   */
/*    int Path[][]:城市间最短路径结点数据               */
/*    int *NodNum:指针变量，表示读入数据的多少          */
/* 输入数据：数据文件：MinPathDataFile                  */
/*    文件数据格式：二进制数据，数据存放顺序：          */
/*      <城市个数n><n*n个最短路径值><n*n个结点值>       */
/* 输出数据：指从该函数中带回到调用函数的数据，包括：   */
/*           city[][]                                   */
/*           Path[][]                                   */
/*           NodeNum                                    */
/* 返回值：数据读入是否成功的标志                       */
/*         0--失败    1--成功                           */
/********************************************************/
int InputMinPath(int dist[][CityNum],int Path[][CityNum],int *NodeNum)
 {int n;
  FILE *fp; 
  if(!(fp=fopen(MinPathDataFile,"rb")))
    { printf("最小路径数据文件不存在!\n");
      getch();
      return(0);
      }
   fread(&n,sizeof(int),1,fp);
   fread(dist,sizeof(int),n*n,fp);
   fread(Path,sizeof(int),n*n,fp);
   fclose(fp);
   *NodeNum=n;
   return(1);
   }
/********************************************************/
/*                     查找城市名                       */
/* 函数参数：                                           */
/*    char str[][]:存放城市名的数组                     */
/*    int n：str中数据的行数，即城市名的个数            */
/*    char *p:指针变量，表示需要查找的城市名            */
/* 输入数据：全部函数参数均为输入数据                   */
/* 输出数据：返回值作为函数的输出数据                   */
/*    查找成功：被查找的城市名在数组str中的序号         */
/*    查找失败：－1，表示被查找的城市名未出现在数组中   */
/********************************************************/
int search(char str[][NameLenght],int n,char *p)
  { int i=0;
    while(i<n)
     { if(!strcmp(str[i],p)) return(i);
       i++;
       }
    return(-1);
    }
/********************************************************/
/*                计算城市间最短路径                    */
/* 函数参数：<无>                                       */
/* 输入数据：文本数据文件：CityNameFile                 */
/*              文件数据格式：                          */
/*                 <城市个数>                           */
/*                 <城市名>                             */
/*           文本数据文件：CityPathFile                 */
/*              文件数据格式：                          */
/*                 <边数>                               */
/*                 <城市名><城市名><边值>               */
/* 输出数据：数据文件：MinPathDataFile                  */
/*    文件数据格式：二进制数据，数据存放顺序：          */
/*      <城市个数n><n*n个最短路径值><n*n个结点值>       */
/* 返回值：<无>                                         */
/* 说明：文本数据文件中数据间用空格或换行符格开         */
/********************************************************/
void shorttestpath()
{
  int i,j,k,NodeNum,EgeNum,val;
  int arc[CityNum][CityNum];       //权值矩阵
  char city[CityNum][NameLenght];  //城市结点
  int dist[CityNum][CityNum];      //最短路径长度矩阵
  int Path[CityNum][CityNum];      //最短路径矩阵
  char city1[NameLenght],city2[NameLenght];
  FILE *fp;
 /*----------------------------------------------------*/
 /*   算法步骤：                                       */ 
 /*     1、读入城市结点数据                            */ 
 /*     2、邻接矩阵初始化：所有元素赋Infinity，        */
 /*            对角线元素赋0                           */
 /*     3、读入城市间边的数据，转换为邻接矩阵的数据    */  
 /*     4、路径矩阵初始化，若arc[i][j]<Infinity，      */
 /*          则： at[i][j]=i 否则：Path[i][j]=-1       */
 /*     5、计算最短路径                                */
 /*     6、保存最小路径数据                            */
 /*----------------------------------------------------*/  

//----------------------<<<<<<<<<<<<<<<<<<<<<<<----------------------------------------------------
//--------初始化邻接矩阵------------
  if(!InputCityNode(city,&NodeNum)) return;
  else
  {
     for(i=0;i<NodeNum;i++)
     {
	  for(j=0;j<NodeNum;j++)
          {
              if(i==j) arc[i][j]=0;
              else   arc[i][j]=Infinity;
          }
          printf("%s\n",city[i]);
     }
  }
 //-----读入城市间边的数据-------
  if(!(fp=fopen(CityPathFile,"r")))
  {
     printf("城市间边的数据文件不存在!!!\n");
     getch();
     return;
  }
  fscanf(fp,"%d",&EgeNum);
  if(!EgeNum)
  {
      printf("文件中无城市间边的数据!!!\n");
      getch();
      return;
  }
  for(k=0;k<EgeNum;k++)
  {
      fscanf(fp,"%s",city1);
      fscanf(fp,"%s",city2);
      fscanf(fp,"%d",&val);
      //  printf("%s  %s   %d\n",city1,city2,val);getch();
      i=search(city,NodeNum,city1);
      j=search(city,NodeNum,city2);
      arc[i][j]=arc[j][i]=val;
  }
  fclose(fp);

//---------路径矩阵初始化-------------
  for(i=0;i<NodeNum;i++)
     for(j=0;j<NodeNum;j++)
     {
        if((arc[i][j]<Infinity)&&(i!=j))
           Path[i][j]=i;
        else Path[i][j]=-1;
     }

    //初始化 最短路径长度矩阵 dist[][]
    for(i=0;i<NodeNum;i++)
      for(j=0;j<NodeNum;j++)
        dist[i][j]=arc[i][j];
    //弗罗伊德算法
    for(k=0;k<NodeNum;k++)
      for(i=0;i<NodeNum;i++)
        for(j=0;j<NodeNum;j++)
          if(dist[i][k]+dist[k][j]<dist[i][j])
          {
             dist[i][j]=dist[i][k]+dist[k][j];
             Path[i][j]=Path[k][j];
          }
    /*
    //  输出最短路径长度矩阵 dist[][]
    for(i=0;i<NodeNum;i++)
      for(j=0;j<NodeNum;j++)
      {
         printf("%-6d",dist[i][j]);
         if(j%10==0) printf("\n");
         else if(j==NodeNum-1)
              {
                  printf("\n");   //  输出矩阵的一行后,自动换行
                  getch();
              }
      }
    printf("\n");
    //输出最短路径结点矩阵 Path[][];
    for(i=0;i<NodeNum;i++)
      for(j=0;j<NodeNum;j++)
      {
         printf("%-3d",Path[i][j]);
         if(j==NodeNum-1)    printf("\n");
      }
     */
//---------保存城市间最短路径的信息-----------------
  if(!(fp=fopen(MinPathDataFile,"wb")))
  {