华师本科生数据结构课件 第4章 栈与队列

1、引例,餐馆中一叠一叠的盘子：如果它们是按 1,2,n 的次序往上叠的，那么使用时候的次序应是什么样的？,必然是依从上往下的次序，即n,2,1。它们遵循的是后进先出的规律，这正是本章要讨论的栈的结构特点。,是排队。在计算机程序中，模拟排队的数据结构是队列。,栈和队列是两种特殊的线性表,是操作受限的线性表,称限定性数据结构。,在日常生活中，为了维持正常的社会秩序而出现的常 见现象是什么？,第4章 栈和队列,4.1 栈 4.2 栈的应用举例 4.3 队列 4.4 队列应用举例,【学习目标】,掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 熟练掌握栈类型的两种实现方法。 熟

2、练掌握循环队列和链队列的基本操作实现算法。 理解递归算法执行过程中栈的状态变化过程。,【重点和难点】,栈和队列是在程序设计中被广泛使用的两种线性数据结构，本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。,重点：栈和队列的基本特征，表示与实现 难点：递归、循环队列 算法：栈和队列的实现及其应用,顺序栈、链栈、递归、循环队列、链队列,【知识点】,【学习指南】,本章主要是学习如何在求解应用问题中适当地应用栈和队列,栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。,本章要求必

3、须完成的算法设计题为： 4.1, 4.2, 4.3, 4.4, 4.5, 4.6, 4.9, 4.11, 4.12,4.1 栈,是限定仅在表尾进行插入或删除操作的线性表。 允许插入,删除的一端称为栈顶(top),另一端称为栈底(bottom),top,bottom,进栈,出栈,an . . . . a1,基本操作：,后进先出(LIFO),定义：,栈 特殊的线性表：操作受限的线性表,逻辑特征：,创建一个空栈； 判断栈是否为空栈； 判断栈是否为满； 往栈中插入(或称推入)一个元素； 从栈中删除(或称弹出)一个元素； 求栈顶元素的值。 访问栈中每个元素,栈和队列是两种常用的数据类型,栈和队列是限定插

4、入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x)Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,一般线性表 堆栈 逻辑结构：一对一 逻辑结构：一对一 存储结构：顺序表、链表 存储结构：顺序栈、链栈 运算规则：随机存取 运算规则：后进先出(LIFO),1. 定义,与线性表相同,仍为一对一关系。,用顺序栈或链栈存储均可,顺序栈更常见,只能在栈顶运算,且访问结点时依照后进先出(LIFO)或先进后出(FILO)的原则。,关键是编写入栈和出栈

5、函数，具体实现依顺序栈或链栈的不同而不同。 基本操作有入栈、出栈、读栈顶元素值、建栈、判栈满、判栈空等。,限定只能在表的一端进行插入和删除运算的线性表(只能在栈顶操作),4.1.1 栈的特点和操作,例如： 栈 s = ( a1 , a2, a3, , an-1, an ),an 称为栈顶元素,插入元素到栈顶(即表尾)的操作，称为入栈。 从栈顶(即表尾)删除最后一个元素的操作，称为出栈。,强调：插入和删除都只能在表的一端（栈顶）进行！,a1 称为栈底元素,栈是仅在表尾进行插入、删除操作的线性表。 表尾(即 an 端)称为栈顶 top ; 表头(即 a1 端)称为栈底base,“进” 压入=PUS

6、H（x) “出” 弹出=POP ( y ),4.1.1 栈的特点和操作,栈的基本操作,InitStack(,顺序栈中的PUSH函数 status Push( ElemType x ) if ( topM ) 上溢 else vtop+ = x; ,Push( B );,Push( C );,Push( D );,低地址L,Push( A );,高地址M,B,C,D,出栈操作: 例如从栈中取出B（注意要遵循“后进先出” 原则）,核心语句： Pop ( ); Pop ( ); Printf( Pop () );,顺序栈中的POP函数 status Pop( ) if ( top=L ) 下溢 el

7、se y = v-top; return( y ); ,若入栈动作使地址向高端增长，称为“向上生成”的栈； 若入栈动作使地址向低端增长，称为“向下生成”的栈； 对于向上生成的栈 入栈口诀：堆栈指针top先压后加（vtop+=x）； 出栈口诀：堆栈指针top先减后弹（y=v-top) 。,栈不存在的条件：base=NULL; 栈为空 的条件 ： base=top; 栈满的条件 ： top-base=stacksize;,问：为什么要设计堆栈？它有什么独特用途？,调用函数或子程序非它莫属； 递归运算的有力工具； 用于保护现场和恢复现场； 简化了程序设计的问题。,答：,问：栈是什么？ 它与一般线性表

8、有什么不同？,答：栈是一种特殊的线性表,它只能在表的一端(即栈顶)进行插入和删除运算。 与一般线性表的区别：仅在于运算规则不同。,例 对于一个栈,给出输入项A、B、C,如果输入项序列由ABC组成， 试给出所有可能的输出序列。,A进 A出 B进 B出 C进 C出 ABC A进 A出 B进 C进 C出 B出 ACB A进 B进 B出 A出 C进 C出 BAC A进 B进 B出 C进 C出 A出 BCA A进 B进 C进 C出 B出 A出 CBA 不可能产生输出序列CAB,例 一个栈的输入序列是12345，若在入栈的过程中允许出栈，则栈的输出序列43512可能实现吗？12345的输出呢？,43512

9、不可能实现，主要是其中的12顺序不能实现； 12345的输出可以实现，只需压入一个立即弹出一个即可。,435612中到了12顺序不能实现； 135426可以实现。,例 如果一个栈的输入序列为123456，能否得到435612和135426的出栈序列？,答：,答：,例：设依次进入一个栈的元素序列为c,a,b,d, 则可得到出栈的元素序列是： ）a,b,c,d）c,d,a,b）b,c,d,a）a,c,d,b,A、D可以( B、C不行)。,讨论：有无通用的判别原则？ 有。在可能的输出序列中，不存在这样的输入序列i,j,k，能同时满足 ijk 和 PjPkPi,答：,SqStack：结构类型名； Sq

10、Stack: 它的三个域分别是： base： 栈底指针，指向栈底位置； top： 栈顶指针； Stacksize：已分配的存储空间(一元素为单位)大小；,const STACK_INIT_SIZE 100 const STACKINCREMENT 10 typedef struct SElemType *elem; int top /栈顶指针 int stacksize; int increment; SqStack;,顺序栈算法,约定栈顶指针指向栈顶元素的下(后面)一个位置,void InitStack_Sq(SqStack /InitStack_Sq,1) 初始化操作InitStack_S

11、q(SqStack struct node *next; Node; typedef LinkList LinkStack;,栈底,top,q,链栈的定义,typedef int bool; #define TRUE 1; #define FALSE 0; typedef int Data; typedef struct node ElemType data; struct node *next; LNode; Typedef LinkList LinkStack,初始化 void InitStack_L( LinkStack *S ) S = NULL; 入栈 void Push_L ( L

12、inkStack *S, ElemType e ) LNode *p = new LNode ; p-data = e; p-next = S; S = p; ,顺序栈算法,入栈算法,栈底,x,p,判栈空 bool StackEmpty_L( LinkStack *S ) return !S; 出栈 bool Pop_L( LinkStack *S, ElemType *e ) if ( S ) LNode *p = S; S = S-next; *e = p-data; delete p; return TRUE; else return FALSE; ,取栈顶 bool GetTop_L(

13、 LinkStack *S, ElemType *e ) if ( !S ) return 0; else *e = S-data; return 1; 置栈空 int MakeEmpty_L( LinkStack *S ) Lnode *p; while( S ) p = S; S = S-next; delete p; ,链栈算法,出栈算法,栈底,top,X,3.2 栈的应用举例,例一、 数制转换,例二、 括号匹配的检验,例三、 背包问题求解,例四、 表达式求值,例五、 实现递归,例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 81348 1

14、68 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,算法基于原理：N = (N div d)d + N mod d,例一 数制转换,void conversion () InitStack(S); scanf (%d,N); while (N) Push(S, N % 8); N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( %d, e ); / conversion,假设在表达式中: （）或（ ） 等为正确的格式，（ ）或（ ）或 ( ( ) ) 均为不正确的格式。,检验括号是否匹配的方法可用 “期待的急迫程度” 来描述

15、。,例二 括号匹配的检验,例如: 考虑下列括号序列: ( ) 1 2 3 4 5 6 7 8,分析可能出现的不匹配的情况:,算法的设计思想,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空,若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈” 否则表明不匹配,3）表达式检验结束时，若栈空，则表明表达式中匹配正确 否则表明“左括弧”有余,bool matching(string exp ) int state = 1; ch = *exp+； while ( ch != # ,设有一个背包可以放入的物品的重量为s，现有n件物品，重量分别为w1,w2,wn。

16、问能否从这n件物品中选择若干件放入此背包中，使得放入的重量之和正好为s。如果存在一种符合上述要求的选择，则称此背包问题有解(或称其解为真)；否则称此背包问题无解(或称其解为假)。,例三 背包问题,一个背包可以放入的物品重量为s, 现有n件物品, 重量分别为w1,w2,wn,问能否从这些物品中选若干件放入背包中, 使得放入的重量之和正好是s。如果存在一种符合上述要求的选择,则称此背包问题有解,否则此问题无解。,例三 背包问题,如果有解： 1. 选择的一组物品中不包含wn; knap( s,n-1 ) 的解就是knap( s,n)的解； 2. 选择的一组物品中包含wn; knap( s-wn,n

17、-1 )的解就是knap( s,n)的解.,背包问题表示：int knap( int s,int n ) 其中，s=0, n=1,8,4,3,5,2,1,背包容积 T=10,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,k=0,0 1 2,3 4 5,k,背包问题求解,T=10,1-8,4,3,5,2,0-1,背包容积 T=1,k=2 放不进去,0 1 2,3 4 5,k=3 放不进去,k=4 放不进去,K=0,1进栈,k=3,4,5 放不进去 ,k=6 注意内循环条件 while (T 0 条件满足输出一组解,栈顶元素出栈,物品体积 wi = 1, 8, 4, 3

18、, 5, 2 i=05, n=6,背包问题求解,T=10,8,2-4,3-3,5,2,0-1,背包容积 T=2,k=5,0 1 2,3 4 5,栈不空继续找解(注意外循环条件),物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,2-4,3-3,5,2,0-1,背包容积 T=2,k=6,0 1 2,3 4 5,T不等于0,不输出,栈顶出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,2-4,3,5,2,0-1,背包容积 T=5,k=3,0 1 2,3 4 5,k=4 继续入栈,物品体积

19、wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,2-4,3,4-5,2,0-1,背包容积 T=0,k=4,0 1 2,3 4 5,T=0 又找到一组解,栈顶元素出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,2-4,3,5,2,0-1,背包容积 T=5,k=4,0 1 2,3 4 5,K=5 进栈,继续找解,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,2-4,3,5,5-2,0-1,背包容积 T=3,k=5,0 1 2,3 4 5,T

20、不为0 继续找解,栈顶出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,2-4,3,5,2,0-1,背包容积 T=5,k=5,0 1 2,3 4 5,栈不空继续找解(外循环),物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,2-4,3,5,2,0-1,背包容积 T=5,k=6,0 1 2,3 4 5,不满足内循环条件,T0,出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3,5,2,0-1,背包容积 T=9,k=2,0

21、1 2,3 4 5,继续找解,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3-3,4-5,2,0-1,背包容积 T=1,k=3 进栈,0 1 2,3 4 5,脱离内循环,必须出栈,继续找解,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3-3,5,2,0-1,背包容积 T=6,k=4,0 1 2,3 4 5,k=4栈顶出栈后， k=5进栈继续找解,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3-3,5,5-2,0

22、-1,背包容积 T=4,k=5,0 1 2,3 4 5,T不为0不输出,栈顶出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3-3,5,2,0-1,背包容积 T=6,k=5出栈,0 1 2,3 4 5,外循环条件,栈不空继续找解,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3,5,2,0-1,背包容积 T=9,k=3出栈,0 1 2,3 4 5,不进入内循环,栈顶出栈,继续找解,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=

23、10,8,4,3,4-5,5-2,0-1,背包容积 T=2,k=4进栈,0 1 2,3 4 5,T不为0不输出,栈顶出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3,4-5,5-2,0-1,背包容积 T=4,k=5出栈后,0 1 2,3 4 5,栈不空继续找解,k=6不进入内循环,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3,5,2,0-1,背包容积 T=9,k=4出栈,0 1 2,3 4 5,继续找解,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05

24、, n=6,背包问题求解,T=10,8,4,3,5,5-2,0-1,背包容积 T=7,k=5进栈,0 1 2,3 4 5,T不为0不输出,不进入内循环,出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3,5,2,0-1,背包容积 T=9,k=5出栈后,0 1 2,3 4 5,栈不空继续找解,不进入内循环,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3,5,2,1,背包容积 T=10,k=0出栈后,0 1 2,3 4 5,栈空了，但kn继续找解,进入内循环,物品体积 wi

25、 = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,1-8,4,3,5,2,1,背包容积 T=2,k=2 不进栈,0 1 2,3 4 5,继续找解,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,1-8,4,3,5,5-2,1,背包容积 T=0,k=5进栈,0 1 2,3 4 5,找到一组解,栈顶出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,1-8,4,3,5,2,1,背包容积 T=0,k=5出栈,0 1 2,3 4 5,栈不空继续找解,不进入内循环,栈顶

26、出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,8,4,3,5,2,1,背包容积 T=10,k=1出栈后,0 1 2,3 4 5,栈空了，但kn继续找解,进入内循环,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,继续找解 继续找解 吐血！,8,4,3,5,5-2,1,背包容积 T=2,快完了k=5进栈,0 1 2,3 4 5,脱离内循环,栈顶出栈,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,背包问题求解,T=10,背包问题求解,8,4,3,5,2,1,背包容

27、积 T=10,k=5,0 1 2,3 4 5,终于！栈空了,k=n了，呜呼哀哉！ 没有计算机是多么痛苦并快乐的事！,物品体积 wi = 1, 8, 4, 3, 5, 2 i=05, n=6,T=10,递归定义,int knap( int s, int n ) if ( s=0 ) return 1; else if ( s0 ,非递归程序,struct NodeBag int s , n ; int r ; /* r的值为1,2,3 */ int k; ; typedef struct NodeBag DataType; PSeqStack st; struct NodeBag x;,void

28、 knapsack( int w, int T, int n ) InitStack(S); k = 0; do while( T0 ,限于二元运算符的表达式定义: 表达式 := (操作数) (运算符) (操作数) 操作数 := 简单变量 | 表达式 简单变量 : = 标识符 | 无符号整数,例四 表达式求值,表达式的三种标识方法：,设 Exp = S1 OP S2,则称 OP S1 S2 为前缀表示法,S1 S2 OP 为后缀表示法,S1 OP S2 为中缀表示法,例如: Exp = a b + (c d / e) f 前缀式: + a b c / d e f 中缀式: a b + c d

29、/ e f 后缀式: a b c d e / f +,结论:,1) 操作数之间的相对次序不变;,2) 运算符的相对次序不同;,3) 中缀式丢失了括弧信息, 致使 运算的次序不确定;,4) 前缀式的运算规则为: 连续出现的两个操作数和在它们前且紧靠它们的运 算符构成一个最小表达式;,5) 后缀式的运算规则为: 运算符在式中出现的顺序恰为表达式的运算顺序; 每个运算符和在它之前出现 且紧靠它的两个操作数构成一个最小表达式;,如何从后缀式求值？,先找运算符，再找操作数,例如： a b c d e / f +,ab,d/e,c-d/e,(c-d/e)f,如何从原表达式求得后缀式？,每个运算符的运算次序

30、要由它之后的一个运算符来定，在后缀式中,优先数高的运算符领先于优先数低的运算符。,分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a + b c d / e f 后缀式: a b c + d e / f ,从原表达式求得后缀式的规律为：,1) 设立暂存运算符的栈;,2) 设表达式的结束符为“#”, 予设运算符栈的栈底为“#”,3) 若当前字符是操作数，则直接发送给后缀式;,4) 若当前运算符的优先数高于栈顶运算符，则进栈;,5) 否则，退出栈顶运算符发送给后缀式;,“(” 对它之前后的运算符起隔离作用，“)”可视为自相应左 括弧开始的表达式的结束符。,算法思想 设定两栈：操作符栈

31、OPTR ，操作数栈 OPND 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 #； 依次读入字符：是操作数则入OPND栈，是操作符则要判断： if 操作符 栈顶元素，压入OPTR栈。,表达式求值,中缀表达式 后缀表达式（RPN) a*b+c ab*c+ a+b*c abc*+ a+(b*c+d)/e abc*d+e/+,中缀表达式：操作数栈和运算符栈,例 计算 2+4-3*6,中缀表达式求值举例,表达式求值示意图：5+6(1+2)-4,#,+,(,+,-,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18

32、=23,23-4=19,6,1,2,3,18,4,5,23,19,中缀表达式求值,后缀表达式求值步骤： 1、读入表达式一个字符 2、若是操作数，压入栈，转4 3、若是运算符，从栈中弹出2个数，将运算结果再压入栈 4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1,例 计算 4+3*5,后缀表达式：435*+,后缀表达式求值,double evalution ( char suffix ) ch = *suffix+; InitStack( S ); while ( ch != “#” ) if ( !OpMember(ch) ) Push(S,ch); else Pop( S, b

33、 ); Pop( S, a ); Push( S, Operate( a, ch, b ) ); ch = *suffix+; Pop( S, result ); return result; ,void transform( char suffix , char exp ) InitStack(S); Push(S, #); p = exp; ch = *p; k=0; while (!StackEmpty(S) if (!OpMember(ch) Suffixk+ = ch; else if ( ch!= # ) ch = *+p; / while suffixk = 0; , ,swit

34、ch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) suffixk+ = c; Pop(S, c); break; defult : while( Gettop(S, c) / switch,递归的定义,例5 实现递归,递归的过程：一个过程直接或间接地调用自己 如：0的阶乘是1，n(n0)的阶乘等于n乘上(n-1)的阶乘,线性表的另一种定义: 若元素个数为0，则称为空表 若元素个数大于0,则有且仅有一个第一个元素(即表头) , 剩余 元素形成一个表(即表尾) 。,递归的对象：一个对象部分地包含它自己，或

35、用它自己给自己定义。 (如某些数据结构的定义),递归的应用 递归定义：如阶乘、Fibonacci数列等 数据结构：如表、树、二叉树等 问题求解：如Hanoi塔,例5 实现递归,将所有的实在参数、返回地址等信息传递给被调用函数保存; 为被调用函数的局部变量分配存储区; 将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,从被调用函数返回调用函数之前,应该完成三项任务：,保存被调函数的计算结果; 释放被调函数的数据区; 依照被调函数保存的返回地址将控制转移到调用函数。,多个函数嵌套调用的规则是:,此时的内存管理实行“栈式管理”,后调用

36、先返回！,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,main的数据区,函数a的数据区,函数b的数据区,递归工作栈：递归过程执行过程中占用的数据区。 递归工作记录：每一层的递归参数合成一个记录。 当前活动记录：栈顶记录指示当前层的执行情况。 当前环境指针：递归工作栈的栈顶指针。,递归函数执行过程可视为同一函数进行嵌套调用,例如：,栈的应用 - 过程的嵌套调用,递归调用执行情况如下：,void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i=w;+i) pr

37、intf(“%3d,”,w); printf(“/n”); ,运行结果： 1， 2，2， 3，3，3，,栈与递归的实现,定义是递归的,求解阶乘函数的递归算法 long fact ( long n ) if ( n = 0 ) return 1;/递归结束条件 else return n*fact (n-1); /递归的规则 ,我们看一下n=3阶乘函数fact(n)的执行过程,main( ) int n=3,y; L y= fact(n); ,L 3,L1 1,L1 2,1,n*fact (n-1),n*fact (n-1),fact(n),返回地址 实参,注意递归调用中 栈的变化,栈与递归的实

38、现,主程序 main( ): fact(4),直接定值为1,计算 4*fact(3),计算 3*fact(2),计算 2*fact(1),计算 1*fact(0),例 Ackermann函数A(n,x,y)的计算 x+1 n=0 x n=1,y=0 0 n=2,y=0 A(n,x,y)= 1 n=3,y=0 2 n=4,y=0 A(n-1,A(n,x,y-1),x) n!=0, y!=0,A(3,1,2) =A(2,A(3,1,1),1) =A(2,A(2,A(3,1,0),1),1) =A(2,A(2,1,1),1) =A(2,A(1,A(2,1,0),1),1) =A(2,A(1,0,1)

39、,1) =A(2,A(0,A(1,0,0),0),1) =A(2,A(0,0,0),1) =A(2,1,1) =A(1,A(2,1,0),1) =A(1,0,1) =A(0,A(1,0,0),0) =A(0,0,0),计算Ackermann函数A(n,x,y)的算法思想可以描述如下： 反复执行： (1) 递归：只要有n!=0 若栈空则结束算法， 否则: 出栈一组值，作新参数(n,y)；v赋给x； 构造出一个新函数A(n,x,y)，再递归。 定义递归出口，即n=0或y=0时的Ackermann函数.,int Ackerman( int n, int x, int y ) InitStack(S)

40、; e.nval = n; e.xval = x; e.yval = y; Push( S, e ); do GetTop( S, e ); while( e.navl!=0 ,typedef struct int nval; int xval; int yval; Elemtype;,int value( int n, int x, int y ) if ( n=0 ) return ( x+1 ); else switch( n ) case 1: return x; case 2: return 0; case 3: return 1; default: return 2; ,5.3 队

41、列 ( Queue ),定义 队列是只允许在一端删除，在另一端插入的顺序表, 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear)。 特性 先进先出(FIFO, First In First Out) 常用操作 初始化空队、入队、出队、判断队空、 判断队满、取队头,a0 a1 a2 an-1,front,rear,队头,入队,出队,队尾,队列的抽象数据类型定义见教材 队列的存储结构为链队或顺序队（常用循环顺序队）,插入元素称为入队；删除元素称为出队。,定 义,4.3.1 队列的结构特点和操作,与同线性表相同，仍为一对一关系。,顺序队或链队，以循环顺序队更常见。,只能在队首和

42、队尾运算，且访问结点时依照先进先出（FIFO）的原则。,关键是掌握入队和出队操作，具体实现依顺序队或链队的不同而不同。 基本操作有入队或出队，建空队列，判队空或队满等操作。,只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表 （头删尾插）,例如：队列 Q = ( a1, a2 , a3, ., an-1, an ),队头,队尾,队列的进队和出队原则,进队时队尾指针先进一 rear = rear + 1， 再将新元素按 rear 指示位置加入。 出队时队头指针先进一 front = front + 1， 再将下标为 front 的元素取出。 队满时再进队将溢出出错； 队空时再出队将队空

43、处理。 解决办法之一：将队列元素存放数组首尾相接, 形成循环(环形)队列。,队列的进队和出队示例,front,rear,空队列,front,rear,A进队,A,front,rear,B进队,A B,front,rear,C, D进队,A B C D,front,rear,A退队,B C D,front,rear,B退队,C D,front,rear,E,F,G进队,C D E F G,C D E F G,front,rear,H进队,溢出,队列的基本操作,InitQueue( rear=S; 出队（头部删除）：front-next=p-next;, 队列会满吗？,front=rear,一般不

44、会，因为删除时有free动作。除非内存不足！,Typedef LinkList QuencePtr; typedef struct / 链队列类型 QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,空队列,队列链队列的表示与实现,void InitQueue_L( LinkQueue ,void DestroyQuence_L( LinkQueue ,void EnQueue_L( LinkQueue ,bool DeQueue_L( LinkQueue ,if ( Q.rear = p ) Q.rear = Q.front;,nu

45、ll,*q,q.rear,x,null,q.front,p,存储池,循环队列 队列的顺序存储 约定与类型定义：Q.front和Q.rear的含义 删除：避免大量的移动-头指针增1 问题：假上溢首尾相接的环（钟）,队头 Q.front,入队,出队,a1,a2,a3,an,Q.rear,队尾,2、循环队列,基本操作的实现 初始化空队：Q.front=Q.rear=0; 入队：判断是否队满；非队满时，Q.rear位置放新插入的元素, Q.rear+ 出队：判断是否队空，非队空时，Q.front位置为待删除的元素, Q.front+ 队空条件：Q.front = Q.rear 队满条件：Q.rear

46、= MAXQSIZE 问题：假上溢(),Q.front,入队,出队,a1,a2,a3,an,Q.rear,队尾,循环队列,实现：用一维数组实现sqM,J1,J2,J3,设两个指针front,rear,约定： rear指示队尾元素； front指示队头元素前一位置 初值front=rear=-1,空队列条件：front=rear 入队列：sq+rear=x; 出队列：x=sq+front;,循环队列,当J6 入队后, 队尾指针Q.rear越界,不可能再插入新的队尾元素,但是另一方面,队列的实际可用空间并未占满。一个巧妙的办法是,将顺序队列设想为首尾相连的环状空间,当Q.rear 值超出队列空间的

47、最大位置时,令Q.rear= 0,使队列空间能“循环”使用。这种循环使用空间的队列称为循环队列。,循环队列图示,存在问题: 设数组维数为M，则：队首固定，每次出队剩 余元素向下移动浪费时间 解决方案: 循环队列 基本思想：把队列设想成环形，让sq0接在sqM-1之后, 若rear+1=M,则令rear=0;,实现：利用“模”运算 入队：rear=(rear+1)%M; sqrear=x; 出队：front=(front+1)%M; x=sqfront; 队满、队空判定条件,循环队列,假上溢的解决办法把顺序队列看成首尾相接的环(钟表)-循环队列 基本操作的实现 入队：Q.rear = ( Q.r

48、ear+1)%MAXQSIZE 出队：Q.front = ( Q.front+1)%MAXQSIZE 队空条件：Q.front = Q.rear 由于出队Q.front追上了Q.rear 队满条件：Q.front = Q.rear由于入队Q.rear追上了Q.front 问题：队空和队满的判断条件一样,循环队列,队空：front=rear 队满：front=rear,解决方案： 1. 另外设一个标志以区别队空、队满 2. 少用一个元素空间： 队空：front=rear 队满：(rear+1)%M=front,新问题：在循环队列中，空队特征是front=rear；队满时也会有front=rear

49、；判决条件将出现二义性！ 解决方案有三： 加设标志位，让删除动作使其为1,插入动作使其为0,则可识别当前front=rear 使用一个计数器记录队列中元素个数（即队列长度）； 人为浪费一个单元，令队满特征为front=(rear+1)%N；,循环队列讨论, 队列会满吗？ 很可能会，因为数组前端空间无法释放。因此数组应当有长度限制。, 空队列的特征？ 约定：front=rear,入队(尾部插入)：vrear=e; rear+; 出队(头部删除)：x=vfront; front+;,讨论：,假溢出,有缺陷, 怎样实现入队和出队操作？,问2： 在具有n个单元的循环队列中，队满时共有多少个元素？,n-

50、1个,6,问1：上图中队列长度L=？,队列存放数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队头指针出: front = (front+1) % maxSize; 队尾指针进: rear = (rear+1) % maxSize; 队列初始化：front = rear = 0; 队空条件： front = rear; 队满条件： (rear+1) % maxSize = front,4. 循环队列 (Circular Queue),队空：Q.front =Q. rear 队满： Q.front =(Q.rear + 1)

51、% maxSize 入队: Q.rear = (Q.rear + 1) % maxSize 出队: Q.front = (front + 1) % maxSize; 求队长:(Q.rear-Q.front+maxSize)%maxSize,#define MAXQSIZE 100 /最大队列长度 const QUENCE_INIT_SIZE = 100; Const QUENCEINCREMENTSIZE = 10; typedef struct QElemType *elem; / 动态分配存储空间 int front; /头指针,若队列不空,指向队列头元素 int rear; /尾指针,若

52、队列不空,指向队列尾元素 的下一个位置 int queuesize; int incrementsize; SqQueue;,循环队列,void InitQueue_Sq(SqQueue ,int QuenceLength(SqQueue Q) /返回Q的元素个数，即队列的长度 return (Q.rear-Q.front+Q.quencesize)%Q.quencesize; ,Status DeQueue (SqQueue ,void EnQueue (SqQueue ,例：一循环队列如下图所示，若先删除4个元素，接着再插入4个元素，请问队头和队尾指针分别指向哪个位置?,解：由图可知，队头

53、和队尾指针的初态分别为front=1和rear=6。,删除4个元素后front=5；再插入4个元素后，r=(6+4)%6=4,问：什么叫“假溢出” ？如何解决？,答：在顺序队中，当尾指针已经到了数组的上界，不能再有入队操作，但其实数组中还有空位置，这就叫“假溢出”。,解决假溢出的途径采用循环队列,例：数组n用来表示一个循环队列，f 为当前队列头元素的前一位置，r 为队尾元素的位置。假定队列中元素的个数小于n，计算队列中元素的公式为:,（） rf （）（nfr）% n （）nrf （） （nrf）% n,4种公式哪种合理？ 当 r f 时（A）合理； 当 r f 时（C）合理；,分析：,综合2种

54、情况，以（D）的表达最为合理,例：在一个循环队列中，若约定队首指针指向队首元素的前一个位置。那么，从循环队列中删除一个元素时，其操作是 先 ，后 。,移动队首指针,取出元素,问：为什么要设计队列？它有什么独特用途？,离散事件的模拟（模拟事件发生的先后顺序）； 操作系统中多道作业的处理（一个CPU执行多个作业）； 3. 简化程序设计。,答：,第 1 行 1 1 第 2 行 1 2 1 第 3 行 1 3 3 1 第 4 行 1 4 6 4 1,二项式系数值（杨辉三角）,设第 i-1行的值：(a0=0) a1.ai (ai+1=0) 则第 i 行的值：bj = aj-1+aj, j=1,2,i+1,1、计算 n 行杨辉三角的值,4.4 队列应用举例,利用循环队列计算二项式的过程：,假设只计算三行，则队列的最大容量为 5。,1,1,0,0,q.front,q.rear,1,1,0,0,1,q.front,q.rear,1,1,0,2,1,q.front,q.rear,1,1,0,2,1,q.front,q.rear,1,0,0,2,1,q.front,q.rear,1,0,1,2,1,q.front,q.rear,1,0,1,2,1,q.fro