栈的典型应用-web服务稳定性测试 负载测试 可靠性测试 测试报告

【文件属性】：

文件名称：栈的典型应用-web服务稳定性测试 负载测试 可靠性测试 测试报告

文件大小：10.35MB

文件格式：PDF

更新时间：2024-07-30 10:59:07

数据结构 邓俊辉 清华大学 mooc学堂在线 教材

§4.3 栈癿典型应用 第4章 栈不队列 9900 §4.3 栈的典型应用 4.3.1 逆序输出 在栈所擅长解决的典型问题中，有一类具有以下共同特征：首先，虽有明确的算法，但其解 答却以线性序列的形式给出；其次，无论是递归还是迭代实现，该序列都是依逆序计算输出的； 最后，输入和输出规模不确定，难以事先确定盛放输出数据的容器大小。因其特有的“后进先出” 特性及其在容量方面的自适应性，使用栈来解决此类问题可谓恰到好处。  进制转换 考查如下问题；任给十进制整数n，将其转换为进制的表示形式。比如 = 8时有 12345(10) = 30071(8) 一般地，设 n = (dm ... d2 d1 d0)() = dm m + ... + d2 2 + d1 1 + d0 0 若记 ni = (dm ... di+1 di)() 则有 di = ni %  和 ni+1 = ni /  这一递推关系对应的计算流程如下。可见，其输出的确为长度不定的逆序线性序列。 图4.4 迕刢转换算法流秳  递归实现 根据如图4.4所示的计算流程，可得到如代码4.2所示递归式算法。 1 void convert(Stack& S, __int64 n, int base) { //十迕刢数n刡base迕刢癿转换（逑弻版） 2 static char digit[] //0 < n, 1 < base <= 16，新迕刢下癿数位符号，可规base叏值范围适弼扩充 3 = { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'A', 'B', 'C', 'D', 'E', 'F' }; 4 if (0 < n) { //在尚有余数乀前，丌断 5 convert(S, n / base, base); //通过逑弻得刡所有更高位 6 S.push(digit[n % base]); //输出低位 7 } 8 } //新迕刢下由高刡低癿各数位，自顶而下保存亍栈S中 代码4.2 迕刢转换算法（递归版） 尽管新进制下的各数位须按由低到高次序逐位算出，但只要引入一个栈并将算得的数位依次 入栈，则在计算结束后只需通过反复的出栈操作即可由高到低地将其顺序输出。  迭代实现 这里的静态数位符号表在全局只需保留一份，但与一般的递归函数一样，该函数在递归调用 栈中的每一帧都仍需记录参数S、n和base。将它们改为全局变量固然可以节省这部分空间，但 依然不能彻底地避免因调用栈操作而导致的空间和时间消耗。为此，不妨考虑改写为如代码4.3 所示的迭代版本，既能充分发挥栈处理此类问题的特长，又可将空间消耗降至O(1)。