003.cpp

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

     printf("Cannot open file %s !!!\n",MinPathDataFile);
     getch();
     return;
  }
  fwrite(&NodeNum,sizeof(int),1,fp);
  fwrite(dist,sizeof(int),NodeNum*NodeNum,fp);
  fwrite(Path,sizeof(int),NodeNum*NodeNum,fp);
  fclose(fp);
  return;
//---------------------->>>>>>>>>>>>>>>>>>>>>>>----------------------------------------------------

}

/********************************************************/
/*          求一个城市到其它城市的最短路径              */
/* 函数参数：<无>                                       */
/* 输入数据：文本数据文件：CityNameFile                 */
/*           数据文件：MinPathDataFile                  */
/*           指定城市名,从键盘输入                      */
/* 输出数据：                                           */
/*     指定城市到其它所有城市的最短路径值和路径         */
/*               (屏幕显式)                             */
/* 返回值：<无>                                         */
/********************************************************/
void One_To_Other_Path()
 { int i,j,k,NodeNum,StartNode;
   char city[CityNum][NameLenght];    //城市结点
   int dist[CityNum][CityNum];        //最短路径长度矩阵
   int Path[CityNum][CityNum];        //最短路径矩阵
   int top,PathStack[CityNum];
   char city1[NameLenght];
   FILE *fp;

/*-----------------------------------------------------*/
 /*   算法步骤：                                       */
 /*     1、输入城市结点数据                            */
 /*     2、输入最小路径数据                            */
 /*     3、输入起点城市名称，并确定其正确性            */
 /*       方法：调用查找函数，若返回值>=0则正确        */
 /*     4、依次求起点城市到其它城市的最短路径          */
 /*        方法：根据两城市的序号i,j在dist数组中获得   */
 /*             最短路径值。根据Path数组中结点间路径   */
 /*             数据的关系求的其结点序列并放入栈中，   */
 /*             然后依次输出栈数据。                   */
 /*----------------------------------------------------*/

 //---------<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<-----------------------------------
    //从文件中读入城市结点数据
    if(!InputCityNode(city,&NodeNum))
    {
        printf("Read CityNode from file %s ERROR!!!\n",CityNameFile);
        getch();
        return;
    }
    //从文件中读入最小路径数据
    if(!InputMinPath(dist,Path,&NodeNum))
    {
        printf("Read MinPathData from file %s ERROR!!!\n",MinPathDataFile);
        getch();
        return;
    }
    //输入起点城市名
    printf("Please Input the CityName: ");
    scanf("%s",&city1);
    k=search(city,NodeNum,city1);
    if(k<0)
    {
       printf("ERROR CityName %s !!!\n",city1);
       getch();
       return;
    }
    //获得路径结点关系，并依次入栈
    for(i=0;i<NodeNum;i++)
    {
       j=i;
       top=StartNode=0;
       if(i==k) continue;
       printf("The Start and Terminus Station is:    %s==>%s\n",city[k],city[i]);
       printf("The MinPath is:    %d km\n",dist[k][i]);
       PathStack[top++]=j;
       while(Path[k][j]!=k)
       {
         PathStack[top++]=Path[k][j];
         j=Path[k][j];
       }

       //依次输出最小路径上的结点
       printf("The Path is: \n%s",city[k]);
       while(top)
       {
           printf("==>%s",city[PathStack[--top]]);
       }
       getch();
       printf("\n\n");
    }
 //--------->>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>-----------------------------------

 }

/********************************************************/
/*          求一个城市到另一个城市的最短路径            */
/* 函数参数：<无>                                       */
/* 输入数据：文本数据文件：CityNameFile                 */
/*           数据文件：MinPathDataFile                  */
/*           起点城市名,终点城市名，从键盘输入          */
/* 输出数据：                                           */
/*     起点城市到终点城市的最短路径值和路径             */
/*               (屏幕显式)                             */
/* 返回值：<无>                                         */
/********************************************************/
void One_To_One_Path()
{ int i,j,k,NodeNum,StartNode,EndNode;
   char city[CityNum][NameLenght];    //城市结点
   int dist[CityNum][CityNum];        //最短路径长度矩阵
   int Path[CityNum][CityNum];        //最短路径矩阵
   int top,PathStack[CityNum];
   char city1[NameLenght],city2[NameLenght];
   FILE *fp;

/*-----------------------------------------------------*/
 /*   算法步骤：                                       */ 
 /*     1、输入城市结点数据                            */ 
 /*     2、输入最小路径数据                            */
 /*     3、输入起点城市和终点城市名称，并确定其正确性  */  
 /*       方法：调用查找函数，若返回值>=0则正确        */
 /*     4、求起点城市到终点城市的最短路径              */
 /*        方法：根据两城市的序号i,j在dist数组中获得   */
 /*             最短路径值。根据Path数组中结点间路径   */
 /*             数据的关系求的其结点序列并放入栈中，   */
 /*             然后依次输出栈数据。                   */
 /*----------------------------------------------------*/

 //-------------<<<<<<<<<<<<<<<<<<<<<<<<<---------------------------------------
    //从文件中读入城市结点数据
    if(!InputCityNode(city,&NodeNum))
    {
        printf("Read CityNode from file %s ERROR!!!\n",CityNameFile);
        getch();
        return;
    }
    //从文件中读入最小路径数据
    if(!InputMinPath(dist,Path,&NodeNum))
    {
        printf("Read MinPath from file %s ERROR!!!\n",MinPathDataFile);
        getch();
        return;
    }
    //用户输入起点城市和终点城市
    printf("Please Input the Start CityName: ");
    scanf("%s",city1);
    printf("Please Input the Terminus CityName: ");
    scanf("%s",city2);
    //调用查找函数，
    StartNode=search(city,NodeNum,city1);
    EndNode=search(city,NodeNum,city2);
    if(StartNode<0||EndNode<0)  // 检测城市名正确性
    {
       printf("ERROR CityName!!!\n");
       getch();
       return;
    }
    //获得城市结点关系，并依次进栈，输出之
    printf("The distance between %s==>%s is: %d km\n",city1,city2,dist[StartNode][EndNode]);
    i=StartNode;
    j=EndNode;
    top=0;
    PathStack[top++]=j;  //终点城市入栈
    while(Path[i][j]!=i)
    {
        PathStack[top++]=Path[i][j];  //最短路径上其它城市结点入栈
        j=Path[i][j];
    }
    printf("The MinPath is:\n");
    printf("%s",city1);
    while(top)
    {
        printf("==>%s",city[PathStack[--top]]);
    }
    getch();
    return;
 //------------->>>>>>>>>>>>>>>>>>>>>>>>>---------------------------------------
 }

int nemu()
{
    int num;
    printf("\n    ************* shortest path program **************\n");
    printf("    *%15c1---Initial%23c\n",' ','*');
    printf("    *%15c2---One to Other Cities%11c\n",' ','*');
    printf("    *%15c3---One to Another City%11c\n",' ','*');
    printf("    *%15c4---Quit%26c\n",' ','*');
    printf("    **************************************************\n");
    printf("%15cSelcet 1,2,3,4: ",' ');
    do{
	scanf("%d",&num);
	}while(num<1 ||num>4);
    return(num);
}

void main()
{
    while(1)
    {
	switch(nemu())
	{
	    case 1:
		shorttestpath();
		break;
	    case 2:
		One_To_Other_Path();
		break;
	    case 3:
		One_To_One_Path();
		break;
	    case 4:
		return;
        }
    }
}