数据结构名师课件

《数据结构名师课件》由会员分享，可在线阅读，更多相关《数据结构名师课件（144页珍藏版）》请在金锄头文库上搜索。

1、第三章 栈和队列通常称，栈和队列是限定插入和删除 只能在表的“端点”进行的线性表。线性表 栈 队列 Insert(L, i, x) Insert(S, n+1, x) Insert(Q, n+1, x)1in+1Delete(L, i) Delete(S, n) Delete(Q, 1)1in栈和队列是两种常用的数据类型3.1 栈的类型定义3.2 栈类型的实现3.3 栈的应用举例3.4 队列的类型定义3.5 队列类型的实现栈（stack）定义栈是只能在一端插入和删除的线性表特性：后进先出（LIFO）或 先进后出（FILO）设栈s=（a1，a2，. . . ,ai，. . . ，an），其中a1

2、是栈底元素， an是栈顶元素。栈顶（top)：允许插入和删除的一端；约定top始终指向新数据元素将存放的位置。栈底（bottom):不允许插入和删除的一端。a1a2.an进栈出栈栈顶栈底3.1 栈的类型定义ADT Stack 数据对象：D ai | ai ElemSet, i=1,2,.,n, n0 数据关系：R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： ADT StackInitStack( / 存储空间的初始分配量#define STACKINCREMENT 10; / 存储空间的分配增量typedef struct SElemType

3、*base; / 栈底指针SElemType *top; / 栈顶指针(栈顶元素的下一个位置)int stacksize; / 当前分配的存储容量 SqStack;类似于线性表的顺序映象实现， 指向表尾的指针可以作为栈顶指针。1）和顺序表一样采用增量式的空间分配；2）操作和栈顶相关：插入操作（入栈）：将待插元素插入到栈顶元素的下一个位置；删除操作（出栈）：删除栈顶元素；取元素操作：取栈顶元素的值。各操作的操作位置与栈顶元素的位置或其下一个位置相关，希望在O(1)时间内能获取操作位置，故可设置专门的栈顶指针top。3）约定：top指向栈顶元素的下一个位置（便 于表示空栈）。 4）栈顶的初始化：S

4、.top = S.base(在上述3) 约定下的空栈形式)， 5）栈空：S.base = S.top，栈满：S.top - S.base = S.stacksize 6）入栈：*S.top + = e，出栈：e = *-S.top 注意：4), 5), 6)步受3)制约。约定不同，相 应的判定和处理也不一样。 如假设top就指向栈顶元素，此时4),5),6)如何 ？基本操作的实现base 空栈a 进栈b 进栈atopbasetop basetopab约定：top指向栈顶元素的下一个位置base e 进栈f 进栈溢出e出栈e d c b atopbasetopbasetope d c b ad

5、c b aStatus InitStack (SqStack if (!S.base) exit (OVERFLOW); /存储分配失败S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK; 取栈顶元素GetTop_Sq 算法设计参数：顺序栈S、取得的栈顶元素 e = *( S.top -1); return OK; 入栈操作Push_Sq算法设计 参数：顺序栈 Status Push (SqStack if (!S.base) exit (OVERFLOW); /存储分配失败S.top = S.base + S.stacksize;S.

6、stacksize += STACKINCREMENT;*S.top+ = e; T(n) = O(1) return OK; 出栈操作Pop_Sq 算法设计参数：顺序栈e = *-S.top; /* 注意与GetTop( )的区别*/ return OK; T(n) = O(1) 在一个程序中同时使用两个栈0M-1栈1底栈1顶栈2底栈2顶栈顶指针链栈a1an注意: 链栈中 指针的方向an-1与链表类似，只是链表的头指 针即为栈顶指针。因其操作均 在栈顶进行，故可以不引入头 结点。 用指针来实现的栈叫链栈。栈 的容量事先不能估计时采用这 种存储结构。 无栈满问题(除非分配不出内 存), 空间可

7、扩充 栈顶-链表的表头3.3 栈的应用举例例一、 数制转换 例二、 括号匹配的检验例三、 行编辑程序问题例四、 迷宫求解例五、 表达式求值例六、 实现递归例一、 数制转换算法基于原理：N = (N div d)d + N mod d 多进制输出：例 把十进制数159转换成八进制数(159)10=(237)81598198 28 02 3 7 余 7余 3余 2toptop7top73top7321）将N%d的结果保存，2）N=N/d，3）若N=0结束，否则继续1）。保存的余数从先到后依次表示转换后的d 进制数的低位到高位，而输出是由高位到低位的，因此必须定义先进后出的线性表栈来保存；当全部的余

8、数求出后，通过逐个出栈输出d进制数。 例如：（1348)10 = (2504)8 ，其运算过程如下：N N div 8 N mod 8 1348 168 4168 21 021 2 52 0 2计算顺序输出顺序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例二、 括号匹配的检验 假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 （）)均为不

9、正确的格式。则 检验括号是否匹配的方法可用 “期待的急迫程度”这个概念来描述。从左至右扫描表达式，遇左括号入栈，遇右括号与栈顶元素比较：若左右括号匹配，则继续扫描；否则说明不匹配，结束。在上述操作中，若栈为空，或扫描结束后栈不为空，均说明不匹配。分析可能出现的不匹配的情 况: 到来的右括弧并非是所“期待”的 ；例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 到来的是“不速之客”； 直到结束，也没有到来所“期待”的括弧。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余，否则和栈顶元素比较，若相匹配，则“左括弧出栈” ，否

10、则表明不匹配。 3）表达式检验结束时，若栈空，则表明表达式中匹配正确，否则表明“左括弧”有余。Status matching(stringwhile (ic：Pop(OPTR, theta); Pop(OPND, b); Pop(OPND, a);x=Operate(a, theta, b); Push(OPND, x); 继续读入字符处理。 算法思想表达式的三种标识方法：设 Exp = S1 + OP + S2则称 OP + S1 + S2 为前缀表示法(波兰式) S1 + OP + S2 为中缀表示法 S1 + S2 + OP 为后缀表示法(逆波兰式) 例如: Exp = a b + (c

11、 d / 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 + CD 为例说明利用栈的求值过程 。

12、优先级： 4 3 3 2 2 1 1 0操作数变量：A B C DA*B + C/D;top2 top1初态;(a)OSNSB A* ;(b)NSOST1;(c) T1=A*BNSOSD C T1/ + ; (d)NSOS(g)NSOST2=C/DT2 T1+ ;(e)NSOST3;(f)T3=T2+T1NSOS思想：从左到右扫描表达式，若当前读入的是操作数，则进操 作数（NS）栈，若读入的符号是运算符，应进行判断：1. 若是“（”，进运算符栈；若是“）”，当运算符栈顶是“（”， 则弹出栈顶元素，继续扫描下一符号。否则当前读入符号暂 不处理，从操作数栈弹出两个操作数，从运算符栈弹出一个 运算符

13、，生成运算指令，结果送入操作数栈，继续处理当前 读入符号。2.若读入的运算符的优先级大于运算符栈顶的优先级，则进运算 符栈，继续扫描下一符号；否则从操作数栈顶弹出两个操作 数，从运算符栈弹出一个运算符，生成运算指令，把结果送 入操作数栈。继续处理刚才读入的符号。3. 若读入的是“；”，且运算符栈顶的符号也是“；”时，则表达 式处理结束。从操作数栈弹出表达式结果。例 计算 2+4-3*6操作数运算符24 + 操作数运算符6- 操作数运算符6-36 *操作数运算符6-18操作数运算符12n表达式的不同表示之间的相互转换n逆波兰式波兰式n如：abcd+*e*+ +a*b+cden共同点n运算对象的次

14、序一致n不需要括号区分优先级和结合性n某算符在所有算符中的次序决定了它的计算次序n转换的思想n参照逆波兰式的计算过程，将计算转换为待计算的算符和运算对 象的串的拼接n逆波兰式中缀表达式n如： abcd+*e*+ a+b*(c+d)*e 输入：表达式符号序列表达式求值算法：输出：表达式值 y初始化栈 NS、OSPush (OS, “;” , top2)；t=0; /表示扫描下一个符号while (tp)or(W=“(“) THEN Push (OS, W, top2); t=0;ELSE IF (p=“;” ）and (W=“ ;”) THEN Pop (NS, y,top1); t=2; /处理过程结束ELSE IF (p=“(“ )and (w=“）”）THENELSE Pop(NS,x,top1); Pop(NS,z,top1) ; Pop(OS,p,top2） ；x=z x; Push(NS ,x ,top1);t=1; /t=1,当前的符号下次重新考虑 输出 y;return; Pop(OS ,p,top2); t=0; 练习1：A+B*C-D/E；top1初态; (a)top2OSNSB A+ ;(b)OS*CNST1=B*CA+ ;(c)NSOST1T2; (d)NSOST2=A+T1E D T2/ - ;(e)NSOST3 T2- ;(f)T3=D/ENSO