《第三章栈和队列S教材课程》由会员分享，可在线阅读，更多相关《第三章栈和队列S教材课程（52页珍藏版）》请在金锄头文库上搜索。
1、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.熟练掌握栈类型的两种实现方法，即两种存 储结构表示时的基本操作实现算法，特别应 注意栈满和栈空的条件以及它们
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,InitSta
3、ck( #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,Statu
4、s 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进制数的转换原理:
5、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 括号匹配的检验,则 检验括号是否匹配的
6、方法可用 “期待的急迫程度”这个概念来描述。,假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 （）)均为不正确的格式。,21,分析可能出现的不匹配的情况:,到来的右括弧并非是所“期待”的；,例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,直到结束，也没有到来所 “期待”的括弧。,22,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余， 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” ， 否则表明不匹配。,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确， 否则表明“左括弧”有余。,23,
7、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
8、 != 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,
9、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
10、 ) 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 /
11、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
12、.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 ; /队
13、尾指针 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 /最大队列长度 typed
14、ef 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;,实现：利用
15、“模”运算 入队： 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
