第3章 队列与堆栈ppt课件

1、3.2 栈的应用举例3.2.5 表达式求值,算符优先法: （4+2*3）-10/5 =（4+6）-10/5 = 10-10/5 =10-2 = 8 操作数(operand): 进OPND栈 操作符(operator): 进OPTR栈 界限符(delimiter): #、（）等 #是我们设定的表达式开始和结束标识符。,算符间的优先关系:,1 2+-*/()# + - * / ( # =,Precede: 判定运算符栈的栈顶运算符1与读入的运算符2之间的优先关系的函数。 Operate: 进行二元运算ab的函数。 假定出现的表达式没有语法错误。,算法基本思想:,1、设置操作数栈OPND为空，表达式起始符#为运算符栈OPTR的栈底元素； 2、依次读入表达式中的每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后做相应操作，直到整个表达式求值完毕。,算术表达式求值过程(算法3.4)OperandType EvaluateExpression(),InitStack(OPTR); Push(OPTR, #); InitStack(OPND); c = getch

2、ar(); 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; default: printf(“Expression error!”); return(ERROR); / switch / while return GetTop(OPND); / EvaluateExpression,对算术表达式3*(7-2)求值.,步骤 OPTR栈 OPND栈 输入字符 主要操作 1 # 3 * ( 7 - 2 ) # Push(OPND,3) 2 # 3 * ( 7 - 2 ) # Push(OPTR,*) 3 # * 3 ( 7 - 2 ) # Push(OPTR,() 4 # * ( 3 7 - 2 ) # Pus

3、h(OPND,7) 5 # * ( 3 7 - 2 ) # Push(OPTR,-) 6 # * ( - 3 7 2 ) # Push(OPND,2) 7 # * ( - 3 7 2 ) # Operate(7,-,2) 8 # * ( 3 5 ) # POP(OPTR) 9 # * 3 5 # Operate(3,*,5) 10 # 15 # Return(GetTop(OPND),*3.3 栈与递归的实现,将所有的实在参数、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,保存被调函数的计算结果； 释放被调函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。,从被调用函数返回调用函数之前，应该完成下列三项任务：,多个函数嵌套调用的规则是：,此时的内存管理实行“栈式管理”,后调用先返回 ！,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,Main的数据区,函

4、数a的数据区,函数b的数据区,递归工作栈：递归过程执行过程中占用的 数据区。 递归工作记录：每一层的递归参数合成 一个记录。 当前活动记录：栈顶记录指示当前层的 执行情况。 当前环境指针：递归工作栈的栈顶指针。,递归函数执行的过程可视为同一函数进行嵌套调用，例如：,void hanoi (int n, char x, char y, char z) / 将塔座x上按直径由小到大且至上而下编号为1至n / 的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。 1 if (n=1) 2 move(1,x , z); / 将编号为的圆盘从x移到z 3 else 4 hanoi(n-1, x, z, y); / 将x上编号为至n-1的 /圆盘移到y, z作辅助塔 5 move(n,x, z); / 将编号为n的圆盘从x移到z 6 hanoi(n-1, y, x, z); / 将y上编号为至n-1的 /圆盘移到z, x作辅助塔 7 8 ,8 3 a b c,返址 n x y z,5 2 a c b,5 1 a b c,7 1 c a b,void hanoi (int n, char x, char

5、 y, char z) 1 2 if (n=1) 3 move(1,x, z); 4 else 5 hanoi(n-1, x, z, y); 6 move(n,x, z); 7 hanoi(n-1, y, x, z); 8 9 执行函数hanoi(3,a,b,c),例：汉诺塔问题： 将x柱子上的盘移到 z柱，用 y柱放临时盘 要求：一次只能移动一个盘，大盘不可放于小盘上。,x,y,z,hanoi塔问题:栈的递归实现,3.4 队列,3.4.1 队列的定义,3.4.2 队列的顺序存储结构及其基本运算的实现,3.4.3 队列的链式存储结构及其基本运算的实现,3.4.4 队列的应用例子,3.4 队列3.4.1抽象数据类型队列的定义,队列（Queue）: 先进先出(First In First Out) (缩写为FIFO）的线性表。 仅在队尾进行插入和队头进行删除操作的线性表。 队头（front）: 线性表的表头端，即可删除端。 队尾（rear）: 线性表的表尾端，即可插入端。,队头,队尾,队列的入队和出队操作示意图,队列的抽象数据类型,ADT Queue 数据对象：D = ai | aiEle

6、mSet, (i=1,2,n, n0) 数据关系：R1 = ai-1,ai|ai-1,ai D,(i=2,3,n) 约定an为队尾, a1为队头。 基本操作： InitQueue( QueueTraverse(Q ,visit () ADT Queue,队列的基本操作(之一),InitQueue (否则返回FALSE。 QueueLength(Q) 初始条件: 队列Q已经存在。 操作结果: 返回队列Q中的数据元素个数, 即队列Q的长度。 GetHead(Q, 2)插入新的元素时, rear+; 3)删除队头元素时,front+; 头指针始终指向队头元素位置，而尾指针始终指向队尾元素的下一个位置。,J5,J6,Q.front,Q.rear,Q.rear,Q.front,1,0,2,3,5,4,顺序队列，队空、满如何表示？如何改变指针到初始位置？,3.4.2 队列的顺序存储结构及其基本运算的实现,假设队列的元素个数最大不超过整数MaxSize,所有的元素都具有同一数据类型ElemType,则顺序队列类型SqQueue定义如下: typedef struct ElemType elemMax

7、Size； int front, rear；/*队首和队尾指针*/ SqQueue,从前图中看到,图(a)为队列的初始状态,有front=rear成立,该条件可以作为队列空的条件。 那么能不能用rear=MaxSize-1作为队满的条件呢？显然不能,在图(d)中,队列为空,但仍满足该条件。这时入队时出现“上溢出”,这种溢出并不是真正的溢出,在elem数组中存在可以存放元素的空位置,所以这是一种假溢出。 为了能够充分地使用数组中的存储空间,把数组的前端和后端连接起来,形成一个环形的顺序表,即把存储队列元素的表从逻辑上看成一个环,称为循环队列。,循环队列首尾相连,当队首front指针满足 front=MaxSize-1后,再前进一个位置就自动到0,这可以利用除法取余的运算()来实现: 队首指针进1:front=(front+1)MaxSize 队尾指针进1:rear=(rear+1)MaxSize 循环队列的除头指针和队尾指针初始化时都置0:front=rear=0。在入队元素和出队元素时,指针都按逆时针方向进1。,循环列表-解决数组越界但未占满空间的办法,当Q.rear Q.front时

8、: Q.rear Q.front = 队列中元素个数 当Q.rear Q.front时: Q.rear Q.front +maxsize = 队列中 元素个数 当Q.rear = Q.front时: 队列是空或满(怎样区分？),循环队列的头尾指针,队满条件：(Q.rear+1)%MAX=Q.front 队空条件: Q.rear = Q.front 元素个数: (Q.rear Q.front +maxsize )%maxsize 注：实际上为了避免与队空标志冲突，还留有一个空间。,循环队的入队和出队操作示意图,循环队列-队列的顺序存储结构实现(1),typedef struct QElemType *base; / 存储空间基地址 int front; /队头指针，若队列不空，指向队列头元素 int rear; / 队尾指针，若队列不空，指向 / 队列尾元素 的下一个位置 SqQueue; #define MAXQSIZE 100/最大队列长度，不能动态追加。 Status InitQueue(SqQueue / InitQueue,循环队列-队列的顺序存储结构实现(2),Status

9、EnQueue(SqQueue / EnQueue,循环队列-队列的顺序存储结构实现(3),Status DeQueue(SqQueue / DeQueue,3.4.3 链队列 - 队列的链式表示与实现,typedef struct QNode /队列结点 QElemType data; struct QNode *next; QNode, *QueuePtr; typedef struct QueuePtr front; / 队头指针 QueuePtr rear; / 队尾指针 LiQueue; #define OK 1 #define OVERFLOW -1 #define ERROR 0,data,*next,front,rear,链队列示意图（带头结点）,front,rear,front,rear,front,rear,钱,赵,front,rear,钱,赵,(a)空队列,(b)元素“赵”入队列,(c)元素“钱”入队列,(d)元素“赵”出队列,链队列的操作实现举例/* InitQueue 构造一个空的队列Q*/,Status InitQueue(LiQueue / InitQueue,链队列的操作实现(DestroyQueue) / 销毁队列Q,Status DestroyQueue(LiQueue / DestroyQueue,链队列的操作实现(EnQueue) / 插入元素e为新的队尾元素,Status EnQueue(LiQue

《第3章 队列与堆栈ppt课件》由会员我***分享，可在线阅读，更多相关《第3章 队列与堆栈ppt课件》请在金锄头文库上搜索。