《栈和队列PPT演示文稿.ppt》由会员分享，可在线阅读，更多相关《栈和队列PPT演示文稿.ppt（86页珍藏版）》请在三一文库上搜索。
1、21.01.2021,1,第三章栈和队列,两种特殊的线性表,21.01.2021,2,栈和队列,3.1 栈 3.2 栈的应用举例 3.3 栈与递归 3.4 队列,21.01.2021,3,3.1 栈,栈是仅限定在表的一端操作的线性表。它的插入和删除都只能在表的一端进行。,定义,21.01.2021,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 栈的类型定义,21.01.2021,5,InitSta
2、ck( stack; stack S;,s,top,21.01.2021,8,栈的顺序存储,# define Maxsize 100+1 typedef struct elemtype STMaxsize int top; stack; stack S;,top,s,21.01.2021,9,栈的顺序存储,1.栈空的条件： S.top = 0,21.01.2021,10,2. 栈的压入操作,Push( ,21.01.2021,11,2. 栈的压入操作,Push( ,23,50,21.01.2021,12,3. 栈的弹出操作,pop ( ,23,50,21.01.2021,13,例题,一个栈的入
3、栈序列是12345，则栈的不可能的出栈序列是什么？ 判断一个顺序栈st(最多元素为maxsize)为栈空he栈满的条件分别是 和 A) st-top !=0 B) st-top=0 C) st-top != maxsize -1 D) st-top = maxsize -1,B,D,21.01.2021,14,栈的链式存储,进栈 出栈 读栈顶元素,21.01.2021,15,3.2 栈的应用举例,ClearStack(S) 重置S为空栈 empty (s) 判断栈空 push(s，ch) 将一个元素e推入栈s pop(s) 将栈顶元素弹出，且返回其元素 gettop(s,e) 取栈顶元素,21
4、.01.2021,16,例1 行编辑程序问题,假设“#”为退格符，表示前一个字 符无效； “”为退行符，表示当前行无效； 设立一个栈（输入缓冲区），用以接受用户输入的一行字符，然后逐行存入用户数据区。,21.01.2021,17,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,则实际有效的是下列两行： while (*s) putchar(*s+);,21.01.2021,18,假设从终端接受了这样两行字符： whli#ilr#e,当 # : Pop(S,e) /弹出,当 : ClearStack(S)/清栈,否则 入栈,21.01
5、.2021,19,假设从终端接受了这样两行字符： whli#ilr#e,当 # : Pop(S,e) /弹出,当 : ClearStack(S)/清栈,否则 入栈,21.01.2021,20,假设从终端接受了这样两行字符： whli#ilr#e,当 # : Pop(S,e) /弹出,当 : ClearStack(S)/清栈,否则 入栈,while (ch != EOF / 从终端接收下一个字符 ,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar();,while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的字符传送至调用过
6、程的 数据区；,21.01.2021,22,表达式 := (操作数1) + (运算符op) + (操作数2) 操作数 := 简单变量 | 表达式 简单变量 : = 标识符 | 无符号整数,例2 表达式求值,-利用算符优先级法则,21.01.2021,23,算符间的优先级关系,21.01.2021,24,例如: Exp = a b + (c d / e) f 中缀式: #a b + c d / e f#,21.01.2021,25,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,21.01.2021,26,算符间的优先级关系,21.01.2021,27,例如: #4+
7、2 3 10 / 5 #,OPTR,OPND,#,4,+,2,+,+,21.01.2021,28,算符间的优先级关系,21.01.2021,29,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2,3,21.01.2021,30,算符间的优先级关系,21.01.2021,31,例如: #4+ 2 3 10 / 5 #,OPTR,OPND,#,4,+,2,3,退栈,3,2,23=6,6,进栈,10,/,21.01.2021,32,3.3 栈与递归的实现,求n! Hanoi塔问题,例1 求n! (用递归调用),1 n=0 fac= n (n-1)! n0,int fac
8、( 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( f ); ,main ( ) int n=3; p= fac (n); printf(%d,p); ,将所有的实参、返回地址等信息传递给被调用函数保存； 为
9、被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。,求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); ,保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。,21.01.2021,36,递归的要点：,由系统提供一个信息栈，保留函数调用时的相关信息（调用时的信息、返回地址、
10、局部变量）； 每执行递归调用语句时，将有关信息送入栈，转入函数入口； 每当执行到返回语句时，保存计算结果，释放被调函数的数据区，弹出返回地址返回。,21.01.2021,37,多个函数嵌套调用的规则是：,此时的内存管理实行“栈式管理”,后调用先返回 ！,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,Main的数据区,函数a的数据区,函数b的数据区,21.01.2021,38,21.01.2021,40,例2 Hanoi 塔问题,a,b,c,21.01.2021,41,例2 Hanoi 塔问题,a,b,c,21.01
11、.2021,42,例2 Hanoi 塔问题,a,b,c,21.01.2021,43,例2 Hanoi 塔问题,a,b,c,21.01.2021,44,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, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔 5 move(x, n, z); / 将编号为n的圆盘从
12、x移到z 6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔 7 8 ,21.01.2021,45,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 x y z,6 2 a c b,6 1 a b c,8 1 c a b,21.01.2021,46,3.4 队列,21.01
13、.2021,47,3.4.1 抽象数据类型队列的定义,队列：是一种先进先出的线性表，它的操作只能在表的两端进行。,队尾,队首,a1 a2 a3 an-1 an,21.01.2021,48,ADT Queue 数据对象： Dai | aiElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头， an 端为队列尾,基本操作：, ADT Queue,队列的抽象数据类型,21.01.2021,49,队列的基本操作：,1、InitQueue( struct QNode *next; QNode, *QPtr;,链队de结点结构
14、,21.01.2021,59,QPtr front; / 队头指针 QPtr rear; / 队尾指针,a1,an,front,front,空队列,rear,rear,front = rear,表示1,21.01.2021,60,typedef struct / 链队列类型 QPtr front; / 队头指针 QPtr rear; / 队尾指针 LinkQueue;,a1,an,Q.front Q.rear,Q.front Q.rear,空队列,表示2,21.01.2021,61,Status InitQueue (LinkQueue ,21.01.2021,62,Status EnQueu
15、e (LinkQueue ,21.01.2021,63,Status DeQueue (LinkQueue ,21.01.2021,64,21.01.2021,65,3.4.3 队列的顺序存储结构,顺序队列数组表示 队列的顺序存储结构称为顺序队列。,队首,队尾,21.01.2021,66,1. 顺序队列数组表示,初始化建空队列时令,front = rear = 0,21.01.2021,67,1. 顺序队列数组表示,入队时: 加入结点; rear+1;,J1,21.01.2021,68,1. 顺序队列数组表示,入队：加入结点; 头指针rear+1;,J1,J2,J3,21.01.2021,69
16、,1. 顺序队列数组表示,出队： 删除结点; 队头指针front+1;,J1,J2,J3,J1,在非空队列中，头指针front总是指向队头元素，而尾指针rear总是指向队尾元素的下一个位置,21.01.2021,70,（1）入队操作 enqueue (Q , x) if ( rear+1=MAX-1) printf (队满溢出) else Qrear= x; rear +; return OK; ,2顺序队列的基本运算,21.01.2021,71,（2）出队操作 Dequeue (Q , e) if ( front=rear) return ERROR/队空 else e = Qfront;
17、front +; return OK; ,21.01.2021,72,3. 循环队列,if ( rear+1=MAX-1) 队满溢出 在顺序队列中，当队尾指针已经指向了队列的最后一个位置时，此时若有元素入列，就会发生“溢出”。在图中，虽然队尾指针已经指向最后一个位置，但事实上队列中还有空位置。也就是说，队列的存储空间并没有满，但队列却发生了溢出，我们称这种现象为假溢出。,21.01.2021,73,解决的方法:将队列看成是循环表,：,21.01.2021,74,但当队满时rear=front,：,21.01.2021,75,但当队满时rear=front当队空时rear=front,：,无法判
18、断！,21.01.2021,76,解决的方法:少用一的单元,：,队满条件 (rear+1) mod max=front,21.01.2021,77,解决的方法:少用一的单元,：,队满条件 (rear+1) mod max=front,队空条件 front=rear,21.01.2021,78,入队,Enqueue (Q, x) if (front = (rear+1) % max ) exit (over) else Qrear=x; rear= (rear+1) % max; return OK ,21.01.2021,79,出队,Delqueue (Q, e) if (front = re
19、ar) exit (over) else e=Qfront; front = (front+1) % max; return OK ,21.01.2021,80,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针，若队列不空， / 指向队列头元素 int rear; / 尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue;,循环队列结构2,21.01.2021,81,Status InitQueue (SqQueue ,21.01.2021,82,Status EnQueue (SqQueue ,21.01.2021,83,Status DeQueue (SqQueue ,21.01.2021,84,21.01.2021,85,1. 掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。,2. 熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。,3. 熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。,4. 理解递归算法执行过程中栈的状态变化过程。,本章学习要点,