考研数据结构cha.ppt

《考研数据结构cha.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章栈和队列3.1栈的表示和实现3.2递归过程3.3队列的表示和实现栈和队列的逻辑结构、物理结构，以及它们之间的相互关系；定义与之相适应的运算；设计相应的算法；分析算法的效率。一、栈的概念栈（stack）是插入和删除操作限定在表尾进行的线性表。栈的逻辑表示为：S=（a1,a2,…,an）表尾元素an称为栈顶(top)表头元素a1称为栈底(bottom)不含元素的空表称为空栈栈的运算特性是后进先出(LastInFirstOut--LIFO)或先进后出(FirstInLastOut--FILO)3.1栈的表示和实现3.1栈的表示和实现二、栈的基

2、本运算INISTACK(S)初始化操作，设定一个空栈SEMPTY(S)判栈S是否为空函数（true/false）PUSH(S,x)入栈操作，在栈S顶部插入元素x，相当于线性表的INSERT(L,n+1,x)POP(S)出栈函数，若S不空，则返回栈顶元素，并删除栈顶元素；否则返回空元素NULL，相当于线性表的DELET(L,n)GETTOP(S)取栈顶元素函数，与POP(S)的差别在不删除栈顶元素，相当于线性表的GET(L,n)CURRENT-SIZE(S)求S栈中当前元素个数函数，相当于线性表的LENGTH(L)CLEAR(S)置栈空操作3.

3、1栈的表示和实现三.栈的表示和实现1.顺序栈的存储结构描述及出入栈运算CONSTarrmax=栈允许存放元素个数的最大值；TYPEsqstktp=RECORDelem：ARRAY[1．．arrmax]OFelemtp；top：0．．arrmaxEND；S=sqstktp；S．elem[i]表示第i个进栈的元素S．elem[S．top]表示栈顶元素当S．top=0表示空栈当S．top=arrmax表示栈满3.1栈的表示和实现入栈函数push(S，x)的实现算法思想：若栈满返回false；否则将x入栈，并返回true。FUNCpush_stack

4、(VARs：sqstktp；x：elemtp)：boolean；IFs．top=armaxTHENRETURN（false）ELSE[s．top：=s．top+1；s．elem[s．top]：=x；RETURN（true）]ENDF；{push_stack}3.1栈的表示和实现出栈函数pop(S)的实现算法思想：若栈空则返回空元素NULL；否则返回栈顶元素。FUNCpop_stack(VARs：sqstktp)：elemtp；IFs．top=0THENRETURN（NULL）ELSE[s．top：=s．top-1；RETURN（s．elem[

5、s．top+1]）]ENDF；{pop_stack}3.1栈的表示和实现2.链栈的存储结构描述TYPEpointer=↑nodetype；nodetype=RECORDdata：elemtp；next：pointerEND；linkstktp=pointer；3.2递归过程递归是栈的另一个重要应用，也是程序设计的一个强有力的工具。1.应用递归的原因和领域递归定义┏1当n=0阶乘n!=┃┗n*(n-1)!当n>0┏0n=0Fibonacci数列Fib(n)=┃1n=1┗Fib(n-1)+Fib(n-2)n>1递归结构后面将要介绍的二叉树，广义表

6、结构本身固有递归特性，操作也可递归描述。用递归求解更简单例：计算两个非负整数a*b的算法1.递归方式：a*b=b+(a-1)*bFUNCmul1(a，b：integer)：integer；IFa=0THENRETURN(0)ELSERETURN(b+mul1(a-1，b))ENDF；{mul1}3.2递归过程2.迭代方式：a*b=a个b之和FUNCmul2(a，b：integer)：integer；z：=0；FORi：=1TOaDOz：=z+b；RETURN(z)ENDF；{mul2}3.2递归过程2.递归过程的特点：是程序设计的一个强有力的

7、工具，它具有结构清晰，程序易编、易读、易调试，程序正确性易证明等优点；但运行效率低。3.基本原理：基本原理是重复地把问题转化为与原问题相似的新问题，直到问题可解决为止。4.关键点：①用较简单的新问题来表示较复杂的原问题例如：n！=n(n-1)！，或n!=(n+1)！/(n+1)前者(n-1)！较原问题n！简单，可行；而后者(n+1)！较n！更复杂，不可行。②不能产生自己调用自己的无穷序列，即必须有一个递归调用序列的“出口”，来终止递归调用。5.实现：递归过程都是通过栈来实现的，并且任何递归算法均可通过栈改写为非递归算法。3.2递归过程6.汉诺

8、（Hanoi)塔问题设：有X、Y、Z三个塔座，在X上按直径大小递减次序依次插有n个直径各不相同的圆盘，各圆盘按直径从小到大编为1~n。要求：将X塔上的n个圆盘按规则