第三章栈和队列2009.ppt

1、2020/8/5,1,第三章栈和队列,两种特殊的线性表,2020/8/5,2,栈和队列,3.1 栈 3.2 栈的应用举例 3.3 栈与递归 3.4 队列,2020/8/5,3,3.1 栈,栈是仅限定在表的一端操作的线性表。它的插入和删除都只能在表的一端进行。,定义,2020/8/5,4,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：, ADT Stack,3.1.1 栈的类型定义,2020/8/5,5,InitStack( stack;

2、 stack S;,s,top,2020/8/5,8,栈的顺序存储,# define Maxsize 100+1 typedef struct elemtype STMaxsize int top; stack; stack S;,top,s,2020/8/5,9,栈的顺序存储,1.栈空的条件： S.top = 0,2020/8/5,10,2. 栈的压入操作,Push( ,2020/8/5,11,2. 栈的压入操作,Push( ,23,50,2020/8/5,12,3. 栈的弹出操作,pop ( ,23,50,2020/8/5,13,栈的链式存储,进栈 出栈 读栈顶元素,2020/8/5,14

3、,3.2 栈的应用举例,ClearStack(S) 重置S为空栈 empty (s) 判断栈空 push(s，ch) 将一个元素e推入栈s pop(s) 将栈顶元素弹出，且返回其元素 gettop(s,e) 取栈顶元素,2020/8/5,15,例1 行编辑程序问题,假设“#”为退格符，表示前一个字 符无效； “”为退行符，表示当前行无效； 设立一个栈（输入缓冲区），用以接受用户输入的一行字符，然后逐行存入用户数据区。,2020/8/5,16,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,则实际有效的是下列两行： while (*s

4、) putchar(*s+);,2020/8/5,17,假设从终端接受了这样两行字符： whli#ilr#e,当 # : Pop(S,e) /弹出,当 : ClearStack(S)/清栈,否则 入栈,2020/8/5,18,假设从终端接受了这样两行字符： whli#ilr#e,当 # : Pop(S,e) /弹出,当 : ClearStack(S)/清栈,否则 入栈,2020/8/5,19,假设从终端接受了这样两行字符： whli#ilr#e,当 # : Pop(S,e) /弹出,当 : ClearStack(S)/清栈,否则 入栈,while (ch != EOF / 从终端接收下一个字符

5、 ,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar();,while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的 数据区；,2020/8/5,21,表达式 := (操作数1) + (运算符op) + (操作数2) 操作数 := 简单变量 | 表达式 简单变量 : = 标识符 | 无符号整数,例2 表达式求值,-利用算符优先级法则,2020/8/5,22,算符间的优先级关系,2020/8/5,23,例如: Exp = a b + (c d / e) f 中缀式: #a b + c d / e f#,2

6、020/8/5,24,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2020/8/5,25,算符间的优先级关系,2020/8/5,26,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2,+,+,2020/8/5,27,算符间的优先级关系,2020/8/5,28,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2,3,2020/8/5,29,算符间的优先级关系,2020/8/5,30,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2,3,退栈,3,2,23=6,6,进栈,10,/,202

7、0/8/5,31,3.3 栈与递归的实现,求n! Hanoi塔问题,例1 求n! (用递归调用),1 n=0 fac= n (n-1)! n0,int fac ( int n ) int f; if ( n=0) fac=1; else f= fac(n-1) * n; return( f ); ,main ( ) int n=3; p= fac (n); printf(%d,p); ,求n! (用递归调用),1 n=0 fac= n (n-1)! n0,int fac ( int n ) int f; if ( n=0) fac=1; else f= fac(n-1) * n; return

8、( f ); ,main ( ) int n=3; p= fac (n); printf(%d,p); ,将所有的实参、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。,求n! (用递归调用),1 n=0,1 fac= n (n-1)! n0,int fac ( int n ) int f; if ( n=0) fac=1; else f= fac(n-1) * n; return( f ); ,main ( ) int n=3; p= fac (n); printf(%d,p); ,保存被调函数的计算结果； 释放被调函数的数据区； 依照

9、被调函数保存的返回地址将控制转移到调用函数。,2020/8/5,35,递归的要点：,由系统提供一个信息栈，保留函数调用时的相关信息（调用时的信息、返回地址、局部变量）； 每执行递归调用语句时，将有关信息送入栈，转入函数入口； 每当执行到返回语句时，保存计算结果，释放被调函数的数据区，弹出返回地址返回。,2020/8/5,36,多个函数嵌套调用的规则是：,此时的内存管理实行“栈式管理”,后调用先返回 ！,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,Main的数据区,函数a的数据区,函数b的数据区,2020/8/5,

10、37,2020/8/5,39,例2 Hanoi 塔问题,a,b,c,2020/8/5,40,例2 Hanoi 塔问题,a,b,c,2020/8/5,41,例2 Hanoi 塔问题,a,b,c,2020/8/5,42,例2 Hanoi 塔问题,a,b,c,2020/8/5,43,void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n / 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 1 if (n=1) 2 move(x, 1, z); / 将编号为的圆盘从x移到z 3 else 4 hanoi(n-1, x,

11、 z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔 5 move(x, n, z); / 将编号为n的圆盘从x移到z 6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔 7 8 ,2020/8/5,44,void hanoi (int n, char x, char y, char z) 1 2 if (n=1) 3 move(x, 1, z); 4 else 5 hanoi(n-1, x, z, y); 6 move(x, n, z); 7 hanoi(n-1, y, x, z); 8 9 ,0 3 a b c,返址 n

12、x y z,6 2 a c b,6 1 a b c,8 1 c a b,2020/8/5,45,3.4 队列,2020/8/5,46,3.4.1 抽象数据类型队列的定义,队列：是一种先进先出的线性表，它的操作只能在表的两端进行。,队尾,队首,a1 a2 a3 an-1 an,2020/8/5,47,ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾,基本操作：, ADT Queue,队列的抽象数据类型,2020/8/5,48,队列的基本操作：,1

13、、InitQueue( struct QNode *next; QNode, *QPtr;,链队de结点结构,2020/8/5,58,QPtr front; / 队头指针 QPtr rear; / 队尾指针,a1,an,front,front,空队列,rear,rear,front = rear,表示1,2020/8/5,59,typedef struct / 链队列类型 QPtr front; / 队头指针 QPtr rear; / 队尾指针 LinkQueue;,a1,an,Q.front Q.rear,Q.front Q.rear,空队列,表示2,2020/8/5,60,Status I

14、nitQueue (LinkQueue ,2020/8/5,61,Status EnQueue (LinkQueue ,2020/8/5,62,Status DeQueue (LinkQueue ,2020/8/5,63,3.4.3 队列的顺序存储结构,顺序队列数组表示 队列的顺序存储结构称为顺序队列。,队首,队尾,2020/8/5,64,1. 顺序队列数组表示,初始化建空队列时令,front = rear = 0,2020/8/5,65,1. 顺序队列数组表示,入队时: 加入结点; rear+1;,J1,2020/8/5,66,1. 顺序队列数组表示,入队：加入结点; 头指针rear+1;,

15、J1,J2,J3,2020/8/5,67,1. 顺序队列数组表示,出队： 删除结点; 队头指针front+1;,J1,J2,J3,J1,在非空队列中，头指针front总是指向队头元素，而尾指针rear总是指向队尾元素的下一个位置,2020/8/5,68,（1）入队操作 enqueue (Q , x) if ( rear+1=MAX-1) printf (队满溢出) else Qrear= x; rear +; return OK; ,2顺序队列的基本运算,2020/8/5,69,（2）出队操作 Dequeue (Q , e) if ( front=rear) return ERROR/队空 e

16、lse e = Qfront; front +; return OK; ,2020/8/5,70,3. 循环队列,if ( rear+1=MAX-1) 队满溢出 在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，此时若有元素入列，就会发生“溢出”。在图中，虽然队尾指针已经指向最后一个位置，但事实上队列中还有空位置。也就是说，队列的存储空间并没有满，但队列却发生了溢出，我们称这种现象为假溢出。,2020/8/5,71,解决的方法:将队列看成是循环表,：,2020/8/5,72,但当队满时rear=front,：,2020/8/5,73,但当队满时rear=front当队空时rear=fro

17、nt,：,无法判断！,2020/8/5,74,解决的方法:少用一的单元,：,队满条件 (rear+1) mod max=front,2020/8/5,75,解决的方法:少用一的单元,：,队满条件 (rear+1) mod max=front,队空条件 front=rear,2020/8/5,76,入队,Enqueue (Q, x) if (front = (rear+1) % max ) exit (over) else Qrear=x; rear= (rear+1) % max; return OK ,2020/8/5,77,出队,Delqueue (Q, e) if (front = rear) exit (over) else e=Qfront; front = (front+1) % max; return OK ,2020/8/5,78,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;,循