黑42栈的应用举例 章线和队列 计算机教研宦 第6页 2021/2/19
Data Structure 数据结构—— 第4章栈和队列 胡建华 2021/2/19 计算机教研室 第 6 页 4.2 栈的应用举例
@例41数制转换 ·十进制数N和其他d进制数的转换是计算机实现计算的 基本问题,其解决方法很多,其中一个简单算法基于 下列原理: N=( n diy d)×d+ n mod d (其中:div为整除运算,mod为求余运算) 例如:(1348)10=(2504)8,其运算过程如下: n div 8 n mod 8 1348 168 168 21 章线和队列 21 2 4052 计算机教研宦 第7页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第7页 例4.1 数制转换 • 十进制数N和其他d进制数的转换是计算机实现计算的 基本问题，其解决方法很多，其中一个简单算法基于 下列原理： N = (N div d)×d + N mod d (其中：div 为整除运算，mod 为求余运算） 例如：（1348)10 = (2504)8 ，其运算过程如下： N N div 8 N mod 8 1348 168 4 168 21 0 21 2 5 2 0 2
@算法4.1数制转换问题 void conversion(( ∥对于输入的任意一个非负十进制整数,打印输出与其等值的八进制数 nitstack(S);∥构造空栈 cin>>N; while(Ni Push(s,N%8);∥余数”入栈 N=N/8;∥“商”继续运算 3/while Whle( StackEmpty){∥和“求余”所得相逆的顺序输出八进制 章线和队列 的各位数 Pop(s, e) cout<<e: while 第8页
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第8页 算法 4.1 数制转换问题 void conversion () { // 对于输入的任意一个非负十进制整数，打印输出与其等值的八进制数 InitStack(S); // 构造空栈 cin>>N; while (N) { Push(S, N % 8); // “余数”入栈 N = N/8; // “商”继续运算 }//while while (!StackEmpty) { // 和“求余”所得相逆的顺序输出八进制 的各位数 Pop(S,e); cout< <e； }//while } // conversion
@例42括号匹配的检验 假设表达式中允许包含两种括号:圆括号和方括号 其嵌套的顺序随意,即([]()或[( 等为正确的格式,[(])或([())或()])均为 不正确的格式。检验括号是否匹配的方法可用″期待 的急迫程度”这个概念来描述。例如考虑下列括号序 列: [([][])] 12345678 分析可能出现的不匹配的情况: 意1.到来的右括弧非是所“期待”的; 2.到来的是“不速之客 双3.直到结束,也没有到来所“期待”的。 计算机教研宦 第9页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第9页 例4.2 括号匹配的检验 • 假设表达式中允许包含两种括号：圆括号和方括号， 其嵌套的顺序随意，即([ ］( ))或［(［ ］［ ］)］ 等为正确的格式，［( ］)或(［( ) )或 (( )])均为 不正确的格式。检验括号是否匹配的方法可用"期待 的急迫程度"这个概念来描述。例如考虑下列括号序 列： [ ( [ ] [ ] ) ] 1 2 3 4 5 6 7 8 • 分析可能出现的不匹配的情况: 1. 到来的右括弧非是所“期待”的; 2. 到来的是“不速之客”; 3. 直到结束，也没有到来所“期待”的
@栈和递归函数的关系 递归:函数直接或间接的调用自身叫 实现:建立递归工作栈 ·例递归的执行情况分析 void print(int w) i int i if(w!=0) print(w-1) for(i=l; K<=w; ++i) printf( o3d,, w); 章线和队列 printf(/n” 计算机教研宦 第10页 2021/2/19
Data Structure 数 据 结 构—— 第 4 章 栈 和 队 列 胡建华 2021/2/19 计算机教研室 第10页 栈和递归函数的关系 • 递归：函数直接或间接的调用自身叫~ • 实现：建立递归工作栈 • 例 递归的执行情况分析 void print(int w) { int i; if ( w!=0) { print(w-1); for(i=1;i<=w;++i) printf(“%3d,”,w); printf(“/n”); } }