第三章栈和队列(公共邮箱).ppt

1、第三章 栈 和 队列,3.1 栈 3.2 栈的应用举例 *3.3 栈与递归的实现 3.4 队列 *3.5 离散事件模拟,从数据结构的角度看: 栈、队列和线性表相同 从数据类型的角度看: 栈、队列和线性表不同 ListInsert(L, i, e) (1in+1) ListInsert(S, n+1, e) ListDelete(L, i，e)(1in) ListDelete(S, n),栈底,栈顶,只允许在一端插入和删除操作的线性表. 允许插入和删除的一端 称为栈顶 (top)，另一端 称为栈底(base) 特点: 后进先出 (LIFO),3.1 栈 ( Stack ),退栈,进栈,a1,an

2、,an-1,top,base,ADT Stack 数据对象：D ai |aiElemSet,i=1,2,.,n, n0 数据关系：R1|ai-1,aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： InitStack(/存储空间初始分配量 #define STACKINCREMENT 10;/存储空间分配增量 typedef struct SElemType *base; /栈底指针 SElemType *top; /栈顶指针 int stacksize; /当前已分配的存储空间,以元素为单位 SqStack;,空栈:S.base=S.top (初始化状态),a,b,c

3、,d,e,栈满:S.top-S.base=S.stacksize,若栈结构不存在，base为NULL,栈顶指针始终是指在栈顶元素的后面一个位置,顺序栈的初始化操作 Status InitStack(SqStack / InitStack,获取栈顶元素操作,Status GetTop(SqStack S, SElemType /GetTop,进栈操作,Status Push(SqStack /Push,出栈操作,Status Pop(SqStack /Pop,- - S.top;,e=*(S.top-1);,栈的链接存储表示 链栈,插入与删除仅在栈顶处执行,非常简单,不作讨论。,链栈: 利用链表

4、实现栈 注意链表中指针的方向是从栈顶到栈底。,3.2 栈的应用举例,问题有后进先出的特点 例一 数制转换 例二 括号匹配的检验 例三 行编辑程序问题 例四 迷宫求解 例五 表达式求值 例六 实现递归（3.3）,例一 数制转换 十进制数N和其他d进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理： N = (N div d)d + N mod d (其中:div为整除运算，mod为求余运算） 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,输出顺

5、序,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,例二 括号匹配的检验,假设表达式中允许包含两种括号: 即（）或（ ）等为正确的格式 （ ）或 ( )或（ ）均为不正确的格式。 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。 例如考虑下列括号序列： ( ) 1 2 3 4

6、 5 6 7 8 分析可能出现的不匹配的情况: 到来的右括弧非是所“期待”的; 到来的是“不速之客”; 直到结束，也没有到来所“期待”的。,算法设计思想： 1)凡出现左括号，则进栈； 2)凡出现右括号，首先检查栈是否空 若栈空，则表明右括号多了； 否则和栈顶元素比较,若匹配,则左括号出栈； 否则不匹配； 3)表达式检验结束时 若栈空，则匹配正确； 否则表明左括号多了，不匹配；,status matching(SqList exp) /顺序表exp中存有数据元素为字符的表达式,检验表达式中所含括弧是否正确嵌套,若是,则返回OK,否则返回ERROR state= 1; i =0; InitStac

7、k(S); while (i exp.length /matching,作业,1、从键盘输入一个整数序列：a1,a2,a3，an,编写算法PushPops实现;用栈存储输入的整数序列,当ai-1时,将ai进栈;当ai=-1时,输出栈顶元素并出栈.算法应对异常情况(栈满,栈空)等给出相应信息。,void PushPops (SqStack ,1、从键盘输入一个整数序列：a1,a2,a3，an,编写算法PushPops实现;用栈存储输入的整数序列,当ai-1时,将ai进栈;当ai=-1时,输出栈顶元素并出栈.算法应对异常情况(栈满,栈空)等给出相应信息。,例三 行编辑程序问题,一个简单的行编辑程序

8、的功能是：接收用户从终端输入的程序或数据，并存入用户的数据区。 “每接收一个字符即存入用户数据区”不恰当。 较好的做法是：设立一个输入缓冲区，用以接收用户输入的一行字符，然后逐行存入用户数据区。允许用户输入出差错，并在发现有误时可以及时更正。,退格符： # 退行符： 例如，假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+); 则实际有效的是下列两行： while (*s) putchar(*s+);,保留已经输入的字符的缓冲区结构应该是一个栈,void LineEdit( ) / 利用字符栈S,从终端接收一行并传送至调用过程的数据区。 I

9、nitStack(S); ch = getchar(); /从终端接收第一个字符 while (ch != EOF) /EOF为全文结束符 while (ch != EOF / LineEdit,例五 表达式求值,限于二元运算符的表达式定义: 表达式 : (操作数)+(运算符)+(操作数) 操作数 : 简单变量 | 表达式 简单变量 : 标识符 | 无符号整数,设 Exp = S1 + OP + S2 在计算机中,表达式可以有三种不同的表示方法 称 OP + S1 + S2 为表达式的前缀表示法 称 S1 + OP + S2 为表达式的中缀表示法 称 S1 + S2 + OP 为表达式的后缀表

10、示法 可见，它以运算符所在不同位置命名的。,例如： Exp= a b +(c-d/e) f 前缀式： + a b (c-d/e) f + a b (c-d/e) f + a b - c d/e f + a b -c /d e f 中缀式： a b + c-d/e f 后缀式： a b (c-d/e) f+ a b (c-d/e) f+ a b cd/e- f+ a b cde/- f+,写出 23 +(12*3-2)/4 +34*5/7)+108/9 的后缀表达式： 23 12 3*2-4/34 5*7/+108 9/+,结论 1)操作数之间的相对次序不变; 2)运算符的相对次序不同; 3)中

11、缀式丢失了括弧信息，致使运算的次序不确定; 4)前缀式的运算规则为:连续出现的两个操作数和在它们 之前且紧靠它们的运算符构成一个最小表达式; 5)后缀式的运算规则为: 运算符在式中出现的顺序恰为表达式的运算顺序; 每个运算符和在它之前出现且紧靠它的两个操作数构成一个最小表达式; 如何从后缀式求值？先找运算符，后找操作数,后缀式计算机处理起来比较方便，所以很多编译程序，每碰到一个表达式先求出后缀形式，然后再求值。,如何从原表达式求得后缀式？ 分析 “原表达式” 和 “后缀式”中的运算符 每个运算符的运算次序要由它之后的一个运算符来定,在后缀式中优先级高的运算符领先于优先级低的运算符，若当前运算符

12、的优先数小,则暂不进行;否则立即进行。,从原表达式求得后缀式的规律为： 1)设立运算符栈; 2)设表达式的结束符为“#”,设运算符栈的栈底为“#” 3)若当前字符是操作数，则直接发送给后缀式; 4)若当前运算符的优先数高于栈顶运算符，则进栈; 5)否则，退出栈顶运算符发送给后缀式; 6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。,void transform(char suffix, char exp ) / 从合法的表达式字符串exp求得其相应的后缀式 InitStack(S); Push(S, #); p = exp; ch = *p; while

13、(!StackEmpty(S) if (!IN(ch, OP) Pass( Suffix, ch); / 直接发送给后缀式 elseswitch (ch) case ( : Push(S, ch); break; case ) : Pop(S,c); while(c!=() Pass(Suffix,c);Pop(S,c) break; defult: while(!Gettop(S,c) / while / CrtExptree,OperandType EvaluateExpression() /算术表达式求值的算符优先算法.设OPTR和OPND分别为运算符栈和运算数栈,OP为运算符集合 In

14、itStack(OPTR); Push (OPTR,#); IinitStack(OPND); c=getchar(); while (c!=#|GetTop(OPTR)!=#) if(!In(c,OP)Push(OPND,c);c=getchar();/不是运算符则进栈 else switch (precede(GetTop(OPTR), c) case # /退栈并将运算结果入栈 Pop(OPTR,theta);Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b);break; / switch / while return GetT

15、op(OPND); / EvaluateExpression,3.3 实现递归,递归( recursion)做为一种算法在程序设计语言中广泛应用.是指函数在运行过程序中直接或间接调用自身而产生的重入现像.用递归思想写出的程序往往十分简洁易懂。 设a是含n个分量的整数数组,写出求n个整数之和 f(n)的递归定义：,void hanoi (int n, char x, char y, char z) /汉诺塔问题：将塔座x上按直径由小到大且至上而下编号 /为1至n的n个圆盘按规则搬到塔座z上,y可用作辅助塔座 if(n=1) move(x,1,z);/将编号为的圆盘从x移到z else hanoi

16、(n-1,x,z,y);/将x上编号为至n-1的圆盘 移到y,z作辅助塔 move(x,n,z); hanoi(n-1,y,x,z); ,3,2,1,hanoi (3,a,b,c),1,2,1,3,1,2,1,3.4 队列 ( Queue ),定义 队列是只允许在一端插入,在另一端删除的顺序表。 允许插入的一端叫做队尾(rear) ,允许删除的一端叫做队头(front)。 特性 先进先出(FIFO, First In First Out),抽象数据类型队列的定义 ADT Queue 数据对象：Dai | aiElemSet,i=1,2,.,n, n0 数据关系:R1 |ai-1, aiD, i

17、=2,.,n 约定其中a1 端为队列头，an 端为队列尾。 基本操作： InitQueue( struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,Q.rear,Q.front,Q.front,Q.front,/- 基本操作的函数原型说明 - Status InitQueue (LinkQueue InitQueue(Q); ch=getchar( ); while(ch!=) Push(S, ch); EnQueue(Q, ch)

18、; ch=getchar( ); state=TRUE; while(!StackEmpty(S) ,判断abcba是否是回文,a,b,c,b,a,a,b,a,b,c,链队列链式映象 typedef struct QNode QElemType data; struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LinkQueue;,Q.rear,Q.front,3.4.3 循环队列队列的顺序表示和实现 #define MAXQSIZE 10 /最大队列长

19、度 typedef struct QElemType *base; / 初始化的动态分配存储空间 int front; / 头指针，若队列不空，指向队列头元素 int rear;/尾指针,若队列不空,指向队列尾元素的下一个位置 SqQueue;,普通的顺序存储队满时再进队将溢出出错； 解决办法之一：将队列元素存放数组首尾相接， 形成循环(环形)队列。,0,1,2,3,4,5,6,7,Q.front:0,Q.rear:0,空队列,Q.base,队列的进队和出队原则,进队时队尾指针先进一 rear = rear + 1， 再将新元素按 rear 指示位置加入。 出队时队头指针先进一 front =

20、 front + 1， 再将下标为 front 的元素取出。,队列存放数组被当作首尾相接的表处理。 队头、队尾指针加1时从MAXQSIZE -1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1: Q.front = (Q.front+1) % MAXQSIZE; 队尾指针进1: Q.rear = (Q.rear+1) % MAXQSIZE; 队列初始化：Q.front = Q.rear = 0; 队空条件：Q.front = Q.rear; 队满条件：(Q.rear+1) % MAXQSIZE = Q.front,循环队列 (Circular Queue),P64,0,1,2,3,4

21、,5,6,7,front,0,1,2,3,6,7,front,A,A,B,C,rear,rear,A进队,B, C进队,0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,A退队,B退队,0,1,2,3,4,5,6,7,D,E,F,G,H,I进队,front,B,C,rear,A,front,B,C,rear,front,C,rear,D,E,F,G,H,I,0,1,2,3,4,5,6,7,front,rear,空队列,练习：假设循环队列定义为：以域变量rear和length分别指示循环队列中队尾元素的下一个位置和内含元素的个数。给出此循环队列的队满条件，并写出相应的入队列和出队列

22、的算法。 队满条件 Q.length= MAXQSIZE; 1）入队列操作 Status EnQueue(SqQueue / EnQueue,2）出队列操作 Status DeQueue(SqQueue / DeQueue,将队列Q中元素逆置。（使用顺序栈进行过渡，要求使用基本操作实现） Status ReverseQueue(SqQueue / ReverseQueue,练习,1、设栈的输入序列是1，2，3，4，5，则（ ）不可能是其出栈序列。 A. 54321 B. 45321 C. 43512 D. 12345 2、若已知一个栈的入栈序列是1，2，3，,n,其输出序列为p1,p2,p3,pn，若p1=n,则pi为（ ）。 A. i B.n=i C.n-i+1 D.不确定,C,C,4、一个递归算法必须包括（ ） A.递归部分 B.终止条件和递归部分 C.迭代部分 D.终止条件和迭代部分 5、用链表方式存储的队列，在进