当前课程知识点:数据结构 > 第3章 栈和队列 > 3.3 栈的应用 > 3.3 栈的应用
同学们大家好,我是云南大学信息学院教师孔兵
这节课我们讨论栈的应用和递归
上一节我们讲过
因为栈中插入和删除位置受限
这样的受限使栈具有一些特性
最重要的特征就是所谓的后进先出
后插入的先删除
正是因为这样的特性
在一些问题当中
我们可以使用这样的特性来比较有效的解决相关问题
下面,我们看两个例子
第1个例子是数制转换
10进制数和其它进制数的转换
是计算机实现计算的基本问题
解决这个问题的方法很多
其中一个简单的算法是基于下列的原理
就是n等于n整除d,乘以d加上n对d求余
其中n是10进制数,d是我们要转换的进制
比如d是8,表示要转换为8进制
我们看一个例子
10进制数,1348
如果转换为8进制数是2504
基于上述原理
它的转换过程如下
1348整除8,它的商是168
1348对8求余,余数是4
利用商168整除8商是 21
168对8求余,余数是0
用商21继续重复上述的计算
直到商为0,余数为2
我们观察它获得的余数
根据计算的先后次序
获得的次序是4052
从上面面我们看到
1348转换的8进制数是2504
从前向后看
它的次序和求余的计算次序刚好相反
那么,如果我们要编程实现这样的转换
可以在程序中利用一个栈
按照求得余数的次序入栈
例子中入栈的次序是4052
计算完成后再依次出栈
因为栈后进先出的特征
我们获得的出栈序列就是2504
在这个函数当中
利用栈后进先出的特征
解决了数制转换中
计算次序和最终8进制数正常次序相反的问题
第2个例子我们看一下括号匹配的检验
如果表达式中有三种括号,小括号
中括号和大括号
我们希望编写判定表达式中所含括号是否正确配对出现的算法
在这个问题中,也可以利用一个栈
我们忽略表达式中的其它成分
只关注括号序列
假设有例子中的括号系列
下面我们以它为例
来讨论一下
怎么利用战实现括号配对的检验
依次读入括号序列中的括号
遇到左括号,不管他的类型
就把它入栈
在括号序列中
首先遇到的左大括号
左中括号和左小括号,依次入栈
如果遇到的是右括号
则栈顶左括号出栈
进行考察
例子中,第4个读入了右小括号
把栈顶括号出栈
是左小括号
随后考察读入的又括号和出栈的栈顶左括号的匹配情况
可能有两种情况
如果左括号和右括号匹配则进行消解
例子当中,读入是右小括号
出栈的是左小括号
它们是匹配的
则进行消解
随后读入下一个括号
第二种情况是
读入的右括号和出栈的左括号不匹配
比如,读入的是右小括号
出栈的是左大括号或左中括号
这种情况就是括号不匹配
则可以直接判定括号匹配不正确
退出匹配检验函数
上述过程
就是利用栈进行括号匹配检验的主要过程
这个过程可以重复下去
在这样的过程当中
可能出现其它的几种情况
一是,读入右括号后,发现栈为空
这是右括号多了,没有相应的左括号
我们也可以判定括号匹配不正确
二是,括号序列已经读完
右括号都正常消解
但是栈中还有未被消解的左括号
说明左括号多了,没有匹配的右括号
这也可以判定括号匹配不正确
三是,括号序列读完
栈空
所有括号都被消解
这时就可以说括号配对是正确的
这是在应用的第2个例子
好了,今天的内容就到这儿
下节课我们讨论栈与递归的实现
同学们再见
-1.算法概念导入
-2.数据结构课程介绍
-0.1变量、类型和表达式
-0.2 函数
--0.2 函数
-0.3 指针和单链表
-0.4 数组、指向函数的指针
-1.1什么是数据结构
--测试题
-1.2基本概念和术语
--测试题
-1.3数据结构的描述
--测试题
-1.4抽象数据类型的定义和实现
--测试题
-1.5算法和算法分析概念
--测试题
-1.6算法分析示例
--测试题
-2.1 线性表的类型定义
--测试题
-2.2线性表的顺序表示和实现
--测试题
-2.3 线性链表
--2.3 线性链表
--测试题
-2.4 静态链表
--2.4 静态链表
--测试题
-2.5 循环链表和双向链表
--测试题
-3.1 栈
--3.1栈
--测试题
-3.2 栈的实现
--3.2 栈的实现
--测试题
-3.3 栈的应用
--3.3 栈的应用
-3.4 栈与递归的实现
--测试题
-3.5 队列和链队列
--测试题
-3.6 循环队列
--3.6 循环队列
--测试题
-4.1 串
--4.1 串
--测试题
-5.1 数组定义和表示
--测试题
-5.2矩阵的压缩存储
--测试题
-6.1 树的定义和基本术语
-6.2 二叉树和二叉树的性质
--测试题
-6.3 二叉树的存储结构
--测试题
-6.4 遍历二叉树
--测试题
-6.5 线索二叉树
--测试题
-6.6 树的存储
--6.6树的存储
-6.7 树的转换和遍历
--测试题
-6.8 赫夫曼树
--6.8 赫夫曼树
-6.9 赫夫曼编码
--测试题
-7.1 图的定义和术语
--测试题
-7.2 图的存储结构
--测试题
-7.3 图的遍历
--测试题
-7.4 最小生成树
--测试题
-7.5 有向无环图
--测试题
-7.6 最短路径
--测试题
-8.1 查找基本概念和顺序查找
--测试题
-8.2 有序表的查找
--测试题
-8.3 二叉排序树
--测试题
-8.4 平衡二叉树
--测试题
-8.5 哈希表
--测试题
-9.1插入排序
--测试题
-9.2 希尔排序
--9.2 希尔排序
--测试题
-9.3 快速排序
--9.3 快速排序
--测试题
-9.4 选择排序
--9.4 选择排序
--测试题
-9.5 堆排序
--9.5 堆排序
--测试题
-9.6 归并排序
--9.6 归并排序
--测试题
-9.7 基数排序
--9.7 基数排序
--测试题
-9.8 排序方法总结