第三章栈和队列.ppt

第三章栈和队列,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 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返回其值,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顺序栈 利用一组地址连续的空间存放栈底到栈顶的元素 用指针top指出栈顶元素的位置,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,否则返回FALSEint StackLength(SqStack 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,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)凡出现右括号，首先检查栈是否空 如果栈空，表明右括号多了 否则与栈顶元素比较，若相匹配，左括号出栈 否则不匹配(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!=)return ERROR;scanf(ch);if(StackEmpty(S)return OK;else return ERROR;/match,三、迷宫求解,墙通道入口出口,墙通道入口出口,算法思想:若当前位置可通,则加入路径 若当前位置不可通,则后退,换一个方向搜索 若四周都不可通,则从路径中删除,路径中最先被删除的位置是最近搜索过的利用栈存放路径,设定当前位置的初值为入口位置;do 若当前位置可通,将当前位置入栈;切换当前位置的东邻方块为新的当前位置;while(栈不空),若当前位置不可通,出栈 找到下一个可能通的位置,设定当前位置的初值为入口位置;do 若当前位置可通,则 将当前位置入栈;纳入路径 若该位置是出口位置,则结束;求得路径存放在栈中 否则切换当前位置的东邻方块为新的当前位置;while(栈不空),否则 若栈不空 出栈e 若e的四周均不可通(或探索过)则继续出栈 若e尚有其他方向未经探索 沿顺时针方向找到新的当前位置,typedef struct int ord;通道块在路径上的序号 PosType seat;通道块在迷宫中的坐标位置 int di;从此通道块走向下一通道块的方向 SElemType;栈的元素类型,FootPrint(curpos);/记录位置curpos已经搜索过,Pass(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=start;设定当前位置为入口位置 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);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()算术表达式求值的算符优先算法,OP为运算符集合/设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);Push(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 main()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;,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队列的定义 队列是一种先进先出的线性表（FIFO）限定：只能在表的一端插入，而在另一端删除 允许插入的一端称为队尾(rear)允许删除的一端称为队头(front)若线性表q=（a1，a2，.，an）是一个队列，则a1是队头，an是队尾,一、队列,2队列的ADTADT 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清为空队列.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()失败,则操作失败,/ADT Queue,二、顺序队列 用一组地址连续的存储单元依次存放队列中的元素,方式一：用一维数组表示队列typedef structQElemType*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 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.rear=Q.front，队空full=0（2）专门空出一个位置不用,循环队列的基本操作的算法描述,Statue InitQueue(SqQueue,Status EnQueue(SqQueue,Status DeQueue(SqQueue,队列的链式存储结构typedef struct QNodeQElemType data;Struct QNode*next;QNode,*QueuePtr;,四、链式队列,typedef struct QueuePtr front;队头指针 QueuePtr rear;队尾指针LinkQueue,Status InitQueue(LinkQueue 否则返回ERRORStatus EnQueue(LinkQueue&Q,QElemType e)插入元素e为Q的新的队尾元素,基本操作的函数原型说明,Status DeQueue(LinkQueue 否则返回ERRORStatus QueueTraverse(LinkQueue Q,visit()从队头到队尾依次对队列Q中每个元素调用函数visit()./一旦visit失败,则操作失败.,Status InitQueue(LinkQueue,基本操作的算法描述,Status DestroyQueue(LinkQueue,Status DeQueue(LinkQueue,Status EnQueue(LinkQueue,