（1小时数据结构）数据结构c++描述（十三）--- 队列应用（电路布线/ 迷宫最短路径）代码详细解析
首先有关队列的定义在上节中已经定义：链表描述
本章的应用使用的是队列的链表描述，若大家不想使用自己定义的，可以将代码使用STL中的queue来代替。
电路布线/迷宫最短路径
如图，我们想从a到b，要如何到达b呢，产生一个最短路径就是今天教大家的这个用法，方法采用了：深度优先探索法，与回溯法。
听着方法很高端，其实很简单的.我们在初始位置的上，下，左，右，分别加1，遇到黑色的障碍不加，有数的不加，然后从下个位置开使重复的动作，知道遇到终点，就是最短路径了，这就是深度优先探索法。
找到终点后，从最后的位置，往回找数，依次找比上个数小1的数，让后把路径记录下来，这就是回溯法。
是不是非常简单呢，话不多说开始上代码吧：
最短路径FindPath ：
/*
数组结构中的 队列应用 电路布线
对应书中代码：数据结构算法与应用c++描述
程序编写：比卡丘不皮
编写时间： 2020年7月16日 13:37:58
*/
/***
说明，书中说要定义Position class, 为了方便我才用stl 中的东西代替。
队列使用的是书中编写的程序。
主要对应的应用
***/
#pragma once
#include <iostream>
#include "LinkedQueue.h"
#include <vector>
#include <utility>
/*
start : 格子的起始位置
finish： 要到达的位置
length： 走的长度
path： 走的路径点
Mapin： 加入地图
*/
bool FindPath(pair<int, int>& start, pair<int, int>& finish,
int & length, vector<pair<int,int> >& path, vector<vector<int> > & Mapin)
{
if (Mapin.empty())
{
cout << "地图为空" << endl;
return false;
}
//判断开始与到达的位置是不是同一位置
if (start.first == finish.first && start.second == finish.second)
{
length = 0;
return true;
}
//初始化迷宫外面的障碍墙，这是为了处理边界位置时比较方便
int ncol = Mapin[0].size();//获取列数
vector<int> vtemp(ncol +2,1);
int nrow = Mapin.size();//获取行数
vector<vector <int> > newMap(nrow + 2, vtemp);
//把迷宫重行建造 加障碍
for (int i =1; i <nrow; i++)
{
for (int j =1; j < ncol; j++)
{
newMap[i][j] = Mapin[i - 1][j - 1];
}
}
//方向设置
vector<pair<int, int> > offset;
offset.push_back(make_pair(0,1)); //第一种写法
//offset[1] = make_pair(1,0); //第二种写法
offset.push_back(make_pair(1, 0));
offset.push_back(make_pair(0, -1));
offset.push_back(make_pair(-1, 0));
int NumOfNbrs = 4; //一个网格位置的相邻位置数
pair<int, int> here = start;
//1表示障碍，0表示可以通过，大于1表示相距起始点的距离(0+2)
newMap[here.first][here.second] = 2; //*
//标记可到达的网格位置
LinkedQueue<pair<int, int> > Q;
pair<int, int> nbr;
do
{
for (int i = 0; i<NumOfNbrs; i++)
{
nbr.first = here.first + offset[i].first;
nbr.second = here.second + offset[i].second;
if (newMap[nbr.first][nbr.second] == 0)
{
newMap[nbr.first][nbr.second] = newMap[here.first][here.second] + 1;
if (nbr.first == finish.first && nbr.second == finish.second)
{
break;
}
Q.Add(nbr);
}
}
if (nbr.first == finish.first && nbr.second == finish.second)
{
break;
}
if (Q.IsEmpty())
{
return false;
}
Q.Delete(here); //队列删除头，并把数据给here
} while (true);
length = newMap[finish.first][finish.second] - 2; //获得的长度
//回溯追踪最短路径经过的点
path.clear();
path.resize(length);
here = finish; //从终点追踪
for (int j = length-1; j>=0; j--)
{
path[j] = here;
for (int i = 0; i<NumOfNbrs; i++)
{
nbr.first = here.first + offset[i].first;
nbr.second = here.second + offset[i].second;
if (newMap[nbr.first][nbr.second] == j + 2) //下个位置与here位置差1
{
break; //找到回去的位置
}
}
here = nbr;
} //一直找到原来位置，path 记录行走的路径
return true;
}其中#include "LinkedQueue.h" 为上一章记录的代码，连接在开头。
测试函数：
void FindPathQueue()
{
//地图与书中的一样 1代表障碍物，0代表可走路径
vector<vector<int> > mapIn{ { 0,0,1,0,0,0,0 },
{ 0,0,1,1,0,0,0 },
{ 0,0,0,0,1,0,0 },
{ 0,0,0,1,1,0,0 },
{ 1,0,0,0,1,0,0 },
{ 1,1,1,0,0,0,0 },
{ 1,1,1,0,0,0,0 }
};
pair<int, int> start(3, 2);//代表第3行第2列，新图中会对应书中的位置
pair<int, int> finish(4, 6);
vector<pair<int, int> > path;
int length = -1; //路径长度
if (FindPath(start,finish,length, path, mapIn)) //如果找到路径
{
cout << "路径长度为：" << length << endl;
for (auto pa : path)
{
cout << pa.first << " " << pa.second << endl;
}
}
else
{
cout << "没有找到路径" << endl;
}
}输出结果：
代码详细解析：
if (Mapin.empty())
{
cout << "地图为空" << endl;
return false;
}这里是用来判断加载的地图是不是空的，如果是空的话，输出地图为空，返回false
//判断开始与到达的位置是不是同一位置
if (start.first == finish.first && start.second == finish.second)
{
length = 0;
return true;
}这里判断的是初始位置与最终的位置是不是同一个位置，如果是就返回长度为0；
//初始化迷宫外面的障碍墙，这是为了处理边界位置时比较方便
int ncol = Mapin[0].size();//获取列数
vector<int> vtemp(ncol +2,1);
int nrow = Mapin.size();//获取行数
vector<vector <int> > newMap(nrow + 2, vtemp);
//把迷宫重行建造 加障碍
for (int i =1; i <nrow; i++)
{
for (int j =1; j < ncol; j++)
{
newMap[i][j] = Mapin[i - 1][j - 1];
}
}这段代码是创建一个新的地图，就是让输入的地图四周变1，相当于障碍物，为了后面寻找方便，这里说明一下，地图中0,代表可以走的格子，1代表障碍物. 大于1的数为记录的数据。
于是地图变成这个样子：
其中的黑色就是1的代表空白为0；
//方向设置
vector<pair<int, int> > offset;
offset.push_back(make_pair(0,1)); //第一种写法
//offset[1] = make_pair(1,0); //第二种写法
offset.push_back(make_pair(1, 0));
offset.push_back(make_pair(0, -1));
offset.push_back(make_pair(-1, 0));设置方向，采用了右，下，左，上的4个顺序,为后面探索与回溯需要用。
int NumOfNbrs = 4; //一个网格位置的相邻位置数
pair<int, int> here = start;
//1表示障碍，0表示可以通过，大于1表示相距起始点的距离(0+2)
newMap[here.first][here.second] = 2; //*
//标记可到达的网格位置
LinkedQueue<pair<int, int> > Q;
pair<int, int> nbr;
do
{
for (int i = 0; i<NumOfNbrs; i++)
{
nbr.first = here.first + offset[i].first;
nbr.second = here.second + offset[i].second;
if (newMap[nbr.first][nbr.second] == 0)
{
newMap[nbr.first][nbr.second] = newMap[here.first][here.second] + 1;
if (nbr.first == finish.first && nbr.second == finish.second)
{
break;
}
Q.Add(nbr);
}
}
if (nbr.first == finish.first && nbr.second == finish.second)
{
break;
}
if (Q.IsEmpty())
{
return false;
}
Q.Delete(here); //队列删除头，并把数据给here
} while (true);这里一部分就是探索法了，NumOfNbrs 为4 代表方向数，这里我们让初始位置的值变成 2，Q是记录探索的记录。
nbr 记录了4个周边的数据位置，然后判断当前周围情况，当为0的时候，这个位置是上个位置 + 1的值，若是1不变，如果是终点就跳出循环，表示找到了。
如下图：
循环一次的do语句对应的图：
在算的同时，把初始点的右，下，左，上的位置放进队列中了：Q.Add(nbr);
然后开始从队列取出位置，并且赋值给here。Q.Delete(here);
这个时候here代表的是开始位置的右边的位置，然后开始查找它的四周然后赋值：
同样加入到刚才的队列中间去，然后在取队列的数，这时候为A 的下边的数，然后操作：
以此类推最终找到终点位置：
找到后，我们要采用回溯法，来找到那条路径：
length = newMap[finish.first][finish.second] - 2; //获得的长度
//回溯追踪最短路径经过的点
path.clear();
path.resize(length);
here = finish; //从终点追踪首先我们要找到最短的长度，让结果值 - 2，就是最短路径的长度了（不算初始位置，算结束位置）如上图 11 - 2 = 9,
9就是最短路径的长度了。然后path 是为记录路径的过程点。 这里here记录了finish位置。
for (int j = length-1; j>=0; j--)
{
path[j] = here;
for (int i = 0; i<NumOfNbrs; i++)
{
nbr.first = here.first + offset[i].first;
nbr.second = here.second + offset[i].second;
if (newMap[nbr.first][nbr.second] == j + 2) //下个位置与here位置差1
{
break; //找到回去的位置
}
}
here = nbr;
} //一直找到原来位置，path 记录行走的路径
return true;回溯就非常简单了，还是寻找右，下，左，上的位置，寻找比本身值少1的位置，就想11，下个就是找10的值，找到一个添加到对应位置path中，一直找到起始位置。这样就记录路径的全部的点了。于是就是：
是不是非常的简单，喜欢我的博客，可以关注一下，需要源码可以私信我，一起加油吧。
上一篇： Android make脚本简记