《工学数据结构》PPT课件.ppt

实验安排 时间：8-15周 单周：周四 5、6节 双周：周二 5、6节 地点：1、2班 软419 3、4班 软420,第3章 栈和队列,栈和队列是两种常用的线性结构,【学习目标】 1. 掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。 2. 熟练掌握栈类型的两种实现方法。 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.1 栈,3.1 栈,定义：限定仅在表尾进行插入或删除操作的线性表。 表尾(允许插入和删除)栈顶，表头栈底 特点：后进先出（LIFO）,3.1.1 栈的定义,3.1 栈,栈的抽象数据类型 ADT Stack 数据对象： D ai | ai ElemSet, i=1,2,.,n, n0 数据关系： R1 | ai-1, aiD, i=2,.,n 约定an 端为栈顶，a1 端为栈底。 基本操作： ADT Stack,建栈、入栈、出栈、 读栈顶元素、判断栈满或栈空等。,3.1 栈,3.1.2 栈的表示和实现 顺序栈：(栈的顺序存储结构)利用一组地址连续的 存储单元依次存放自栈底到栈顶的数据元素。,/- 栈的顺序存储表示 - typedef struct SElemType *base; /栈底指针即栈的基址 SElemType *top; /指向栈顶元素的上一个位置 int stacksize; /栈的容量(已分配的存储空间) SqStack;,栈顶元素的说明,3.1 栈,3.1.2 栈的表示和实现 如：SqStack s; s为一个顺序栈的变量。s的存储空间为： s.base s.top s. stacksize,s.base0 s.basestacksize-1,该空间的申请由初始化操作实现,3.1 栈,栈空出栈，则下溢(underflow) 栈满入栈，则上溢(overflow),3.1.2 栈的表示和实现,A,B,C,D,E,F,栈满:top- base = stacksize,栈空,*S.top+ = e,e = *- S.top,3.1 栈,思考：如果进栈顺序为1，2，3，4。不限制出栈 的时间，则下面哪一种出栈顺序不可能。 (1) 1, 2, 3, 4 (2) 2, 1, 4, 3 (3) 3, 1, 2, 4 (4) 4, 3, 2, 1,3.1.2 栈的表示和实现,3.1 栈,3.1.2 栈的表示和实现 栈的基本操作在顺序栈中的实现,InitStack(&S) / 构造栈,Push(&S，e) / 入栈,Pop(&S，&e) / 出栈,GetTop(S，&e) / 取栈顶元素,3.1 栈,3.1.2 栈的表示和实现 栈初始化 算法描述： Status InitStack (SqStack / InitStack,3.1 栈,3.1.2 栈的表示和实现 入栈 算法描述： Status Push (SqStack /Push,e插入后栈顶指针加1,if (S.top - S.base = S.stacksize) /栈满,追加存储空间 S.base = (SElemType *)relloc(S.base , (STACK_INI_SIZE+STACKINCREMENT)* sizeof (SElemType); If(!S.base) exit(OVERFLOW); /存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT；,3.1 栈,3.1.2 栈的表示和实现 出栈 算法描述： Status Pop (SqStack /Pop,栈顶指针减1，取所指元素,3.1 栈,3.1.2 栈的表示和实现 取栈顶元素 算法描述： Status GetTop(SqStack S，SElemType /GetPop,3.1 栈,链栈(补充): 用链式结构来表示的栈就是链栈 (1)链栈的构造方式: 以头指针为栈顶，在头指针处插入或删除,栈顶元素,栈底元素,通常链栈不设头结点，因为栈顶(表头）操作频繁,基本操作：p-data=e; p-next=top; top=p;,3.1 栈,链栈(补充): 入栈：,出栈：,基本操作：e=top-data; q=top; top=top-next; free(q); return(e);,3.1 栈,3.1.3 栈的应用举例,例一：数制转换,例二：括号匹配的检验,例三：行编辑程序,例四：迷宫求解,例五：表达式求值,例六：汉诺塔问题*,设计思路： 用栈暂存低位值,3.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,3.1 栈,算法描述： void conversion () /对于输入的十进制非负整数，输出对应的八进制数 InitStack(S); /构造空栈S scanf (“%d“,N); while (N) Push(S, N % 8); /入栈 N = N/8; while (!StackEmpty(S) Pop(S,e); printf ( “%d”, e ); /出栈 / conversion,例一：数制转换,3.1 栈,例二：括号匹配的检验 假设在表达式中 （）或（ ） 等为正确的格式， （ ）或（ ）或 ( ) 均为不正确的格式。 则 检验括号是否匹配的方法可用“期待的 急迫程度”这个概念来描述。,“期待的急迫程度” :即后出现的“左括弧”，它等待与其匹配的“右括弧”出现的“急迫”心情要比先出现的左括弧高。换句话说，对“左括弧”来说，后出现的比先出现的“优先”等待检验，对“右括弧”来说，每个出现的右括弧要去找在它之前“最后”出现的那个左括弧去匹配。 显然，必须将先后出现的左括弧依次保存，为了反映这个优先程度，保存左括弧的结构用栈最合适。这样对出现的右括弧来说，只要“栈顶元素”相匹配即可。如果在栈顶的那个左括弧正好和它匹配，就可将它从栈顶删除。,3.1 栈,3.1 栈,例二：括号匹配的检验 例如：考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 分析：当接受了第一个括号“”后，期待与其匹配的第八个 出现，而等来的确是第二个“（”，此时，第二个括号期待匹 配的程度高于第一个，第一个“”只能放一边；而迫切等待 与第二个括号相匹配的、第七个括号“）”的出现，可等来的 是第三个括是号“”，因而，其期待匹配程度高于第二个， 第二个括号让位于第三个；直到第四个括号“”出现，第三 个括号期待得到满足，消解之后，第二个括号期待匹配成 了最急迫的任务,设计思路： 用栈暂存左括号,3.1 栈,例二：括号匹配的检验 算法的设计思想：,1. 出现的凡是“左括号”，则进栈；,2. 出现的是“右括号”， 首先检查栈是否空？ 若栈空，则表明该“右括号”多余 否则和栈顶元素比较？ 若相匹配，则栈顶“左括号出栈” 否则表明不匹配,3.表达式检验结束时， 若栈空，则表明表达式中匹配正确 否则表明“左括号”有余,3.1 栈,例二：括号匹配的检验,算法描述 （作 业）,3.1 栈,例三：行编辑程序 “每接受一个字符即存入存储器” ? 并不恰当！ 在用户输入一行的过程中，允许用户输入出差错， 并在发现有误时可以及时更正。,合理的作法是： 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区; 并假设“#”为退格符，“”为退行符。,3.1 栈,例三：行编辑程序,假设从终端接受了这样两行字符： whli#ilr#e（s#*s) outchaputchar(*s=#+);,则实际有效的是下列两行： while (*s) putchar(*s+);,3.1 栈,例三：行编辑程序 while (ch != EOF) /EOF为全文结束符 while (ch != n) /判断是否换行 switch (ch) case # : Pop(S, c); break; case : ClearStack(S); break;/ 重置S为空栈 default : Push(S, ch); break; ch = getchar(); / 从终端接收下一个字符 将从栈底到栈顶的字符传送至调用过程的数据区； ClearStack(S); / 重置S为空栈 if (ch != EOF) ch = getchar(); ,3.1 栈,例四：迷宫求解(穷举求解),出口,入口,1-东 2-南 3-西 4-北,1 1 1,1 2 2,2 2 2,3 2 1,3 3 1,3 4 4,2 4 1,2 5 1,2 6 4,1 6 3,1 5 3,1 4 4,3,$,$,$,$,$,$,$,$,蓝-坐标，红-方向,3.1 栈,例四：迷宫求解 算法的基本思想是： 若当前位置“可通”，则纳入路径，继续前进; 若当前位置“不可通”，则后退，换方向继续探索; 若四周“均无通路”，则将当前位置从路径中删除出去。,3.1 栈,例四：迷宫求解 设定当前位置的初值为入口位置； do 若当前位置可通， 则将当前位置插入栈顶； 若该位置是出口位置，则算法结束； 否则切换当前位置的东邻方块为新的当前位置； 否则 while (栈不空）；,3.1 栈,例四：迷宫求解 若栈不空且栈顶位置尚有其他方向未被探索， 则设定新的当前位置为: 沿顺时针方向旋转 找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则删去栈顶位置；/ 从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空； 若栈空，则表明迷宫没有通路。,3.1 栈,例五：表达式求值 表达式求值是栈应用的典型例子 (1)表达式求值必须满足算术四则运算规则： a. 先乘除，后加减 b. 从左算到右 c. 先括号内，后括号外 (2)任何一个表达式由：操作数、运算符、界限符 组成 (3)运算符和界限符统称算符。 根据上面的运算规则，在运算的每一步中，任意两个 相继出现的算符1和2之间的优先关系至多是下面三 种关系之一： 1 2 : 1的优先权高于2,3.1 栈,例五：表达式求值,（下表给出了算符之间的优先级）,由上表可看出，右括号 ) 和井号 # 作为2时级别最低； 由c 规则得出： * ，/， + ，-为1时的优先权低于（，高于） 由b 规则得出：（ = ） 表明括号内的运算已完成； # = # 表明表达式求值完毕。,3.1 栈,例五：表达式求值 为了实现算符优先算法，可以设定两个工作栈： OPND存放操作数或运算结果， OPTR存放运算符号。 算法思想： 1）首先置操作数栈OPND为空栈，表达式的起始符#为运算符栈OPTR的栈底元素； 2）依次读入表达式中的每个字符， 若运算符是#或栈顶是#，结束计算，返回OPND栈顶值。 if（是操作数） 则PUSH（ OPND，操作数）； if（是运算符） 则与OPTR栈顶元素1进行比较，按优先级(规定详见P53表3.1）进行操作； if栈顶元素运算符，则退栈、按栈顶计算，将结果压入OPND栈。,判C是否操作符,3.1 栈,例五：表达式求值 算法描述：,Status EvaluateExpression( OperandType /EvaluateExpression,Operate=a b,运算符与栈顶比较并查3.1表,3.1 栈,例五：表达式求值 例：对表达式3*（7 2 ）求值,练习： 3+4-(6-9/2)+7*5# (参照例3-1),3.1 栈,例六：汉诺塔问题* 汉诺（ Hanoi）塔 传说在创世纪时，在一个叫Brahma的寺庙里，有三 个柱子，其中一柱上有64个盘子从小到大依次叠放，僧 侣的工作是将这64个盘子从一根柱子移到另一个柱子上。,移动时的规则： 每次只能移动一个盘子； 只能小盘子在大盘子上面； 可以使用任一柱子。,当工作做完之后，就标志着世界末日到来。,3.1 栈,例六：汉诺塔问题* 分析： 设三根柱子分别为 x, y, z , 盘子在 x 柱上，要移 到z 柱上。 1、当 n=1 时，盘子直接从 x 柱移到 z 柱上； 2、当 n1 时, 则: 设法将前 n 1 个盘子 从 x 移到 y 柱上（借助z），则 盘子 n 就能从 x 移到 z 柱上； 再设法把n 1 个盘子 从 y 移到 z 柱上(这又是一 个与原来相同的问题，只是规模少了） 。,递归函数：一个直接调用自己或通过一系列的调用语句间接调用自己的函数,3.1 栈,例六：汉诺塔问题* 算法描述： Void Hanoi ( int n, char x, char y, char z ) 1 /将n个编号从上到下为1n的盘子从x柱，借助y柱移到z柱 2 if ( n = = 1 ) 3 move ( x , 1 , z ) ; /将编号为1的盘子从x柱移到z柱 4 else 5 Hanoi ( n-1