本 章 说 明 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队 列 本 章 小 结 返回主目录.

Presentation on theme: "本 章 说 明 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队 列 本 章 小 结 返回主目录."— Presentation transcript:

1 本 章 说 明 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队 列 本 章 小 结 返回主目录

2 本章说明 学习目标 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们 熟练掌握栈类型的两种实现方法
熟练掌握循环队列和链队列的基本操作实现算法 理解递归算法执行过程中栈的状态变化过程。 重点和难点 掌握栈和队列这两种结构的特点，以便能在应用问题中正确使用 知识点 顺序栈、链栈、循环队列、链队列

3 栈和队列是在程序设计中被广泛使用的两种线性数据结构，它们的特点在于基本操作的特殊性，栈必须按“后进先出”的规则进行操作，而队列必须按“先进先出”的规则进行操作。和线性表相比，它们的插入和删除操作受更多的约束和限定，故又称为限定性的线性表结构。线性表和栈及队列的插入和删除操作的主要区别： 线性表允许在表内任一位置进行插入和删除 栈只允许在表尾一端进行插入和删除 队列只允许在表尾一端进行插入，在表头一端进行删除

4 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO）
3.1  栈 1.栈的定义和特点 定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈 特点：先进后出（FILO）或后进先出（LIFO） 基本操作： 插入 删除 初始化 取栈顶元素 判空等 an a1 a2 ……... 栈底 栈顶 ... 出栈 进栈 栈s=(a1,a2,……,an)

5 数据对象：D={ ai| ai∈ElemSet, i=1, …, n, n>=0}
3.1  栈 2.栈的抽象数据类型定义 ADT Stack{ 数据对象：D={ ai| ai∈ElemSet, i=1, …, n, n>=0} 数据关系：R1={<ai-1, ai>|ai-1, ai∈D, i=2 ,…, n } 基本操作： InitStack(&S) //建空栈 DestroyStack(&S) //撤消栈 ClearStack(&S) //清空栈

6 StackLength(S) //返回栈元素个数 GetTop(S, &e) //用e返回栈顶元素
3.1  栈 StackEmpty(&S) //判空栈 StackLength(S) //返回栈元素个数 GetTop(S, &e) //用e返回栈顶元素 Push(&S, e) //在栈顶插入元素e Pop(&S, &e) //在栈顶删除元素，e返 StackTraverse(S,visit()) }ADT Stack

7 top=base,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow)
3.1  栈 3.栈的表示和实现 （1）栈的存储结构 顺序栈 实现：一维数组s[M] 栈空 栈满 top top top 1 2 3 4 5 A B C D E F top=0 1 2 3 4 5 栈空 top 1 2 3 4 5 F top top E top top D top top C top top B top A 出栈 进栈 设数组维数为M top=base,栈空，此时出栈，则下溢（underflow) top=M,栈满，此时入栈，则上溢（overflow) 栈顶指针top,指向实际栈顶 后的空位置，栈底base

8 3.1 栈 栈的存储结构: 入栈算法 出栈算法 在一个程序中同时使用两个栈 取栈顶元素 表示
3.1  栈 栈的存储结构: 表示 入栈算法 出栈算法 *避免栈“上溢”的办法是事先分配一个足够大的空间。但事先无法估计。实际上，各个栈的大小都是动态变化的，往往有这样的情况:即其中某个栈发生上溢，而其余的栈尚有很多空间。此时，我们可以设法调整空间，减少“上溢”的发生。 如果只有两个栈，则可以这样做(该做法经常被采用): 在一个程序中同时使用两个栈 M-1 栈1底 栈1顶 栈2底 栈2顶 取栈顶元素 表示

9 3.1 栈 （2）链栈 typedef struct LNode 结点定义 { int data; struct LNode *next;
3.1  栈 （2）链栈 栈顶 ^ …... top data next 栈底 typedef struct LNode { int data; struct LNode *next; }LNode; 结点定义 入栈算法 top ^ …... 栈底 top x p 出栈算法 q top ^ …... 栈底 top

10 1. 回文游戏：顺读与逆读字符串一样（不含空格） （1）读入字符串 （2）去掉空格（原串） （3）压入栈 （4）原串字符与出栈字符依次比较
3.2 栈的应用 1. 回文游戏：顺读与逆读字符串一样（不含空格） d a top （1）读入字符串 （2）去掉空格（原串） （3）压入栈 （4）原串字符与出栈字符依次比较 若不等，非回文 若直到栈空都相等，回文 字符串：“madam im adam” 2. 数制转换 例 把十进制数159转换成八进制数 (159)10=(237)8 159 8 19 2 余 7 余 3 余 2 top 7 3 2 3.1 算法:

11 3.2 栈的应用 3.行编辑程序 功能：接受用户从终端输入的程序和数据，并存入数据区。 如：whli##ilr#e(s#*s) 是：while(*s) putchar(*s++);

12 设行输入缓冲区为一个栈结构，每接受一个字符后便进行判断： （1）如果它既不是退格符#也不是退行符@，则将其压入栈顶；
3.2 栈的应用 算法思想 设行输入缓冲区为一个栈结构，每接受一个字符后便进行判断： （2）如果是一个#，则从栈顶删除一个字符； 算法 3.2

13 a+(b*c+d)/e abc*d+e/+ 算符：运算符和界符。 算符的优先关系：<、=、> （见表3.1)
3.2 栈的应用 4.表达式求值 概念 前缀表达式 : +a b 中缀表达式 : a+b 后缀表达式 : a b+ 中缀表达式 后缀表达式（逆波兰表达式) a*b+c ab*c+ a+b*c abc*+ a+(b*c+d)/e abc*d+e/+ 算符：运算符和界符。 算符的优先关系：<、=、> （见表3.1) 这里重点介绍中缀表达式、后缀表达式求值。

14 3.2 栈的应用 刚读入的 栈顶的 表 3.1 算符间的优先关系

15 ①设置两个工作栈,运算符栈OPTR 和操作数栈OPND。操作数栈也放表达式的运算结果；
3.2 栈的应用 （1）中缀表达式求值：操作数栈和运算符栈 算法思想 ①设置两个工作栈,运算符栈OPTR 和操作数栈OPND。操作数栈也放表达式的运算结果； ②置操作数栈为空栈，置运算符栈的栈底为表达式的起始符#； ③自左向右扫描表达式(即每次读一个字符)； ④若遇操作数，则进栈OPND，转③ ---Reverse Polish Notation

16 ⑤遇运算符，则运算符与OPTR栈顶进行优先数比较(同级的栈项为大，刚读入的为小)： 若读的运算符大于OPTR栈顶项，则进栈，转③；
3.2 栈的应用 ⑤遇运算符，则运算符与OPTR栈顶进行优先数比较(同级的栈项为大，刚读入的为小)： 若读的运算符大于OPTR栈顶项，则进栈，转③； 若栈顶项大，则栈顶运算符退栈，操作数栈顶两个元素退栈，并作一个运算，结果入栈OPND，转③； 若相等且为括号，则脱括号，转③ ； 若读的运算符为#，则转⑥； ⑥若运算符栈顶项为#，则操作数栈顶为计算结果，结束；否则出错 ---Reverse Polish Notation

17 3.2 栈的应用 例：扫描 A+B*C-D/(E+F)# # # A B*C + C 进栈 ‘+’>’#’ B *
3.2 栈的应用 例：扫描 A+B*C-D/(E+F)# # 操作数 运算符 操作数 # 运算符 A B*C + C 进栈 遇"-" <"*" 做B*C并进栈 ‘+’>’#’ B * ’ *’ >’+’ A + F + 操作数 # 运算符 A+B*C 操作数 # 运算符 A+B*C 进栈 ‘+’ > ‘( ‘ ‘(‘ > ’/’ ’/’ > ’-‘ ‘-’ > # ---Reverse Polish Notation "-"<"+" 做A+B*C 并进栈 E ( D / -

18 3.2 栈的应用 # A+B*C D - / E F ( + # A+B*C D - / ( 遇’)’ < ’+’ E+F 做E+F
3.2 栈的应用 操作数 # 运算符 A+B*C D - / E F ( + 操作数 # 运算符 A+B*C D - / ( 遇’)’ < ’+’ E+F 做E+F 操作数 # 运算符 A+B*C D - / E+F 操作数 # 运算符 A+B*C D/(E+F) - ’ ) ’ = ’( ‘ 脱括号 ‘做D/(E+F) ---Reverse Polish Notation ‘#’<‘/’

19 3.2 栈的应用 算法 D/(E+F) A+B*C - A+B*C-D/(E+F) # # 3.4 操作数 运算符 操作数 运算符
3.2 栈的应用 操作数 # 运算符 A+B*C D/(E+F) - 操作数 # 运算符 A+B*C-D/(E+F) ‘#’<’/’ 做D/(E+F) ‘#’<’/’ 做A+B*C-D/(E+F) ‘#’=‘#’ 操作数出栈 ---Reverse Polish Notation 即计算结果 算法 3.4

20 从左到右扫描向量IFX，重复下述两步操作，直到表达式尾。 ① 从IFX中取出下个TOKEN(数字、运算符、左括号、右括号)；
3.2 栈的应用 （2）中缀表达式转为后缀表达式 设中缀表达式和后缀表达式分别在向量IFX和PFX中，用栈S实现中缀式转为后缀式，对IFX中表达式从左到右扫描，设TOKEN是扫描读到的符号，转换算法可描述如下: 栈初始化。 从左到右扫描向量IFX，重复下述两步操作，直到表达式尾。 ① 从IFX中取出下个TOKEN(数字、运算符、左括号、右括号)；

21 操作符：如栈空或TOKEN比栈顶元素优先级高，将TOKEN进栈；否则，退栈并将退栈元素送入PFX，然后再将TOKEN与新栈顶元素比较之;
3.2 栈的应用 ② CASE TOKEN OF '('：将TOKEN压入栈S; 操作数：将操作数直接送入PFX; 操作符：如栈空或TOKEN比栈顶元素优先级高，将TOKEN进栈；否则，退栈并将退栈元素送入PFX，然后再将TOKEN与新栈顶元素比较之; ‘)' ：退栈并将退栈元素送PFX，直到碰到左括号，左括号退栈不送PFX。 当遇到中缀表达式结束符号，连续退栈并送退栈元素到PFX，直至栈空。

22 c.若是运算符，从栈中弹出2个数，将运算结果再压入栈 d.若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转a
3.2 栈的应用 （3）后缀表达式求值步骤： a.读入表达式一个字符 b.若是操作数，压入栈，转d c.若是运算符，从栈中弹出2个数，将运算结果再压入栈 d.若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转a 后缀表达式：435*+ 例 计算 4+3*5 top 7 3 5 top 4 top 4 3 top 4 15 top 19 top

23 当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：
3.3 栈与递归的实现 当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事： 将所有的实在参数、返回地址等信息传递给被调用函数保存 为被调用函数的局部变量分配存储区 将控制转移到被调用函数的入口 而从被调用函数返回调用函数之前，应该完成： 保存被调函数的计算结果 释放被调函数的数据区 依照被调函数保存的返回地址将控制转移到调用函数 由于函数的运行规则是：后调用先返回，因此各函数占有的存储管理应实行"栈式管理"

24 3.3 栈与递归的实现 1. 过程的嵌套调用 r s t 子过程2 r s 子过程1 r s t 子过程3 r 主程序 r s r

25 3.3 栈与递归的实现 例 递归的执行情况分析 2. 递归过程及其实现 递归：函数直接或间接的调用自身叫递归 实现：建立递归工作栈
3.3 栈与递归的实现 2. 递归过程及其实现 递归：函数直接或间接的调用自身叫递归 实现：建立递归工作栈 例 递归的执行情况分析 void print(int w) { int i; if ( w!=0) { print(w-1); for(i=1;i<=w;++i) printf(“%3d,”,w); printf(“/n”); } 运行结果： 1， 2，2， 3，3，3，

26 3.3 栈与递归的实现 3.递归调用执行情况如下： 1 print(0); （3）w=1 （2）w=2 （1）w=3 top (4)输出：1
3.3 栈与递归的实现 1 print(0); （3）w=1 （2）w=2 （1）w=3 top (4)输出：1 w （4）w=0 （3）w=1 （2）w=2 （1）w=3 top w 3.递归调用执行情况如下： 2 print(1); （2）w=2 （1）w=3 top (3) 输出：2, 2 w 3 print(2); （1）w=3 top (2) 输出：3, 3, 3 w (4)输出：1 (3) (2) (1) top 返回 (3) (2) (1) 3 top (4) 主程序 (3) 输出：2, 2 (2) 2 (1) 3 top (1) print(w) w=3; (2) 输出：3, 3, 3 (1 ) 3 top 结束 (1)

27 3.3 栈与递归的实现 5.Tower of Hanoi问题 问题描述：有X,Y,Z三个塔座，X上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔,编号1,2,3……n。要求将n个圆盘从X移到Z，叠放顺序不变，移动过程中遵循下列原则： 每次只能移一个圆盘 圆盘可在三个塔座上任意移动 任何时刻，每个塔座上不能将大盘压到小盘上 解决方法： n=1时，直接把圆盘从X移到Z n>1时，先把上面n-1个圆盘从X移到Y,然后将n号盘从X移到Z,再将n-1个盘从Y移到Z。即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题

28 3.3 栈与递归的实现 X Y Z

29 3.3 栈与递归的实现 X Y Z

30 3.3 栈与递归的实现 X Y Z

31 3.3 栈与递归的实现 X Y Z

32 3.3 栈与递归的实现 X Y Z

33 3.3 栈与递归的实现 X Y Z

34 3.3 栈与递归的实现 X Y Z

35 3.3 栈与递归的实现 X Y Z

36 3.3 栈与递归的实现 X Y Z

37 3.3 栈与递归的实现 X Y Z

38 3.3 栈与递归的实现 X Y Z

39 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示
3.3 栈与递归的实现 X Y Z 执行情况： 递归工作栈保存内容：形参n,x,y,z和返回地址 返回地址用行编号表示 n x y z 返回地址

40 3.3 栈与递归的实现 main() { int m; printf("Input number of disks”);
3.3 栈与递归的实现 A B C 1 2 3 main() { int m; printf("Input number of disks”); scanf("%d",&m); printf(”Steps : %3d disks”,m); hanoi(m,'A','B','C'); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,x,z,y); (6) move(n,x,z); (7) hanoi(n-1,y,x,z); (8) } (9) } 3 A B C 0 3 A B C 0 2 A C B 6 3 A B C 0 2 A C B 6 1 A B C 6 A B C 3 A B C 0 2 A C B 6

41 3.3 栈与递归的实现 main() { int m; printf("Input the number of disks
3.3 栈与递归的实现 3 A B C 0 2 A C B 6 main() { int m; printf("Input the number of disks scanf("%d",&m); printf("The steps to moving %3d hanoi(m,'A','B','C'); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,x,z,y); (6) move(n,x,z); (7) hanoi(n-1,y,x,z); (8) } (9) } A B C 3 A B C 0 2 A C B 6 1 C A B 8 A B C 3 A B C 0 2 A C B 6 3 A B C 0

42 3.3 栈与递归的实现 main() { int m; printf("Input the number of disks
3.3 栈与递归的实现 main() { int m; printf("Input the number of disks scanf("%d",&m); printf("The steps to moving %3d hanoi(m,'A','B','C'); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,x,z,y); (6) move(n,x,z); (7) hanoi(n-1,y,x,z); (8) } (9) } 3 A B C 0 A B C 3 A B C 0 2 B A C 8 3 A B C 0 2 B A C 8 1 B C A 6 A B C 3 A B C 0 2 B A C 8

43 3.3 栈与递归的实现 main() { int m; printf("Input the number of disks
3 A B C 0 2 B A C 8 3.3 栈与递归的实现 main() { int m; printf("Input the number of disks scanf("%d",&m); printf("The steps to moving %3d hanoi(m,'A','B','C'); (0) } void hanoi(int n,char x,char y,char z) (1) { (2) if(n==1) (3) move(1,x,z); (4) else{ (5) hanoi(n-1,x,z,y); (6) move(n,x,z); (7) hanoi(n-1,y,x,z); (8) } (9) } A B C 3 A B C 0 2 B A C 8 1 A B C 8 A B C 3 A B C 0 2 B A C 8 3 A B C 0 栈空

44 3.3 栈与递归的实现 6.地图四染色问题 1# 紫色 2# 黄色 3# 红色 4# 绿色 1 2 3 4 5 6 7
3.3 栈与递归的实现 6.地图四染色问题 R [ 7][ 7 ] (1) (2) (4) (5) (6) (7) (3) 1# 紫色 2# 黄色 3# 红色 4# 绿色 1 2 3 2 4 3 2 4 4 3 3 1

45 1.队列的定义及特点 3.4 队列 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端
3.4 队列 1.队列的定义及特点 定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表 队尾(rear)——允许插入的一端 队头(front)——允许删除的一端 队列特点：先进先出(FIFO) a1 a2 a3…………………….an 入队 出队 front rear 队列Q=(a1,a2,……,an) 双端队列 a1 a2 a3…………………….an 端1 端2 入队 出队

46 3.4 队列 2.链队列 typedef struct Qnode 结点定义 { QElemType data;
3.4 队列 2.链队列 结点定义 typedef struct Qnode { QElemType data; struct Qnode *next; }Qnode, *QueuePtr; Typedef struct { QueuePtr front; QueuePtr rear; } 头结点 ^ …... front 队头 队尾 rear 设队首、队尾指针front和rear, front指向头结点，rear指向队尾

47 3.4 队列 空队 ^ front rear x入队 x ^ front rear y入队 x y ^ front rear x出队 x y
3.4 队列 front rear 空队 ^ front rear x入队 ^ x front rear y入队 x ^ y front rear x出队 x ^ y front rear y出队 ^

48 3.4 队列 入队算法 出队算法

49 3.4 队列 3.循环队列——队列的顺序存储结构 实现：用一维数组实现sq[M] 空队列条件：front==rear
3.4 队列 3.循环队列——队列的顺序存储结构 实现：用一维数组实现sq[M] rear 1 2 3 4 5 J4,J5,J6入队 J4 J5 J6 front Q.front=0 Q.rear=0 1 2 3 4 5 队空 1 2 3 4 5 front J1,J1,J3入队 rear 1 2 3 4 5 J1,J2,J3出队 J1 J2 J3 rear rear front J3 front rear J2 front J1 front 设两个指针front,rear,约定： Q.rear指示队尾元素的下一个位置； Q.front指示队头元素 初值Q.front=Q.rear=0 空队列条件：front==rear 入队列：sq[rear++]=x; 出队列：x=sq[front++];

50 3.4 队列 存在问题 设数组大小为M，则： 当front=0,rear=M时，再有元素入队发生溢出——真溢出
3.4 队列 存在问题 设数组大小为M，则： 当front=0,rear=M时，再有元素入队发生溢出——真溢出 当front0,rear=M时，再有元素入队发生溢出——假溢出 解决方案 队首固定，每次出队剩余元素向下移动——浪费时间 循环队列 基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear==M,则令rear=0; M-1 rear 1 front …... 实现：利用“模”运算 入队： sq[rear]=x; rear=(rear+1)%M; 出队： x=sq[front]; front=(front+1)%M; 队满、队空判定条件

51 3.4 队列 front rear rear J5 J4 J3,J4,J5出队 队空：front==rear J3 J6,J7,J8入队
3.4 队列 1 2 3 4 5 rear front J3 J4 J5 1 2 3 4 5 rear front 初始状态 J3,J4,J5出队 队空：front==rear J4 J5 J6 1 2 3 4 5 rear front J3 J8 J7 J6,J7,J8入队 解决方案： 1.另外设一个标志以区别队空、队满 2.少用一个元素空间： 队空：front==rear 队满：(rear+1)%M==front 队满：front==rear

52 循环队列的顺序存储结构 #define MAXQSIZE 100 // 最大队列长度
3.4 队列 循环队列的顺序存储结构 #define MAXQSIZE 100 // 最大队列长度 typedef struct { 　　QElemType *base;// 初始化的动态分配存储空间 　　int rear; 　　　// 队尾指针，指向队尾元素的下一个位置 　　int front;　　　// 队头指针，指向队头元素　　 } SqQueue;

53 循环队列的基本操作的算法描述 3.4 队列 Status InitQueue (SqQueue &Q){ // 构造一个空队列 Q
3.4 队列 循环队列的基本操作的算法描述 Status InitQueue (SqQueue &Q){ // 构造一个空队列 Q Q.base = (QElemType *)malloc(MAXQSIZE *sizeof(QElemType)); // 为循环队列分配存储空间 if (!Q.base) exit(OVERFLOW); // 存储分配失败 Q.front = Q.rear = 0; return OK; } // InitQueue

54 int QueueLength (SqQueue Q){ // 返回队列Q中元素个数，即队列的长度
return ((Q.rear-Q.front+MAXQSIZE) % MAXQSIZE); }

55 3.4 队列 入队算法： 出队算法：

56 本章小结 栈和队列都属线性结构，因此它们的存储结构和线性表非常类似，同时由于它们的基本操作要比线性表简单得多，因此它们在相应的存储结构中实现的算法都比较简单，相信对大家来说都不是难点。 这一章的重点则在于栈和队列的应用。通过本章所举的例子学习分析应用问题的特点，在算法中适时应用栈和队列。

57 2. 如果进栈序列为123456，则能否得到435612和135426的出栈序列，并请说明为什么不能得到。
基础知识题 1. 进栈序列为123，则可能得到的出栈序列是什么? 2. 如果进栈序列为123456，则能否得到435612和135426的出栈序列，并请说明为什么不能得到。 3. 简述栈和线性表的差别。 4. 简述队列和栈这两种数据类型的相同点和差异处。