查看原文
其他

程序员有话说 | 程序猿在乘地铁的时候都在想什么?

宋广泽 程序人生 2019-02-14

作者 | 宋广泽

本文系作者投稿

责编 | 胡巍巍

程序猿在乘地铁的时候都在想什么?

二话不说,先上一张青岛地铁交通图。

我是个在青岛上大学的计算机专业的大二学生,有一次我在烟台的朋友和他的女朋友坐高铁过来找我玩,他在青岛北站下高铁。

我从青岛二中站上车,准备去青岛北站接他,去接他前我已经知道了青岛地铁3号线的一端是青岛站,另一端是青岛北站,于是我选择了相信自己,而不是高德地图。

从上面那个地铁交通图中也能看出来,想要到三号线上去要先换乘到2号线,再换乘到3号线,到了苗岭路站,走到2号线的站台,看着安全门上方的一维交通图,我看到了两个可以换乘到3号线的换乘站,分别是五四广场和李村。

并且两个换乘站距离苗岭路差不多,开往五四广场方向的列车先到了,我想都没想就上去了。

等真的到了五四广场,哭都来不及呀。五四广场开往青岛北站,也要经过李村!!!并且李村距离青岛北站只隔着3站,而五四广场距离青岛北站整整隔着14站!!!

于是,原本一个小时就能到青岛北站的,却用了两个多小时,白白让朋友和他的女朋友等了我很长一段时间。

我决定,决不能让这种悲剧重演。。。。。。这个学期学了数据结构,就想着用图的知识和C/C++来解决我的问题。

首先,将实际的站点信息抽象成一个结构体数组,将实际站点与数组中的元素一一对接起来。

初始化这个结构体数组:

//站点信息

struct

{


   int id;

   int line;

   int istransfer;

   char staname[16];

}sta[63]=

{

   {1,3,0,"青岛北站"},

   {2,3,0,"永平路"},

   {3,3,0,"振华路"},

   {4,3,0,"君峰路"},

   {5,3,1,"李村"},

   {6,3,0,"万年泉路"},

   {7,3,0,"海游路"},

   {8,3,0,"地铁大厦"},

   {9,3,0,"长沙路"},

   {10,3,0,"双山"},

   {11,3,0,"清江路"},

   {12,3,0,"错埠岭"},

   {13,3,0,"敦化路"},

   {14,3,0,"宁夏路"},

   {15,3,0,"江西路"},

   {16,3,1,"五四广场"},

   {17,3,0,"延安三路"},

   {18,3,0,"太平角公园"},

   {19,3,0,"中山公园"},

   {20,3,0,"汇泉广场"},

   {21,3,0,"人民会堂"},

   {22,3,0,"青岛站"},

   {23,2,0,"泰山路"},

   {24,2,0,"利津路"},

   {25,2,0,"台东"},

   {26,2,0,"海信桥"},

   {27,2,0,"芝泉路"},

   {28,2,0,"浮山所"},

   {29,2,0,"燕儿岛路"},

   {30,2,0,"高雄路"},

   {31,2,0,"麦岛"},

   {32,2,0,"海游路"},

   {33,2,0,"海川路"},

   {34,2,0,"海安路"},

   {35,2,0,"石老人浴场"},

   {36,2,1,"苗岭路"},

   {37,2,0,"同安路"},

   {38,2,0,"辽阳东路"},

   {39,2,0,"东韩"},

   {40,2,0,"华楼山路"},

   {41,2,0,"枣山路"},

   {42,2,0,"李村公园"},

   {43,11,0,"会展中心"},

   {44,11,0,"青岛二中"},

   {45,11,0,"青岛科大"},

   {46,11,0,"张村"},

   {47,11,0,"枯桃"},

   {48,11,0,"海洋大学"},

   {49,11,0,"世博园"},

   {50,11,0,"北宅"},

   {51,11,0,"北九水"},

   {52,11,0,"庙石"},

   {53,11,0,"浦里"},

   {54,11,0,"鳌山卫"},

   {55,11,0,"山东大学"},

   {56,11,0,"蓝色硅谷"},

   {57,11,0,"水泊"},

   {58,11,0,"博览中心"},

   {59,11,0,"温泉东"},

   {60,11,0,"皋虞"},

   {61,11,0,"臧村"},

   {62,11,0,"钱谷山"},

   {63,11,0,"鳌山湾"}

};

然后选取邻接矩阵作为图的载体,i行j列上的元素为1表示ID为i的站点和ID为j的站点是直接相连的,i行j列上的元素为0表示ID为i的站点和站点为j的站点不是直接相连的。

声明一个表示图的连接关系矩阵的二维数组,并将这个邻接矩阵初始化。

为了让矩阵的行列和站点的ID更好地对应起来,站点ID即为行(或列)的值,第0行和第0列不表示邻接关系。

//表示连接关系的矩阵

int nodelist[65][65];

//将地图初始化

void readgraph()

{

   //初始化站点总数

   n=63;

   //先将矩阵所有元素置零

   for(i=0;i<65;i++)

       for(j=0;j<65;j++)

           nodelist[i][j]=0;

   //初始化3号线

   for(i=1;i<22;i++)

   {

       nodelist[i][i+1]=1;

       nodelist[i+1][i]=1;

   }

   //初始化2号线

   for(i=23;i<42;i++)

   {

       nodelist[i][i+1]=1;

       nodelist[i+1][i]=1;

   }

   //初始化11号线

   for(i=43;i<63;i++)

   {

       nodelist[i][i+1]=1;

       nodelist[i+1][i]=1;

   }

   //初始化换乘站点的连接信息

   nodelist[16][27]=1;//连接五四广场和芝泉路

   nodelist[27][16]=1;//连接芝泉路和五四广场

   nodelist[16][28]=1;//连接五四广场和浮山所

   nodelist[28][16]=1;//连接浮山所和五四广场

   nodelist[5][42]=1;//连接李村和李村公园

   nodelist[42][5]=1;//连接李村公园和李村

   nodelist[5][41]=1;//连接李村和枣山路

   nodelist[41][5]=1;//连接枣山路和李村

   nodelist[36][43]=1;//连接苗岭路和会展中心

   nodelist[43][36]=1;//连接会展中心和苗岭路

}

经过初始化后的矩阵图(部分):


解析:整个地铁交通图的站点过于的多,一个一个地初始化代码过于庞杂。某一条地铁线路上的列车就只在一条线路上行使,这给了我启发,可以通过for循环来批量连接各个站点,就像列车沿着某一条线路行驶将该线路串起来一样,从3号线开始,先将3号线串起来,再将2号线串起来,再将1号线串起来,依次将nodelist[i][i+1]置为1,最后统一处理换乘站点的连接信息。

再就是最为关键的环节——求解最短路径。

求解最短路径的算法用到了图的广度优先搜索,学过数据结构的人都知道,广度优先搜索算法依托的数据结构是队列,因此我们先要解决好队列的问题。

如果使用的是C++的编译环境,可以选择#include<queue>;如果使用的是纯C语言的编译环境,队列就需要建一个<Queue.h>头文件自己去实现,下面是纯C语言实现<Queue.h>的代码:

#ifndef QUEUE_H_INCLUDED

#define QUEUE_H_INCLUDED

//队列结构体

typedef struct

{


   int q[10000];

   //队头、队尾

   int f,r;

}queue;

//入队操作

void enq(queue *Q,int x)

{

   Q->q[Q->r]=x;

   if(Q->r==9999)

       Q->r=0;

   else

       Q->r++;

   if(Q->r==Q->f)

       printf("队溢出! ");

}

//取队头元素

int front(queue *Q)

{

   if(Q->r==Q->f)

   {

       printf("front函数:队空! ");

       return 0;

   }

   else

       return Q->q[Q->f];

}

//出队操作

void dep(queue *Q)

{

   if(Q->r==Q->f)

       printf("dep函数:队空! ");

   else

   {

       if(Q->f==9999)

           Q->f=0;

       else

           Q->f++;

   }

}

//判断队列是否为空队列

int qempty(queue Q)

{

   if(Q.f==Q.r)

       return 1;

   else

       return 0;

}

#endif // QUEUE_H_INCLUDED

队列的一系列操作被实现后,就可以通过图的广度优先遍历求解最短路径了,最短路径将被保存在整型数组z[65]中。

观察寻找最短路径函数中的while循环,每找到一个可访问的结点,就将该结点上一个结点的id存放在该可访问结点对应的z数组元素中。

例如,结点j可访问,结点j是通过结点i访问到的,那么就让z[j]=i。

另外还有一些其他的全局变量:

//队列声明

queue Q;

//队列声明

queue Q;

//起点和终点

int a,b;

//站点总数

int n;

int i,j,x,y;

//判断是否结束的标志

int finished;

求解最短路径的函数:

//寻找最短路径

void shortest(int a,int b)

{

   if(a==b)

       nodelist[a][a]=2;

   else

   {

       enq(&Q,a);

       nodelist[a][a]=2;

       finished=0;

       while(!qempty(Q)&&!finished)

       {

           //取队头结点

           a=front(&Q);

           //删除一个队头结点

           dep(&Q);

           //从ID为1的结点开始check

           j=1;

           while(j<=n&&!finished)

           {

               //必须保证结点j和刚出队的结点a直接相连

               //且结点j没有被访问过

               if(nodelist[a][j]==1&&nodelist[j][j]!=2)

               {

                   enq(&Q,j);

                   //标志结点j已经被访问过

                   nodelist[j][j]=2;

                   //保证能够通过z[j]索引到结点a

                   z[j]=a;

                   //广度优先遍历到达终点

                   if(j==b)

                   {

                       finished=1;

                   }

               }

               if(!finished)

                   j++;

           }

       }

       if(!finished)

           printf("没有路径!");

   }

}

解析:从顶点A开始,依次访问与A邻接的顶点VA1,VA2,,...,VAK,将上述顶点访问一遍后,若没有访问B,则继续访问与VA1邻接的顶点VA11,VA12,...,VA1M,再访问与VA2邻接的顶点......如此下去,直到找到B。最先到达B的路径,一定是边数最少的路径。

采用队列记录被访问过的顶点,每次访问与队头相邻接的顶点,然后将队头顶点出队。

若队空,则说明A到B不存在通路。其中,nodelist[i][i]=1表示站点id为i的顶点在寻找最短路径的过程中已经被访问过。

最后将最短路径显示到屏幕上,这一部分不同的界面有不同的显示方法,下面是DOS界面显示最短路径的函数:

void writepath(int a,int b)

{

   i=b;

   while(i!=a)

   {

       if(sta[i-1].istransfer)

       {

           printf("|换乘|");

       }

       else

       {

           printf("|%d号线|",sta[i-1].line);

       }

       printf("%s <- ",sta[i-1].staname);

       i=z[i];

   }

   if(!sta[a-1].istransfer)

   {

       printf("|%d号线|",sta[a-1].line);

   }

   printf("%s",sta[a-1].staname);

   printf(" ");

}

下面是DOS界面下的运行结果:

下面是将算法搬运到QT中,用QT将数据可视化后的运行结果:

完整的DOS界面源代码我已经上传到了https://paste.ubuntu.com/p/PjNfKdS9Gj/,为了大家方便复制粘贴,我将所有的自定义头文件的内容都搬运到了一个文件中。

整个系统还有个模糊搜索站点的功能,用的是BF算法,在完整的DOS界面源代码中也有体现。

同理,大家可以自己动手实现以下北京地铁、上海地铁、广州地铁、郑州地铁、西安地铁......的交通咨询系统。

作者:宋广泽,青岛某普通一本大学计算机专业在校生,本科在读,学生开发者。喜欢用C/C++编写有意思的程序,解决实际问题。

 热 文 推 荐 

谁人来帮库克卖“苹果”?

程序员的年度未解之谜:加班背锅的是我,得优秀员工的却是他

华为波兰销售总监被捕!

程序员崩溃了!想拿的年终奖怎么说黄就黄?!

云漫圈:什么是微服务?

STO不会火,比特大陆不会死,币安会去非洲:区块链行业的63个预测

清华北大“世界排名断崖式下跌”?

刚刚!程序员集体荣获2个冠军,这份2018&nbsp;IT报告还说这些!

print_r('点个好看吧!');
var_dump('点个好看吧!');
NSLog(@"点个好看吧!");
System.out.println("点个好看吧!");
console.log("点个好看吧!");
print("点个好看吧!");
printf("点个好看吧!");
cout << "点个好看吧!" << endl;
Console.WriteLine("点个好看吧!");
fmt.Println("点个好看吧!");
Response.Write("点个好看吧!");
alert("点个好看吧!")
echo "点个好看吧!"

点击“阅读原文”,打开 CSDN App 阅读更贴心!

喜欢就点击“好看”吧

    您可能也对以下帖子感兴趣

    文章有问题?点此查看未经处理的缓存