第3章 链栈及栈的应用

第3章链栈及栈的应用,栈的链接存储结构及实现,链栈：栈的链接存储结构,特殊线性表栈,链栈需要加头结点吗？,如何改造链表实现栈的链接存储？,将哪一端作为栈顶？,将链头作为栈顶，方便操作。,链栈不需要附设头结点。,栈的链接存储结构及实现,栈顶,栈底,链栈：栈的链接存储结构,特殊线性表栈,两种示意图在内存中对应同一种状态,栈顶,栈底,3链栈栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。其类型说明为：typedefstructStackNodeDataTypedatastructStackNode*next;StackNode*top;,(1)初始化栈voidInitStack(StackNode*top)top=NULL;(2)判断空栈intStackEmpty(StackNode*top)return(top=NULL);(3)取栈顶DataTypeGetTop(StackNode*top)if(StackEmpty(top)error(“stackisempty.”);returntopdata;,算法描述：voidPush(StackNode*top,DataTypex)s=(StackNode*)malloc(sizeof(StackNode);s-data=x;s-next=top;top=s;,an,an-1,a1,(4)入栈,操作接口：voidPush(StackNode*top,DataTypex),为什么没有判断栈满？,算法描述：DataTypePop(StackNode*top)if(StackEmpty(top)error(“stackunderflow.”);x=top-data;p=top;top=top-next;free(p);returnx;,(5)出栈,操作接口：DataTypePop(StackNode*top),an,an-1,a1,top+可以吗？,3.2栈的应用举例1数制转换十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理:N=(ndivd)*d+nmodd(其中:div为整除运算,mod为求余运算)例如(1348)10=(2504)8，其运算过程如下：,NNdiv8Nmod8134816841682102125202先入栈,再出栈入栈顺序:4,0,5,2.出栈顺序:2,5,0,4所以1348=(2504)o,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,2行编辑程序接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。例如:用户发现输入错误时,输入”#”(退格符),以表示前一个字符无效;输入”(退行符),表示当前输入的一行无效;设一个栈接受输入,每输入一个字符,做如下判断:是无效符,删除前一个入栈的符号是退行符,删除前一行入栈的符号其它,入栈,行编辑程序算法如下:voidLineEdit()/利用字符栈S,从终端接收一行并传送至数据区InitStack(S);/构造空栈ch=getcher();/从终端接收第一个字符while(ch!=EOF)/EOF为全文结束符while(ch!=EOF/其它,入栈,ch=getchar();/从终端接收下一个字符/while/将从栈底到栈顶的栈内字符传送至调用过程的数据区ClearStack(S);if(ch!=EOF)ch=getchar();DestroyStack(S);/LindeEdit,表达式的计算,在计算机中进行算术表达式的计算是通过栈来实现的。(1)算术表达式的三种表示：中缀：双目运算符出现在两个操作数中间,例：a+b前缀：双目运算符出现在两个操作数前面,例：+ab后缀：双目运算符出现在两个操作数后面,例：ab+,(2)三种表达式之间的转换：按运算的优先次序全部加上括号，逐个括号写成另一种表示式（括号*，/+，-）注意：操作数出现的顺序不变,3表达式求值,三种表达式之间的转换：例将中缀表达式：转换成后缀表达式（A+B）*DE/（F+A*D）+C,AB+FAD*+,AB+D*EFAD*+/,AB+D*EFAD*+/-,AB+D*EFAD*+/-C+,例：A+B*DE/F+A*D+C,ABD*+EF/-AD*+C+,把表达式翻译成正确的机器执行指令,要正确地解释表达式.算符优先法是根据算术四则运算的规定来编译或解释表达式的.表达式由操作数,运算符,界限符组成.操作数可以是变量或常量;此处考虑的运算符仅为+-*/,界限符有左右括号和结束符”#”.为实现算符优先法,可以使用两个工作栈.OPTR:存放运算符,OPND:存放操作数或运算结果.,1)设立暂存运算符的OPTR栈;,2)设表达式的结束符为“#”,予设运算符栈OPTR的栈底为“#”,3)若当前字符是操作数，则直接进入OPND栈;,4)若当前运算符的优先数高于栈顶运算符，则进栈;,5)否则，退出栈顶运算符参与运算;,6)“(”对它之前后的运算符起隔离作用，“)”可视为自相应左括弧开始的表达式的结束符。,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,7,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,7,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,7,-,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,7,-,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,7,-,2,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,7,-,2,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,7,-,2,),表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,(,5,),表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,5,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,5,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,3,5,#,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,15,#,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,15,#,表达式的计算：如计算表达式的值：x=3(7-2),解：(*/+-)#,如：x=3(7-2),OPND栈,OPTR栈,执行过程：#3(7-2)#,#,15,#,算法：1.#压入到OPTR栈。2扫描中遇到操作数，进入OPND栈。3.运算符及(则进OPTR栈。在同一()表达式中，运算符进栈时，必须保持栈顶的运算符的优先级最高，否则应将OPND栈中的操作数完成该运算符对应的操作。并将该运算符自OPTR栈中弹出。,算法描述：OpeandTypeEvaluateExpression()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)case:Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;returnGetTop(OPND);,“-”大于”)”,“(”等于”)”,3.3栈与递归,若在一个函数、过程或者数据结构定义的内部，直接或间接出现定义本身的应用，则称它们是递归的，或者是递归定义的。递归是一种强有力的数学工具，它可使问题的描述和求解变得简洁和清晰。递归算法常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归算法特别合适。,例:斐波那契数列为：0、1、1、2、3、，即：fib(0)=0;fib(1)=1;fib(n)=fib(n-1)+fib(n-2)（当n1时）。写成递归函数有：intfib(intn)if(n=0)return0;if(n=1)return1;if(n1)returnfib(n-1)+fib(n-2);,递归执行分递推和回归两个阶段。在递推阶段，把较复杂的问题（规模为n）的求解推到比原问题简单一些的问题（规模小于n）的求解。例如求解fib(n)，把它推到求解fib(n-1)和fib(n-2)。而计算fib(n-1)和fib(n-2)，又必须先计算fib(n-3)和fib(n-4)。依次类推，直至计算fib(1)和fib(0)，分别能立即得到结果1和0。在递推阶段，必须要有终止递归的情况。例如在函数fib中，当n为1和0的情况。在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，例如得到fib(1)和fib(0)后，返回得到fib(2)的结果，在得到了fib(n-1)和fib(n-2)的结果后，返回得到fib(n)的结果。,通常,一个函数调用另一个函数之前,要作如下工作:a)将实在参数,返回地址等信息传递给被调用函数保存;b)为被调用函数的局部变量分配存储区;c)将控制转移到被调函数的入口.从被调用函数返回调用函数之前,也要做三件事情:a)保存被调函数的计算结果;b)释放被调用函数的数据区;c)依照被调函数保存的返回地址将控制转移到调用函数.变量和地址等数据都是保存在系统所分配的栈中的.为了保证递归函数正确执行,系统需设立一个”递归工作栈”,作为数据存储区.用来存储所有的实在参数,所有的局部变量以及上一层的返回地址.,例递归的执行情况分析,voidprint(intw)inti;if(w!=0)print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”);,运行结果：1，2，2，3，3，3，,递归调用执行情况如下：,voidhanoi(intn,charx,chary,charz)/将塔座x上按直径由小到大且至上而下编号为1至n/的n个圆盘按规则搬到塔座z上，y可用作辅助塔座。1if(n=1)2move(x,1,z);/将编号为的圆盘从x移到z3else4hanoi(n-1,x,z,y);/将x上编号为至n-1的/圆盘移到y,z作辅助塔5move(x,n,z);/将编号为n的圆盘从x移到z6hanoi(n