北京地铁乘坐路线查询
发布时间
阅读量：
阅读量
【问题描述】
编写一个程序实现北京地铁最短乘坐（站）线路查询，输入为起始站名和目的站名，输出为从起始站到目的站的最短乘坐站换乘线路。注：1. 要求采用Dijkstra算法实现；2）本题在实际测试时对数据文件进行了调整，使得输入的两站间只有一条最短路径。
【输入形式】
文件bgstations.txt为数据文件（可从课程网站中课程信息处下载），包含了北京地铁的线路及车站信息。其格式如下：
<地铁线路总条数>
<线路1> <线路1站数>
<站名1> <换乘状态>
<站名2> <换乘状态>
...
<线路2> <线路2站数>
<站名1> <换乘状态>
<站名2> <换乘状态>
...
说明：文件第一行为地铁总线路数；第二行第一个数为某条地铁线线号（如，1为1号线），第二个数为该条地铁线的总站数（如1号线共有23站），两数之间由一个空格分隔；第三行两个数据分别为地铁站名及换乘状态（0为非换乘站，1为换乘站），两数据间由一个空格分隔；以下同，依次为该线地铁其它站信息。在一条线路信息之后是下条地铁线路信息，格式相同。若某条地铁线为环线，则首站与末站信息相同（如北京地铁2号线，首站信息“西直门 1” ，末站信息为“西直门 1”）。例如本题提供的bgstations.txt文件（可从课程网站中课程信息处下载）内容如下：
12
1 23
苹果园 0
古城 0
八角游乐园 0
八宝山 0
玉泉路 0
五棵松 0
万寿路 0
公主坟 1
军事博物馆 1
木樨地 0
南礼士路 0
复兴门 1
西单 1
...
2 19
西直门 1
积水潭 0
鼓楼大街 1
...
西直门 1
...
该文件表明当前北京地铁共有12条线路（不含郊区线路），接着为每条线路信息。
打开当前目录下文件bgstations.txt，读入地铁线路信息，并从标准输入中读入起始站和目的站名（均为字符串，各占一行）。
【输出形式】
输出从起始站到目的站的乘坐信息，要求乘坐站数最少。换乘信息格式如下：
SSN-n1(m1)-S1-n2(m2)-...-ESN
其中：SSN和ESN分别为起始站名和目的站名；n为乘坐的地铁线路号，m为乘坐站数。
【样例输入】
西土城
北京西站
【样例输出】
西土城-10(1)-知春路-13(2)-西直门-4(2)-国家图书馆-9(4)-北京西站
【样例说明】
打开文件bgstations.txt，读入地铁线路信息，并从标准输入中读入查询起始站名为“西土城”，目的站名为“北京西站”。程序运行结果两站间最少乘坐站数的乘坐方式为“西土城站乘坐10号线1站至知春路站换乘13号线乘坐2站至西直门站换乘4号线乘坐2站至国家图书馆站换乘9号线乘坐4站至北京西站”。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSTRLEN 41
#define INF 0x3f3f3f3f
#define MAXSTATNUM 500
typedef struct _Edge
{
int adjseq;
int weight;
int lineseq;
struct _Edge *next;
} Edge;
typedef struct _Station
{
char name[MAXSTRLEN];
int trans;
int lineseq;
int statseq;
Edge *link;
} Station;
typedef struct _Line
{
int size;
int seq;
int isloop;
struct _Station *list;
} Line;
typedef struct _Railway
{
int size;
struct _Station list[MAXSTATNUM];
} Railway;
void insert_Edge(Station *head, int end, int lineseq)
{
Edge *rear = head->link;
Edge *newEdge = (Edge *)malloc(sizeof(Edge));
if (newEdge == NULL)
{
printf("allocation failure");
exit(1);
}
newEdge->weight = 1;
newEdge->lineseq = lineseq;
newEdge->adjseq = end;
newEdge->next = NULL;
if (rear == NULL)
{
head->link = newEdge;
}
else
{
while (rear->next != NULL) rear = rear->next; // reach the rear
rear->next = newEdge; // add the new Edge at the rear
}
}
void input_Station(Railway *railway, Line line, int seq_inline, int seq_inrail)
{// input a station in a processed line to a railway system, and in this case seq_inrail == railway->size
strcpy(railway->list[seq_inrail].name, line.list[seq_inline].name);
railway->list[seq_inrail].trans = line.list[seq_inline].trans;
railway->list[seq_inrail].lineseq = line.seq;
railway->list[seq_inrail].statseq = seq_inrail;
railway->list[seq_inrail].link = NULL;
railway->size++;
if (seq_inline == 0)
{// the first station
if (line.isloop)
{// the line is a loop, with the same station as start and end
insert_Edge(&(railway->list[seq_inrail]), line.list[1].statseq, line.seq);
insert_Edge(&(railway->list[seq_inrail]), line.list[line.size - 2].statseq, line.seq);
}
else
{// the start station in a non-loop has no previous station
insert_Edge(&(railway->list[seq_inrail]), line.list[1].statseq, line.seq);
}
}
else if (seq_inline == line.size - 1 - line.isloop)
{// the last station
if (line.isloop)
{// the line is a loop, with the same station as start and end
insert_Edge(&(railway->list[seq_inrail]), line.list[0].statseq, line.seq);
insert_Edge(&(railway->list[seq_inrail]), line.list[line.size - 3].statseq, line.seq);
}
else
{// the last station in a non-loop has no following station
insert_Edge(&(railway->list[seq_inrail]), line.list[line.size - 2].statseq, line.seq);
}
}
else
{
insert_Edge(&(railway->list[seq_inrail]), line.list[seq_inline + 1].statseq, line.seq);
insert_Edge(&(railway->list[seq_inrail]), line.list[seq_inline - 1].statseq, line.seq);
}
}
void update_Station(Railway *railway, Line line, int seq_inline, int seq_inrail)
{// update a station's edges in a railway system
if (seq_inline == 0)
{// the first station
if (line.isloop)
{// the line is a loop, with the same station as start and end
insert_Edge(&(railway->list[seq_inrail]), line.list[1].statseq, line.seq);
insert_Edge(&(railway->list[seq_inrail]), line.list[line.size - 2].statseq, line.seq);
}
else
{// the start station in a non-loop has no previous station
insert_Edge(&(railway->list[seq_inrail]), line.list[1].statseq, line.seq);
}
}
else if (seq_inline == line.size - 1 - line.isloop)
{// the last station
if (line.isloop)
{// the line is a loop, with the same station as start and end
insert_Edge(&(railway->list[seq_inrail]), line.list[0].statseq, line.seq);
insert_Edge(&(railway->list[seq_inrail]), line.list[line.size - 3].statseq, line.seq);
}
else
{// the last station in a non-loop has no following station
insert_Edge(&(railway->list[seq_inrail]), line.list[line.size - 2].statseq, line.seq);
}
}
else
{
insert_Edge(&(railway->list[seq_inrail]), line.list[seq_inline + 1].statseq, line.seq);
insert_Edge(&(railway->list[seq_inrail]), line.list[seq_inline - 1].statseq, line.seq);
}
}
int in_Rail(Railway railway, char name[])
{// find the station and return its sequence number in railsystems
int iter_rail;
for (iter_rail = 0; iter_rail < railway.size; iter_rail++)
{
if (strcmp(railway.list[iter_rail].name, name) == 0)
return iter_rail;
}
return -1; // not found
}
void input_Line(Railway *railway, Line line)
{// inputting a processed line into a railway system
int seq_inline, seq_inrail;
if (railway->size == 0) // empty system
{// initialize a railway system
for (seq_inline = 0; seq_inline < line.size; seq_inline++)
{// in an empty railway system, the inline seq equals the inrail seq
railway->list[seq_inline].link = NULL;
input_Station(railway, line, seq_inline, seq_inline);
}
}
else
{
int seq_fromsize = railway->size;
for (seq_inline = 0; seq_inline < line.size - line.isloop; seq_inline++)
{
seq_inrail = in_Rail(*railway, line.list[seq_inline].name);
if (seq_inrail != -1)
{// this station already exists in the railway system
update_Station(railway, line, seq_inline, seq_inrail);
}
else
{// this is a new station
input_Station(railway, line, seq_inline, seq_fromsize);
seq_fromsize++;
}
}
}
}
void process_Line(Railway *railway, Line *line)
{// pre-process the statseq of the stations in a line (for the inputting of stations)
int seq_inline, seq_inrail;
if (railway->list == NULL)
{// empty railway system
for (seq_inline = 0; seq_inline < line->size; seq_inline++)
line->list[seq_inline].statseq = seq_inline;
}
else
{
int seq_fromsize = railway->size;
for (seq_inline = 0; seq_inline < line->size; seq_inline++)
{
seq_inrail = in_Rail(*railway, line->list[seq_inline].name);
if (seq_inrail != -1)
{// this station already exists in the railway system
line->list[seq_inline].statseq = seq_inrail;
}
else
{// new station
line->list[seq_inline].statseq = seq_fromsize;
seq_fromsize++;
}
}
}
}
void Dijkstra(Railway *railway, char startname[], char destname[], int path[])
{
int start = in_Rail(*railway,startname);
int dest = in_Rail(*railway, destname);
int *dist = (int *)malloc(railway->size*sizeof(int));
// dist[] stores the minimum distance from start to the indexed station
// 0 means this station has been enclosed
memset(dist, INF, railway->size*sizeof(int));
dist[start] = 0;
Edge *link = railway->list[start].link;
while (link != NULL)
{
dist[link->adjseq] = link->weight;
path[link->adjseq] = start;
link = link->next;
}
while (dist[dest] == INF)
{
int min = INF, minstat = dest, iter;
for (iter = 0; iter < railway->size; iter++)
{
if (dist[iter] != 0 && dist[iter] < min)
{// not enclosed, and find the minimum
min = dist[iter];
minstat = iter;
}
}
link = railway->list[minstat].link;
if (link == NULL) exit(1);
while (link != NULL)
{
if (dist[minstat] + link->weight < dist[link->adjseq])
{
dist[link->adjseq] = dist[minstat] + link->weight;
path[link->adjseq] = minstat;
}
link = link->next;
}
dist[minstat] = 0;
}
free(dist);
/* just for debugging
while (dest != start)
{
printf("%s<-",railway->list[dest].name);
dest = path[dest];
}
printf("%s\n", railway->list[start].name);
*/
}
int get_Lineseq(Railway railway, int stat1, int stat2)
{
Edge *link = railway.list[stat1].link;
while (link != NULL)
{
if (link->adjseq == stat2)
return link->lineseq;
link = link->next;
}
return -1; // not connected
}
void depict_Path(Railway *railway, int start, int dest, int path[])
{
int *track = (int *)malloc(railway->size*sizeof(int));
memset(track, INF, railway->size*sizeof(int));
int iter = 0;
while (dest != start)
{
track[iter++] = dest;
dest = path[dest];
}
track[iter] = start;
int i = 0, j = iter;
while (i < j)
{// reverse track[]
int tmp;
tmp = track[j];
track[j] = track[i];
track[i] = tmp;
i++, j--;
}
/*for (i = 0; i <= iter; i++)
printf("%s %d -", railway->list[track[i]].name, railway->list[track[i]].lineseq);*/
int currstats = 1;
printf("%s-",railway->list[track[0]].name);
for (i = 1; i < iter; i++)
{
if ( get_Lineseq(*railway, railway->list[track[i - 1]].statseq, railway->list[track[i]].statseq)
!= get_Lineseq(*railway, railway->list[track[i + 1]].statseq, railway->list[track[i]].statseq))
{// the previous station and the next one is not on the same line: transfering
printf("%d(%d)-%s-", get_Lineseq(*railway, railway->list[track[i - 1]].statseq,
railway->list[track[i]].statseq), currstats, railway->list[track[i]].name);
currstats = 1;
}
else
{
currstats++;
}
}
printf("%d(%d)-%s\n", get_Lineseq(*railway, railway->list[track[i - 1]].statseq,
railway->list[track[i]].statseq), currstats, railway->list[track[iter]].name);
}
int main()
{
FILE *fin;
fin = fopen("bgstations.txt","r");
if (fin == NULL) exit(1);
int linenum, lineseq, statnum, trans;
int i, j;
char statname[MAXSTRLEN];
Railway *beijing = (Railway *)malloc(sizeof(Railway));
beijing->size = 0;
Line *newline = (Line *)malloc(sizeof(Line));
fscanf(fin,"%d\n",&linenum);
for (i = 1; i <= linenum; i++)
{
fscanf(fin, "%d %d\n",&lineseq, &statnum);
newline->seq = lineseq;
newline->size = statnum;
newline->isloop = 0;
newline->list = (Station *)malloc(statnum*sizeof(Station));
for (j = 0; j < statnum; j++)
{
fscanf(fin, "%s %d\n", statname, &trans);
newline->list[j].lineseq = i;
strcpy(newline->list[j].name,statname);
newline->list[j].trans = trans;
}
if (strcmp(newline->list[0].name, statname) == 0)
newline->isloop = 1;
process_Line(beijing, newline);
input_Line(beijing, *newline);
free(newline->list);
fscanf(fin, "\n");
}
char startname[MAXSTRLEN], destname[MAXSTRLEN];
scanf("%s",startname);
scanf("%s",destname);
int *path = (int *)malloc(beijing->size*sizeof(int));
Dijkstra(beijing, startname, destname, path);
depict_Path(beijing, in_Rail(*beijing, startname), in_Rail(*beijing, destname), path);
/* just for debugging
for (i = 0; i < beijing->size; i++)
{
printf("%s %d %d\n", beijing->list[i].name, beijing->list[i].statseq, beijing->list[i].trans);
Edge *curr = beijing->list[i].link;
while (curr != NULL)
{
printf(" %s %d %d\n", beijing->list[curr->adjseq].name, curr->adjseq, beijing->list[curr->adjseq].trans);
curr = curr->next;
}
}*/
free(newline);
free(path);
fclose(fin);
return 0;
}全部评论 (0)
还没有任何评论哟~