-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathch12s04.html
209 lines (197 loc) · 8.77 KB
/
ch12s04.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>4. 队列与广度优先搜索</title><link rel="stylesheet" href="styles.css" type="text/css" /><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><link rel="start" href="index.html" title="Linux C编程一站式学习" /><link rel="up" href="ch12.html" title="第 12 章 栈与队列" /><link rel="prev" href="ch12s03.html" title="3. 深度优先搜索" /><link rel="next" href="ch12s05.html" title="5. 环形队列" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">4. 队列与广度优先搜索</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="ch12s03.html">上一页</a> </td><th width="60%" align="center">第 12 章 栈与队列</th><td width="20%" align="right"> <a accesskey="n" href="ch12s05.html">下一页</a></td></tr></table><hr /></div><div class="sect1" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="id2750621"></a>4. 队列与广度优先搜索</h2></div></div></div><p>队列也是一组元素的集合，也提供两种基本操作：Enqueue（入队）<a id="id2750629" class="indexterm"></a>将元素添加到队尾，Dequeue（出队）<a id="id2750637" class="indexterm"></a>从队头取出元素并返回。就像排队买票一样，先来先服务，先入队的人也是先出队的，这种方式称为FIFO（First In First Out，先进先出）<a id="id2750647" class="indexterm"></a>，有时候队列本身也被称为FIFO。</p><p>下面我们用队列解决迷宫问题。程序如下：</p><div class="example"><a id="id2750660"></a><p class="title"><b>例 12.4. 用广度优先搜索解迷宫问题</b></p><div class="example-contents"><pre class="programlisting">#include <stdio.h>
#define MAX_ROW 5
#define MAX_COL 5
struct point { int row, col, predecessor; } queue[512];
int head = 0, tail = 0;
void enqueue(struct point p)
{
queue[tail++] = p;
}
struct point dequeue(void)
{
return queue[head++];
}
int is_empty(void)
{
return head == tail;
}
int maze[MAX_ROW][MAX_COL] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
void print_maze(void)
{
int i, j;
for (i = 0; i < MAX_ROW; i++) {
for (j = 0; j < MAX_COL; j++)
printf("%d ", maze[i][j]);
putchar('\n');
}
printf("*********\n");
}
void visit(int row, int col)
{
struct point visit_point = { row, col, head-1 };
maze[row][col] = 2;
enqueue(visit_point);
}
int main(void)
{
struct point p = { 0, 0, -1 };
maze[p.row][p.col] = 2;
enqueue(p);
while (!is_empty()) {
p = dequeue();
if (p.row == MAX_ROW - 1 /* goal */
&& p.col == MAX_COL - 1)
break;
if (p.col+1 < MAX_COL /* right */
&& maze[p.row][p.col+1] == 0)
visit(p.row, p.col+1);
if (p.row+1 < MAX_ROW /* down */
&& maze[p.row+1][p.col] == 0)
visit(p.row+1, p.col);
if (p.col-1 >= 0 /* left */
&& maze[p.row][p.col-1] == 0)
visit(p.row, p.col-1);
if (p.row-1 >= 0 /* up */
&& maze[p.row-1][p.col] == 0)
visit(p.row-1, p.col);
print_maze();
}
if (p.row == MAX_ROW - 1 && p.col == MAX_COL - 1) {
printf("(%d, %d)\n", p.row, p.col);
while (p.predecessor != -1) {
p = queue[p.predecessor];
printf("(%d, %d)\n", p.row, p.col);
}
} else
printf("No path!\n");
return 0;
}</pre></div></div><br class="example-break" /><p>运行结果如下：</p><pre class="screen">2 1 0 0 0
2 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 0 0 0 0
0 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 0 0 0
2 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 2 0 0
2 1 1 1 0
0 0 0 1 0
*********
2 1 0 0 0
2 1 0 1 0
2 2 2 0 0
2 1 1 1 0
2 0 0 1 0
*********
2 1 0 0 0
2 1 2 1 0
2 2 2 2 0
2 1 1 1 0
2 0 0 1 0
*********
2 1 0 0 0
2 1 2 1 0
2 2 2 2 0
2 1 1 1 0
2 2 0 1 0
*********
2 1 0 0 0
2 1 2 1 0
2 2 2 2 2
2 1 1 1 0
2 2 0 1 0
*********
2 1 2 0 0
2 1 2 1 0
2 2 2 2 2
2 1 1 1 0
2 2 0 1 0
*********
2 1 2 0 0
2 1 2 1 0
2 2 2 2 2
2 1 1 1 0
2 2 2 1 0
*********
2 1 2 0 0
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 0
*********
2 1 2 2 0
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 0
*********
2 1 2 2 0
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 0
*********
2 1 2 2 0
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 2
*********
2 1 2 2 2
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 2
*********
2 1 2 2 2
2 1 2 1 2
2 2 2 2 2
2 1 1 1 2
2 2 2 1 2
*********
(4, 4)
(3, 4)
(2, 4)
(2, 3)
(2, 2)
(2, 1)
(2, 0)
(1, 0)
(0, 0)</pre><p>其实仍然可以像<a class="xref" href="ch12s03.html#stackqueue.dfs">例 12.3 “用深度优先搜索解迷宫问题”</a>一样用<code class="literal">predecessor</code>数组表示每个点的前趋，但我想换一种更方便的数据结构，直接在每个点的结构体中加一个成员表示前趋：</p><pre class="programlisting">struct point { int row, col, predecessor; } queue[512];
int head = 0, tail = 0;</pre><p>变量<code class="literal">head</code>和<code class="literal">tail</code>是队头和队尾指针，<code class="literal">head</code>总是指向队头，<code class="literal">tail</code>总是指向队尾的下一个元素。每个点的<code class="literal">predecessor</code>成员也是一个指针，指向它的前趋在<code class="literal">queue</code>数组中的位置。如下图所示：</p><div class="figure"><a id="stackqueue.bfsqueue"></a><p class="title"><b>图 12.3. 广度优先搜索的队列数据结构</b></p><div class="figure-contents"><div><img src="images/stackqueue.bfsqueue.png" alt="广度优先搜索的队列数据结构" /></div></div></div><br class="figure-break" /><p>为了帮助理解，我把这个算法改写成伪代码如下：</p><pre class="programlisting">将起点标记为已走过并入队;
while (队列非空) {
出队一个点p;
if (p这个点是终点)
break;
否则沿右、下、左、上四个方向探索相邻的点
if (和p相邻的点有路可走，并且还没走过)
将相邻的点标记为已走过并入队，它的前趋就是刚出队的p点;
}
if (p点是终点) {
打印p点的座标;
while (p点有前趋) {
p点 = p点的前趋;
打印p点的座标;
}
} else
没有路线可以到达终点;</pre><p>从打印的搜索过程可以看出，这个算法的特点是沿各个方向同时展开搜索，每个可以走通的方向轮流往前走一步，这称为广度优先搜索（BFS，Breadth First Search）<a id="id2750820" class="indexterm"></a>。探索迷宫和队列变化的过程如下图所示。</p><div class="figure"><a id="id2750839"></a><p class="title"><b>图 12.4. 广度优先搜索</b></p><div class="figure-contents"><div><img src="images/stackqueue.bfs.png" alt="广度优先搜索" /></div></div></div><br class="figure-break" /><p>广度优先是一种步步为营的策略，每次都从各个方向探索一步，将前线推进一步，图中的虚线就表示这个前线，队列中的元素总是由前线的点组成的，可见正是队列先进先出的性质使这个算法具有了广度优先的特点。广度优先搜索还有一个特点是可以找到从起点到终点的最短路径，而深度优先搜索找到的不一定是最短路径，比较本节和上一节程序的运行结果可以看出这一点，想一想为什么。</p><div class="simplesect" lang="zh-cn" xml:lang="zh-cn"><div class="titlepage"><div><div><h3 class="title"><a id="id2750872"></a>习题</h3></div></div></div><p>1、本节的例子直接在队列元素中加一个指针成员表示前趋，想一想为什么上一节的<a class="xref" href="ch12s03.html#stackqueue.dfs">例 12.3 “用深度优先搜索解迷宫问题”</a>不能采用这种方法表示前趋？</p><p>2、本节例子中给队列分配的存储空间是512个元素，其实没必要这么多，那么解决这个问题至少要分配多少个元素的队列空间呢？跟什么因素有关？</p></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="ch12s03.html">上一页</a> </td><td width="20%" align="center"><a accesskey="u" href="ch12.html">上一级</a></td><td width="40%" align="right"> <a accesskey="n" href="ch12s05.html">下一页</a></td></tr><tr><td width="40%" align="left" valign="top">3. 深度优先搜索 </td><td width="20%" align="center"><a accesskey="h" href="index.html">起始页</a></td><td width="40%" align="right" valign="top"> 5. 环形队列</td></tr></table></div></body></html>