/*输入两个城市名，然后在cityTable中查找与城市名对应的下标，*/
/*最后用该下标在kmTable中找到两城市之间的距离*/
/*函数说明：（1)FindCityInSortedArray的功能是用二分查找法在*/
/*全局数组cityTable中查找城市名所对应的下标值。*/
/*(2)GetCity的功能是读入城市名，调用FindCityInSortedArray来*/
/*获取城市所对应的下标值。如果该城市名不存在，则提示重新输入*/

#include"stdio.h"
#define NCities 8       /*城市个数*/
#define TRUE 1
static char * cityTable[NCities]={   /*城市名按字典序升序排列*/
        "Beijing",
        "Chengdu",
        "Chongqing",
        "Dalian",
        "Guiyang",
        "Lanzhou",
        "Nanjing",
        "Sanya",
};
static int kmTable[NCities][NCities]={        /*各城市间对应的距离*/
        {0,1697,2695,937,1784,1356,926,2543},
        {1697,0,313,1840,533,940,1409,1505},
        {2695,313,0,1734,343,1117,1206,1306},
        {937,1840,1734,0,1995,1594,818,2602},
        {1784,533,343,1995,0,1113,1346,976},
        {1356,940,1117,1594,1113,0,1654,2075},
        {926,1409,1206,818,1346,1654,0,1806},
        {2543,1505,1306,2602,976,2075,1806,0}
};
int main(){
        int city1,city2;
        city1=GetCity("Input first City:");
        city2=GetCity("Input second City:");
        printf("%s and %s are length:%d km.\n",
        cityTable[city1],cityTable[city2],
        kmTable[city1][city2]);
        return 0;
}
static int GetCity(char * prompt){
        char * cityName;
        int index;
        cityName=(char *)malloc(20*sizeof(char));
        while(TRUE){
        printf("%s",prompt);
        gets(cityName);
        index=FindCityInSortedArray(cityName);
        if(index>-1) break;
        printf("Not exist cityName,please input again!\n");
    }
        free(cityName);
        return index;
}
static int FindCityInSortedArray(char * key){
        int lh,rh,mid,cmp;
        lh=0;
        rh=NCities-1;
        while(lh<=rh){
             mid=(lh+rh)/2;
             cmp=strcmp(key,cityTable[mid]);
             if(cmp==0) return mid;
             if(cmp<0) {rh=mid-1;}
             else {lh=mid+1;}
        }
        return (-1);
}