栈的应用举例

3.3　栈的应用举例

3.3.1　数制的转换问题

【问题描述】　要求编制一个程序实现下述功能:对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数。

【算法思想】　十进制转换为八进制的方法是除8取余。现以（1348）₁₀＝（2504）₈为例进行分析,其转换过程如下。

这一计算过程是从低位到高位依次产生八进制数的各个数位；而打印输出时,应从高位到低位进行,恰好与计算过程相反。因此,可将计算过程中得到的八进制数的各位顺序进栈,则按出栈顺序打印的序列即为与输入十进制数对应的八进制数。具体算法如下。

3.3.2　括号匹配的检测

【问题描述】　假设一个算术表达式中允许含圆括号、方括号和花括号三种类型的括号,其嵌套的顺序随意,但是左右括号必须正确匹配。例如,“[（）]））”是不正确的格式。编写一个判别表达式中括号是否正确配对出现的函数,函数原型为

intcorrect(charexp[])

其中,exp为字符串类型的变量,表示被判别的表达式；函数返回一个整型数据,当exp是括号正确配对的表达式时返回1,反之返回0。

【算法思想】　该问题利用栈能很好地解决。具体算法为:从前向后扫描表达式exp中的每一个字符e,若e为左括号就将e进栈,若e为右括号就弹出栈顶元素,判断它们是否属于同一种括号,若是则继续扫描,否则返回不配对标识。当整个算术表达式扫描完毕时,若栈为空,则表示括号正确配对,否则表示不配对。具体算法如下。

3.3.3　栈与递归

在编程语言中,将直接或间接调用自己的函数称为递归函数。其中,直接调用自己的函数称为直接递归函数,间接调用自己的函数称为间接递归函数。递归（recursion）是程序设计中的一个有力工具,而栈在实现递归调用中起了关键性的作用。

【例3－1】　阶乘函数的递归定义如下:

要求采用递归的方法求解该问题。

【算法思想】　按照这个公式,可将求n！的问题变成求（n－1）！的问题,而求（n－1）！的问题又可以变成求（n－2）！的问题,可将该问题一直分解下去直到n＝1,而1！是可以直接计算出来的,无需再继续分解。当1！计算出来之后可以计算出2！,进而计算3！,…,直到n！。具体程序如下。

一般来说,每一个递归函数的定义都应包括以下两个基本要素。

（1）递归终止的条件,即对无需递归的最小问题的处理方法。

（2）将一般问题简化为一个或多个规模较小的相同性质的问题,递归地调用同样的方法求解这些问题,使这些问题最终到达递归终止。

例3－1中递归终止的条件是n＝0或n＝1,此时n！＝1。当n＞1时,将n！分解成规模较小的子问题n×（n－1）！。如上所述,直到分解到n＝1为止。

一个递归函数的执行过程类似于多个函数的嵌套调用,只是调用函数和被调用函数是同一个函数。与函数递归调用相关的一个重要概念是递归执行的“层次”。假设将调用该递归函数的主函数所处的层次定义为0层,则从主函数调用递归函数为进入第1层,从第1层递归调用本函数为进入第2层,依此类推,直至从第i层递归调用本函数为进入第i＋1层。反之,在退出第i层递归时,应返回到上一层,即第i－1层。为保证递归的正确执行,系统也如同处理函数嵌套调用那样,在系统工作栈中为递归函数开辟数据存储区。每一层递归所需的信息构成了一个工作记录,该工作记录记录了所有的实际参数和局部变量,以及返回到上一层的地址。每进入一层递归,就产生一个新的工作记录“进栈”,每退出一层递归,就从栈顶“退出”一个工作记录。这项工作一直进行到栈空为止,此时整个程序运行结束。