队列的应用提问
关于队列里有这么一道例题 : 解迷宫问题:迷宫是如图示的m行n列的0-1矩阵,其中0表示无障碍,1表示有障碍.设入口为(1,1),出口为(m,n) , 每次移动只能从一个无障碍的单元移到其周围8个方向上任一无障碍的单元.列号---->12345
行号-->1|00010
2|01000
3|00101
4|11010
5|
使用这样的数据结构:用数组mg表示迷宫,为了算法方便, 在四周加上一圈"哨兵",即变为数组
mg表示迷宫, 用数组zx, zy 分别表示 X, Y 方向的移动增量,如图示, 使用一个队列queue记录走过的点, 并用变量front, rear分别表示队列的首与尾.
队列的结构如下:
struct stype
{
int x, y,pre /*x,y为点的坐标, pre为到达本点的上一步步号*/
} queue;
图2:
方向 北 东北 东 东南 南 西南 西 西北
下标 1 2 3 4 5 6 7 8
zx -1 -1 0 1 1 1 0 -1
zy 0 1 1 1 0 -1 -1 -1
算法搜索过程: 首先从(1,1)处开始搜索,将其周围8个方向可走(为0值)的点均插入到队列queue中,pre为到达本点的上一步步号,也就是当前的front之值,并将该点赋值为-1,避免回来重复搜索.如果其中某点是出口,算法结束,根据 rear 指示的前驱步号可回溯得到走迷宫的最短路径;否则从队列 删除一个点,进入下一步,同样将其周围8个方向可走的点插入到队列中,pre为到达本点的上一步步号,也就是当前的front之值,并将该点赋值为-1,避免回来重复搜索.如果其中某点是出口,算法结束,根据 rear 指示的前驱步号可回溯得到走迷宫的最短路径;否则从队列 删除一个点,进入下一步 ,直到循环算法结束,如果queue队列中没有元素且末找到出口,则表示不存在路径.
图3:迷宫路径搜索过程
步号 x y pre
1 1 1 0
2 1 2 1
3 2 1 1
4 1 3 2
5 2 3 2
6 3 2 3
7 3 1 3
8 2 4 4
9 3 4 5
10 4 3 6
11 1 5 8
12 2 5 8
13 4 5 9
14 5 3 10
15 5 2 10
16 5 5 13
程序如下:
#include<stdio.h>
#define m 5
#define n 5
#define MaxSize 100
struct stype
{
int x,y,pre;
}queue;
int mg;
int zx,zy;
void printlj(int rear)
{
int i=rear,j;
do /*反向找到最短路径,将路径上点的pre成员设置成-1*/
{
j=i;
i=queue.pre;
queue.pre=-1;
}
while (i!=0);
printf("search the maze road:\n\t entry->");
i=0;
while(i<MaxSize) /*正向搜索pre为-1的点,构成正向路径*/
{
if(queue.pre==-1)
printf("(%d,%d)->",queue.x,queue.y);
i++;
}
printf("exit\n");
}
void mglj()
{
int i,j,x,y,v,front,rear,find=0;
queue.x=1;queue.y=1;queue.pre=0;/*从(1,1)开始搜索,将该点插入队列*/
front=1;rear=1; /*队列指针置初值1*/
mg=-1; /*将其赋值-1,避免回来重复搜索*/
while(front<=rear && !find) /*队列不为空且末找到路径时循环*/
{
x=queue.x;
y=queue.y;
for(v=1;v<=8;v++) /*循环扫描每个方向,把每个可走方向插入队列*/
{
i=x+zx;j=y+zy; /*选择一个前进方向(i,j) */
if(mg==0) /*如果该方向可走*/
{
rear++; /*将该方向插入队列*/
queue.x=i;/*将其赋值-1,避免重复搜索*/
queue.y=j;
queue.pre=front;
mg=-1;
}
if(i==m && j==n) /* 找到出口*/
{
printlj(rear);/*打印找到的路径*/
find=1; /*设置为1退出循环*/
}
}
front++; /*从队列中删除一个元素*/
}
if(!find) printf("no presence!\n");
}
void main()
{
int i,j;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++) /*获取迷宫数据, 自己输入*/
scanf("%d",&mg);
for(i=0;i<=m+1;i++)
{
mg=1;mg=1; /*加上为1的外框*/
}
for(j=0;j<=n+1;j++)
{
mg=1;mg=1;
}
zx=-1;zx=-1;zx=0;zx=1; /*建立方向数据*/
zx=1;zx=1;zx=0;zx=-1;
zy=0;zy=1;zy=1;zy=1;
zy=0;zy=-1;zy=-1;zy=-1;
mglj(); /*产生迷宫路径
}
问题:
1.首先对这程序的实现很难理解,不知从何入手,
2.开始时他所说的加上一圈"哨兵"是什么意思呢?
3.为什么要设图2 这样的移动增量?
4.图3的搜索过程怎么理解呢?
5.在mglj() 函数中为什么要用 front++ 来删除数据呢?
6.main函数里为什么要加上什么 1的外框?
7.他的结果(1,1)->(1,2)->(2,3)->(3,4)->(4,5)->(5,5)到底是怎么判断得到的?? 总体来说,这是一个广度优先的搜索算法.
1. 画个图就清楚了,跟随算法步骤在图上用纸笔和大脑来算
2. 这是硬翻的英语了...原文是sentinel,就是一种表示"无效""不存在"的值,作为错误或边界的检查条件之类.在这里,设置成任意非0的值意味着是障碍,所以任意非0的值都可以作为"哨兵". (这词用中文说真不习惯 =_=
3. 为了代码整洁.完全可以用if...else或者switch代替,但现在的这种做法属于table-driven的一种表现,代码更容易维护
4. 参考1.
5. 在mglj()的while循环里有
x=queue.x;
y=queue.y;
这就是说每次都用队列的头的数据来获取当前步的数据.在while循环中的最后一句之后,进到下次循环前,要更新循环量.所以要把头从当前节点向后移到下次的头.结果就是删除了队列原本的头(注意到队列的FIFO性质)
6. 参考2.
7. 参考1 还有这里,这个 zx , zy关于这两个数组的赋值, 为什么它们去到 zx=-1,zy=-1
这样为啥不会出错呢?这不是下标越界了吗 引用第2楼august于2007-11-03 16:32发表的:
还有这里,这个 zx , zy关于这两个数组的赋值, 为什么它们去到 zx=-1,zy=-1
这样为啥不会出错呢?这不是下标越界了吗
呵呵，这确实值得吐槽。要是声明为zx, zy会比较安全（更好还是遵循0起始的下标）。
至于为什么不会出错，其实这种小范围的越界很难引发立即的、明显的错误。很有可能很长时间都不会出错。即便如此也不应该容许自己的代码有不安全的地方，除非你清楚知道自己这么做的理由（例如有时候会申请长度为1的数组然后故意越界之类） 我还想问问,上面的 queue.x=1, queue.y=1,在以后是 queue.x,那么当 queue.x
queue.y,的时候,它怎么确定,它们的值是多少呢? 哦,偶知道了,不好意思
页:
[1]