4

孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 9 月 28 日

2

栈及其抽象数据类型 栈的实现 栈的应 用 3

基本概念 栈是 一种特殊的线性表, 它所有的插 入和删除都限制在表的同 一端进 行行 表中允许进 行行插 入 删除操作的 一端叫做栈的顶 表的另 一端则叫做栈的底 当栈中没有元素时, 称之为空栈 栈的插 入运算通常称为进栈或 入栈, 栈的删除运算通常称为退栈或出栈 4

5

ADT Stack is operations Stack createemptystack ( void ) 创建 一个空栈 int isemptystack ( Stack st ) 判断栈 st 是否为空栈 void push ( Stack st, DataType x ) 往栈 st 的栈顶插 入 一个值为 x 的元素 void pop ( Stack st ) 从栈 st 的栈顶删除 一个元素 DataType top ( Stack st ) 求栈顶元素的值 end ADT Stack 6

用顺序的 方式实现栈时, 可定义如下 : struct SeqStack { /* 顺序栈类型定义 */ int MAXNUM; /* 栈中最 大元素个数 */ int t; /* t < MAXNUM, 指示栈顶位置 而 非元素个数 */ DataType *s; }; typedef struct SeqStack *PSeqStack; /* 顺序栈的指针类型 */ 7

8

由于栈是 一个动态结构, 而数组是静态结构, 因此会出现所谓的溢出问题 当栈中已经有 MAXNUM 个元素时, 如果再作进栈运算, 则会产 生溢出, 通常称为上溢 (Overflow) 而对空栈进 行行出栈运算时也会产 生溢出, 通常称为下溢 (Underflow) 9

创建 一个空栈 PSeqStack createemptystack_seq( int m ) 与创建空表 PSeqList createnulllist_seq(int m) 类似, 需为栈结构申请空间, 不不同之处是将栈顶变量量赋值为 -1 判断栈是否为空栈 int isemptystack_seq( PSeqStack pastack ) 当 pastack 所指栈为空栈时, 则返回 1, 否则返回 0 10

void push_seq( PSeqStack pastack, DataType x ) { /* 在栈中压 入 一元素 x */ if( pastack->t >= MAXNUM - 1 ) printf( "Overflow! \n" ); else{ pastack->t = pastack->t + 1; pastack->s[pastack->t] = x; } } 11

void pop_seq( PSeqStack pastack ) { /* 删除栈顶元素 */ if (pastack->t == -1) printf( "Underflow!\n" ); else pastack->t = pastack->t - 1; } 12

DataType top_seq( PSeqStack pastack ) { /* 当 pastack 所指的栈不不为空时, 求栈顶元素的值 */ if (pastack->t == -1) printf( "It is empty!\n" ); else return (pastack->s[pastack->t]); } 13

用链接 方式实现栈时, 每个结点的结构可定义如下 : struct Node; /* 单链表结点 */ typedef struct Node *PNode; /* 指向结点的指针类型 */ struct Node { /* 单链表结点定义 */ DataType info; Pnode link; }; 14

为了了强调栈顶是栈的 一个属性, 这 里里对栈增加了了 一层封装, 引 入LinkStack 结构的定义 struct LinkStack /* 链接栈类型定义 */ { PNode top; /* 指向栈顶结点 */ }; typedef struct LinkStack *PLinkStack; /* 链接栈类型的指针类型 */ 15

plstack top info link k n-1 top k n-1 头结点在哪 里里? 不不需要吗? 需要吗? k 0 Λ 栈底... k 1 k 0 16

PLinkStack createemptystack_link(void) { PLinkStack plstack; plstack = (PLinkStack)malloc(sizeof(struct LinkStack)); if (plstack!= NULL) plstack->top = NULL; else printf("out of space! \n"); /* 创建失败 */ return plstack ; } 17

int isemptystack_link( PLinkStack plstack ) { } return (plstack->top == NULL); 18

void push_link( PLinkStack plstack, DataType x ) { PNode p; p = (PNode)malloc( sizeof( struct Node ) ); if ( p == NULL ) printf("out of space!\n"); else { p->info = x; p->link = plstack->top; plstack->top = p; } } 19

void pop_link( PLinkStack plstack ) { PNode p; if(isemptystack_link(plstack))printf("empty stack pop.\n"); else{ p = plstack->top; plstack->top = plstack->top->link; free(p); } } 20

DataType top_link( PLinkStack plstack ) { if (pastack->top == NULL ) printf( "Stack is empty!\n" ); else return(plstack->top->info); } 21

栈与递归 迷宫问题 22

我们在引 入递归概念的基础上, 介绍栈是怎样 用来实现递归, 以及怎样把 一个递归的函数转换成 一个等价的 非递归的函数 设有 一个程序 sub 要调 用函数 rout(x),sub 本身也是 一个函数, 称之为调 用函数, 而称 rout 为被调函数 调 用函数中使 用调 用语句句 rout(a) 来引起 rout 函数的执 行行, 这 里里a 称为实参,x 称为形参 23

通常 用来说明递归的最简单的例例 子是阶乘的定义, 它可以表示成 : n! = n 1 ( n 1)! 这种 用 自身的简单情况来定义 自 己的 方式, 称为递归定义 在 n 阶乘的定义中, 当 n 为 0 时定义为 1, 它不不再 用递归来定义, 称为递归定义的出 口, 简称为递归出 口 n n = > 0 0 24

int fact( int n ) { int res=n; if ( n >1 ) res=res* fact( n 1 ) ; return res; } 25

假设 ( 主 ) 程序中包含 一个 k=fact(3) 语句句, 这个语句句 的执 行行过程如下图所示 : 26

fact 函数计算过程中程序运 行行栈的变化 : 3 - - n fact res 27

一般来说, 函数调 用的实现可以分解成下列列三步来进 行行 : (1) 传送调 用信息 (2) 分配被调函数需要的数据区, 并接收传送来的调 用信息 (3) 把控制转移到被调函数的 入 口 当被调函数运 行行结束, 需要返回到调 用函数时, 一般的返回处理理也可以分解成下列列三步 : (1) 传送返回信息 (2) 释放被调函数的数据区 (3) 把控制按返回地址转移到调 用函数中去 28

在 非递归调 用的情况下, 数据区的分配可以在程序运 行行前进 行行, 一直到整个程序运 行行结束才释放, 这种分配称为静态分配 在递归调 用的情况下, 被调函数的局部量量不不能分配给固定的某些单元, 而必须每调 用 一次就分配 一份, 当前程序使 用的所有的量量 ( 包括参数 局部变量量和中间 工作单元等 ), 都必须是最近 一次递归调 用时所分配的数据区中的量量 即所谓的动态分配 29

动态分配通常的处理理 方法是 : 在内存中开辟 一个存储区域称为运 行行栈 ( 或简称栈 ) 每次调 用时, 在栈上为递归定义函数开辟 一块区域, 称为 一个函数帧 ( 或简称帧 ), 保存这个调 用的相关信息 ; 函数执 行行总以栈顶的帧为当前帧 ; 每次返回时, 函数的上 一层执 行行取得下层函数调 用得到的结果, 执 行行系统弹出已经结束的调 用对应的帧, 然后回到调 用前上 一层执 行行时的状态 30

int nfact( int n ) { int res; PSeqStack st; /* 使 顺序存储结构实现的栈 */ st = createemptystack_seq( ); while (n>0) {push_seq(st,n); n = n 1; } res = 1; while (! isemptystack_seq(st)) {res = res * top_seq(st); pop_seq(st); } free(st); return ( res ); } 31

迷宫可 用下 页的左图所示的 方块来表示, 其中每个元素或为通道 ( 以空 白 方块表示 ), 或为墙 ( 以带阴影的 方块表示 ) 迷宫问题要求的就是 : 从 入 口到出 口的 一个以空 白 方块构成的 ( 无环 ) 路路径 32

33

从 入 口出发, 沿某 一 方向进 行行探索, 若能 走通, 则继续向前 走 ; 否则沿原路路返回, 换 一 方向再进 行行探索, 直到所有可能的通路路都探索到为 止 这类 方法统称回溯法 34

35

从 入 口出发, 采 用试探 方法, 搜索到 目标点 ( 出 口 ) 的 路路径 遇到出 口则成功结束 遇到分 支点时选 一个 方向向前探索 这时需记录当时的分 支点和在这 里里已试探过的分 支 ( 和尚未试探过的分 支 ) 若遇到死路路 ( 所有 方向都不不能 走或已试探过 ), 就退回前 一分 支点, 换 一 方向再探索 直到找到 目标, 或者所有可能通路路都探索到为 止 36

def mazeframe: 创建 个 ( 保存探索过程的 ) 空栈 把 位置压 栈中 while 栈不空时 : 取栈顶位置并设置为当前位置 while 当前位置存在试探可能 : 取下 个试探位置 if 下 个位置是出 : 打印栈中保存的探索过程然后返回 if 下 个位置是通道 : 把下 个位置进栈并且设置为当前位置 37

迷宫可 用 二维数组 maze[m][n] 来表示. 数组中元素为 0 的表示通道, 为 1 的表示墙 迷宫的 入 口处为 maze[1][1], 出 口处为 maze[m-2][n-2], 它们的元素值必为 0 任意时刻在迷宫中的位置可 用元素的 行行下标和列列下标 (i,j) 来表示 38

在某 一点 maze[i][j] 时, 可能的运动 方向有四个 可以建 立 一个数组 direction[4][2], 给出相对于位置 (i,j) 的四个 方向上,i 与 j 的增量量值 若在位置 (i,j), 要进 入 E 方向的位置 (g,h), 则可根据由该增量量值表来修改 (i,j) 的坐标, g = i + direction[0][0]; h = j + direction[0][1]; 39

栈中元素需要记录 走过的位置和已经选择过的 方向 包括位置的 行行 列列坐标, 及在该位置已试探过的 方向 的最 大下标 (4 个 方向编码为 directon 数组的下标值 0 1 2 3) 下 面的算法使 用顺序栈, 栈元素类型 : typedef struct { int x, y, d; /* 当前位置 (x,y) 和已试探 方向的最 大下标 d */ } DataType; 40

对迷宫问题, 需要从 入 口出发搜索 遇到出 口时成功结束 遇分 支结点时记录信息, 继续探查并可能回溯 搜索中把哪些位置 入栈? 存在两种合理理的选择 : 从 入 口到当前探查位置, 途径的所有位置都 入栈 只在栈 里里保存上述路路径中存在未探查 方向的那些位置 这 一 方式要求在 入栈操作前检查所考虑位置的情况, 有可能节省空间 仔细考虑, 可以看到两个情况 : 把 一个存在未探查 方向的位置 入栈, 后来回溯到这 里里时也可能不不再存在未探查 方向了了 ( 原有的未探查 方向在此期间已经检查过了了 ) 为在算法最后输出找到的路路径, 也需要知道路路径上所有的位置下 面算法采 用记录经过所有位置的 方式, 主要是为了了输出结果路路径 41

void mazepath (int *maze[],int *direction[],int x1, int y1,int x2,int y2,int M,int N) { int i,j,k,g,h; PSeqStack st; DataType element; st = createemptystack_seq(m*n ); maze[x1][y1] = 2; element.x = x1; element.y = y1; element.d = -1; push_seq(st,element); while (! isemptystack_seq(st)) { element = top_seq(st); pop_seq(st); i = element.x; j = element.y; k = element.d + 1; while (k<=3) { g = i + direction[k][0]; h = j + direction[k][1]; if (g==x2 && h==y2 && maze[g][h]==0) { printf("the revers path is:\n"); while(!isemptystack-seq(st)){ element=top_seq(st); pop_seq(st); printf("the node is: %d %d \n", element.x,element.y); } return; } if (maze[g][h]==0) { maze[g][h] = 2; element.x = i; element.y = j; element.d = k; push_seq(st,element); i = g; j = h; k = -1; } k = k + 1; } } printf("the path has not been found.\n"); } 42

迷宫问题是具有下列列特征的 一 大类问题的代表 存在 一组可能的状态 ( 位置 情况等 ) 存在 一个初始状态 s 0 有 一个或者多个结束状态 ( 或存在 一种判断结束的 方法 ) 对每个状态 s,neighbor(s) 表示与 s 相邻的状态 ( 一步可达 ) 有 一个判断函数 valid(s) 判断 s 是否为合法的可 行行状态 共同问题 : 找出从 s 0 到某个 ( 或全部 ) 结束状态的路路径 ; 或者是从 s 0 出发, 设法找到 一个 / 全部解 ( 一个 / 全部结束状态 ) 这类路路径搜索问题, 都可以 用递归的 方法求解 ; 也可以借助于 一个栈, 通过回溯法求解 这类问题也被称为搜索问题 其他例例 子如 : 八皇后问题, 骑 士周游问题等 实际中的例例 子包括许多调度问题 ( 例例如背包问题 ), 定理理证明等 许多实际应 用问题需要通过空间搜索的 方式解决, 如 许多调度 规划 优化问题 ( 如背包问题 ) 数学定理理证明 ( 有 一些事实和推理理规则 ) 43

栈的 ADT, 存储表示和算法的实现 栈与递归的内在联系 栈在回溯法求解中的作 用 本讲内容 非常重要!! 44

45