《树结构综合版1——7数据结构ch3栈和队列》由会员分享，可在线阅读，更多相关《树结构综合版1——7数据结构ch3栈和队列（76页珍藏版）》请在金锄头文库上搜索。
1、数 据 结 构 Data Structure,主讲人： 刘 玮,第三章 栈和队列,栈的应用,3.2,递归,3.3,3.1 栈,限定只能在表的一端进行插入和删除操作的线性表。,3.1.1 栈的定义,其中a1为栈底元素(bottom) an为栈顶元素(top),a1,a2,an,进 栈,出 栈,top,bottom,栈顶：允许插入和删除的一端 栈底：不允许插入和删除的一端,特点：后进先出(LIFO),例：有三个元素按a，b，c的次序依次进栈，且每个元素只允许进一次栈，则可能的出栈序列？,c b a,c a b,a b c,a c b,b c a,b a c,3.1 栈,3.1.2 栈的抽象数据类型
2、ADT,ADT Stack 数据对象: D ai | aiElemSet, i=1,2,.,n, n0 数据关系：R1 |ai-1 ,aiD, i=2,.,n 基本操作： InitStack ( &S) DestoryStack(&S) Push ( &S, e) Pop (&S ,&e) GetTop (S, &e ) StackEmpty (S) StackLength(S) StackTraverse(S,visit() ,InitStack( &S ) 操作结果：构造一个空栈S DestroyStack(&S) 初始条件: 栈S已存在 操作结果：栈S被销毁,StackEmpty(S)
3、初始条件：栈S已存在 操作结果：若S为空栈，则返回 TRUE，否则FALSE。,StackLength(S) 初始条件：栈S已存在 操作结果：返回S的元素个数， 即栈的长度。,GetTop(S, &e) 初始条件：栈S已存在且非空。 操作结果：用e返回S的栈顶元素。,ClearStack(&S) 初始条件：栈S已存在。 操作结果：将S清为空栈。,Push(&S,e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈 顶元素。,Pop(&S,&e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，用 e返回它的值。,3.1 栈,3.1.3 栈的表示和实现,-顺序存储结构：顺序栈(S
4、equential Stacks) -链式存储结构：链栈(Linked Stacks),1、顺序栈,1) 存储特点： 利用一组地址连续的存储单元依次存放栈元素 附设指针top指示栈顶元素在顺序栈中的位置 2) 顺序栈的表示,#define STACK_INIT_SIZE 100; #define STACKINCREMENT 10; typedef struct SElemType *base； SElemType *top； int stacksize； SqStack,base,top,base,top,base,top,base,top,空栈,栈满,1、顺序栈,3) 基本操作的实现 栈的
5、初始化 进栈（PUSH） 出栈（POP）, 栈的初始化 算法思想：构造一个空栈，设置栈的参数,Status InitStack(SqStack , 进栈（PUSH） 算法思想 首先判断栈满？ 若栈满，则不能进栈操作; 数据元素入栈; 栈顶指针加1。,top,a6,base,Status Push(SqStack *(S.top+)=e； return OK； ,1、顺序栈, 出栈（POP） 算法思想 首先判断栈空？ 栈顶指针减1，数据元素出栈,top,a6,Status Pop(SqStack return OK； ,2、链栈,1）存储特点 是一种特殊形式的单链表（插入、删除操作限定在表一端进
6、行） 链式栈无栈满问题，空间可扩充,2、链栈,2) 链栈的表示（C语言描述）,typedef struct int len； SNode *top； LStack；,typedef struct SNode SElemType data； struct SNode *next； SNode；,进栈（PUSH）,. . .,top,p=(SNode *)malloc(sizeof(SNode);,p,e,p-data = e;,p-next = top;,top = p;,top,出栈（POP）,. . .,top,e = p-data;,S.top = p-next;,free(p);,p =
7、 S.top;,if(!StackEmpty(S) return ERROR;,p,e,top,顺序栈和链栈的比较,时间性能: 相同，都是常数时间O(1)。,空间性能：,顺序栈:有元素个数的限制和空间浪费的问题。 链栈：没有栈满的问题，只有当内存没有可用空间时才会出现栈满，但是每个元素都需要一个指针域，产生结构性开销。,总之，当栈的使用过程中元素个数变化较大时或不清楚栈元素个数时，用链栈适宜；反之，应该采用顺序栈。,3.2 栈的应用,3.2.1 数制转换问题,对于输入的任意一个非负十进制整数，打印输出与其等值的N进制数。,原理：即用该十进制数值除以n，并保留其余数；重复此操作，直到该十进制数值
8、为0。最后将所有的余数反向输出就是所对应的N进制数值。,（692）10 = （1010110100）2,（159）10 = （237）8,例：把十进制数159转换成八进制数。,void Conversion() InitStack( printf(“%d”,data) ,3.2.2 括号匹配的检验,括号匹配检验算法，即检查表达式或者语句中的 , ,( )等括号是否成对出现。其算法是各种编译器中的基本组成部分。,例如：表达式 a=a+b-(d-c(b+d),检验括号是否匹配的方法用“期待的急迫程度”这个概念来描述。,设置一个工作栈,工作栈stack,依次读入表达式中的每个字符,若是左括号（(,）
9、，则将其入栈； 若是右括号（），）：,若工作栈stack为空栈，则错误返回； 若工作栈stack不为空： 若栈顶元素与当前字符不匹配则错误退出； 否则将栈顶元素出栈；,算法思想：,表达式读取完毕，若栈非空则错误退出；,3.2.3 迷宫求解,1,2,3,4,5,6,7,8,9,10,y,x,算法思想：,3.2.4 表达式求值,表达式的组成：,操作数（operand）：常数、变量。 运算符（operator）: 算术运算符、关系运算符和逻辑运算符。 界限符（delimiter）：左右括弧和表达式结束符。,算术运算的规则：,先乘除后加减 先左后右 先括弧内后括弧外,例：4+2*3-10/5 =4+6
10、-10/5 =10-10/5 =10-2 =8,在计算机中，表达式可以有三种不同的标识方法：,设 Exp = S1 + OP + S2,则称 OP + S1 + S2 为表达式的前缀表示法,称 S1 + OP + S2 为表达式的中缀表示法,称 S1 + S2 + OP 为表达式的后缀表示法,可见，它以运算符所在不同位置命名的。,在计算机中，表达式可以有三种不同的标识方法：,例如： Exp = a b + (c d/e) f,前缀式： + a b - c / d e f,结论：,中缀式： a b + c d/e f,后缀式： a b c d e / - f +,（1）操作数之间的相对次序不变；
11、,（2）运算符的相对次序不同；,（3）中缀式丢失了括弧信息， 致使运算的次序不确定；,（4）前缀式中，连续出现的两个操作数和它们 之前且紧靠它们的运算符构成一个最小表 达式；,（5）后缀式中，运算符在式中出现的顺序恰为 表达式的运算顺序；每个运算符和在它之 前出现且紧靠它的两个操作数构成一个最 小表达式；,设置两个工作栈,运算符栈OPTR，运算符栈的栈底为表达式的起始符#。 操作数栈OPND，操作数为空栈。,依次读入表达式中的每个字符,若是操作数则进OPND栈； 若是运算符，则和OPTR中的栈顶元素做比较在操作。,若运算符优先级高于OPTR中的栈顶元素，则运算符入栈； 若运算符优先级低于OPT
12、R中的栈顶元素，则从OPND栈顶弹出两个操作数，与OPTR中的栈顶元素做运算，并将运算结果入OPND； 若运算符优先级等于OPTR中的栈顶元素，则将OPTR中的栈顶元素出栈。,算法思想：,直至表达式求值完毕。,例：计算2+4-3*6,当一个函数在运行期间调用另一个函数时，在运行该被调用函数之前，需先完成三件事：,将所有的实参、返回地址等信息传递给被调用函数保存； 为被调用函数的局部变量分配存储区； 将控制转移到被调用函数的入口。,而从被调用函数返回调用函数之前，应该完成：,保存被调用函数的计算结果； 释放被调用函数的数据区； 依照被调函数保存的返回地址将控制转移到调用函数。,由于函数的运行规则
13、是：后调用先返回，因此各函数占有的存储管理应实行“栈式管理”。,3.2.6 函数的调用,3.3 递归,3.3.1 递归的概念,递归的定义 若一个对象部分地包含它自己, 或用它自己给自己定义, 则称这个对象是递归的；若一个过程直接地或间接地调用自己, 则称这个过程是递归的过程。 以下三种情况常用到递归方法。 定义是递归的 数据结构是递归的 问题的解法是递归的,3.3 递归,3.3.2 定义递归,求解阶乘函数的递归算法 long Factorial ( long n ) if ( n = 0 ) return 1; else return n*Factorial (n-1); ,例如，阶乘函数,3
14、.3 递归,3.3.3 数据结构递归,某些数据结构就是递归的。例如，链表就是一种递归的数据结构。链表结点LNode的定义由数据域data和指针域next组成；而指针域next则又由LNode定义。,不仅单链表，广义表、树和图也都是递归结构。所以关于它们的一些算法，也需要用递归思想实现。,3.3 递归,3.3.4 解法递归,有些问题只能用递归方法来解决，若不用递归就只能用枚举法了。,一个典型的例子就是“Tower of Hanoi”问题：婆罗门神庙里有一个塔台，台上有3根柱子(假设叫x,y,z)。在x柱上有64个金盘，每一个都比下面的小。把x柱上的金盘全部移到z柱上，移动的条件是：一次只能移动一
15、个金盘，移动过程中大盘子只能放在小盘子下面。,汉诺塔(Tower of Hanoi)问题,有A、B、C三个塔座，A上套有n个直径不同的圆盘，按直径从小到大叠放，形如宝塔，编号1,2,3n。要求将n个圆盘从A移到C，叠放顺序不变，移动过程中遵循以下原则：,每次只能移动一个圆盘； 圆盘可在三个塔座上任意移动； 任何时刻，每个塔座上不能将大盘压倒小盘上。,算法思想,n=1时，直接把圆盘从A移到C。,把上面n-1个圆盘从A移动到B； 然后将n号盘从A移到C； 将n-1个盘从B移到C。,n1时，,即把求解n个圆盘的Hanoi问题转化为求解n-1个圆盘的Hanoi问题，依次类推，直至转化成只有一个圆盘的Hanoi问题。,main() int m; printf(“Input number of disks”); scanf(“%d”, (8) (9),递归的思想,我们把这种解决问题的“先分解再求解”的策略称为“分而治之”(divide and conquer)的策略，简称“分治法”。一个问题如能用“分治法”解决，就可以用递归算法实现。,前面看到的阶乘函数、幂函数、单链表、汉诺塔等问题的求解过程都蕴含着分而治之或先分解再求解的思想，因此都能用递归方法解决。而在其他学科中，如“运筹学”和“现代控制论”中的“动态规划”也是采用了分治的思想。,递归的结构,递归本身具有一定的特点，它是自己
