第3章链栈及栈的应用

第3章链栈及栈的应用栈的链接存储结构及实现链栈：栈的链接存储结构特殊线性表——栈firsta1a2an∧ai链栈需要加头结点吗？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将链头作为栈顶，方便操作。链栈不需要附设头结点。栈的链接存储结构及实现栈顶栈底链栈：栈的链接存储结构特殊线性表——栈topanan-1a1∧firsta1a2an∧ai两种示意图在内存中对应同一种状态topa1an-1an∧栈顶栈底3链栈栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行.由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。其类型说明为：typedefstructStackNode{DataTypedatastructStackNode*next};StackNode*top;(1)初始化栈voidInitStack(StackNode*top){top=NULL;}(2)判断空栈intStackEmpty(StackNode*top){returntop==NULL;}(3)取栈顶DataTypeGetTop(StackNode*top){if(StackEmpty(p))error(“stackisempty.”);returntop–data;}算法描述：voidPush(StackNode*top,DataTypex){s=(StackNode*)malloc(sizeof(StackNode));s-data=x;s-next=top;top=s;}topanan-1a1∧(4)入栈xstop操作接口：voidPush(StackNode*top,DataTypex){为什么没有判断栈满？算法描述：DataTypePop(StackNode*top){if(StackEmpty(top)error(“stackunderflow.”);x=top-data;p=top;top=top-next;deletep;returnx;}(5)出栈操作接口：DataTypePop(StackNode*top)topanan-1a1∧topptop++可以吗？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)ovoidconversion(){//输入任意一个非负十进制整数,打印输出与其等值的八进制数InitStack(S);//初始化栈scanf(“%d”,N);//输入一个非负十进制数while(N){//非零时,循环push(S,N%8);//余数入栈N=N/8;}while(!StackEmpty(S)){Pop(S,e);//余数出栈printf(“%d”,e);}}//conversion2行编辑程序接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。例如:用户发现输入错误时,输入”#”(退格符),以表示前一个字符无效;输入”@”(退行符),表示当前输入的一行无效;设一个栈接受输入,每输入一个字符,做如下判断:是无效符,删除前一个入栈的符号是退行符,删除前一行入栈的符号其它,入栈行编辑程序算法如下:voidLineEdit(){//利用字符栈S,从终端接收一行并传送至数据区InitStack(S);//构造空栈ch=getcher();//从终端接收第一个字符while(ch!=EOF){//EOF为全文结束符while(ch!=EOF&&ch!=‘\n’){switch(ch){case‘#’:Pop(S,c);//无效符,出栈case‘@’:ClearStack(S);//退行符,清空栈default:Push(S,ch);//其它,入栈}ch=getchar();//从终端接收下一个字符}//while//将从栈底到栈顶的栈内字符传送至调用过程的数据区ClearStack(S);if(ch!=EOF)ch=getchar();}DestroyStack(S);}//LindeEdit表达式的计算在计算机中进行算术表达式的计算是通过栈来实现的。(1)算术表达式的三种表示：中缀：——双目运算符出现在两个操作数中间,例：a+b前缀：——双目运算符出现在两个操作数前面,例：+ab后缀：——双目运算符出现在两个操作数后面,例：ab+(2)三种表达式之间的转换：按运算的优先次序全部加上括号，逐个括号写成另一种表示式（括号——*，/——+，-）注意：操作数出现的顺序不变3表达式求值三种表达式之间的转换：例将中缀表达式：——转换成后缀表达式（A+B）*D–E/（F+A*D）+CAB+FAD*+AB+D*EFAD*+/AB+D*EFAD*+/-AB+D*EFAD*+/-C+例：A+B*D–E/F+A*D+CABD*+EF/-AD*+C+把表达式翻译成正确的机器执行指令,要正确地解释表达式.算符优先法是根据算术四则运算的规定来编译或解释表达式的.表达式由操作数,运算符,界限符组成.操作数可以是变量或常量;此处考虑的运算符仅为+-*/,界限符有左右括号和结束符”#”.为实现算符优先法,可以使用两个工作栈.OPTR:存放运算符,OPND:存放操作数或运算结果.算法的基本思想:(1)置操作数栈为空,表达式起始符”#”,作为运算符栈的栈底.(2)依次读入表达式中每个字符,若是操作数进OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为”#”).算法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){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));break;}//switch}//whilereturnGetTop(OPND);}//EvaluateExpression步骤OPTR栈OPND栈输入字符主要操作1#3*(7–2)#PUSH(OPND,’3’)2#3*(7–2)#PUSH(OPTR,’*’)3#*3(7–2)#PUSH(OPTR,’(’)4#*(37–2)#PUSH(OPND,’7’)5#*(37–2)#PUSH(OPTR,’-’)6#*(-372)#PUSH(OPND,’2’)7#*(-372)#operate(‘7’,’-’,’2’)8#*(35)#POP(OPTR){消去括号}9#*35#operate(‘3,’,’*’,’5’)10#15#return(GetTop(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，递归调用执行情况如下：主程序(1)print(w)w=3;3print(2);（1）w=3top(2)输出：3,3,3w2print(1);（2）w=2（1）w=3top(3)输出：2,2w1print(0);（3）w=1（2）w=2（1）w=3top(4)输出：1w0（4）w=0（3）w=1（2）w=2（1）w=3topw(3)输出：2,2(2)2(1)3top(4)输出：1(3)1(2)2(1)3top(2)输出：3,3,3(1)3top返回(3)1(2)2(1)3top(4)0结束(1)