数据结构栈的应用本

第三章栈的应用数制转换“除基取余法”算法基于原理除以基数取余数，逆序排列。例如：（1348)10=(2504)8，其运算过程如下：NNdiv8Nmod8134816841682102125202计算顺序输出顺序进制转换算法思想1.初始化一个空栈S；2.当十进制数N非零时，循环执行以下操作：把N与8求余得到的八进制数压入栈S；N更新为N与8的商。3.当栈S非空时，循环执行以下操作：弹出栈顶元素e，然后输出e。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余数入栈余数出栈括号匹配括号匹配问题1.括号匹配{[()]},((){}),()2.括号不匹配[(]),([()),(()])检验括号匹配的方法：“期待的急迫程度”检查括号匹配算法的设计思想设一栈；遇到左括号则入栈；遇到右括号时，若栈空，则不匹配(右括号太多)，否则，如果栈顶元素与该右括号匹配，则出栈，否则不匹配(括号不配对)。输入结束后，若栈为空，则匹配，否则不匹配(左括号太多)。StatusMatching(){intstate=1;InitStack(S);ch=getchar();while(ch!=‘#’&&state){switch(ch){case‘(‘||’[’:{Push(S,ch);break;}case‘)’:{if(!StackEmpty(S)&&GetTop(S)==‘(‘){Pop(S,e);}else{state=0;}break;}case‘]’:{if(!StackEmpty(S)&&GetTop(S)==‘[‘){Pop(S,e);}else{state=0;}break;}ch=getchar();}if(StackEmpty(S)&&state)returnOK;elsereturnERROR;}行编辑程序出现的问题每接受一个字符立即存入存储器吗？NO合理的做法设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退格符，“@”为退行符。用户输入缓存区（用栈模拟）用户数据区入栈出栈假设从终端接受了这样两行字符：whli##ilr#e（s#*s)outcha@putchar(*s=#++);则实际有效的是下列两行：while(*s)putchar(*s++);行编辑程序算法的设计思想设一栈（输入缓冲区）；读入的字符为退格符，则删除栈顶字符；读入的字符为退行符，则清空栈；否则，读入的字符入栈。每处理完一行字符，将栈底到栈顶的字符存入存储器，清空栈，开始进行下一行的字符处理，直到文件结束。voidLineEdit(){InitStack(S);//缓存栈Sch=getchar();while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!='\n'){switch(ch){case'#':Pop(S,c);break;//重置S为空栈case'@':ClearStack(S);break;default:Push(S,ch);break;}ch=getchar();//接收本行下一个字符}将从栈底到栈顶的字符传送至调用过程的数据区；可以借助另一个辅助栈来完成InitStack(S2);.//辅助栈S2while(!EmptyStack(S)){//从S栈出来，进入S2Pop(S,e);Push(S2,e);}while(!EmptyStack(S2)){Pop(S2,e);将e写入用户数据区}ClearStack(S);ClearStack(S2);if(ch!=EOF)ch=getchar();//读取下一行字符}DestroyStack(S);DestroyStack(S2);}（算术）表达式求值算术表达式的组成操作数（运算对象或运算量）运算符界限符（如圆括号，作用是改变运算次序）常量、变量、函数、表达式单目、双目以+、-、*、/四种运算为例算术表达式的分类根据运算符在表达式中的不同位置中缀表达式后缀表达式前缀表达式例：表达式3*(5–2)3*(5–2)352-**3–52操作数之间的相对次序不变；运算符的相对次序可能不同；中缀式必须有括号信息，否则运算顺序改变；前缀式：无括号；连续出现的两个操作数和在它们之前出现且紧靠它们的运算符构成了一个最小表达式；后缀式：无括号；运算符的排列顺序就是计算顺序，每个运算符加上在它之前且紧靠它的两个操作数构成了一个最小表达式。三种表达式的特点中缀表达式求值设置两个工作栈：运算符栈S1和操作数栈S2。S2也放表达式的运算结果。算法思想1、首先置操作数栈S2为空栈，置运算符栈S1的栈底为表达式的起始符#(优先级最低)。2、依次读入表达式中的每个字符ch，直至表达式结束：若ch是操作数,则进S2栈；若ch是运算符，若其优先级不高于S1栈顶运算符的优先级时，则取出栈S2的栈顶和次栈顶的两个元素以及栈S1的栈顶运算符，进行相应的运算，并将结果放入栈S2中；如此下去，直至ch的优先级高于S1栈顶运算符的优先级，将ch入S1栈。OperandTypeEvaluateExpression(){InitStack(S1);Push(S1,#);InitStack(S2);c=getchar();while(c!=‘#’||GetTop(S1)!=‘#’){if(!In(c,OP)){Push(S2,c);c=getchar();}else{}}//whilereturnGetTop(S2);}//EvaluateExpression……switch(Precede(GetTop(S1),c){case:Push(S1,c);c=getchar();break;case=:Pop(S1,x);c=getchar();break;case:Pop(S1,op);Pop(S2,b);Pop(S2,a);Push(S2,Operate(a,op,b));break;}//switch举例:3*(5-2)步骤optr栈S1opnd栈S2输入字符ch主要操作－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－1#3*(5-2)#push(s2,’3’)2#3*(5-2)#push(s1,’*’)3#*3(5-2)#push(s1,’(’)4#*(35-2)#push(s2,’5’)5#*(35-2)#push(s1,’-’)6#*(-352)#push(s2,’2’)7#*(-352)#operate(‘5’,’-’,’2’)8#*(33)#pop(s1){消除一对括号}9#*33#operate(‘3’,’*’,’3’)10#9#return(gettop(s2))后缀表达式求值1.运算符已经按计算顺序从左到右排好；2.没有括号算法思想设一栈存放操作数；遇到操作数直接入栈；遇到运算符，则取出栈顶的两个数进行运算，将结果入栈；最终结果保存在栈中（栈中唯一元素）。intPostfix(){InitStack(S);//操作数栈c=getchar();while(c!=‘#'){if(isdigit(c)){//操作数入栈Push(S,c);}else{Pop(S,b);Pop(S,a);Push(S,Operate(a,c,b));}c=getchar();}Pop(S,result);returnresult;}后缀表达式求值：835+562/-*-#883835+83+5=8888562/6/2=38853-885-3=22*88*2=1616-8-16=-8-8栈与递归1.函数调用与返回的过程2.递归函数3.递归的设计原则4.递归的优点和缺点5.消除递归函数调用与返回的过程函数调用当在一个函数的运行期间调用另一个函数时，在运行被调用函数之前，需先完成三项任务：1.将所有的实在参数、返回地址等信息传递给被调用函数保存；2.为被调用函数的局部变量分配存储区；3.将控制转移到被调用函数的入口。函数调用与返回的过程函数返回从被调用函数返回调用函数之前，应该完成下列三项任务：1.保存被调函数的计算结果；2.释放被调函数的数据区；3.依照被调函数保存的返回地址将控制转移到调用函数。函数嵌套调用时，后调用的函数先返回。递归函数递归的定义函数直接或间接调用自身，称为递归。(Recursion)递归的应用1.问题具有递归的数学定义2.使用了递归的数据结构3.问题存在递归的解决方法阶乘n!、Fibonacci数列链表、二叉树Hanoi塔问题递归过程的应用（1）问题的数学定义是递归的例1：求n的阶乘n！longFact(intn){if(n==0)return(1);elsereturn(n*Fact(n-1));}求阶乘(n!)过程的模拟n=3fac(3)n=2F=3*fac(2)n=1F=2*fac(1)n=0F=1*fac(0)fac(0)returnfac(3)=3*2*1returnfac(2)=2*1returnfac(1)=1*1returnfac(0)=1这种分解-求解的策略叫“分治法”采用“分治法”进行递归求解的问题需要满足以下三个条件：1.能将一个问题转变成一个新问题，而新问题与原问题的解法相同或类同，不同的仅是处理的对象，并且这些处理对象更小且变化有规律。2.可以通过上述转化而使问题简化。3.必须有一个明确的递归出口，或成递归的边界。voidp(参数表){if(递归结束条件成立)可直接求解；elsep(较小的参数);}递归过程的应用（1）问题的数学定义是递归的例2：计算Fibonacci数列：0,1,1,2,3,5,8,13,21,…longFib(intn){if(n==1)return0;if(n==2)return1;returnFib(n-1)+Fib(n-2);}递归过程的应用（2）数据结构是递归的例1：逆序打印链表中各结点的值LL-next…voidPrintLinkList(LinkListL){if(L-next!=NULL){PrintLinkList(L-next);printf(L-next-data);}}逆序打印带头结点的单链表L!=NULL){L-data);逆序打印不带头结点的单链表递归过程的应用（2）数据结构是递归的例2：顺序打印链表中各结点的值LL-next…voidPrintLinkList(LinkListL){if(L-next!=NULL){printf(L-next-data);PrintLinkList(L-next);}}顺序打印带头结点的单链表递归过程的应用（3）问题存在递归的解决方法例1：Hanoi塔问题n阶Hanoi塔问题：假设有三个分别命名为X,Y,Z的塔座，在X塔座上插有n个直径大小各不相同，依小到大编号为1，2，…,n的圆盘，要求：把X上的n个圆盘移到Z上，排列顺序相同，移动规则为：1.每次只能移动一个圆盘；2.圆盘可以在任一塔上做多次移动；3.在任何时刻，大盘不能压在小盘的上面。XYZ问题存在递归的解决方法Hanoi(n,x,y,z)表示解决n个盘子的汉诺塔问题（从x搬到z，可以借助y）。解决方法：若n=1，直接将盘子从x搬到z即可；否则，可以分解为如下步骤：Hanoi(n-1,x,z,y)move(n,x,z)Hanoi(n-1,y,x,z)Hanoi算法实现voidHanoi(intn,charx,chary,charz){if(n==1)move(n,x,z);else{Hanoi(n-1,x,z,y);move(n,x,z);Hanoi(n-1,y,x,z);}}123465789演示Hanoi塔中递归工作栈变化过程03abc返址nxyz62acb61abcacabc