|
栈和队列的应用非常之广只要问题满足后进先出和先进先出原则均可使用栈和队列作为其数据结构 栈的应用 数制转换 将一个非负的十进制整数N转换为另一个等价的基为B的B进制数的问题很容易通过除B取余法来解决 【例】将十进制数转化为二进制数 解答按除取余法得到的余数依次是则十进制数转化为二进制数为 分析由于最先得到的余数是转化结果的最低位最后得到的余数是转化结果的最高位因此很容易用栈来解决 转换算法如下 typedef int DataType;//应将顺序栈的DataType定义改为整型 void MultiBaseOutput (int Nint B) {//假设N是非负的十进制整数输出等值的B进制数 int i; SeqStack S; InitStack(&S); while(N){ //从右向左产生B进制的各位数字并将其进栈 push(&SN%B); //将bi进栈<=i<=j N=N/B; } while(!StackEmpty(&S)){ //栈非空时退栈输出 i=Pop(&S); printf(%di); } } 除数制的转换外栈还可用于解决括号匹配检查行编辑处理和表达式求解等问题具体【参见参考书目】 栈与递归 （） 递归 所谓递归是指若在一个函数过程或者数据结构定义的内部直接（或间接）出现定义本身的应用则称它们是递归的或者是递归定义的 递归是一种强有力的数学工具它可使问题的描述和求解变得简洁和清晰 递归算法常常比非递归算法更易设计尤其是当问题本身或所涉及的数据结构是递归定义的时候使用递归算法特别合适 （）递归算法的设计步骤 第一步骤（递归步骤）将规模较大的原问题分解为一个或多个规模更小但具有类似于原问题特性的子问题即较大的问题递归地用较小的子问题来描述解原问题的方法同样可用来解这些子问题 第二步骤确定一个或多个无须分解可直接求解的最小子问题（称为递归的终止条件） 【例】非负整数n的阶乘可递归定义为 （）栈在递归算法的内部实现中所起的作用 ①调用函数时系统将会为调用者构造一个由参数表和返回地址组成的活动记录并将其压入到由系统提供的运行时刻栈的栈顶然后将程序的控制权转移到被调函数若被调函数有局部变量则在运行时刻栈的栈顶也要为其分配相应的空间因此活动记录和这些局部变量形成了一个可供被调函数使用的活动结构 注意 参数表的内容为实参返回地址是函数调用语句的下一指令的位置 ②被调函数执行完毕时系统将运行时刻栈栈顶的活动结构退栈并根据退栈的活动结构中所保存的返回地址将程序的控制权转移给调用者继续执行 【例】Factorial（）递归函数执行期间运行时刻栈的变化（不考虑局部变量temp的入出栈情况）【参见动画演示】 |
