栈的应用举例.ppt

《栈的应用举例.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、3.1栈3.2栈的应用举例3.3栈与递归的实现3.4队列第三章栈和队列￡3.2.1数制转换￡3.2栈的应用举例十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：N=(Ndivd)×d+Nmodd（其中：div为整除运算，mod为求余运算）例如：(1348)10＝(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若计算过程

2、中得到八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。算法3.1如下：voidconversion(){//对于输入的任意一个非负十进制整数，//打印输出与其等值的八进制数。InitStack(S);//构造空栈scanf(“%d”,N);while(N){Push(S,N%8);N=N/8;}while(!StackEmpty(s)){Pop(S,e);printf(“%d”,e);}}//conversion￡3.2.2括号匹配检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即([]())或[

3、([][])]等为正确的格式，[(])或[())或(()])均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如：[([][])]12345678当计算机接受了第一个括号后,它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号“[”只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号”)”的出现,类似的,因等来的是第三个括号“[”，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号之后，第三个括号

4、的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，……，依次类推。可见，这个处理过程恰与栈的特点相吻合。由此，在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的栈中的所有未消解的期待的急迫性都降了一级。另外，在算法的开始和结束时，栈都应该是空的。算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明

5、不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余Statusmatching(string&exp){intstate=1;while(i<=Length(exp)&&state){switchofexp[i]{case“(”:{Push(S,exp[i]);i++;break;}case”)”:{if(NOTStackEmpty(S)&&GetTop(S)=“(“{Pop(S,e);i++;}else{state=0;}break;}……}if(StackEmpty(S)&&state)returnOK;…

6、...￡3.2.3行编辑程序功能：接受用户从终端输入的程序或数据，并存入用户的数据区。退格符“#”：表示前一个字符无效。退行符“@”：表示当前行中的字符均无效。例如：whli##ilr#e(s#*s)outcha@putchar(*s=#++);等效为：while(*s)putchar(*s++);为了提高程序的效率，我们设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。在此，将这个输入缓冲区设为一个栈结构，每当从终端接受了一个字符之后先作如下判断：①如果它既不是退格符也不是退行符，则将该字符压入栈顶；②如果是一个退格

7、符，则从栈顶删去一个字符；③如果它是一个退行符，则将字符栈清为空栈。voidLineEdit{//利用字符栈S，从终端接收一行并传送至调用过程的数据区。InitStack(S);//构造空栈Sch=getchar();//从终端接收第一个字符while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!=‘’){switch(ch){case‘#’:Pop(S,c);break;//仅当栈非空时退栈case’@’:ClearStack(S);break;//重置S为空栈default:Push(S,ch);br

8、eak;//有效字符进栈，//未考虑栈满情况}ch=getchar();//从终端接收下一个字符}将从栈底到栈顶的栈内字符传送至调用过程的数据区；ClearStack(S);//