开始

最近有大一的学弟找我做一个C语言的实验报告，看了下感觉和我当时大一的题目差不多，刚好很久没写C语言了就写一下试试。

题目

题目比较简单，给了一个公交车线路信息的文件，数据比较少，只有30多行。

题目要求：

1. 请给出站点S1018-S2184的直达线路的查询结果
2. 请给出站点S1771-S0886换乘一次线路的查询结果，并分析查询所得线路方案的优劣

思路

写两个函数，函数1是查询搜索经过某一站点的所有线路，函数2是查询搜索某两条公交线路的公共站点。

对于问题1，我们只需要通过函数1得到包含起点站start和终点站end的所有线路start_routes和end_routes，然后取出相同的线路（既包括起点站又包括终点站）然后判断起点站和终点站在线路中的位置索引是否满足start_idx<end_idx即可。比如下表中假设我们得到了包含S1018的线路有L005,L010,L020三条，包含S2184的有四条。因为需要直达，因此我们必须选择左右相同的线路，即选择L005线路，同时需要判断S1018站在L005中的位置索引是否小于S2184的位置索引，只有满足这个关系才可以从S1018直达S2184。

对于问题2，同样的我们需要通过函数1得到包含起点站start和终点站end的所有线路start_routes和end_routes，然后取出不同的线路（因为要换乘，所以一条线路不能同时包含起点站和终点站）然后利用函数2得到任意两条不同线路的公共站点（注意这里公共站点可能有多个），然后同样的判断位置索引关心即可。只是这里需要注意的是，这里因为是不同的两条线路，所以判断的时候要两边公共站点在线路1中的索引大于起点站索引且在线路2中的索引小于终点站索引。示意图如下：

代码

函数1：

//查询搜索经过某一站点的所有线路,idx是输入站点所在的线路索引和输入站点在所在线路中的位置
int get_all_routes(char *station, int idx[36][2])
{
    int station_num, i, j, routes_num = 0;
    char **ret;
    for(i = 0; i < 36; i++)
    {
        ret = explode('-', bus_route[i][1], &station_num); //将当前线路切分后返回一个数组
        for(j = 0; j < station_num; j++)
        {
            if( strcmp(ret[j], station) == 0 ) //判断当前线路是否经过输入站点
            {
                idx[routes_num][0] = i;
                idx[routes_num][1] = j;
                routes_num = routes_num + 1;
            }
            free(ret[j]);
        }
        free(ret);
    }
    return routes_num;
}

函数2：

//查询搜索给定两条线路的所有公共站点,common_idx是给定两条线路公共站点在各自线路中的位置
int get_common_station(int station_idx1, int station_idx2, int common_idx[100][2])
{
    int i, j, ret1_num, ret2_num, common_num = 0;
    char **ret1 = explode('-', bus_route[station_idx1][1], &ret1_num);
    char **ret2 = explode('-', bus_route[station_idx2][1], &ret2_num);
    for(i = 0; i < ret1_num; i++)
    {
        for(j = 0; j < ret2_num; j++)
        {
            if( strcmp(ret1[i], ret2[j]) == 0 )
            {
                common_idx[common_num][0] = i;
                common_idx[common_num][1] = j;
                common_num = common_num + 1;
            }
        }
    }
    free(ret1);
    free(ret2);
    return common_num;
}

主函数部分主要代码：

if( ch == 1 )
        {   //定义所需要用到的数据类型
            int i, start_num, end_num, routes_idx = 0;
            int start_idx[36][2], end_idx[36][2];
            char start_station[10], end_station[10];
            char **routes = calloc(start_num + end_num, sizeof(char *));
            //将矩阵初始化为全-1
            init_matrix(36, 2, (int**)start_idx);
            init_matrix(36, 2, (int**)end_idx);
            //按照提示输入起点和终点
            printf("请输入起点站：");
            scanf("%s", start_station);
            printf("请输入终点站：");
            scanf("%s", end_station);
            //使用函数get_all_routes计算包含起点和终点的所有线路的"索引"
            start_num = get_all_routes(start_station, start_idx);
            end_num = get_all_routes(end_station, end_idx);
            //比较包含起点和终点线路中相同的线路，同时满足起点索引小于终点索引即可直达
            for(i = 0; i < start_num; i++)
            {
                int j;
                for(j = 0; j < end_num; j++)
                {
                    if( start_idx[i][0] == end_idx[j][0] && start_idx[i][1] < end_idx[j][1] )
                    {
                        routes[routes_idx] = calloc(strlen(bus_route[start_idx[i][0]][0]) + strlen(bus_route[start_idx[i][0]][1]) + 1, sizeof(char));
                        memcpy(routes[routes_idx], bus_route[start_idx[i][0]][0], strlen(bus_route[start_idx[i][0]][0]) + 1);
                        strcat(routes[routes_idx], bus_route[start_idx[i][0]][1]);
                        routes_idx = routes_idx + 1;
                    }
                }
            }
            //打印出直达线路，包括线路名称和具体线路路线
            printf("从%s站到%s站的直达线路为：(查询结果为空则表示当前两站点没有直达线路)\n", start_station, end_station);
            for(i = 0; i < routes_idx; i++)
            {
                puts(routes[i]);
                printf("\n");
            }

            free(routes);

        }

        if( ch == 2 )
        {
            int common_idx[100][2], start_idx[36][2], end_idx[36][2];
            int i, start_num, end_num, common_num, ret_num, routes_idx1 = 0, routes_idx2 = 0, common_station_idx = 0;
            char start_station[10], end_station[10];
            char **routes1 = calloc(100, sizeof(char *));
            char **routes2 = calloc(100, sizeof(char *));
            char **common_station = calloc(100, sizeof(char *));

            init_matrix(100, 2, (int**)common_idx);
            init_matrix(36, 2, (int**)start_idx);
            init_matrix(36, 2, (int**)end_idx);

            printf("请输入起点站：");
            scanf("%s", start_station);
            printf("请输入终点站：");
            scanf("%s", end_station);

            start_num = get_all_routes(start_station, start_idx);
            end_num = get_all_routes(end_station, end_idx);
            
            for(i = 0; i < start_num; i++)
            {
                int j;
                for(j = 0; j < end_num; j++)
                {
                    if( start_idx[i][0] != end_idx[j][0] )
                    {
                        common_num = get_common_station(start_idx[i][0], end_idx[j][0], common_idx);
                        int k;
                        for(k = 0; k < common_num; k++)
                        {
                            if( start_idx[i][1] < common_idx[k][0] && common_idx[k][1] < end_idx[j][1])
                            {
                                routes1[routes_idx1] = calloc(strlen(bus_route[start_idx[i][0]][0]) + strlen(bus_route[start_idx[i][0]][1]) + 1, sizeof(char));
                                memcpy(routes1[routes_idx1], bus_route[start_idx[i][0]][0], strlen(bus_route[start_idx[i][0]][0]) + 1);
                                strcat(routes1[routes_idx1], bus_route[start_idx[i][0]][1]);
                                routes_idx1 = routes_idx1 + 1;

                                common_station[common_station_idx] = explode('-', bus_route[start_idx[i][0]][1], &ret_num)[common_idx[k][0]];
                                common_station_idx = common_station_idx + 1;

                                routes2[routes_idx2] = calloc(strlen(bus_route[end_idx[j][0]][0]) + strlen(bus_route[end_idx[j][0]][1]) + 1, sizeof(char));
                                memcpy(routes2[routes_idx2], bus_route[end_idx[j][0]][0], strlen(bus_route[end_idx[j][0]][0]) + 1);
                                strcat(routes2[routes_idx2], bus_route[end_idx[j][0]][1]);
                                routes_idx2 = routes_idx2 + 1;
                            }
                        }
                    }
                }
            }

            printf("从%s站到%s站的一站换乘线路为：(查询结果为空则表示当前两站点没有一站换乘线路)\n", start_station, end_station);
            for(i = 0; i < routes_idx1; i++)
            {
                printf("第一程%s", routes1[i]);
                printf("-------在%s站下车同站换乘--------", common_station[i]);
                puts(routes2[i]);
                printf("\n");
            }

            free(routes1);
            free(routes2);
            free(common_station);

        }

运行结果

其他

由于C不想python这种抽象度比较高的语言有很多现成的API可以用，因此许多功能需要自己实现一下，除了上边写到的比较核心的代码，文中还用到了：

• 一个是生成一个全为某个值的矩阵

//将矩阵初始化为值全为-1
void init_matrix(int row, int column, int **matrix)
{
    int i, j;
    for(i = 0; i < row; i++)
    {
        for(j = 0; j < column; j++)
        {
            *((int*)matrix + column*i + j) = -1;
        }
    }
}

如何调用前边的main代码里有

• 一个是制定字符进行切割，这里网上有很多，我这里直接copy了这位大哥的，有兴趣可以看原文，下边把代码也放上

//返回一个 char *arr[], size为返回数组的长度,该函数用于切割字符串
char **explode(char sep, const char *str, int *size)
{
        int count = 0, i;
        for(i = 0; i < strlen(str); i++)
        {
                if (str[i] == sep)
                {
                        count ++;
                }
        }

        char **ret = calloc(++count, sizeof(char *));

        int lastindex = -1;
        int j = 0;

        for(i = 0; i < strlen(str); i++)
        {
                if (str[i] == sep)
                {
                        ret[j] = calloc(i - lastindex, sizeof(char)); //分配子串长度+1的内存空间
                        memcpy(ret[j], str + lastindex + 1, i - lastindex - 1);
                        j++;
                        lastindex = i;
                }
        }
        //处理最后一个子串
        if (lastindex <= strlen(str) - 1)
        {
                ret[j] = calloc(strlen(str) - lastindex, sizeof(char));
                memcpy(ret[j], str + lastindex + 1, strlen(str) - 1 - lastindex);
                j++;
        }

        *size = j;

        return ret;
}

同样如何调用主函数里都有

• 哦对了还有如何读取文件的函数…

//读入文件函数
void read_bustxt(char *file)
{
    int i,split_num;
    char mybus_route[100][500];
    char **ret = calloc(300, sizeof(char *));
    FILE * fp;
    //读取文件
    if((fp=fopen(file,"r"))==NULL)
    {
        printf("cannot open file\n");
        exit(0);
    }
    for(i=0;i<100;i++)                        // 设定 文件公交线路信息.txt 有300行
    {
        fscanf(fp,"%s",mybus_route[i]);                         //读文件的每一行

        if(strcmp(mybus_route[i],"END")==0)
            break;                       //判断是否结束
    }
    fclose(fp);
    for(i=0;i<36;i++)
    {
        ret = explode(',', mybus_route[i], &split_num);
        bus_route[i][0] = ret[0];
        bus_route[i][1] = ret[1];
    }
    free(ret);
}

结语

总之写的很粗糙，给以后还有需要的学弟们一点小小帮助吧。。。另外如果需要整个完整项目代码的话，点这里。