第三章栈和队列.ppt

《第三章栈和队列.ppt》由会员分享，可在线阅读，更多相关《第三章栈和队列.ppt（59页珍藏版）》请在三一文库上搜索。

1、第三章栈和队列,3.1 栈 3.2 栈的应用 3.3 栈与递归的实现 3.4 队列,3.1 栈stack,什么是栈? 栈的操作原则是什么? 若有栈S=(a1，a2，.，an),哪个是栈顶元素,哪个是栈底元素? 栈的基本操作有哪些?,窗口 函数调用 撤消undo,一、 栈的定义 栈是限定仅在表尾进行插入或删除操作的线性表,表尾称为栈顶（top） 表头称为栈底（bottom）,火车站,入站,出站,栈的抽象数据类型 ADT Stack 数据对象:D =a ia i ElemSet, i= 1,2,n, n0 数据关系: R = a i-1 , a i D, i = 2,n 约定a n端为栈顶, a

2、1端为栈底. 基本操作:,DestroyStack(&S)； 操作结果:栈S被销毁,ClearStack(&S)； 操作结果:栈S清为空栈.,InitStack(&S)； 操作结果:构造一个空栈S.,StackLength(S)； 操作结果:返回S的元素个数,GetTop(S, &e)； 初始条件:栈S已存在且非空. 操作结果:用e返回S的栈顶元素.,StackEmpty(S)； 操作结果:若栈S为空栈,则返回TRUE, 否则FALSE,Push(&S, e)； 操作结果:插入元素e为新的栈顶元素.,Pop(&S, &e)； 初始条件:栈S已存在且非空. 操作结果:删除S的栈顶元素,并用e返回

3、其值,StackTraverse(S, visit( )； 初始条件:栈S已存在且非空. 操作结果:从栈底到栈顶依次对S的每个数据元素调用函数visit(). 一旦visit()失败, 则操作失效.,ADT Stack,DestroyStack(&S)；,ClearStack(&S)；,InitStack(&S)；,StackLength(S)；,GetTop(S, &e)；,StackEmpty(S)；,Push(&S, e)；,Pop(&S, &e)；,StackTraverse(S, visit( )；,二、栈的表示和实现 1顺序栈 利用一组地址连续的空间存放栈底到栈顶的元素 用指针to

4、p指出栈顶元素的位置,2顺序栈定义 typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,3 顺序栈的实现 栈的顺序存储表示 #define STACK_INIT_SIZE 100 存储空间初始分配 #define STACKINCREMENT 10 存储空间分配增量, 基本操作的函数原型说明 Status InitStack(SqStack 把S置为空栈,Status StackEmpty(SqStack S); 若栈S为空栈,则返回TRUE,否则返回FALSE int StackLength(SqSt

5、ack S); 返回S的元素个数,即栈的长度 Status GetTop(SqStack S, SElemType 从栈底到栈顶依次对栈中每个元素调用函数visit(). 一旦visit()失败,则操作失败., 基本操作的算法描述(部分) Status InitStack(SqStack InitStack,100,Status GetTop(SqStack S, SElemType GetTop,Status Push (SqStack Push,e,e,Status Pop(SqStack Pop,e,e,4栈式链 *top为首元结点，做栈顶 链式栈是在表头进行插入删除操作的链,a5,a4

6、,a3,a2,a1,top,头结点?,三、 多个栈共享空间 1两个栈共享空间,32栈的应用,一、数制转换,对于输入的任意一个非负十进制整数 打印输出与其等值的八进制数,4107,3,513,1,64,0,8,0,1,1,0,余数产生顺序,八进制输出顺序,void conversion ( ) InitStack(S); 建空栈 scanf( printf(“%d“,e)； conversion,二、 括号匹配,输入一个符号串，判断其中圆括号和方括号是否匹配,( a b h j ( f h ( j ) k g h ) ),算法思想： (1)凡出现左括号，则进栈 (2)凡出现右括号，首先检查栈是否

7、空 如果栈空，表明右括号多了 否则与栈顶元素比较，若相匹配，左括号出栈 否则不匹配 (3)表达式检查结束时，若栈空，则匹配正确,Status match( ) InitStack(S); scanf(ch); while (ch!= n) if (ch= ( | ch= ) Push(S,ch); else if (ch= ) if(StackEmpty(S) return ERROR; Pop(S, t); if (t!= ( ) return ERROR; else if (ch= ) if(StackEmpty(S) return ERROR; Pop(S, t); if (t!= )

8、return ERROR; scanf(ch); if(StackEmpty(S) return OK; else return ERROR; /match,三、迷宫求解,墙 通道 入口 出口,墙 通道 入口 出口,算法思想: 若当前位置可通,则加入路径 若当前位置不可通,则后退,换一个方向搜索 若四周都不可通,则从路径中删除,路径中最先被删除的位置是最近搜索过的 利用栈存放路径,设定当前位置的初值为入口位置; do 若当前位置可通, 将当前位置入栈; 切换当前位置的东邻方块为新的当前位置; while(栈不空),若当前位置不可通, 出栈 找到下一个可能通的位置 ,设定当前位置的初值为入口位置

9、; do 若当前位置可通, 则 将当前位置入栈; 纳入路径 若该位置是出口位置,则结束; 求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置; while(栈不空),否则 若栈不空 出栈e 若e的四周均不可通(或探索过)则继续出栈 若e尚有其他方向未经探索 沿顺时针方向找到新的当前位置 ,typedef struct int ord; 通道块在路径上的“序号“ PosType seat; 通道块在迷宫中的“坐标位置“ int di; 从此通道块走向下一通道块的“方向“ SElemType; 栈的元素类型,FootPrint(curpos); /记录位置curpos已经搜索过,Pass

10、(curpos) /返回位置curpos是否可通(搜索过),NextPos(curpos,i); /返回从位置curpos按方向i到达的新位置,MarkPrint(curpos); /记录位置curpos4个方向都搜索过不可通,typedef struct int x,y; PosType; 坐标,Status MazePath (MazeType maze, PosType start, PosType end) 若迷宫maze中存在从入口start到出口end的通道,则求得一条存放在栈中 (从栈底到栈顶),并返回TRUE;否则返回FALSE InitStack(S); curpos = s

11、tart; 设定“当前位置“为“入口位置“ curstep = 1; 探索第一步 do if(Pass(curpos) 当前位置可以通过,即是未曾走到过的通道块 FootPrint(curpos); 留下足迹 e = (curstep,curpos,1); Push(S,e); 加入路径 if(curpos=end) return(TRUE); 到达终点(出口) curpos = NextPos(curpos,1); 一位置是当前位置的东邻 curstep +; 探索下一步,else /if(!Pass(curpos) 当前位置不能通过 if(!StackEmpty(S) Pop(S,e);

12、while (e.di=4 MazePath,四、表达式求值,a+b*(c+d)+(c-d)/f,(1) 初始化，置OPND为空栈， 将#压入OPTR栈底 (2) 依次读入表达式中的每个成员： (a)若是操作数，压入OPND栈 (b)若是界限符或运算符， 则与OPTR栈内运算符比较优先级， 若栈内高， 则从OPTR弹出运算符， 并OPND从弹出相应个数的操作数进行运算， 将运算结果压入OPND栈 否则，将读入的运算符压入OPTR栈 (3) 重复(2)，直到读入#且栈顶为#为止,操作数,运算符,OperandType EvaluateExpression( ) 算术表达式求值的算符优先算法, O

13、P为运算符集合 /设OPTR和OPND分别为运算符栈和运算数栈 InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c = getchar( ); while(c!=#GetTop(OPTR)!=#) if (!In(c,OP) Push(OPND,c);c = getchar( ); else while,return GetTop(OPND); EvaluataeExpression,switch(Precede(GetTop(OPTR),c) case: Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Pu

14、sh(OPND,Operate(a,theta,b); break; switch,后缀表达式（逆波兰表达式）,一种不需要括号的后缀表达式 如： ab+d* abd+* 如何利用堆栈计算后缀表达式的值？ 中缀表达式如何转换为后缀表达式,3.3 栈与递归的实现,保存B的计算结果 （return.） 释放B的数据区 按返回地址返回A继续执行,B(int x) int a, b; return () ,A( ) int m,n; . B(m); . ,当函数A调用B，在执行B之前,从B返回A之前：,int first(int s, int t); int second(int d); int mai

15、n( ) int m, n; . first(m, n); 1: ,int first(int s, int t) int i; . second(i); 2: ,int second(int d) int x,y; . ,返回地址,s,t(m,n),i,m,n,返回地址,d(i),x,y,调用second时栈内的数据,调用函数前： 返回地址入栈 实参入栈 (形参) 调用函数时先： 局部变量入栈 返回调用函数前： 局部变量出栈 形参出栈 返回地址出栈,float fac(int n) float f; if(n=0 |n=1) f=1; else f=fac(n-1)*n; return f;

16、 ,float fac(int n) float f; if(n=0 |n=1) f=1; else f=fac(n-1)*n; return f; ,float fac(int n) float f; if(n=0 |n=1) f=1; else f=fac(n-1)*n; return f; ,3,n,6,f,2,f,1,f,数制问题,void f1(int num) if(num=8) f1(num/8); printf(“%d“,num%8); int main() int x=4107; f1(x); return 0; ,x(4107),34队列Queue,1队列的定义 队列是一种

17、先进先出的线性表（FIFO） 限定：只能在表的一端插入，而在另一端删除 允许插入的一端称为队尾(rear) 允许删除的一端称为队头(front) 若线性表q=（ a1，a2，.，an ）是一个队列，则a1是队头，an是队尾,一、 队列,2队列的ADT ADT Queue 数据对象:D = ai | ai ElemSet, i = 1,2,n; n0 数据关系:R1 = ai-1, ai D, i = 1,2,n 基本操作: InitQueue(&Q) 操作结果:构造一个空队列 DestroyQueue(&Q) 操作结果:队列Q被销毁,不再存在. ClearQueue(&Q) 操作结果:将Q清为

18、空队列. QueueEmpty(Q) 操作结果:若Q为空队列,则返回TRUE,否则返回FALSE.,QueueLength(Q) 操作结果:返回Q的元素个数,即队列的长度. GetHead(Q,&e) 初始条件:Q为非空队列. 操作结果:用e返回Q的队头元素. EnQueue(&Q,e) 操作结果:插入元素e为Q的新的队尾元素. DeQueue(&Q,&e) 初始条件:Q为非空队列. 操作结果:删除Q的队头元素,并用e返回其值. QueueTraverse(Q,visit() 初始条件:Q已存在且非空. 操作结果:从对头到队尾,依次对Q的每个数据元素 调用函数visit().一旦visit()

19、失败,则操作失败, /ADT Queue,二、 顺序队列 用一组地址连续的存储单元依次存放队列中的元素,方式一：用一维数组表示队列 typedef struct QElemType *q; int rear; SqQueue1;,Q.q0表示队头，Q.qQ.rear-1表示队尾 队空：Q.rear=0 队满：Q.rear=100（空间大小） 出队：e=Q.q0; Q.q1至Q.qQ.rear-1往前挪 入队：Q.qQ.rear=e; Q.rear+;,方式二： #define Queue_SIZE 100 typedef struct QElemType *Q; int front; int

20、rear; SqQueue2;,front,rear,三、 循环队列,a1,a2,a3,a4,a5,a6,a7,a8,队空,队满,循环队列队列的顺序存储结构 #define MAXQSIZE 100 最大队列长度 typedef struct QElemType *base; 初始化的动态分配存储空间 int front; 头指针,若队列不空,指向队列头元素 int rear; 尾指针,若队列不空,指向队列尾元素的下一个位置 SqQueue;,解决方法： （1）专设一个表示队满队空的标记full 一开始，full=0 当入队时出现Q.rear=Q.front，队满full=1 当出队时出现Q.

21、rear=Q.front，队空full=0 （2）专门空出一个位置不用,循环队列的基本操作的算法描述,Statue InitQueue(SqQueue ,Status EnQueue(SqQueue ,Status DeQueue(SqQueue ,队列的链式存储结构 typedef struct QNode QElemType data; Struct QNode *next; QNode, *QueuePtr;,四、链式队列,typedef struct QueuePtr front; 队头指针 QueuePtr rear; 队尾指针 LinkQueue,Status InitQueue(

22、LinkQueue 否则返回ERROR Status EnQueue(LinkQueue &Q,QElemType e) 插入元素e为Q的新的队尾元素,基本操作的函数原型说明,Status DeQueue(LinkQueue 否则返回ERROR Status QueueTraverse(LinkQueue Q,visit() 从队头到队尾依次对队列Q中每个元素调用函数visit(). /一旦visit失败,则操作失败.,Status InitQueue(LinkQueue ,基本操作的算法描述,Status DestroyQueue(LinkQueue ,Status DeQueue(LinkQueue ,Status EnQueue(LinkQueue ,