信息学奥赛辅导资料

《信息学奥赛辅导资料》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、信息学奥赛辅导资料导读：就爱阅读网友为您分享以下“信息学奥赛辅导资料”的资讯，希望对您有所帮助，感谢您对92to.com的支持!表3.1定义了算符之间的这种优先关系.为实现算符优先算法,可以使用两个工作栈.一个称作OPTR,用以寄存运算符;另一个称作POND,用以寄存操作数或运算结果.算法的基本思想是:??1)首先置操作数栈为空,表达式起始符"#"为运算栈的栈底元素;2)依此读入表达式中每个字符,若是操作数则进OPND栈,若是运算符,则和OPTR栈的栈顶运算符比较优先权后104作相应操作,直至整个表达式求值

2、完毕(即OPTR栈的栈顶元素和当前读入的字符均为"#").以下算法描述了这个求值过程.FUNCexp_reduce:operandfype;{算术表达式求值的算符优先算法.假定从终端输入的表达式无语法错误,以"#"作结束符.设OPTR和OPND分别为运算符栈和操作数栈，OP为运算符的集合}INISTACK(OPTR);PUSH(OPTR,'#');INISTACK(OPND);{栈初始化,并在运算符栈的栈底压入表达式左端的虚设字符'#'}read(w);{

3、从终端接受一个字符}WHILENOT104((w='#')AND(GETTOP(OPTR)='#'))DOIFwNOTINopTHENPUSH(OPND,w)ELSECASEprecde(GETTOP(OPTR),w)OF'<':[PUSH(OPTR,w);read(w)];{栈顶元素优先权低}'=":[x:=POP(OPTR);read(w)];{脱括弧并接受下一字符}">':[theta:=POP(OPTR);b:=POP(OP

4、ND);a:=POP(OPND);PUSH(OPND,operate(a,theta,b))]{退栈并将运算结果入栈}ENDC;RETURN(GETTOP(OPND))104ENDF;{exp_reducde}算法中还调用了两个函数。其中precede是判定运算符栈的栈顶运算符θ1与读入的运算符θ2之间优先关系的函数；orerate为进行二元运算aθb的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行该运算，并返回运算结果。例3-2利用算法exp_reducde对

5、算术表达式3*（7-2）求值，操作过程如下所示。2.3.1递归过程及其实现栈的另一个重要应用是在程序设计语言中实现递归过程。一个直接调用自己或通过一系列的过程语句间接地调用自己的过程，称做递归过程。例如，PROCEDUREA;BEGIN···A;···END;104过程A中的语句A直接调用了过程A本身，这叫做直接递归调用。又如：PROCEDUREB;PROCEDUREC;BEGINBEGIN······C;C;······END;END;在过程B中调用了过程C,而过程C又调用了过程B.这两个过程都通过另一个过程调用了它们自己,

6、这就叫做间接调用。递归是程序设计中一个强有力的工具。?其一,有很多数学函数是递归定义的,如大家熟悉的阶乘函数Fact(n)=1若n=1Fact(n)=n·Fact(n-1)若n>12阶Fibonacci数列Fib(n)=0若n=0Fib(n)=1若n=1Fib(n)=Fib(n-1)+Fib(n-2)其它情形和Ackerman函数Ack(m,n)=n+1m=0Ack(m,n)=Ack(m-1,1)n=0Ack(m,n)=Ack(m-1,Ack(m,n-1))其?它情形等;其二,有的数据结构,如二叉树,广义表等,由于结构本

7、身固有的递归特性,则它们的操作可递归地描述;104其三,还有一类问题,虽则问题本身没有明显的递归结构,但用递归求解比迭代求解更简单,如八皇后问题,Hanio塔问题等.树5.1树的结构定义和基本操作树(Tree)是n(n>=0)个结点的有限集。在一棵非空树中：(1)有且仅有一个特定的称为根的结点;(2)当n>1时其余结点可分为m(m>0)个互不相交的有限集T1,T2...Tm,其中,每一个集合本身又是一棵树,并且称为根的子树(subtree)例如,在图6.1中,(a)是只有一个根结点的树;(b)是有13个结点的

8、树,其中A是根,其余结点分成三个互不相交的子树：树是一种数据结构:Tree=(D,R)其中：D是具有相同特性的数据元素的集合；若D只含一个数据元素,则R为空集,否则R是D上个二元关系的集合，即R={H}。H为如下描述二元关系： 104??(1)在D中存在发唯一的称为根的数据元