数据结构课件堆栈的应用.ppt

《数据结构课件堆栈的应用.ppt》由会员分享，可在线阅读，更多相关《数据结构课件堆栈的应用.ppt（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、1、数据结构研究型教学试点课程教学模式的设想 2、课堂讲授 3、课堂讨论 4、课堂作业 5、课后任务安排 6、课后测评,课堂教学内容组织：,一、数据结构研究型教学试点课程教学模式的设想,1、什么是研究型教学？,2、教学模式对人才培养质量的影响,3、研究型教学与传统教学的区别,4、数据结构研究型教学实施方案,一、数据结构研究型教学试点课程教学模式的设想,研究型教学模式是相对于以单向性知识传授为主的教学模式提出的，是指教师以课程内容和学生的学识积累为基础，引导学生创造性地运用知识和能力，自主地发现问题、研究问题和解决问题，在研讨中积累知识、培养能力和锻炼思维的新型教学模式。,1、什么是研究型教学？

2、,研究型教学的要点： 在于极大地引起学生对学科的兴趣，拓宽学生的视野，提高学生的学习积极性，从而对学科进行比较深入地探究、研究，最终使得学生能够有所发现、发明和创造。,2、教学模式对人才培养质量的影响,编写程序,实际问题,输出结果,教学培养,大一新生,毕业生,计算机解决实际问题流程：,大学人才培养流程：,数据结构 + 算法,结果对（好、较好）或结果错,学生生源 + 教学模式,合格（好、较好）或不合格,3、研究型教学与传统教学的区别,(1) 针对每个学时来制定详细的教学方案，具体包括每个学时讲授的内容提纲、拟讨论的题目、课后要收集查阅的资料、学生考核评定标准等。 （2）讲授的内容方面，只讲授最核

3、心的知识点，主要是“四点”，即重点、难点、疑点、新点。 （3）教学过程以学生学习为主体，开展讨论式教学、启发式教学、案例式教学、对偶式教学等。 （4）采用课堂讨论、专题研讨的教学方法 （5）将学生按5人一组分成若干学习、研究小组，分组应该使小组内部尽量异质化，这样小组成员之间就能够各取所长、优势互补；同时，为公平起见，各小组间应该尽量同质化。 （6）改革常规的考核方式。一改过去以笔试成绩为主的现象，考虑结合课程论文和课堂讨论进行综合考评。另外尝试让学生自己出题，变应试过程为研究学习过程。 （7）课程论文纳入平时考评。 （8）充分利用现代网络，进行立体化研究型教学。 （9）实施网络无限时答疑和辅

4、导。制定集中答疑、讨论计划。 （10）针对基础较差的学生，利用空余时间进行补习。,4、数据结构研究型教学实施方案,二、课堂讲授,教学内容 堆栈的应用表达式求值、实现递归,教学目的 熟悉堆栈的特点及其有关操作； 掌握利用堆栈结构来解决实际问题的方法。,重点、难点 重点：后缀表达式求值，堆栈在递归中的作用。 难点：中缀表达式求值。,限于二元运算符的表达式定义: 表达式 := (操作数) (运算符) (操作数) 操作数 := 简单变量 | 表达式 简单变量 : = 标识符 | 无符号整数,例四 表达式求值,表达式的三种标识方法：,设 Exp = S1 OP S2,则称 OP S1 S2 为前缀表示法

5、,S1 S2 OP 为后缀表示法,S1 OP S2 为中缀表示法,例如: Exp = a b + (c 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) 后缀式的运算规则为: 运算符在式中出现的顺序恰为表达式的运算顺序; 每个运算符和在它之前出现 且紧靠它的两个操作数构成

6、一个最小表达式。,先找运算符，再找操作数,例如： a b c d e / f +,ab,d/e,c-d/e,(c-d/e)f,如何从后缀式求值？,ab+(c-d/e)f,如何从原表达式求得后缀式？,每个运算符的运算次序要由它之后的一个运算符来定，在后缀式中,优先数高的运算符领先于优先数低的运算符。,分析 “原表达式” 和 “后缀式”中的运算符: 原表达式: a + b c d / e f 后缀式: a b c + d e / f ,从原表达式求得后缀式的规律为：,1) 设立暂存运算符的栈;,2) 设表达式的结束符为“#”, 予设运算符栈的栈底为“#”,3) 若当前字符是操作数，则直接发送给后缀

7、式;,4) 若当前运算符的优先数高于栈顶运算符，则进栈;,5) 否则，退出栈顶运算符发送给后缀式;,“(” 对它之前后的运算符起隔离作用，“)”可视为自相应左 括弧开始的表达式的结束符。,算法思想 设定两栈：操作符栈 OPTR ，操作数栈 OPND 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 #； 依次读入字符：是操作数则入OPND栈，是操作符则要判断： if 操作符 栈顶元素，压入OPTR栈。,中缀表达式求值算法,表达式求值,中缀表达式 后缀表达式（RPN) a*b+c ab*c+ a+b*c abc*+ a+(b*c+d)/e abc*d+e/+,中

8、缀表达式：操作数栈和运算符栈,例 计算 2+4-3*6,中缀表达式求值举例,表达式求值示意图：5+6(1+2)-4,#,+,(,+,-,5,读入表达式过程：,+,6,(,1,+,2,),-,4,#,=19,1+2=3,63=18,5+18=23,23-4=19,6,1,2,3,18,4,5,23,19,中缀表达式求值演示,后缀表达式求值步骤： 1、读入表达式一个字符 2、若是操作数，压入栈，转4 3、若是运算符，从栈中弹出2个数，将运算结果再压入栈 4、若表达式输入完毕，栈顶即表达式值； 若表达式未输入完，转1,例 计算 4+3*5,后缀表达式：435*+,后缀表达式求值演示,double e

9、valution ( char suffix ) ch = *suffix+; InitStack( S ); while ( ch != “#” ) if ( !OpMember(ch) ) Push(S,ch); else Pop( S, b ); Pop( S, a ); Push( S, Operate( a, ch, b ) ); ch = *suffix+; Pop( S, result ); return result; ,后缀表达式求值程序,void transform( char suffix , char exp ) /将中缀式exp转换为后缀式suffix InitSta

10、ck(S); Push(S, #); p = exp; ch = *p; k=0; while (!StackEmpty(S) if (!OpMember(ch) Suffixk+ = ch; else if ( ch!= # ) ch = *+p; / while suffixk = 0; , ,switch (ch) case ( : Push(S, ch); break; case ) : Pop(S, c); while (c!= ( ) suffixk+ = c; Pop(S, c); break; defult : while( Gettop(S, c) / switch,了解了后

11、缀表达式的计算方法，那么是否借助于该方法来求得中缀表达式的值呢？,递归的定义,例5 实现递归,递归的过程：一个过程直接或间接地调用自己 如：0的阶乘是1，n(n0)的阶乘等于n乘上(n-1)的阶乘,线性表的另一种定义: 若元素个数为0，则称为空表 若元素个数大于0,则有且仅有一个第一个元素(即表头) , 剩余 元素形成一个表(即表尾) 。,递归的对象：一个对象部分地包含它自己，或用它自己给自己定义。 (如某些数据结构的定义),递归的应用 递归定义：如阶乘、Fibonacci数列等 数据结构：如表、树、二叉树等 问题求解：如Hanoi塔,例5 实现递归,将所有的实在参数、返回地址等信息传递给被调

12、用函数保存; 为被调用函数的局部变量分配存储区; 将控制转移到被调用函数的入口。,当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三项任务：,从被调用函数返回调用函数之前,应该完成三项任务：,保存被调函数的计算结果; 释放被调函数的数据区; 依照被调函数保存的返回地址将控制转移到调用函数。,多个函数嵌套调用的规则是:,此时的内存管理实行“栈式管理”,后调用先返回！,例如： void main( ) void a( ) void b( ) a( ); b( ); /main / a / b,main的数据区,函数a的数据区,函数b的数据区,递归工作栈：递归过程执行过程中占

13、用的数据区。 递归工作记录：每一层的递归参数合成一个记录。 当前活动记录：栈顶记录指示当前层的执行情况。 当前环境指针：递归工作栈的栈顶指针。,递归函数执行过程可视为同一函数进行嵌套调用,例如：,栈的应用 - 过程的嵌套调用,递归调用执行情况如下：,void print(int w) int i; if ( w!=0) print(w-1); for(i=1;i=w;+i) printf(“%3d,”,w); printf(“/n”); ,运行结果： 1， 2，2， 3，3，3，,栈与递归的实现,定义是递归的,求解阶乘函数的递归算法 long fact ( long n ) if ( n =

14、0 ) return 1;/递归结束条件 else return n*fact (n-1); /递归的规则 ,我们看一下n=3阶乘函数fact(n)的执行过程,main( ) int n=3,y; L y= fact(n); ,L 3,L1 1,L1 2,1,n*fact (n-1),n*fact (n-1),fact(n),返回地址 实参,注意递归调用中 栈的变化,栈与递归的实现,主程序 main( ): fact(4),直接定值为1,计算 4*fact(3),计算 3*fact(2),计算 2*fact(1),计算 1*fact(0),二、课堂讨论,问题1：如何实现对一个前缀算术表达式进行

15、求值？ 如前缀式: + a b c / d e f,算法思想：建一个操作数栈，从前缀表达式的末端往前取操作数或运算符，若取到的是操作数则入栈，若取到的是运算符则从栈中弹出两个操作数进行计算，并将运算结果入栈，直到整个表达式扫描一遍。,二、课堂讨论,问题2：利用堆栈的基本操作来实现中缀表达式的计算。该中缀表达式中包括：+、-、*、/、（、）和整数。 示例： 输入：10 + (4 20 *) / 4 输出：表达式错误 输入：10 + (20 - 10) / 5 * 2 输出：14,注意的问题： 1、算术表达式的合法性检查； 2、表达式中包含的空格处理； 3、中缀表达式计算中数据超过9时的处理; 4

16、、中缀表达式计算算法。,1、算术表达式的合法性检查,数字字符前合法的字符为： + - * / ( 0 1 2 3 4 5 6 7 8 9 非法的字符为： ) 和 两数字字符之间有空格,运算字符前合法的字符为: ) 0 1 2 3 4 5 6 7 8 9 非法的字符为: ( + - * /,左括号字符前合法的字符为: ( + - * / 非法的字符为: ) 0 1 2 3 4 5 6 7 8 9,右括号字符前合法的字符为: ) 0 1 2 3 4 5 6 7 8 9 非法的字符为: ( + - * /,2、表达式中包含的空格处理,除了两个数字字符之间的空格要处理以外，其他情况空格可以不考虑。,3

17、、中缀表达式计算中数据超过9时的处理,利用循环将一串数字字符变为一个整数,4、中缀表达式计算算法,设定两栈：操作符栈 OPTR ，操作数栈 OPND 栈初始化：设操作数栈 OPND 为空；操作符栈 OPTR 的栈底元素为表达式起始符 #； 依次读入字符：是操作数则入OPND栈，是操作符则要判断： if 操作符 栈顶元素，压入OPTR栈。,三、课堂作业,【作业1】设有一顺序栈S，元素a,b,c,d,e,f依次进栈，如果6个元素出栈的顺序是b,d,c,f,e,a，则栈的容量至少应该是（ ）. A. 2 B. 3 C. 5 D. 6,【作业2】链栈与顺序栈相比较，明显的优点是（ ）. A. 插入操作

18、更加方便 B. 删除操作更加方便 C. 通常不会出现栈满的情况 D。通常不会出现栈空的情况,【作业3】一个栈的输入序列为1,2,3,4,5，则下列序列中不可能是栈的输出序列的是（ ）. A. 2,3,4,1,5 B. 5,4,1,3,2 C. 2,3,1,4,5 D。1,5,4,3,2,三、课堂作业,【作业4】若一个栈以向量V1.n存储，初始栈顶指针top为n+1，则下面x进栈的正确操作是（ ） A. top=top+1; Vtop=x; B. Vtop=x; top=top+1; C. Vtop=x; top=top-1; D. top=top-1; Vtop=x;,【作业5】一般情况下，将

19、递归算法转换成等价的非递归算法应设置（ ）,堆栈,【作业6】中缀表达式A-(B+C/D)*E的后缀形式是（ ）,ABCD/+E*-,【作业7】用S表示入栈操作，P表示出栈操作，若元素入栈的顺序为1,2,3,4，为了得到1,3,4,2出栈顺序，相应的S和P的操作序列为（ ）,SPSSPSPP,三、课堂作业,【作业8】试将下列递归过程改写为非递归过程,void process(int n) if (n 1) printf(n); process(n-1); ,四、课后任务安排,【任务1】: 每人设想一道有关堆栈应用方面的程序设计题。要求必须给出算法思想和标准正确的源程序. 【任务2】: 预习队列的特性及基本操作。,【作业】: 第3章 栈和队列自测试卷,五、课后测评,1、你认为数据结构进行研究型教学改革有无必要? A. 有必要 B. 没必要 C. 无所谓 2、你对本次课的教学方式是否满意？ A. 很满意 B. 基本满意 C。不满意 3、你对本次课的教学内容是否掌握？ A.完全掌握 B. 一般掌握 C. 没掌握 3、你对数据结构研究型教学有何建议？,