第三章 栈应用(递归)

0
1
2
3
4
5
6
7
a1
a2
a3
a4
a5
a6
a7
队头 F＝0
队尾 R＝7
a3 2 1 3 0 4 7 a3 5 6 3 a2 2 1 a1 0 F=0 a4 4 a5 5 6 a6 7 a7 R=0 R=7 3 a2 2 1 a1 0
a4 4 a5 5 6 a6 7
a8
F=0
a7
R=0
F=0
删除所有元素
top X W … B top
top=0 空栈
top
W
…
B A
top=m-1 元素X出栈
top
A
A
top=m 满栈
top=1 元素A入栈
例：堆栈的插入、删除操作。 出栈操作程序如下： # define m 1000; /*最大栈空间*/ 出栈操作算法： 1）栈顶指针top是否为0： typedef struct stack_stru 若是，则返回；若不是， { int s[m]; int top; }; 则执行2。 void pop (stack, y) 2）将栈顶元素送给y， struct stack_stru stack; 栈顶指针减1。 int *y; { if (stack.top = = 0) printf (“The stack is empty ! \n”); top Y Y else { top B B *y=stack.s[stack.top]; A A stack.top - -; } 出栈操作 }
top=p;
} 栈的入栈、出栈操作的时间复杂度都为O(1)。
栈的应用
一、 表达式求值 表达式由操作数、运算符和界限符组成。 运算符可包括算术运算符、关系运算符、逻辑运算符。

实用数据结构基础
第3章 栈
第 3 章 栈
知
识点
栈的定义和特点 栈的基本运算和算法 栈的典型应用
难
点
后缀表达式的算法 数制的换算 利用本章的基本知识设计相关的应用问题
要
求
掌握栈的特点 掌握栈的基本运算 熟悉栈的各种实际应用 能设计栈应用的典型算法 了解栈的运算时间复杂度分析
第3章 目录

2．顺序栈运算的基本算法 （1）置空栈 首先建立栈空间，然后初始化栈顶指针。 SeqStack *Snull( ) { SeqStack *s； s=new (SeqStack)；
// 在C语言中用s=malloc（sizeof（SeqStack）） ；
s->top= –1； return s； }
3-1 栈的定义与运算 3-2 栈的存储和实现 3-3 栈的应用举例 小 结 验证性实验3: 栈子系统 自主设计实验3：后缀表达式求值 单元练习3
3-1 栈的定义和运算
3-1-1 栈（Stack）的定义
1. 栈的定义 栈是限制在表尾进行插入和删除的线性表。 进栈 出栈
an …… a3 a2 a1
图3-1栈的 示意图
3-3.
3-3-1 数制转换
栈的应用举例
数值进位制的换算是计算机实现计算和处理的 基本问题。比如将十进制数N转换为j进制的数，其 解决的方法很多，其中一个常用的算法是除j取余法。 将十进制数每次除以j，所得的余数依次入栈，然后 按“后进先出”的次序出栈便得到转换的结果。 其算法原理是： N =（N / j）* j + N % j
由于栈的操作只能在栈顶进行的，所以用链表的头部做
栈顶是最合适的。链栈结构如图3-4所示。

栈在递归中的作用栈是一种具有特殊性质的线性数据结构，在其中元素的插入和删除操作只能在栈的顶部进行。

栈的特点是元素按照后进先出的顺序进行处理，即最后插入到栈中的元素最先被访问到。

递归是一种程序设计技巧，通过一个函数在其定义中调用自身来解决问题。

递归函数在解决问题时以一种分而治之的办法，将原始问题划分为较小的子问题，并通过解决子问题来解决原始问题。

那么，栈在递归中起到了什么作用呢？一、存储临时变量：递归函数在每一次调用自身时都会入栈，该栈用来保存每个递归调用时的临时变量。

在递归函数内部定义的变量会保存在栈中，每次函数调用时，这些局部变量都会被压入栈中。

当函数的递归调用完成后，栈中保存的该函数的局部变量会被弹出，以便为下一个递归调用或其他操作提供内存空间。

这样，栈起到了一个保存临时变量的作用。

二、存储函数调用的返回地址：在递归调用时，每次调用后都需要返回到上一层调用处。

栈的另一个作用是存储函数调用的返回地址。

当一个函数调用了自身，并进行了递归调用时，当前函数的上下文信息（包括函数指针、参数和局部变量等）都会被保存在栈中，然后在递归调用完成后，栈中保存的上下文信息将被弹出，返回到上一层函数的下一条执行指令的位置，继续执行下去。

三、维护递归层次关系：递归调用时，每次调用自身都需要将当前的状态保存在栈中，这样可以保留每一次递归调用的上下文信息。

栈的深度也反映了递归的层次关系。

当递归调用层数很大时，栈的深度也会相应增加。

四、确保函数调用的正确性：栈在递归中还发挥了确保函数调用的正确性的作用。

每一次递归调用都会将当前的状态保存在栈中，包括参数、局部变量、返回地址等信息。

这样，即使在递归调用过程中发生了其他函数的调用，当递归调用完成后，栈中保存的状态信息都能够正确恢复，确保程序的正确执行。

总结来说，栈在递归中起到了存储临时变量、存储函数调用的返回地址、维护递归层次关系以及确保函数调用的正确性等作用。

栈的使用使递归函数能够按照正确的顺序进行递归调用，并在递归调用完成后正确返回上一层函数的下一条执行指令的位置。

（二）过程与方法
在学习“3.3.2栈的应用”过程中，学生将通过以下方法和过程来达成学习目标：
1.探究学习：通过小组讨论、自主探究，发现并理解栈的特性及其在解决实际问题中的应用。
-教师组织课堂活动，引导学生主动探索，培养其发现问题和解决问题的能力。
2.案例分析：分析栈在解决实际问题中的典型应用，提炼出算法设计的通用方法和步骤。
（二）讲授新知
在讲授新知环节，教师按照以下步骤进行：
1.理论讲解：详细讲解பைடு நூலகம்的基本概念、特性以及在实际问题中的应用场景，如括号匹配、路径问题等。
2.算法分析：通过分析表达式求值、括号匹配等案例，讲解栈在算法设计中的关键作用，引导学生理解算法的步骤和原理。
3.代码演示：以编程语言为例，现场演示栈的实现及在表达式求值中的应用，让学生了解栈的具体操作过程。
在总结归纳环节，教师引导学生进行以下总结：
1.栈的基本概念和特性：回顾栈的定义、特点以及在实际问题中的应用。
2.栈的算法设计：总结栈在解决实际问题中的关键步骤和方法。
3.编程实践：强调编程实践中的注意事项，如代码规范、调试技巧等。
4.团队协作：强调团队协作在解决问题中的重要性，鼓励学生在今后的学习中积极参与合作。
-此作业旨在激发学生的探究兴趣，培养其创新思维和解决实际问题的能力。
4.小组合作项目：以小组为单位，共同完成一个基于栈的应用项目。项目主题自选，可以是游戏、工具软件或任何能够体现栈特性的应用。
-通过小组合作，学生可以锻炼团队协作能力，同时在实际项目中进一步掌握栈的使用。
5.课后反思：请学生结合课堂学习和作业完成情况，撰写一份课后反思，内容包括自己在学习栈的过程中遇到的困难、解决问题的方法、对栈的理解和感受，以及对未来学习的规划。