栈的应用举例

栈的应用举例第一页，共二十五页，编辑于2023年，星期六￡3.2.1数制转换￡3.2栈的应用举例十进制数N和其他d进制数的转换是计算机实现计算的基本问题，其解决方法很多，其中一个简单算法基于下列原理：

N=(Ndivd)×d+Nmodd（其中：div为整除运算，mod为求余运算） 例如：(1348)10＝(2504)8，其运算过程如下：

N Ndiv8 Nmod8 1348168416821 0212 520 2由于上述计算过程是从低位到高位顺序产生八进制数的各个数位，而打印输出，一般来说应从高位到低位进行，恰好和计算过程相反。因此，若计算过程中得到八进制数的各位顺序进栈，则按出栈序列打印输出的即为与输入对应的八进制数。

第二页，共二十五页，编辑于2023年，星期六 算法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第三页，共二十五页，编辑于2023年，星期六￡3.2.2括号匹配检验假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即([]())或[([][])]等为正确的格式，[(])或[())或(()])均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如：

[([][])] 12345678当计算机接受了第一个括号后,它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号“[”只能暂时靠边，而迫切等待与第二个括号相匹配的、第七个括号”)”的出现,类似的,因等来的是第三个括号“[”，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，……，依次类推。可见，这个处理过程恰与栈的特点相吻合。由此，在算法中设置一个栈，每读入一个括号，若是右括号，则或者使置于栈顶的最急迫的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更急迫的期待压入栈中，自然使原有的栈中的所有未消解的期待的急迫性都降了一级。另外，在算法的开始和结束时，栈都应该是空的。第四页，共二十五页，编辑于2023年，星期六算法的设计思想：1）凡出现左括弧，则进栈；2）凡出现右括弧，首先检查栈是否空若栈空，则表明该“右括弧”多余否则和栈顶元素比较，若相匹配，则“左括弧出栈”否则表明不匹配3）表达式检验结束时，若栈空，则表明表达式中匹配正确否则表明“左括弧”有余第五页，共二十五页，编辑于2023年，星期六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;…...第六页，共二十五页，编辑于2023年，星期六￡3.2.3行编辑程序功能：接受用户从终端输入的程序或数据，并存入用户的数据区。退格符“#”：表示前一个字符无效。退行符“@”：表示当前行中的字符均无效。例如：

whli##ilr#e(s#*s) outcha@putchar(*s=#++);

等效为：

while(*s) putchar(*s++);为了提高程序的效率，我们设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区。在此，将这个输入缓冲区设为一个栈结构，每当从终端接受了一个字符之后先作如下判断：①如果它既不是退格符也不是退行符，则将该字符压入栈顶；②如果是一个退格符，则从栈顶删去一个字符；③如果它是一个退行符，则将字符栈清为空栈。第七页，共二十五页，编辑于2023年，星期六voidLineEdit{//利用字符栈S，从终端接收一行并传送至调用过程的数据区。

InitStack(S); //构造空栈S ch=getchar(); //从终端接收第一个字符

while(ch!=EOF){ //EOF为全文结束符

while(ch!=EOF&&ch!=‘\n’){ switch(ch){ case‘#’:Pop(S,c); break; //仅当栈非空时退栈

case’@’:ClearStack(S); break; //重置S为空栈

default:Push(S,ch); break; //有效字符进栈，

//未考虑栈满情况

} ch=getchar(); //从终端接收下一个字符

}

将从栈底到栈顶的栈内字符传送至调用过程的数据区；

ClearStack(S); //重置S为空栈

if(ch!=EOF) ch=getchar(); } DestroyStack(S); }//LineEdit算法3.2如下：第八页，共二十五页，编辑于2023年，星期六￡3.2.4迷宫求解

入口图3.4迷宫0123456789出口空白方块：表示通道。带阴影线的方块：表示墙。当前位置：指在搜索过程中某一时刻所在图中某个方块位置。下一位置：指“当前位置”四周4个方向（东、南、西、北）上相邻的方块。

当前位置可通：指未曾走到过的通道块。即要求该方块位置不仅是通道块，而且既不在当前路径上，也不是曾经纳入过路径的通道块。第九页，共二十五页，编辑于2023年，星期六求迷宫中一条从入口到出口的路径的算法可简单描述如下：

设定当前位置的初值为入口位置；

do{

若当前位置可通， 则{ 将当前位置插入栈顶； //纳入路径 若该位置是出口位置，则结束； //求得路径存放在栈中 否则切换当前位置的相邻方块为新的当前位置；

}

否则， 若栈不空且栈顶位置尚有其他方向未经探索， 则设定新的当前位置为沿顺时针方向旋转找到的栈顶位置的下一相邻块； 若栈不空但栈顶位置的四周均不可通， 则{ 删去栈顶位置； //从路径中删去该通道块 若栈不空，则重新测试新的栈顶位置， 直至找到一个可通的相邻块或出栈至栈空；

} }while(栈不空)；第十页，共二十五页，编辑于2023年，星期六

typedefstruct{ int ord; //通道块在路径上的“序号”

PosType seat; //通道块在迷宫中的“坐标位置”

int di; //从此通道块走向下一通道块的“方向”

}SElemType； //栈的元素类型

StatusMazePath(MazeTypemaze,PosTypestart,PosTypeend){ //若迷宫maze中存在从入口start到出口end的通道，则求得一条存放在栈中

//（从栈底到栈顶），并返回TRUE，否则返回FALSE InitStack(S); curpos=start; //设定“当前位置”为“入口地址”

curstep=1; //探索第一步

do{ if(Pass(curpos)){ //当前位置可以通过，即是未曾走到过的通道块

FootPrint(curpos); //留下足迹

e=(curstep,curpos,1); Push(S,e); //加入路径

if(curpos==end) return(TRUE); //到达终点（出口）

curpos=NextPos(curpos,1); //下一位置是当前位置的东阾

curstep++; //探索下一步

}//if算法3.3如下：第十一页，共二十五页，编辑于2023年，星期六

else{ //当前位置不能通过

if(!StackEmpty(S)){ Pop(S,e); while(e.di==4&&!StackEmpty(S)){ MarkPrint(e.seat); //留下不能通过的标记，并退回一步

Pop(S,e); }//while if(e.di<4){ e.di++; //换下一个方向探索

Push(S,e); curpos=NextPos(e.seat,e.di); //设定当前位置是该新方向上的相邻块

}//if }//if }//else }while(!StackEmpty(S)); return(FALSE); }//MazePath第十二页，共二十五页，编辑于2023年，星期六表达式求值要对算术表达式求值：4+2*3-10/5任何一个表达式都是由操作数、运算符和界限符组成的。第十三页，共二十五页，编辑于2023年，星期六实现运算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存操作数或运算结果。算法的基本思想是：（1）首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符，则和OPTR栈的栈顶运算符比较优先权后作相应操作，直到整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为“#”）第十四页，共二十五页，编辑于2023年，星期六￡3.2.5表达式求值算法3.4如下：

OperandTypeEvaluateExpression(){ //算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和

//运算数栈，OP为运算符集合。

InitStack(OPTR); Push(OPTR,‘#’); InitStack(OPND); c=getchar(); while(c!=‘#’||GetTop(OPTR)!=‘#’){ if(!In(c,OP)){ //不是运算符则进栈

Push(OPND,c); c=getchar(); }elseswitch(Precede(GetTop(OPTR),c)){ //Precede是判定运算符栈的栈顶运算符与读入

//的运算符之间优先关系的函数。第十五页，共二十五页，编辑于2023年，星期六

case‘<’: //栈顶元素优先权低

Push(OPTR,c); c=getchar(); break; case‘=’: //脱括号并接收下一字符

Pop(OPTR,x); c=getchar(); break; case‘>’: //退栈并将运算结果入栈

Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b)); //Operate为进行二元运算aθb的函数。

break; }//switch}//whilereturnGetTop(OPND);}//EvaluateExpression第十六页，共二十五页，编辑于2023年，星期六例如：利用上述算法对表达式3*(7－2)求值的操作过程如下所示：步骤 OPTR栈 OPND栈 输入字符主要操作

1 # 3*(7-2)# Push(OPND,‘3’)2 # 3 *(7-2)# Push(OPTR,‘*’)3 #* 3 (7-2)# Push(OPTR,‘(’)4 #*( 3 7-2)# Push(OPND,‘7’)5 #*( 37 -2)# Push(OPTR,‘-’)6 #*(- 37 2)# Push(OPND,‘2’)7 #*(- 372 )# operate(‘7’,‘-’,‘2’)8 #*( 35 )# Pop(OPTR){消去一对括号}9 #* 35 #operate(‘3’,‘*’,‘5’)10 # 15 #

return(GetTop(OPND))第十七页，共二十五页，编辑于2023年，星期六一个直接调用自己或通过一系列的调用语句间接地调用自己的函数，称做递归函数。递归是程序设计中一个强有力的工具。其一，有很多数学函数是递归定义的；其二，有的数据结构，如二叉树等，由于结构本身固有的递归特性，则它们的操作可递归地描述；其三，如Hanoi塔问题等。3.3栈与递归的实现第十八页，共二十五页，编辑于2023年，星期六当在一个函数的运行期间调用另一个函数时，在运行该被调用函数之前，

需先完成三项任务：将所有的实在参数、返回地址等信息传递给被调用函数保存;为被调用函数的局部变量分配存储区;将控制转移到被调用函数的入口。第十九页，共二十五页，编辑于2023年，星期六从被调用函数返回调用函数之前，应该完成下列三项任务：保存被调函数的计算结果;释放被调函数的数据区;依照被调函数保存的返回地址将控制转移到调用函数。第二十页，共二十五页，编辑于2023年，星期六多个函数嵌套调用时，按照“后调用先返回”的原则进行。intmain(){intm,n;...first(m,n);1:…}intfirst(ints,intt){int i;…second(i);2:…}intsecond(intd){int x,y;3:…}此时的内存管理实行“栈式管理”第二十一页，共二十五页，编辑于2023年，星期六intmain(){ intm,n; ... { int i; … { intx,y; 3:… } 2:… } 1: