《栈和队列是操作受限的线性表栈：后进先出；队列：先进先...的》由会员分享，可在线阅读，更多相关《栈和队列是操作受限的线性表栈：后进先出；队列：先进先...的（98页珍藏版）》请在金锄头文库上搜索。
1、第3章栈和队列,栈和队列是操作受限的线性表。栈：后进先出；队列：先进先出。,线性表 栈 队列 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 栈,3.2 栈的应用举例,3.3 栈与递归实现,3.4 队列,3.1.1 栈的抽象数据类型定义,3.1.2 栈的表示与实现,3.1 栈,ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1,
2、 aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。,基本操作：, ADT Stack,3.1.1 栈的抽象数据类型定义,InitStack(&S),DestroyStack(&S),StackEmpty(S),GetTop(S, &e),Push(&S, e),Pop(&S, &e),InitStack(&S) 操作结果：构造一个空栈 S。,Return,DestroyStack(&S) 初始条件：栈 S 已存在。 操作结果：栈 S 被销毁。,Return,StackEmpty(S) 初始条件：栈 S 已存在。 操作结果：若栈 S 为空栈，则返回 TRUE，否则 FALE。,Re
3、turn,GetTop(S, &e) 初始条件：栈 S 已存在且非空。操作结果：用 e 返回 S 的栈顶元素。,a1,a2,an, ,Return,Push(&S, e) 初始条件：栈 S 已存在。 操作结果：插入元素 e 为新的栈顶元素。,a1,a2,an,e, ,Return,Pop(&S, &e) 初始条件：栈 S 已存在且非空。 操作结果：删除 S 的栈顶元素，并用 e 返回其值。,a1,a2,an,an-1, ,Return,3.1.2 栈的表示与实现,1.顺序栈,2.链 栈,/- 顺序栈的类型描述 - #define STACK_INIT_SIZE 100; typedef int
4、 ElemType; typedef struct ElemType *data; int top; int stacksize; SqStack;,利用顺序存储方式实现的栈称为顺序栈。,通常将数组的0下标作为栈底，这样空栈时栈顶指针top=-1；进栈时，栈顶指针加1，即top+；出栈时，栈顶指针减1，即top-。栈操作的示意图如图3-1所示。,int InitStack (SqStack ,int Push (SqStack ,int Pop (SqStack ,Elemtype GetTop (SqStack S) /栈已存在且不空，返回栈顶元素 if (S.top = -1) retur
5、n ERROR; return S.dataS.top; ,int StackEmpty (SqStack S) /判栈是否为空栈 if (S.top = -1) return OK; return ERROR; ,需要注意的是，对顺序栈，入栈时应首先判断栈是否满了，栈满的条件是S.top=S.stacksize-1。栈满时，不能入栈，否则将出现空间溢出，引起错误，这种现象称为上溢。解决的办法是追加存储空间。出栈和读取栈顶元素时，应先判断栈是否为空，为空时不能操作，否则将产生错误，通常栈空作为控制转移的条件。,链栈,用链式存储结构实现的栈称为链栈。通常链栈用单链表表示，因此其结点结构与单链表的
6、结点结构相同。在此用LinkStack表示，即有：,typedef struct node ElemType data; struct node *next; StackNode,*LinkStack; LinkList top;,因为栈中的主要运算是在栈顶插入、删除，显然在链表的头部做栈顶是最方便的，而且没有必要象单链表那样为了运算方便附加一个头结点。如图3-2：,void InitStack (LinkStack ,int Push (LinkStack ,int Pop (LinkStack ,int StackEmpty (ListStack S) /判栈是否为空栈 if (S.top
7、 = NULL) return OK; return ERROR; ,3.2 栈的应用举例,3.2.1 数制转换,3.2.2 括号匹配的检验,3.2.3 表达式求值,3.2.4 命题公式求值,3.2.1 数制转换 算法基于原理： N = (N div d)d + N mod d,例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,计算顺序,输出顺序,void conversion () InitStack(S); scanf (“%d“, / conversion,3.2.2 括号
8、匹配的检验 假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 ( ) 均为不正确的格式。,则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。,分析可能出现的不匹配的情况:,到来的右括弧非是所“期待”的;,例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8,到来的是“不速之客”;,直到结束，也没有到来所“期待”的括弧;,算法的设计思想：,1）凡出现左括弧，则进栈；,2）凡出现右括弧，首先检查栈是否空 若栈空，则表明该“右括弧”多余 否则和栈顶元素比较， 若相匹配，则“左括弧出栈” 否则表明不匹配,3）表达式检验结束时， 若栈空，则表明表达式中匹配正确
9、 否则表明“左括弧”有余,int matching(char exp) int state = 1;i=0;InitStack(S); while (iLength(exp) ,限于二元运算符的表达式定义: 表达式 := (操作数) + (运算符) + (操作数) 操作数 := 简单变量 | 表达式 简单变量 : = 标识符 | 无符号整数,3.2.3 表达式求值,表达式的三种标识方法：,设 Exp = S1 + OP + S2,则称 OP + S1 + S2 为前缀表示法,S1 + OP + S2 为中缀表示法,S1 + S2 + OP 为后缀表示法,例如: Exp = a b + (c d
10、 / e) f 前缀式: + a b c / d e f 中缀式: a b + c d / e f 后缀式: a b c d e / f +,结论:,1）操作数之间的相对次序不变;,2）运算符的相对次序不同;,3）中缀式丢失了括弧信息， 致使运算的次序不确定;,4)前缀式的运算规则为: 连续出现的两个操作数和在它们 之前且紧靠它们的运算符构成一 个最小表达式;,5)后缀式的运算规则为: 运算符在式中出现的顺序恰为 表达式的运算顺序; 每个运算符和在它之前出现 且 紧靠它的两个操作数构成一个最小 表达式;,如何从后缀式求值？,先找运算符， 再找操作数,例如： a b c d e / f +,ab
11、,d/e,c-d/e,(c-d/e)f,如何从原表达式求得后缀式？,每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中,优先数高的运算符领先于优先数低的运算符。,分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a + b c d / e f 后缀式: a b c + d e / f ,从原表达式求得后缀式的规律为：,1) 设立暂存运算符的栈;,2) 设表达式的结束符为“#”, 予设运算符栈的栈底为“#”,3) 若当前字符是操作数， 则直接发送给后缀式;,4) 若当前运算符的优先数高于栈顶运算符，则进栈;,否则，退出栈顶运算符发送给后缀式;,5) “(” 对它之前后的运算符起
12、隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。,从原表达式求得后缀式的规律为：,void transform(char suffix , char exp ) InitStack(OPTR); Push(OPTR, #); while (*exp!=#) if (*exp=0 / CrtExptree,do /不是运算符,则处理连续出现的数字 Suffixi+=*exp; exp+; while(*exp=0 /操作数之间的间隔符,Return,switch (*exp) case ( : Push(OPTR, *exp); break; case ) : Pop(OPTR, ch)
13、; while (ch!= ( ) Suffixi+=ch; Pop(OPTR,ch) break; defult : while(precede(GetTop(OPTR),*exp)!=) Pop(OPTR, ch);Suffixi+=ch; Push(OPTR, *exp); break; / switch exp+;,Return,求后缀式表示的表达式的值：,int calcul_exp(char *Suffix ) /返回后缀表达式的运算结果 InitStack(OPND); while (*Suffix! = # ) d=0; if (*Suffix=0 ,While(*Suffix
14、!=$) /不是运算符,则处理连续出现的数字 d=10*d+*Suffix-0; Suffix+; Push(OPND,d); /操作数进栈 Suffix+;,Return,Pop(OPND，b); Pop(OPND，a); switch (*Suffix) case ch= + : c=a+b; break; case ch= - : c=a-b; break; case ch= * : c=a*b; break; case ch= / : c=a/b; break; / switch Push(OPND，c); Suffix+;,Return,利用计算机求命题公式真值的关键是：给出命题变元
15、的每一组赋值；计算命题公式在每一组赋值下的真值，其计算类似于中缀表达式的求值。,3.2.4 命题公式求值,设定两个全局变量：字符数组myopnd10和整型数组A102411，分别存储命题公式中的命题变元和命题公式的真值表。全局变量n表示命题公式的变元数，m为其对应的赋值数。,真值表中命题变元的取值具有如下规律：每列中0和1是交替出现的，且0和1连续出现的个数相同。n个命题变元的每组赋值的生成算法可基于这种思想。,求命题公式的真值，可采用与中缀表达求值相类似的算法。算符之间的优先关系如表3-2所示：,为实现算符优先算法，我们采用两个工作栈。一个称作OPTR，用以寄存运算符；另一个称作OPND，用以寄存操作数或运算结果。算法的基本思想是：,(1)首先设置操作数栈为空栈，符号“#”为运算符的栈底元素,(2
