资源预览内容
第1页 / 共52页
第2页 / 共52页
第3页 / 共52页
第4页 / 共52页
第5页 / 共52页
第6页 / 共52页
第7页 / 共52页
第8页 / 共52页
第9页 / 共52页
第10页 / 共52页
亲,该文档总共52页,到这儿已超出免费预览范围,如果喜欢就下载吧!
资源描述
1,第三章 栈和队列,3.1 栈,3.2 栈的应用举例,3.4 队列,2,通常称,栈和队列是限定插入和删除只能在表的“端点”进行的线性表。,线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x) 1in+1 Delete(L, i) Delete(S, n) Delete(Q, 1) 1in,栈和队列是两种常用的数据类型,3,学习提要: 1.掌握栈和队列这两种抽象数据类型的特点, 并能在相应的应用问题中正确选用它们。 2.熟练掌握栈类型的两种实现方法,即两种存 储结构表示时的基本操作实现算法,特别应 注意栈满和栈空的条件以及它们的描述方法。 3.熟练掌握循环队列和链队列的基本操作实现 算法,特别注意队满和队空的描述方法。 重难点内容: 顺序栈的相关操作、循环队列的判空判满,5,栈的定义和特点 定义:限定仅在表尾进行插入或删除操作的线性表,表尾栈顶,表头栈底,不含元素的空表称空栈。,特点:先进后出(FILO)或后进先出(LIFO),3.1.1 栈的类型定义,6,ADT Stack 数据对象: D ai | ai ElemSet, i=1,2,.,n, n0 数据关系: R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶,a1 端为栈底。,基本操作:, ADT Stack,栈的类型定义,7,InitStack( #define STACKINCREMENT 10; typedef struct SElemType *base; SElemType *top; int stacksize; SqStack;,9,实现:一维数组sM,进栈,A,栈满,B,C,D,E,F,设数组维数为M top=base,栈空,此时出栈,则下溢(underflow) top=M,栈满,此时入栈,则上溢(overflow),空栈,出栈,栈空,栈底指针base,始终指向栈底位置;栈顶指针top,其初值指向栈底,始终在栈顶元素的下一个位置,A,B,10,Status InitStack (SqStack ,11,Status Push (SqStack ,12,Status Pop (SqStack ,13,在一个程序中同时使用两个栈,14,链栈 栈的链式存储结构。栈顶指针就是链表的头指针。,栈顶指针,a1,an,注意: 链栈中指针的方向,an-1,注意: 链栈中指针的方向,注意:链栈中的指针方向,15,入栈操作,出栈操作,p-next=top ; top=p,q=top ; top=top-next,16,3.2 栈的应用,3.2.1 数制转换,3.2.2 括号匹配的检验,3.2.3 行编辑程序问题,3.2.4 迷宫求解,3.2.5 表达式求值,17,3.2.1 数制转换,十进制N和其他d进制数的转换原理: N=( N div d )*d + N mod d 其中:div为整除运算,mod为求余运算,18,例如: (1348)10=(2504)8,其运算过程如下: N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,19,void conversion( ) initstack(S); scanf (“%d”,N); while(N) push(S,N%8); N=N/8; while(! Stackempty(s) pop(S,e); printf(“%d”,e); /conversion,20,3.3.2 括号匹配的检验,则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。,假设在表达式中 ()或( ) 等为正确的格式, ( )或( )或 ())均为不正确的格式。,21,分析可能出现的不匹配的情况:,到来的右括弧并非是所“期待”的;,例如:考虑下列括号序列: ( ) 1 2 3 4 5 6 7 8,直到结束,也没有到来所 “期待”的括弧。,22,算法的设计思想:,1)凡出现左括弧,则进栈;,2)凡出现右括弧,首先检查栈是否空 若栈空,则表明该“右括弧”多余, 否则和栈顶元素比较, 若相匹配,则“左括弧出栈” , 否则表明不匹配。,3)表达式检验结束时, 若栈空,则表明表达式中匹配正确, 否则表明“左括弧”有余。,23,3.2.3 行编辑程序问题,如何实现?,“每接受一个字符即存入存储器” ?,不恰当!,合理的作法是:,设立一个输入缓冲区,用以接受用户输入的一行字符,然后逐行存入用户数据区,并假设“#”为退格符,“”为退行符。,24,假设从终端接受了这样两行字符: whli#ilr#e(s#*s) outchaputchar(*s=#+);,则实际有效的是下列两行: while (*s) putchar(*s+);,25,while (ch != EOF / 从终端接收下一个字符 ,ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar();,while (ch != EOF) /EOF为全文结束符,将从栈底到栈顶的字符传送至调用过程的 数据区;,26,3.2.4 迷宫求解,通常用的是“穷举求解”的方法,27,求迷宫路径算法的基本思想是:,若当前位置“可通”,则纳入路径, 继续前进;,若当前位置“不可通”,则后退,换方向继续探索;,若四周“均无通路”,则将当前位置从路径中删除出去。,28,限于二元运算符的表达式定义: Exp = S1 OP S2 操作数 : 变量、常量、表达式 运算符 : 算术运算符、关系运算符、 逻辑运算符 界限符:括号、结束符,3.2.5 表达式求值,29,例:3 * ( 7 2 ),3,*,(,7,2,2,7,5,*,5,3,15,30,例: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 ) # PUSH( OPND, 7 ) 5 # * ( 3 7 2 ) # PUSH( OPTR, ) 6 # * ( 3 7 2 ) # PHSH( 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 ),31,OperandType EvaluateExpression() / 设OPTR和OPND分别为运算符栈和运算数栈,OP为运算符集合。 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); / EvaluateExpression, ,32,switch ( precede(GetTop(OPTR), c) case : / 退栈并将运算结果入栈 Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a); Push(OPND, Operate(a, theta, b); break; / switch,33,3.4 队列,3.4.1 队列的类型定义,3.4.2 链队列,3.4.3 循环队列,34,队列是限定只能在表的一端进行插入,在表的另一端进行删除的线性表。,队列特点:先进先出(FIFO),3.4.1 队列的类型定义,队尾(rear)允许插入的一端 队头(front)允许删除的一端,35,ADT Queue 数据对象: Dai | aiElemSet, i=1,2,.,n, n0 数据关系: R1 | ai-1, ai D, i=2,.,n 约定其中a1 端为队列头, an 端为队列尾,基本操作:,队列的类型定义, ADT Queue,36,队列的基本操作:,InitQueue( struct QNode *next ; QNode, *QueuePtr;,typedef struct /链队列类型 QueuePtr front ; /队头指针 QueuePtr rear ; /队尾指针 LinkQueue;,3.4.2 链队列队列的链式表示和实现,38,a1,an,Q.front Q.rear,Q.front Q.rear,空队列,39,Q.rear - next=p Q.rear=p,p= Q.front - next Q.front - next = p - next,40,Status InitQueue (LinkQueue ,41,Status EnQueue (LinkQueue ,42,Status DeQueue (LinkQueue ,43,3.4.3 循环队列队列的顺序表示和实现,#define MAXQSIZE 100 /最大队列长度 typedef struct QElemType *base; / 动态分配存储空间 int front; / 头指针,若队列不空, /指向队列头元素 int rear; / 尾指针,若队列不空,指向 / 队列尾元素 的下一个位置 SqQueue;,44,实现:用一维数组实现sqM,J1,J2,J3,存在问题: 当front=0,rear=M时再有元素入队发生溢出真溢出 当front0,rear=M时再有元素入队发生溢出假溢出,45,解决方案 队首固定,每次出队剩余元素向下移动浪费时间 循环队列 基本思想:把队列设想成环形,让sq0接在sqM-1 之后,若rear+1=M,则令rear=0;,实现:利用“模”运算 入队: baserear=x; rear=(rear+1)%M; 出队: x=basefront; front=(front+1)%M; 队满、队空判定条件,46,队空:front=rear 队满:front=rear,解决方案: 1.另外设一个标志位以区别队空、队满 2.少用一个元素空间: 队空:front=rear 队满:(rear+1)%M=front 3.使用一个计数器记录队列中元素的总数,47,Status InitQueue (SqQueue ,48,Status EnQueue (SqQueue ,49,Status DeQueue (SqQueue ,50,第三章作业,3.1 设将整数1、2、3、4依次进栈,但只要出栈时栈非空,则可将出栈操作按任何次序夹入其中,请回答下有问题: (1)若入栈次序为push(1),pop(),push(2),p
网站客服QQ:2055934822
金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号