第3章 链栈及栈的应用.ppt

1、第3章 链栈及栈的应用,栈的链接存储结构及实现,链栈：栈的链接存储结构,特殊线性表栈,链栈需要加头结点吗？,如何改造链表实现栈的链接存储？,将哪一端作为栈顶？,将链头作为栈顶，方便操作。,链栈不需要附设头结点。,栈的链接存储结构及实现,栈顶,栈底,链栈：栈的链接存储结构,特殊线性表栈,两种示意图在内存中对应同一种状态,栈顶,栈底,3 链栈 栈的链式存储结构称为链栈，它是运算受限的单链表，其插入和删除操作仅限制在表头位置上进行. 由于只能在链表头部进行操作，故链表没有必要像单链表那样附加头结点。栈顶指针就是链表的头指针。 其类型说明为： typedef struct StackNode Data

2、Type data struct StackNode *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)

3、 s=(StackNode*)malloc(sizeof(StackNode); s-data=x; s-next=top; top=s; ,an,an-1,a1,(4) 入栈,操作接口： 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)出栈,操作接口：

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

5、id conversion( ) /输入任意一个非负十进制整数,打印输出与其等值的八进制数 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 行编辑程序 接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。 例如:用户发现输入错误时,输入”#”(退格符),以表示前一个字符无效; 输入”(退行

6、符),表示当前输入的一行无效; 设一个栈接受输入,每输入一个字符,做如下判断: 是无效符,删除前一个入栈的符号 是退行符,删除前一行入栈的符号 其它,入栈,行编辑程序算法如下: void LineEdit( ) /利用字符栈S,从终端接收一行并传送至数据区 InitStack(S); /构造空栈 ch = getcher( ); /从终端接收第一个字符 while(ch!=EOF)/EOF为全文结束符 while(ch!=EOF /其它,入栈 ,ch=getchar( );/从终端接收下一个字符 /while /将从栈底到栈顶的栈内字符传送至调用过程的数据区 ClearStack(S); if

7、(ch!=EOF) ch=getchar( ); DestroyStack(S); /LindeEdit,表达式的计算,在计算机中进行算术表达式的计算是通过栈来实现的。 (1) 算术表达式的三种表示： 中缀：双目运算符出现在两个操作数中间, 例：a+b 前缀：双目运算符出现在两个操作数前面, 例：+ab 后缀：双目运算符出现在两个操作数后面, 例：ab+,(2) 三种表达式之间的转换： 按运算的优先次序全部加上括号，逐个括号写成另一种表示式 （ 括号 * ，/ +，- ） 注意：操作数出现的顺序不变,3 表达式求值,三种表达式之间的转换： 例 将中缀表达式： 转换成后缀表达式 （A+B）*D

8、E/（F +A*D）+C,AB+ F AD* +,AB+ D* E FAD*+ /,AB+D* EFAD*+/ -,AB+D* EFAD*+/ - C+,例：A+B*D E / F +A*D +C,ABD*+EF/ - AD* + C+,把表达式翻译成正确的机器执行指令,要正确地解释表达式. 算符优先法是根据算术四则运算的规定来编译或解释表达式的. 表达式由操作数,运算符,界限符组成.操作数可以是变量或常量;此处考虑的运算符仅为+-*/,界限符有左右括号和结束符”#”. 为实现算符优先法,可以使用两个工作栈.OPTR:存放运算符, OPND:存放操作数或运算结果.,算法的基本思想: (1)置操

9、作数栈为空,表达式起始符”#”,作为运算符栈的栈底. (2)依次读入表达式中每个字符,若是操作数进OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后作相应操作,直至整个表达式求值完毕(即OPTR栈的栈顶元素和当前读入的字符均为”#”).,算法 OperandType EvaluateExpression() /算术表达式求值的算符优先算法,设OPTR和OPND分别为运算符栈和操作数栈;OP为算符(运算符和界限符)集合 InitStack(OPTR;) Push(OPTR,#);InitStack(OPND);c=getchar(); while(c!=#|GetTop(OPTR)!

10、=#) if (!In(c,OP)Push(OPND,c);c=getchar();/操作数进操作数栈 else switch(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(OPN

11、D,Operate(a,theta,b); break; /switch /while return GetTop(OPND); /EvaluateExpression,“-”大于”)”,“(”等于”)”,3.3 栈与递归,若在一个函数、过程或者数据结构定义的内部，直接或间接出现定义本身的应用，则称它们是递归的，或者是递归定义的。 递归是一种强有力的数学工具，它可使问题的描述和求解变得简洁和清晰。 递归算法常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用递归算法特别合适。,例: 斐波那契数列为：0、1、1、2、3、，即： fib(0)=0; fib(1)=1;

12、 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); ,递归执行分递推和回归两个阶段。 在递推阶段，把较复杂的问题（规模为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)，分别能立

13、即得到结果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)依照被调函数保存的返回地址将控制转移到调用函数. 变量和地址等数据都是保存在系统所分配的栈中的.为了