链栈及栈的应用.ppt

《链栈及栈的应用.ppt》由会员分享，可在线阅读，更多相关《链栈及栈的应用.ppt（26页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、链栈及栈的应用现在学习的是第1页，共26页栈的链接存储结构及实现栈的链接存储结构及实现 链栈：链栈：栈的链接存储结构栈的链接存储结构 特殊线性表特殊线性表特殊线性表特殊线性表栈栈栈栈firsta1a2anai链栈需要加头结点吗？链栈需要加头结点吗？如何改造链表实现栈的链接存储？如何改造链表实现栈的链接存储？将哪一端作为栈顶？将哪一端作为栈顶？将链头作为栈顶，方便操作。将链头作为栈顶，方便操作。链栈不需要附设头结点。链栈不需要附设头结点。现在学习的是第2页，共26页栈的链接存储结构及实现栈的链接存储结构及实现 栈顶栈顶栈底栈底链栈：链栈：栈的链接存储结构栈的链接存储结构 特殊线性表特殊线性表特殊

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

3、typedef struct StackNode DataType data struct StackNode*next ;StackNode*top;现在学习的是第4页，共26页(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;现在学习的是第

4、5页，共26页算法描述：算法描述：void Push(StackNode*top,DataType x)s=(StackNode*)malloc(sizeof(StackNode);s-data=x;s-next=top;top=s;topanan-1a1(4)入栈入栈 xstop操作接口：操作接口：void Push(StackNode*top,DataType x)为为什什么么没没有有判判断断栈栈满满？现在学习的是第6页，共26页算法描述：算法描述：DataType Pop(StackNode*top)if(StackEmpty(top)error(“stack underflow.”);

5、x=top-data;p=top;top=top-next;delete p;return x;(5)出栈出栈操作接口：操作接口：DataType Pop(StackNode*top)topanan-1a1topp top+可以吗？可以吗？现在学习的是第7页，共26页 3.2 栈的应用举例栈的应用举例1 数制转换数制转换 十进制十进制N和其它进制数的转换是计算机和其它进制数的转换是计算机实现计算的基本问题实现计算的基本问题,其解决方法很多其解决方法很多,其其中一个简单算法基于下列原理中一个简单算法基于下列原理:N=(n div d)*d+n mod d (其中其中:div为整除运算为整除运算,

6、mod为求余运算为求余运算)例如例如(1348)10=(2504)8，其运算过程如其运算过程如下：下：现在学习的是第8页，共26页 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现在学习的是第9页，共26页 void conversion()/输入任意一个非负十进制整数输入任意一个非负十进制整数,打印输出与其等值的八进制数打印输出与其等值的八进制数 InitStack(S);/初始化栈初始化栈 scanf(“%d”,N);/输入一个非负十进制

7、数输入一个非负十进制数 while(N)/非零时非零时,循环循环 push(S,N%8);/余数入栈余数入栈 N=N/8;while(!StackEmpty(S)Pop(S,e);/余数出栈余数出栈 printf(“%d”,e);/conversion 现在学习的是第10页，共26页2 行编辑程序行编辑程序 接受用户输入的一行字符，然后逐行存入用户数据接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。区。允许用户输入错误，并在发现有误时可以及时更正。例如例如:用户发现输入错误时用户发现输入错误时,输入输入”#”(退格符退格符),以表示以表示前一个字符

8、无效前一个字符无效;输入输入”(退行符退行符),表示当前输入的表示当前输入的一行无效一行无效;设一个栈接受输入设一个栈接受输入,每输入一个字符每输入一个字符,做如下判断做如下判断:是无效符是无效符,删除前一个入栈的符号删除前一个入栈的符号 是退行符是退行符,删除前一行入栈的符号删除前一行入栈的符号 其它其它,入栈入栈 现在学习的是第11页，共26页行编辑程序算法如下行编辑程序算法如下:void LineEdit()/利用字符栈利用字符栈S,从终端接收一行并传送至数据区从终端接收一行并传送至数据区 InitStack(S);/构造空栈构造空栈 ch=getcher();/从终端接收第一个字符从终

9、端接收第一个字符 while(ch!=EOF)/EOF为全文结束符为全文结束符 while(ch!=EOF&ch!=n)switch(ch)case#:Pop(S,c);/无效符无效符,出栈出栈 case :ClearStack(S);/退行符退行符,清空栈清空栈 default:Push(S,ch);/其它其它,入栈入栈 现在学习的是第12页，共26页 ch=getchar();/从终端接收下一个字符从终端接收下一个字符 /while /将从栈底到栈顶的栈内字符传送至调用过程的数据将从栈底到栈顶的栈内字符传送至调用过程的数据区区ClearStack(S);if(ch!=EOF)ch=getc

10、har();DestroyStack(S);/LindeEdit现在学习的是第13页，共26页表达式的计算表达式的计算在计算机中进行算术表达式的计算是通过栈来实现的。在计算机中进行算术表达式的计算是通过栈来实现的。(1)算术表达式的三种表示：算术表达式的三种表示：中缀：中缀：双目运算符出现在两个操作数中间双目运算符出现在两个操作数中间,例：例：a+b前缀：前缀：双目运算符出现在两个操作数前面双目运算符出现在两个操作数前面,例：例：+ab后缀：后缀：双目运算符出现在两个操作数后面双目运算符出现在两个操作数后面,例：例：ab+(2)三种表达式之间的转换：三种表达式之间的转换：按运算的优先次序全部加

11、上括号，逐个括号写成另一种表示按运算的优先次序全部加上括号，逐个括号写成另一种表示式式 （括号括号*，/+，-）注意：操作数出现的顺序不变注意：操作数出现的顺序不变3 表达式求值表达式求值现在学习的是第14页，共26页 三种表达式之间的转换：三种表达式之间的转换：例例 将将中缀表达式中缀表达式：转换成转换成后缀表达式后缀表达式 （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+现在学习的是第15页，共26页 把表达式翻译成正确的机器执行指令

12、把表达式翻译成正确的机器执行指令,要正确要正确地解释表达式地解释表达式.算符优先法是根据算术四则运算的规定来编算符优先法是根据算术四则运算的规定来编译或解释表达式的译或解释表达式的.表达式由操作数表达式由操作数,运算符运算符,界限符组成界限符组成.操作数操作数可以是变量或常量可以是变量或常量;此处考虑的运算符仅为此处考虑的运算符仅为+-*/,界限符有左右括号和结束符界限符有左右括号和结束符”#”.为实现算符优先法为实现算符优先法,可以使用两个工作栈可以使用两个工作栈.OPTR:存放运算符存放运算符,OPND:存放操作数或运算结存放操作数或运算结果果.现在学习的是第16页，共26页算法的基本思想

13、算法的基本思想:(1)置操作数栈为空置操作数栈为空,表达式起始符表达式起始符”#”,作为运算作为运算符栈的栈底符栈的栈底.(2)依次读入表达式中每个字符依次读入表达式中每个字符,若是操作数进若是操作数进OPND栈栈,若是运算符若是运算符,则和则和OPTR栈的栈顶运算栈的栈顶运算符比较优先权后作相应操作符比较优先权后作相应操作,直至整个表达式求直至整个表达式求值完毕值完毕(即即OPTR栈的栈顶元素和当前读入的字栈的栈顶元素和当前读入的字符均为符均为”#”).现在学习的是第17页，共26页算法算法OperandType EvaluateExpression()/算术表达式求值的算符优先算法算术表达

14、式求值的算符优先算法,设设OPTR和和OPND分别为运算符栈和操作分别为运算符栈和操作数栈数栈;OP为算符为算符(运算符和界限符运算符和界限符)集合集合 InitStack(OPTR;)Push(OPTR,#);InitStack(OPND);c=getchar();while(c!=#|GetTop(OPTR)!=#)if(!In(c,OP)Push(OPND,c);c=getchar();/操作数进操作数栈操作数进操作数栈 else switch(Precede(GetTop(OPTR),c)case:/栈顶元素优先权高栈顶元素优先权高,运算符退栈运算符退栈,操作数退栈操作数退栈,/并将运

15、算结果入栈并将运算结果入栈 Pop(OPTR,theta);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,theta,b);break;/switch /while return GetTop(OPND);/EvaluateExpression现在学习的是第19页，共26页步步骤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#

16、*(-3 72)#PUSH(OPND,2)7#*(-3 7 2)#operate(7,-,2)8#*(3 5)#POP(OPTR)消去括号消去括号9#*3 5#operate(3,*,5)10#1 5#return(GetTop(OPND)“-”大于大于”)”“(”等于等于”)”现在学习的是第20页，共26页3.3 栈与递归栈与递归若在一个函数、过程或者数据结构定义的内若在一个函数、过程或者数据结构定义的内部，部，直接或间接出现定义本身的应用直接或间接出现定义本身的应用，则称它们是，则称它们是递归递归的，或者是的，或者是递归定义递归定义的。的。递归是一种强有力的数学工具，它可使问题的描述递归是

17、一种强有力的数学工具，它可使问题的描述和求解变得简洁和清晰。和求解变得简洁和清晰。递归算法常常比非递归算法更易设计，尤其是当问递归算法常常比非递归算法更易设计，尤其是当问题本身或所涉及的数据结构是递归定义的时候，使用题本身或所涉及的数据结构是递归定义的时候，使用递归算法特别合适。递归算法特别合适。现在学习的是第21页，共26页例例:斐波那契数列为：斐波那契数列为：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;i

18、f(n=1)return 1;if(n1)return fib(n-1)+fib(n-2);现在学习的是第22页，共26页 递归执行分递归执行分递推递推和和回归回归两个阶段。两个阶段。在递推阶段，在递推阶段，把较复杂的问题（规模为把较复杂的问题（规模为n）的求解推到）的求解推到比原问题简单一些的问题（规模小于比原问题简单一些的问题（规模小于n）的求解。）的求解。例如求例如求解解fib(n)，把它推到求解，把它推到求解fib(n-1)和和fib(n-2)。而计算。而计算fib(n-1)和和fib(n-2)，又必须先计算，又必须先计算fib(n-3)和和fib(n-4)。依次类推，。依次类推，直至

19、计算直至计算fib(1)和和fib(0)，分别能立即得到结果，分别能立即得到结果1和和0。在在递推阶段，必须要有终止递归的情况。递推阶段，必须要有终止递归的情况。例如在函数例如在函数fib中，当中，当n为为1和和0的情况。的情况。在回归阶段，当获得最简单情况的解后，逐级返回，在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，依次得到稍复杂问题的解，例如得到例如得到fib(1)和和fib(0)后，后，返回得到返回得到fib(2)的结果，的结果，在得到了，在得到了fib(n-1)和和fib(n-2)的结果后，返回得到的结果后，返回得到fib(n)的结果。的结果。现在学习的是第2

20、3页，共26页 通常通常,一个函数调用另一个函数之前一个函数调用另一个函数之前,要作如下工作要作如下工作:a)将实在参数将实在参数,返回地址等返回地址等信息传递信息传递给被调用函数保存给被调用函数保存;b)为被调用函数的为被调用函数的局部变量分配存储区局部变量分配存储区;c)将将控制转移控制转移到被调函数的到被调函数的入口入口.从被调用函数返回调用函数之前从被调用函数返回调用函数之前,也要做三件事情也要做三件事情:a)保存保存被调函数的被调函数的计算结果计算结果;b)释放释放被调用函数的被调用函数的数据区数据区;c)依照被调函数保存的返回地址将依照被调函数保存的返回地址将控制转移到调用函数控制

21、转移到调用函数.变量和地址等数据都是保存在系统所分配的栈中的变量和地址等数据都是保存在系统所分配的栈中的.为了保证递归函数正确执行为了保证递归函数正确执行,系统需设立一个系统需设立一个”递归工递归工作栈作栈”,作为数据存储区作为数据存储区.用来存储所有的实在参数用来存储所有的实在参数,所有的所有的局部变量以及上一层的返回地址局部变量以及上一层的返回地址.现在学习的是第24页，共26页例例 递归的执行情况分析递归的执行情况分析 void print(int w)int i;if(w!=0)print(w-1);for(i=1;i=w;+i)printf(“%3d,”,w);printf(“/n”

22、);运行结果：1，2，2，3，3，3，现在学习的是第25页，共26页递归调用用执行情况如下：行情况如下：主程序主程序(1)print(w)w=3;3print(2);（1）w=3 top(2)输出：出：3,3,3w2print(1);（2）w=2 （1）w=3 top(3)输出：出：2,2w1print(0);（3）w=1 （2）w=2 （1）w=3 top(4)输出：出：1w0（4）w=0 （3）w=1 （2）w=2 （1）w=3 topw(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)现在学习的是第26页，共26页