公交线路提示

根据真实南京公交线路图，建立南京主要公交线路图的存储结构。

[基本要求]

（1）输入任意两站点，给出转车次数最少的乘车路线。

（2）输入任意两站点，给出经过站点最少的乘车路线。

用地图结构体存储站点及公交车。建立公交车结构体，存放路过站点的编号及公交车编号。建立站点结构体，储存读取过程中新出现的站点编号及路过该站点的公交车编号。

求转车次数最少 采用广度优先遍历算法，判断起点所涉及的每辆公交车经过的所有站点，如果有终点，则无需转车。若无终点，则让起点所涉及的每辆公交车经过的所有站点进入队列，通过Visited数组判断该站点是否已经访问过。队列元素出队，继续判断该点所涉及的每辆公交车经过的所有站点，重复以上步骤，直至找到所需终点。

求经过站数最少 依然采用广度优先遍历算法，判断起点所涉及的每辆公交车经过的起点前后的站点，如果是终点，则经过站数最少。若无终点，则让起点所涉及的每辆公交车经过的起点前后的站点进入队列，通过Visited数组判断该站点是否已经访问过。队列元素出队，继续判断该点所涉及的每辆公交车经过的该点前后的站点，重复以上步骤，直至找到所需终点。

#include <stdio.h>
#include <windows.h>
typedef int Status;

typedef struct Bus
{
    int No;        //该公交车的编号
    int count;     //该公交车经过的站点数量
    int route[80]; //该公交车的路线
} Bus;             //1000
typedef struct Station
{
    short int bus[35]; //经过该站点的公交车的编号
    int count;         //经过该站点的公交车数量
    char name[60];     //站点名称
} Station;             //12000
typedef struct Map
{
    Bus bus[1000];          //该城市的公交车
    Station station[10000]; //该城市的站点
    int BusCount;           //公交车数量
    int StationCount;       //站点数量
} Map;
typedef struct element
{
    int bus;
    int before;
    int cur;
} element;
typedef struct QNode
{
    element data;
    QNode *next;
} QNode, *QueuePtr;
typedef struct
{
    QueuePtr front; //队头指针
    QueuePtr rear;  //队尾指针
} LinkQueue;

Status InitQueue(LinkQueue &Q);          //构造一个空队列Q
Status EnQueue(LinkQueue &Q, element e); //插入元素e作为新的队尾元素，前提Q存在
element DeQueue(LinkQueue &Q);           //若队列不空，删除队头元素,返回其值，前提Q存在
Status GetMap(Map &M);
Status InitMap(Map &M);
int locate_station(Map &M, char name[30]);
int locate_bus(Map &M, int No);
Status GetBusStation(Map &M, char temp[60]);
Status LeastTransfers(Map &M, char name_1[60], char name_2[60]);
Status TraversalSite_CD(Map &M, int v1, int v2);
Status LeastSite(Map &M, char name_1[60], char name_2[60]);
Status TraversalSite_AD(Map &M, int v1, int v2);
void Print(Map M);
//南堡公园站,中山北路萨家湾站,西宁社区站
int visited[10000] = {0};
int main()
{
    Map M;
    InitMap(M);
    GetMap(M);
    while (1)
    {
        system("cls");
        char name_1[60], name_2[60];
        printf("\t\t\t欢迎使用南京公交线路查询系统(如要退出系统,请输入退出)\n");
        printf("请输入起点:");
        scanf("%s", name_1);
        if (strcmp(name_1, "退出") == 0)
            break;
        if (!locate_station(M, name_1))
        {
            printf("未找到该站点,请检查输入是否有误!\n");
            system("pause");
            continue;
        }
        printf("请输入终点:");
        scanf("%s", name_2);
        if (strcmp(name_2, "退出") == 0)
            break;
        if (!locate_station(M, name_2))
        {
            printf("未找到该站点,请检查输入是否有误!\n");
            system("pause");
            continue;
        }
        printf("\n最少站数路线\n");
        LeastSite(M, name_1, name_2);
        printf("\n最少转车路线\n");
        LeastTransfers(M, name_1, name_2);
        system("pause");
    }
    system("pause");
    return 0;
}
Status LeastSite(Map &M, char name_1[60], char name_2[60])
{
    int v1 = locate_station(M, name_1);
    for (int i = 1; i < 10000; i++)
    {
        visited[i] = 0;
    }
    int v2 = locate_station(M, name_2);
    TraversalSite_AD(M, v2, v1);
}
Status TraversalSite_AD(Map &M, int v1, int v2)
{
    element e[8000];
    for (int i = 1; i < 8000; i++)
    {
        e[i].cur = i;
        e[i].bus = 0;
    }
    element e0;
    int count = 1;
    LinkQueue Q;
    InitQueue(Q);
    EnQueue(Q, e[v1]);
    visited[v1] = 1;
    while (1)
    {
        int k = 1;
        count++;
        e0.cur = -1;
        EnQueue(Q, e0);
        while (Q.front != Q.rear)
        {
            v1 = DeQueue(Q).cur;
            if (v1 == -1)
                break;
            for (int i = 1; i <= M.station[v1].count; i++)
            {
                int bus1 = locate_bus(M, M.station[v1].bus[i]);
                for (int j = 1; j <= M.bus[bus1].count; j++)
                {
                    if (M.bus[bus1].route[j] == v1)
                    {
                        if (M.bus[bus1].route[j + 1] == v2 || M.bus[bus1].route[j - 1] == v2)
                        {
                            int bus = e[v1].bus;
                            printf("最少经过%d个站点\n", count);
                            printf("%s(起点,乘坐%d路公交车)-->", M.station[v2].name, M.bus[bus1].No);
                            //printf("%s(乘坐%d路公交车)-->", M.station[v1].name, M.bus[bus1].No);
                            count--;
                            while (count--)
                            {
                                if (count == 0)
                                    printf("%s(终点)\n\n", M.station[v1].name);
                                else
                                    printf("%s(乘坐%d路公交车)-->", M.station[v1].name, bus);
                                v1 = e[v1].before;
                                bus = e[v1].bus;
                            }
                            return 1;
                        }

                        if (!visited[M.bus[bus1].route[j - 1]] && j - 1 > 0)
                        {
                            e[M.bus[bus1].route[j - 1]].bus = M.bus[bus1].No;
                            e[M.bus[bus1].route[j - 1]].before = v1;
                            EnQueue(Q, e[M.bus[bus1].route[j - 1]]);
                            visited[M.bus[bus1].route[j - 1]] = 1;
                        }
                        if (!visited[M.bus[bus1].route[j + 1]] && j + 1 <= M.bus[bus1].count)
                        {
                            e[M.bus[bus1].route[j + 1]].bus = M.bus[bus1].No;
                            e[M.bus[bus1].route[j + 1]].before = v1;
                            EnQueue(Q, e[M.bus[bus1].route[j + 1]]);
                            visited[M.bus[bus1].route[j + 1]] = 1;
                        }
                        break;
                    }
                }
            }
        }
    }
}
Status LeastTransfers(Map &M, char name_1[60], char name_2[60])
{
    int v1 = locate_station(M, name_1);
    for (int i = 1; i < 10000; i++)
    {
        visited[i] = 0;
    }
    int v2 = locate_station(M, name_2);
    TraversalSite_CD(M, v2, v1);
}
Status TraversalSite_CD(Map &M, int v1, int v2) //Adjacency point diffusion邻接点扩散 Connected point diffusion连通点扩散
{
    element e[8000];
    for (int i = 1; i < 8000; i++)
    {
        e[i].cur = i;
        e[i].bus = 0;
    }
    element e0;
    int count = 1;
    LinkQueue Q;
    InitQueue(Q);
    EnQueue(Q, e[v1]);
    visited[v1] = 1;
    while (1)
    {
        int k = 1;
        count++;
        e0.cur = -1;
        EnQueue(Q, e0);
        while (Q.front != Q.rear)
        {
            v1 = DeQueue(Q).cur;
            if (v1 == -1)
                break;
            for (int i = 1; i <= M.station[v1].count; i++)
            {
                int bus1 = locate_bus(M, M.station[v1].bus[i]);
                for (int j = 1; j <= M.bus[bus1].count; j++)
                {
                    if (M.bus[bus1].route[j] == v2)
                    {
                        int bus2;
                        bus2 = locate_bus(M, e[v1].bus);
                        printf("最少转%d次车\n", count - 1);
                        printf("%s(起点,乘坐%d路公交车)-->", M.station[v2].name, M.station[v1].bus[i]);
                        --count;
                        while (count--)
                        {
                            if (count == 0)
                                printf("%s(终点)\n\n", M.station[v1].name);
                            else
                                printf("%s(换乘%d路公交车)-->", M.station[v1].name, M.bus[bus2].No);
                            v1 = e[v1].before;
                            bus2 = locate_bus(M, e[v1].bus);
                        }
                        return 1;
                    }
                    if (!visited[M.bus[bus1].route[j]])
                    {
                        e[M.bus[bus1].route[j]].bus = M.bus[bus1].No;
                        e[M.bus[bus1].route[j]].before = v1;
                        EnQueue(Q, e[M.bus[bus1].route[j]]);
                        visited[M.bus[bus1].route[j]] = 1;
                    }
                }
            }
        }
    }
}
Status GetBusStation(Map &M, char temp[60])
{
    int index = locate_station(M, temp);
    if (!index)
    {
        strcpy(M.station[++M.StationCount].name, temp);
        index = M.StationCount;
    }
    M.bus[M.BusCount].route[M.bus[M.BusCount].count] = index;
    M.station[index].bus[++M.station[index].count] = M.bus[M.BusCount].No;
    for (int i = 0; i < 60; i++)
    {
        temp[i] = '\0';
    }
    return index;
}
int locate_station(Map &M, char name[60])
{
    for (int i = 1; i <= M.StationCount; i++)
    {
        if (strcmp(M.station[i].name, name) == 0)
            return i;
    }
    return 0;
}
int locate_bus(Map &M, int No)
{
    for (int i = 1; i <= M.BusCount; i++)
    {
        if (M.bus[i].No == No)
            return i;
    }
    return 0;
}
void Print(Map M)
{
    for (int i = 1; i <= M.BusCount; i++)
    {
        printf("%d路\t", M.bus[i].No);
        for (int j = 1; j <= M.bus[i].count; j++)
        {
            printf("%s ", M.station[M.bus[i].route[j]].name);
        }
        printf("\n");
    }
}
Status InitMap(Map &M)
{
    M.BusCount = 0;
    M.StationCount = 0;
    return 1;
    for (int i = 0; i < 1000; i++)
    {
        M.bus[i].count = 1;
    }
    for (int i = 0; i < 15000; i++)
    {
        M.station[i].count = 0;
    }
}
Status GetMap(Map &M)
{
    int k = 0;
    char temp[60];
    char ch;
    FILE *fp;
    if ((fp = fopen("南京公交线路.txt", "r")) == NULL)
    {
        printf("can't open this file\n");
        system("pause");
        exit(0);
    }
    for (int i = 1; i <= 1000; i++)
    {
        M.bus[i].count = 1;
    }
    fscanf(fp, "%d", &M.bus[++M.BusCount].No);
    while (ch != ' ')
        ch = fgetc(fp);
    while (1)
    {
        ch = fgetc(fp);
        if (feof(fp))
        {
            GetBusStation(M, temp);
            break;
        }
        if (ch == '\n')
        {
            GetBusStation(M, temp);
            //printf("%s",bus[i].route[j]);
            k = 0;
            char ch2;
            ch2 = fgetc(fp);
            if (feof(fp))
                break;
            fseek(fp, -1L, 1);
            fscanf(fp, "%d", &M.bus[++M.BusCount].No);
            while (ch != ' ')
                ch = fgetc(fp);
            continue;
        }
        if (ch == ' ')
            continue;
        if (ch == ',')
        {
            GetBusStation(M, temp);
            //printf("%s",bus[i].route[j]);
            k = 0;
            M.bus[M.BusCount].count++;
            continue;
        }
        temp[k++] = ch;
    }
    fclose(fp);
}
Status InitQueue(LinkQueue &Q)
{
    Q.front = (QueuePtr)malloc(sizeof(QNode));
    if (!Q.front)
        exit(-2);
    Q.front->next = NULL;
    Q.rear = Q.front;
    return true;
}
Status EnQueue(LinkQueue &Q, element e)
{
    QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); //开辟新结点
    if (!p)
        exit(-2);
    p->data = e;
    p->next = NULL;
    Q.rear->next = p;
    Q.rear = p;
    return true;
}
element DeQueue(LinkQueue &Q)
{
    element e;
    if (Q.front == Q.rear)
    {
        printf("栈空");
        system("pause");
        exit(0);
    }
    QueuePtr p = Q.front->next;
    e = p->data;
    Q.front->next = p->next;
    if (Q.rear == p)
        Q.rear = Q.front;
    free(p);
    return e;
}

 

测试结果