第三章栈和队列

Size: px

Start display at page:

Download "第三章栈和队列"

旁朱
4 years ago
Views:

1 第 3 章栈 3.1 ADT 栈 3.2 ADT 栈的实现 3.3 ADT 栈的应用福州大学数学与计算机科学学院吴英杰 1

2 1 栈的定义和特点 3.1 ADT 栈 (stack) 定义 : 限定仅在表首进行插入或删除操作的线性表, 表首栈顶, 表尾栈底, 不含元素的空表称空栈特点 : 先进后出 (FILO) 或后进先出 (LIFO) 进栈栈顶... an... 出栈栈 S=(a1,a2,,an) a2 栈底 a 福州大学数学与计算机科学学院 2

3 3.1 ADT 栈 (Stack) 2 ADT 栈上定义的常用的基本运算 : (1) StackEmpty(S): 判断栈空 (2) StackFull(S): 判断栈满 (3) StackTop(S): 返回栈顶元素 (4) Push(x, S): 将元素 x 入栈 (5) Pop(S): 出栈, 删除并返回栈 S 的栈顶元素福州大学数学与计算机科学学院 3

4 3 栈应用的简单例子 : 3.1 ADT 栈 (Stack) (1) 程序编译时的表达式或字符串的括号匹配问题例如, 算术表达式 (x*(x+y)-z), 其中位置 1 和 4 处有左括号, 而位置 8 和 11 处有右括号, 满足配对要求但算术表达式 (x+y)*z)(, 其中位置 8 处的右括号没有可与之配对的左括号, 而位置 9 处的左括号没有可与之配对的右号福州大学数学与计算机科学学院 4

5 (2) 回文游戏 : 顺读与逆读字符串一样 ( 不含空格 ) d a d 字符串 : madam im adam (3) 多进制输出 : 例把十进制数 159 转换成八进制数 1. 读入字符串 2. 去掉空格 ( 原串 ) 3. 压入栈 4. 原串字符与出栈字符依次比较若不等, 非回文若直到栈空都相等, 回文余余余 2 0 (159)10=(237) 返回章目录福州大学数学与计算机科学学院 5

6 = 栈的存储结构 1 用数组实现栈 : 栈空 F E D C B A 进栈栈满 F E D C B A 出栈栈空栈顶指针, 指向实际栈顶后的空位置, 初值为 -1 设数组维数为 M = -1, 栈空, 此时出栈, 则下溢 (underflow) =M-1, 栈满, 此时入栈, 则上溢 (overflow) 福州大学数学与计算机科学学院 6

7 (1) 用数组实现的栈结构 Stack 定义 : typedef struct astack *Stack; typedef struct astack { int ; /* 栈顶位置, 当栈为空时,=-1*/ int max; /* 栈顶位置的最大值 */ StackItem *data; /* 栈元素数组 */ } Astack; 福州大学数学与计算机科学学院 7

8 入栈算法 void Push(StackItem x, Stack S) { if( StackFull(S) Error("Stack is full"); else S->data[++ S->] = x; } 出栈算法 StackItem Pop(Stack S) { if(stackempty(s)) Error("Stack is empty"); else return S->data[S->--] ; } 福州大学数学与计算机科学学院 8

9 (2) 栈的数组实现的优缺点优点 : 所列的 7 个基本运算都可在 O(1) 的时间里完成, 效率高缺点 : 为了使每个栈在算法运行过程中不会溢出, 通常要为每个栈预置一个较大的栈空间另一方面, 由于各个栈的实际大小在算法运行过程中不断变化经常会发生其中一个栈满, 而另一个栈空的情形, 空间利用率低福州大学数学与计算机科学学院 9

10 (3) 两个栈共用一个数组利用栈底位置不变的特性, 可以将 2 个栈的栈底分别设在数组 stack 的两端然后各自向数组 stack 的中间伸展, 如下图所示好处 : 提高空间利用率, 减少栈发生上溢的可能性福州大学数学与计算机科学学院 10

11 2 链栈用指针实现栈 (1) 链栈的结点类型定义 : typedef struct snode *slink; typedef struct snode { StackItem element; slink next; }StackNode; 福州大学数学与计算机科学学院 11

12 2 链栈用指针实现栈 (2) 用指针实现的链栈定义 : typedef struct lstack *Stack; typedef struct lstack { slink ; // 栈顶结点指针 }Lstack; 福州大学数学与计算机科学学院 12

13 (2) 入栈出栈算法实现及演示 : 入栈算法 Push.txt p x... 栈底 ^ 出栈算法 Pop.txt p... 栈底 ^ 返回章目录福州大学数学与计算机科学学院 13

14 3.3 栈的应用 1 过程的嵌套调用 : 主程序r 子过程1 r s 子过程2 r st 子过程3 r s t r s r 福州大学数学与计算机科学学院 14

15 2 递归过程及其实现 : 递归 : 函数直接或间接的调用自身叫递归实现 : 建立递归工作栈例递归的执行情况分析运行结果 : 1, 2,2, 3,3,3, 福州大学数学与计算机科学学院 15

16 递归调用执行情况如下 : (1) 主程序 w=3; print(w) w 3 print(2); (2) 输出 :3, 3, 3 w 2 print(1) ; (3) 输出 :2, 2 w 1 w 0 print(0); (4) 输出 :1 返回结束 (1)w=3 (1 ) 3 (2)w=2 (2) 2 (1)w=3 (1) 3 (3)w=1 (3) 1 (2)w=2 (2) 2 (1)w=3 (1) 3 (4)w=0 (4) 0 (3)w=1 (3) 1 (2)w=2 (2) 2 (1)w=3 (1) 福州大学数学与计算机科学学院 16

17 1 算术表达式的定义 3 算术表达式求值在计算机中, 表达式都是由操作数 (operand) 运算符 (operator) 和界限符 (delimiter) 组成只含二元运算符的算术表达式可定义为 : 表达式 ::= 操作数运算符操作数操作数 ::= 简单变量表达式简单变量 ::= 标识符无符号整数例 1:Exp = 3*5+(6-8/4)*7# 福州大学数学与计算机科学学院 17

18 3 算术表达式求值 2 算术表达式的表示方式假设 Exp = S1 + OP + S2 S1 + OP + S2 称为表达式的中缀表示法 ( 简称中缀式 ) S1 + S2 + OP 称为表达式的后缀表示法 ( 简称后缀式 ) OP + S1 + S2 称为表达式的前缀表示法 ( 简称前缀式 ) 例 2: 若 Exp= a b+(c-d/e) f 中缀式为 :a b+c-d/e f 后缀式为 :ab cde/-f + 动画演示 >> 前缀式为 :+ ab -c/def >> 福州大学数学与计算机科学学院 18

19 3 算术表达式求值 << 福州大学数学与计算机科学学院 19

20 3 后缀表达式求值 3 算术表达式求值后缀式的求值规则 : 先找运算符, 后找操作数例 3: 对后缀式 Exp=ab cde/-f +# 求值动画演示 >> 福州大学数学与计算机科学学院 20

21 3 算术表达式求值 >> 福州大学数学与计算机科学学院 21

22 3 后缀表达式求值 3 算术表达式求值利用栈进行后缀表达式求值的基本思想 : 1) 从左到右读入后缀表达式, 2) 若读入的是一个操作数, 就将它压入栈 ; 3) 若读入的是一个运算符 op, 就从栈中弹出两个操作数, 设为 x 和 y, 计算表达式 x op y 的值, 并将计算结果压入栈 ; 对整个后缀表达式读入结束时, 栈顶元素就是计算结果例 4: 求后缀表达式 /-7 +# 的值动画演示 >> >> 福州大学数学与计算机科学学院 22

23 3 算术表达式求值 << 福州大学数学与计算机科学学院 23

24 3 算术表达式求值 4 原表达式向后缀式的转换例 5: (1) 原表达式 :a b/c d-e+f 后缀式 :ab c/d e-f+ (2) 原表达式 :a+b c-d/e f 后缀式 :abc +de/f + 给每个运算符赋以一个优先级, 如下 : 运算符 # ( ) + - / 优先级福州大学数学与计算机科学学院 24

25 3 算术表达式求值 4 原表达式向后缀式的转换利用栈实现原表达式向后缀式转换的基本思想 : 1) 设立运算符栈, 预设运算符栈的栈底为 # ; 2) 若当前字符是操作数, 则直接输出到后缀式 ; 3) 若当前字符为运算符且优先级大于栈顶运算符, 则进栈, 否则弹出栈顶运算符输出到后缀式 ; 例 6: 求表达式 a (b (c+d/e)-f)# 的后缀式动画演示 >> >> 福州大学数学与计算机科学学院 25

26 3 算术表达式求值 << 福州大学数学与计算机科学学院 26

27 R [ 7][ 7 ] 4 地图四染色问题 # 紫色 2# 黄色 3# 红色 4# 绿色 (7) (6) (2) (1) (3) (4) (5) 福州大学数学与计算机科学学院 27

28 (1) 问题的提出 5 等价类划分问题给定集合 S 及一系列形如 x 等价于 y 的等价性条件, 要求给出 S 的满足所列等价性条件的等价类划分其中 x 和 y 是 S 中的元素复习 : (1) 集合上的等价关系和集合关于某一等价关系的等价类划分等概念 ; (2) 举出 3 个你熟悉的等价关系和等价类划分福州大学数学与计算机科学学院 28

29 (2) 问题的数学化我们总可以用整数来表示集合中的元素因此, 如果集合 S 中共有 n 个元素, 则可将集合 S 表示为 {1,2,,n}, 而元素 i 和 j 的等价性条件可表示为 i j,1 i,j n 这样, 问题可一般地表述为 : 已知 S= {1,2,,n} 上的一个等价关系由 r 个等价性条件 {i t j t, 1 i t,j t n, t=1,2,3,,r} 来表示要求该等价关系所确定的等价类划分福州大学数学与计算机科学学院 29

30 (3) 举例给定集合 S ={1,2,,7}, 及等价性条件 :1 2, 5 6,3 4,1 4 则集合 S 的等价类划分如下 : 首先将 S 的每一个元素看成一个等价类然后顺序地处理所给的等价性条件每处理一个等价性条件, 就得到一个相应的等价类划分 : 1 2 {1,2}{3}{4}{5}{6}{7}; 5 6 {1,2}{3}{4}{5,6}{7}; 3 4 {1,2}{3,4}{5,6}{7}; 1 4 {1,2,3,4}{5,6}{7} 最终所得到的集合 S 的等价类划分为 :{1,2,3,4} {5,6}{7} 返回章目录福州大学数学与计算机科学学院 30

31 THE END 福州大学数学与计算机科学学院 31

PowerPoint Presentation

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

第三章 栈和队列

第三章栈和队列