链栈及栈的应用课件.ppt

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

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

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

3、f 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;第5页，此课件共26页哦算法描

4、述：算法描述：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.”);x=top-data;p

5、=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为整除运算为整除运算,mod为求余运算为求余运算)

6、例如例如(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);/输入一个非负十进制数输入一个非负十进制数 while(

7、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();/从终端接收第一个字符从终端接收第一个字符 while(ch!=EOF

9、)/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=getchar();DestroyStack(S);/L

10、indeEdit第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页哦算法的基本思想算法的基本思想:(1)置操作数栈为空置操作数栈为空,表达式起始符

13、表达式起始符”#”,作为运算作为运算符栈的栈底符栈的栈底.(2)依次读入表达式中每个字符依次读入表达式中每个字符,若是操作数进若是操作数进OPND栈栈,若是运算符若是运算符,则和则和OPTR栈的栈顶运算栈的栈顶运算符比较优先权后作相应操作符比较优先权后作相应操作,直至整个表达式求直至整个表达式求值完毕值完毕(即即OPTR栈的栈顶元素和当前读入的字栈的栈顶元素和当前读入的字符均为符均为”#”).第17页，此课件共26页哦算法算法OperandType EvaluateExpression()/算术表达式求值的算符优先算法算术表达式求值的算符优先算法,设设OPTR和和OPND分别为运算符栈和分别为

14、运算符栈和操作数栈操作数栈;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:/栈顶元素优先权高栈顶元素优先权高,运算符退栈运算符退栈,操作数退栈操作数退栈,/并将运算结果入栈并将运算结果入栈 Pop(OPTR,theta);Pop(

15、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#*(-3 72)#PUSH(OPND,2)7#*(-3 7 2)

16、#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;if(n=1)return 1;if(n1)return fib(n-1)

18、+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)。依。依次类推，直至计算次类推，直至计算fib(1)和和fib(0)，分别能立即得到结果，分别能立即得到

19、结果1和和0。在递推阶段，必须要有终止递归的情况。在递推阶段，必须要有终止递归的情况。例如在函例如在函数数fib中，当中，当n为为1和和0的情况。的情况。在回归阶段，当获得最简单情况的解后，逐级返回，在回归阶段，当获得最简单情况的解后，逐级返回，依次得到稍复杂问题的解，依次得到稍复杂问题的解，例如得到例如得到fib(1)和和fib(0)后，后，返回得到返回得到fib(2)的结果，的结果，在得到了，在得到了fib(n-1)和和fib(n-2)的结果后，返回得到的结果后，返回得到fib(n)的结果。的结果。第23页，此课件共26页哦 通常通常,一个函数调用另一个函数之前一个函数调用另一个函数之前,

20、要作如下工作要作如下工作: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”);运行结果：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页哦