4

Size: px

Start display at page:

Download "4"

侪弘
6 years ago
Views:

1 孙猛年 9 月 28 日

2 2

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

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

5 5

6 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

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

8 8

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

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

11 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

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

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

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

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

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

17 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

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

19 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

20 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

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

22 栈与递归迷宫问题 22

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

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

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

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

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

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

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

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

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

33 33

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

35 35

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

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

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

39 在某一点 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

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

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

42 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

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

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

45 45

PowerPoint Presentation

PowerPoint Presentation 数据结构与算法 ( 三 ) 张铭主讲采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 3 章栈与队列栈栈的应用递归到非递归的转换队列 2 栈 (Stack) 操作受限的线性表运算只在表的一端进行队列 (Queue) 运算只在表的两端进行