第3章-链栈及栈的应用

1、第第3 3章章 链栈链栈及栈的应用及栈的应用栈的链接存储结构及实现栈的链接存储结构及实现 链栈：链栈：栈的链接存储结构栈的链接存储结构 特殊线性表特殊线性表栈栈firsta1a2anai链栈需要加头结点吗？链栈需要加头结点吗？如何改造链表实现栈的链接存储？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将哪一端作为栈顶？ 将链头作为栈顶，方便操作。将链头作为栈顶，方便操作。链栈不需要附设头结点。链栈不需要附设头结点。栈的链接存储结构及实现栈的链接存储结构及实现 栈顶栈顶栈底栈底链栈：链栈：栈的链接存储结构栈的链接存储结构 特殊线性表特殊线性表栈栈topanan-1a1firsta1a2anai

2、两种示意图在内存中两种示意图在内存中对应同一种状态对应同一种状态topa1an-1an栈顶栈顶栈底栈底3 链栈链栈 栈的链式存储栈的链式存储结构称为结构称为链栈链栈，它是，它是运算受限运算受限的单链表，其插入和删除操作仅限制在表头位置的单链表，其插入和删除操作仅限制在表头位置上进行上进行. 由于只能在链表头部进行操作，由于只能在链表头部进行操作，故链表没有故链表没有必要像单链表那样附加头结点。必要像单链表那样附加头结点。栈顶指针栈顶指针就是链就是链表的表的头指针头指针。 其类型说明为：其类型说明为： typedef struct StackNode DataType data struct S

3、tackNode *next ; StackNode *top;(1) 初始化栈初始化栈 void InitStack( StackNode *top)top=NULL;(2) 判断空栈判断空栈 int StackEmpty(StackNode *top) return top=NULL; (3)取栈顶取栈顶 DataType GetTop(StackNode *top) if(StackEmpty(p) error(“stack is empty.”); return topdata; 算法描述：算法描述：void Push(StackNode *top,DataType x)s=(Stac

4、kNode*)malloc(sizeof(StackNode); s-data=x; s-next=top; top=s; topanan-1a1(4) 入栈入栈 xstop操作接口：操作接口： void Push( StackNode *top, DataType x)为为什什么么没没有有判判断断栈栈满满 ？算法描述：算法描述：DataType Pop(StackNode *top) if(StackEmpty(top) error(“stack underflow.”); x=top-data; p=top; top=top-next; delete p; return x;(5)出栈出栈

5、操作接口：操作接口： DataType Pop(StackNode *top)topanan-1a1topp top+可以吗？可以吗？ 3.2 栈的应用举例栈的应用举例1 数制转换数制转换 十进制十进制N和其它进制数的转换是计和其它进制数的转换是计算机实现计算的基本问题算机实现计算的基本问题,其解决方法其解决方法很多很多,其中一个简单算法基于下列原理其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中其中:div为整除运算为整除运算,mod为求余运为求余运算算) 例如例如 (1348)10=(2504)8，其运算过程其运算过程如下：如下： N N div 8 N

6、 mod 8 1348 168 4 168 21 0 21 2 5 2 0 2 先入栈,再出栈 入栈顺序:4,0,5,2. 出栈顺序:2,5,0,4 所以 1348 = (2504)o void conversion( ) /输入任意一个非负十进制整数输入任意一个非负十进制整数,打印输出与其等值的八进制数打印输出与其等值的八进制数 InitStack(S); /初始化栈初始化栈 scanf (“%d”,N); /输入一个非负十进制数输入一个非负十进制数 while(N) / 非零时非零时,循环循环 push(S,N%8);/余数入栈余数入栈 N=N/8; while(! StackEmpty(

7、S) Pop(S,e);/余数出栈余数出栈 printf(“%d”,e); /conversion 2 行编辑程序行编辑程序 接受用户输入的一行字符，然后逐行存入用接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时户数据区。允许用户输入错误，并在发现有误时可以及时更正。可以及时更正。 例如例如:用户发现输入错误时用户发现输入错误时,输入输入”#”(退格符退格符),以以表示前一个字符无效表示前一个字符无效; 输入输入”(退行符退行符),表示当表示当前输入的一行无效前输入的一行无效; 设一个栈接受输入设一个栈接受输入,每输入一个字符每输入一个字符,做如下做如下判断判断

8、: 是无效符是无效符,删除前一个入栈的符号删除前一个入栈的符号 是退行符是退行符,删除前一行入栈的符号删除前一行入栈的符号 其它其它,入栈入栈 行编辑程序算法如下行编辑程序算法如下: void LineEdit( ) /利用字符栈利用字符栈S,从终端接收一行并传送至数据区从终端接收一行并传送至数据区 InitStack(S); /构造空栈构造空栈 ch = getcher( ); /从终端接收第一个字符从终端接收第一个字符 while(ch!=EOF)/EOF为全文结束符为全文结束符 while(ch!=EOF & ch!=n) switch(ch) case # : Pop(S,c)

9、; /无效符无效符, 出栈出栈 case : ClearStack(S); /退行符退行符, 清空栈清空栈 default : Push(S,ch); /其它其它,入栈入栈 ch=getchar( );/从终端接收下一个字符从终端接收下一个字符 /while /将从栈底到栈顶的栈内字符传送至调用过将从栈底到栈顶的栈内字符传送至调用过程的数据区程的数据区ClearStack(S);if(ch!=EOF) ch=getchar( );DestroyStack(S);/LindeEdit表达式的计算表达式的计算在计算机中进行算术表达式的计算是通过栈来实现的。在计算机中进行算术表达式的计算是通过栈来实

10、现的。 (1) 算术表达式的三种表示：算术表达式的三种表示：中缀：中缀：双目运算符出现在两个操作数中间双目运算符出现在两个操作数中间, 例：例：a+b前缀：前缀：双目运算符出现在两个操作数前面双目运算符出现在两个操作数前面, 例：例：+ab后缀：后缀：双目运算符出现在两个操作数后面双目运算符出现在两个操作数后面, 例：例：ab+(2) 三种表达式之间的转换：三种表达式之间的转换： 按运算的优先次序全部加上括号，逐个括号写成另一种按运算的优先次序全部加上括号，逐个括号写成另一种表示式表示式 （ 括号括号 * ，/ +，- ）注意：操作数出现的顺序不变注意：操作数出现的顺序不变3 表达式求值表达式

11、求值 三种表达式之间的转换：三种表达式之间的转换：例例 将将中缀表达式中缀表达式： 转换成转换成后缀表达式后缀表达式 （A+B）*D E/（F +A*D）+CAB+ F AD* +AB+ D* E FAD*+ / AB+D* EFAD*+/ - AB+D* EFAD*+/ - C+例：例：A+B*D E / F +A*D +CABD*+EF/ - AD* + C+ 把表达式翻译成正确的机器执行指令把表达式翻译成正确的机器执行指令,要正要正确地解释表达式确地解释表达式. 算符优先法是根据算术四则运算的规定来编算符优先法是根据算术四则运算的规定来编译或解释表达式的译或解释表达式的. 表达式由操作数

12、表达式由操作数,运算符运算符,界限符组成界限符组成.操作数操作数可以是变量或常量可以是变量或常量;此处考虑的运算符仅为此处考虑的运算符仅为+-*/,界限符有左右括号和结束符界限符有左右括号和结束符”#”. 为实现算符优先法为实现算符优先法,可以使用两个工作可以使用两个工作栈栈.OPTR:存放运算符存放运算符, OPND:存放操作数或运算存放操作数或运算结果结果. 算法的基本思想算法的基本思想:(1)置操作数栈为空置操作数栈为空,表达式起始符表达式起始符”#”,作为运算符作为运算符栈的栈底栈的栈底.(2)依次读入表达式中每个字符依次读入表达式中每个字符,若是操作数进若是操作数进OPND栈栈,若是

13、运算符若是运算符,则和则和OPTR栈的栈顶运算栈的栈顶运算符比较优先权后作相应操作符比较优先权后作相应操作,直至整个表达式求直至整个表达式求值完毕值完毕(即即OPTR栈的栈顶元素和当前读入的字栈的栈顶元素和当前读入的字符均为符均为”#”).算法算法OperandType EvaluateExpression() /算术表达式求值的算符优先算法算术表达式求值的算符优先算法,设设OPTR和和OPND分别为运算符分别为运算符栈和操作数栈栈和操作数栈;OP为算符为算符(运算符和界限符运算符和界限符)集合集合 InitStack(OPTR;) Push(OPTR,#);InitStack(OPND);c

14、=getchar(); while(c!=#|GetTop(OPTR)!=#) if (!In(c,OP)Push(OPND,c);c=getchar();/操作数进操作数栈操作数进操作数栈 else switch(Precede(GetTop(OPTR),c) case : /栈顶元素优先权高栈顶元素优先权高, 运算符退栈运算符退栈,操作数退栈操作数退栈, /并将运算结果入栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b); Pop(OPND,a); Push(OPND,Operate(a,theta,b); break; /switch /while return

15、 GetTop(OPND);/EvaluateExpression步骤步骤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# * (3 7 2 ) # PUSH(OPTR,-)6# * ( -3 72 ) # PUSH(OPND,2)7# * ( -3 7 2) # operate(7,-,2)8# * (3 5) # POP(OPTR)消去括号消去括号9# *3

16、5# operate(3,*,5)10#1 5# return(GetTop(OPND)“-”大于大于”)”“(”等于等于”)”3.3 栈与递归栈与递归 若在一个函数、过程或者数据结构定义的若在一个函数、过程或者数据结构定义的内部，内部，直接或间接出现定义本身的应用直接或间接出现定义本身的应用，则称，则称它们是它们是递归递归的，或者是的，或者是递归定义递归定义的。的。 递归是一种强有力的数学工具，它可使问递归是一种强有力的数学工具，它可使问题的描述和求解变得简洁和清晰。题的描述和求解变得简洁和清晰。 递归算法常常比非递归算法更易设计，尤递归算法常常比非递归算法更易设计，尤其是当问题本身或所涉及

17、的数据结构是递归定其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归算法特别合适。义的时候，使用递归算法特别合适。 例例: 斐波那契数列为：斐波那契数列为：0、1、1、2、3、，即：，即： fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2) （当（当n1时）。时）。 写成递归函数有：写成递归函数有： int fib(int n) if (n=0) return 0; if (n=1) return 1; if (n1) return fib(n-1)+fib(n-2); 递归执行分递归执行分递推递推和和回归回归两个阶段。两个阶段。 在递推阶段，在递

18、推阶段，把较复杂的问题（规模为把较复杂的问题（规模为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中，当中，当

19、n为为1和和0的情况。的情况。 在回归阶段，当获得最简单情况的解后，逐级返在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，回，依次得到稍复杂问题的解，例如得到例如得到fib(1)和和fib(0)后，返回得到后，返回得到fib(2)的结果，的结果，在得到了，在得到了fib(n-1)和和fib(n-2)的结果后，返回得到的结果后，返回得到fib(n)的结果。的结果。 通常通常,一个函数调用另一个函数之前一个函数调用另一个函数之前,要作如下要作如下工作工作: a)将实在参数将实在参数,返回地址等返回地址等信息传递信息传递给被调用函数保给被调用函数保存存; b)为被调用函数的为被调用函数的局部变量分配存储区局部变量分配存储区; c)将将控制转移控制转移到被调函数的到被调函数的入口入口. 从被调用函数返回调用函数之前从被调用函数返回调用函数之前,也要做三件事也要做三件事情情: a)保存保存被调函数的被调函数的计算结果计算结果; b)释放释放被调用函数的被调用函数的数据区数据区; c)依照被调函数保存的返回地址将依照被调函数保存的返回地址将控制转移到调用