第03章 第03章 栈

1. 内容介绍

本章详细介绍了栈的定义、顺序栈，和递归

2. 理论目标

• 掌握栈的定义
• 掌握顺序栈
• 掌握递归

3. 实践目标

• 顺序表的底层代码实现，栈的常见应用，以及递归的代码实现

4. 实践案例

无

5. 内容目录

• 1.栈的定义
• 2.顺序栈
• 3.递归

第1节 栈的定义

1.1 为什么使用栈

栈的内涵

1.2栈的定义

定义:栈是只允许在表尾插入、删除的线性表

进栈出栈的变化形式

问题：按照数字1,2,3依次顺序进栈，那么出栈时是否会出现312的变化形式？

答案：不会
因为3只有先进栈，才能出栈。如果3已经进栈，则1和2也必然进栈，
2比1更靠近栈顶，所以先于1出栈

栈的抽象数据类型

什么是抽象数据类型？

抽象数据类型是指一个数学模型及定义在该模型上的一组操作的总称

第2节 顺序栈

2.1 顺序栈的概念

栈包含空栈和非空栈；在顺序栈中，非空栈包含普通栈和满栈

顺序栈的结构定义

进栈的实现

2.2 顺序栈的代码实现

案例效果图

案例要求
创建栈
实现push函数
显示当前栈中元素个数

  

案例效果图

案例要求
实现出栈
显示当前栈中元素个数

      

思路分析：

进制转换
将十进制数除2，将余数存入栈、将商作为下次运算的被除数，直到0为止
菜单
使用switch结构实现菜单

2.3 栈的总结

第3节 递归

3.1 递归的概念

递归和递归函数的关系？

递归是一种算法，算法是一种思想，需要通过载体具体实现。

递归函数就是用来实现递归算法的载体

定义:递归函数是不断调用自身，当满足条件后结束调用的自定义函数

递归函数的执行过程

递归函数与栈的关系

1、递归调用时，会将函数的局部变量、参数值以及返回地址都被压入栈中。

2、在返回结果时，位于栈顶的局部变量、参数值和返回地址被弹出栈，以便恢复使用

在高级语言中，递归函数调用过程由系统自动管理！！！

3.2 递归的应用

案例需求
输入一个非负数的整数，实现计算该整数的阶乘，并显示结果

思路分析
n的阶乘表示从1一直乘到n
n!=123*…(n-1)n
当n的变化不等于1，逐级调用n(n-1)
当n最终等于1时，结束并逐级返回结果

  

斐波那契数列

斐波那契数列的实现

计算15年后树的枝桠数是多少？

思路分析
与斐波那契数列规律一致
从第三年开始，后一年的枝桠数等于前两年的枝桠数之和
计算数列中第15个数字的值
函数结束调用条件
n1或者n2

案例需求

兔子三个月成熟，成熟每月繁殖一对兔子，以此类推，计算10个月后总共有几对兔子

思路分析
第10个月表示在斐波那契数列中第10个位置的数字
第1位和第2位数字都是1，作为结束递归调用的条件
从第3个数开始，后一个数是前两个数的和
公式：F(n)=F(n-1)+F(n-2)

案例需求
编码实现计算数字n的k次幂
能够接收输入
显示计算结果

思路分析
n的k次幂就是计算n的k次方
推导公式：nk=n*(n(k-1))
函数的结束条件
如果k=0，返回1
函数的参数
N：表示数字
K：表示幂的次数

案例需求
编码实现计算数字n的k次幂，例如计算4的11次幂，显示最终计算结果

代码演示

总结

案例需求
编码实现对表达式中括号进行匹配检查

括号的分类

思路分析
对表达式进行扫描
大、中、小任意一种左括号时，压栈
任意一种右括号时，出栈
与出栈元素进行比较，配对成功则继续扫描表达式
配对不成功，停止扫描，返回错误信息

表达式检查完毕后
栈为空，表明括号都配对成功
栈不为空，则表明栈中有未配对的括号

综合应用

案例需求
模仿示例，完成表达式的括号检查

第4节 附录