大学《数据结构》第三章：栈和队列-第二节-栈的应用举例

第二节栈的应用举例一、圆括号匹配的检验对于输入的一个算术表达式字符串，试写一算法判断其中圆括号是否匹配，若匹配则返回TRUE，否则返回FALSE。【分析】利用栈的操作来实现：循环读入表达式中的字符，如遇左括号"("就进栈；遇右括号")"则判断栈是否为空，若为空，则返回FALSE，否则退栈；循环结束后再判断栈是否为空，若栈空则说明括号匹配，否则说明不匹配。【算法描述】intExpr(){SeqStackS；DataTypech，x；InitStack(&S);//初始化栈Sch=getchar();while(ch!='\n'){if(ch=='(')Push(&S，ch)；//遇左括号进栈elseif(ch==')')if(StackEmpty(&S))//遇右括号如果栈空，说明不匹配，返回0return0;elsex=Pop(&s)；//遇右括号退栈ch=getchar();//读入下一个字符}//endofwhileif(StackEmpty(&S))return1;//最后栈空，说明匹配，返回1elsereturn0；}二、字符串回文的判断利用顺序栈的基本运算，试设计一个算法，判断一个输入字符串是否具有中心对称(也就是所谓的"回文"，即正读和反读均相同的字符序列)，例如ababbaba和abcba都是中心对称的字符串。【分析】从中间向两头进行比较，若完全相同，则该字符串是中心对称，否则不是。这就要首先求出字符串串的长度，然后将前一半字符入栈，再利用退栈操作将其与后一半字符进行比较。【算法描述】intsymmetry(charstr[]){SeqStackS；intj，k，i=0；InitStack(&S)；while(Str[i]!='\0')i++;//求串长度for(j=0；j<i/2；j++)Push(&s，str[j])；//前一半字符入栈k=(i+1)／2;//后一半字符在串中的起始位置//特别注意这条命令怎么处理奇偶数个字符的。for(j=k；j<i；j++)//后一半字符与栈中字符比较if(str[j]!=Pop(&s))return0；//有不相同字符，即不对称return1；//完全相同，即对称}三、数制转换将一个非负的十进制整数N转换成d进制【分析】将一个非负的十进制整数N转换成d进制的方法：N除以d，求出每一步所得的余数，然后将所有余数逆序书写就是十进制整数N对应的d进制数。例如（3553）10=（6741）8，其运算过程如下：【算法描述】voidconversion(intN，intd){//将一个非负的十进制数N转换成任意的d进制数SeqStackS；InitStack(&S)while(N){Push(&S，N％d)；//N除以d的余数入栈N=N／d；//N除以d的商}while(!StackEmpty(&S)){i=Pop(&S)；printf("％d"，i)；//出栈完成余数倒序输出}}四、栈与递归栈还有一个非常重要的应用就是在程序设计语言中实现递归。一个直接调用自己或间接调用自己的函数，称为递归函数。递归是程序设计中一个强有力的工具，递归算法有两个关键条件：一是有一个递归公式；二是有终止条件。例如：求n的阶乘可递归地定义为2阶的Fibinocci数列：【例】试分析求阶乘的递归函数。【算法描述】longintfact(intn){inttemp;if(n==0)return1;//递归终止条件elsetemp=n*fact(n-1);//递归公式r12：returntemp;}voidmain()//主函数{longintn;n=fact(5);//调用fact()函数求5！r11：printf("5!=％ld"，n)；}【算法分析】调用层次调用参数n返回地址temp结果退栈时计算结果↑5fact(0)0r121

↓↑4fact(1)1r121*fact(0)1*1=1↓↑3fact(2)2r122*fact(1)2*1=2↓↑2fact(3)3r123*fact(2)3*2=6↓↑1fact(4)4r124*fact(3)4*6=24↓↑0fact(5)5r115*fact(4)5*24=120返回进栈

主函数打印5！=120

退栈当前讲授【例】已知函数，试写一个递归算法，实现其功能。【算法描述】floatfu(intn){if(n<2)return(n+1)；//递归终止条件elsereturnfu(n/2)*fu(n/4);//递归公式}或者为floatfu(intn){floatf1，f2jif(n<2)return(n+