文档介绍：第三章 栈和队列
插入和删除操作受限的线性表
栈（stack）
后进先出(LIFO:Last In First Out)的线性表
表头端称为栈底（bottom）
表尾端称为栈顶（top）
插入和删除都在栈顶进行
队列（que
int top;
堆栈的最大尺寸 3*L*L
迷宫问题算法2的实现
算法实现
stack_init();
push(0, 0);
while(!stack_empty()) {
pop(x, y); maze[x][y] = '#';
if (x,y是出口) return OK;
push_all_next(x, y);
}
return ERROR;
迷宫问题算法2的实现:子程序
#define valid(x,y) \
( (x >= 0 && x < L) && \
(y >= 0 && y < L) && \
maze[x][y] == '.' )
void push_all_next(int x, int y)
{
if (valid(x+1, y)) push(x+1, y); /* North */
if (valid(x, y-1)) push(x, y-1); /* West */
if (valid(x-1, y)) push(x-1, y); /* South */
if (valid(x, y+1)) push(x, y+1); /* East */
}
迷宫问题算法2中的问题
问题：
路径表示
解决方法：
构造与周游顺序倒序的路径链表
struct XY path[L][L];
路径链表的逆转算法
算法2的完善:登记路径
#define PUSH(x1, y1) { \
push(x1, y1); \
path[x1][y1].x = x; \
path[x1][y1].y = y; \
}
void push_all_next(int x, int y)
{
if (valid(x+1, y)) PUSH(x+1, y); /* North */
if (valid(x, y-1)) PUSH(x, y-1); /* West */
if (valid(x-1, y)) PUSH(x-1, y); /* South */
if (valid(x, y+1)) PUSH(x, y+1); /* East */
}
算法2的完善:路径逆转
void revert_path(void)
{
struct XY head, next, pre;
= = -1; = = L-1;
while ( != -1) {
next = path[][];
path[][] = pre;
pre = head;
head = next;
}
}
栈的应用：地图染色问题
地图染色问题
回溯法是一种满足一定条件的穷举搜索法：在求解过程中，不断利用可供选择的规则扩展部分解，一旦当前的部分解不成立，就停止扩展，退回到上一个较小的部分解继续试探，直到找到问题所有的解或无解为止。
0
02
06
6
1
5
3
2
4
0 1 1 1 1 1 0
1 0 0 0 0 1 0
1 0 0 1 1 0 0
1 0 1 0 1 1 0
1 0 1 1 0 1 0
1 1 0 1 1 0 0
0 0 0 0 0 0 0
0 1 2 3 4 5 6
R
0
1
3
2
4
5
6
地图染色问题
邻接矩阵
int adj[N][N];
颜色
int color[N];
取值1-4
0:未染色
地图染色算法
void main(void)
{
stack_init();
push(0, 1);
while (!stack_empty()) {
pop(x, c);
if (c == 5) { color[x] =