数据结构课件第3章.ppt

《数据结构课件第3章.ppt》由会员分享，可在线阅读，更多相关《数据结构课件第3章.ppt（82页珍藏版）》请在三一办公上搜索。

1、第三章 栈、队列,第三章 栈、队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归 3.4 队列,3.1 栈3.1.1 栈的概念3.1.2 栈的顺序存储和实现3.1.3 栈的链式存储和实现,3.1 栈,栈是限定仅能在表尾一端进行插入、删除操作的线性表,（a1,a2,.,ai-1,ai,ai+1,an）,插入,删除,3.1.1 栈的概念一 什么是栈?,3.1 栈,将表中允许进行插入、删除操作的一端称为栈顶(Top)，栈顶的当前位置是动态变化的，由一个栈顶指针指示其位置。表的另一端称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作称为进栈或入栈，删除操作称为出栈或退栈。,栈,3.

2、1 栈,栈的示意图,出栈,进栈,栈的特点后进先出,第一个进栈的元素在栈底，最后一个进栈的元素在栈顶，第一个出栈的元素为栈顶元素，最后一个出栈的元素为栈底元素,3.1 栈,栈的基本操作数据元素：可以是任意类型的数据，但必属于同一个数据对象。关系：栈中数据元素之间是线性关系。1）构造一个空栈S；2）进栈操作Push3）出栈操作Pop4)取栈顶元素top,3.1 栈,栈操作图示,空栈,A进栈,B C D E 进栈,E D C 出栈,3.1 栈,3.1.2 栈的顺序存储和实现,#define MAX 50int stackMAX;int top=0;,3.1 栈,约定栈顶指针指向栈顶元素的下一个位置,

3、3.1 栈,1)进栈操作主要语句if(top=MAX)printf(“overflow”);else stacktop=x;top+;,3.1 栈,2）出栈操作主要语句if(top=0)printf(“underflow”);return(NULL);top-;return(stacktop);,教材中顺序栈的数据类型定义：typedef struct SqStack SelemType*base;/栈底指针 SelemType*top;/栈顶指针 int stacksize；/当前已分配的存储空间SqStack;基本操作 P47,共享栈技术（最常用的是两个栈的共享）：主要利用栈“栈底位置不变

4、，栈顶位置动态变化”的特性。为两个栈申请一个共享的一维数组空间SM，将两个栈的栈底分别放在一维数组的两端，分别是0，M-1。由于两个栈顶动态变化，形成互补，使得每个栈可用的最大空间与实际使用的需求有关。两栈共享比两个栈分别申请M/2的空间利用率高。,设两个栈共享的数据结构定义如下：,define M 100typedef struct DqStack SElemType StackM;int top2;/top0和top1分别为两个栈顶指示器 DqStack;,共享栈,初始化操作?,初始化操作。void InitStack(DqStack*S)S.top0=0;S.top1=M-1;,进栈操作

5、算法?int Push(DqStack*S,SElemType x,int i)/把数据元素x压入i号栈,(2)进栈操作算法。int Push(DqStack*S,StackElementType x,int i)/把数据元素x压入i号栈 if(S.top0+1=S.top1)/栈已满 return(FALSE);switch(i)case 0:S.StackS.top0=x;S.top0+;break;,case 1:S.StackS.top1=x;S.top1-;break;default:/i参数错误 return(FALSE)return(TRUE);,出栈操作算法?int Pop(D

6、qStack*S,SElemType*x,int i)/从i 号栈中弹出栈顶元素并送到x中,(3)出栈操作算法。int Pop(DqStack*S,StackElementType*x,int i)switch(i)case 0:if(S.top0=0)return(FALSE);S.top0-;*x=S.StackS.top0;break;case 1:if(S.top1=M-1)return(FALSE);S.top1+;*x=S.StackS.top1;break;default:return(FALSE);return(TRUE);,3.1 栈,3.1.3 栈的链式存储和实现栈的链式存

7、储结构，也称链栈，如图所示：,有了线性链表的插入、删除操作算法，不难写出链栈初始化、进栈、出栈等操作的算法,3.1 栈,(1)进栈算法主要语句p=(NODE*)malloc(sizeof(NODE);p-data=x;p-next=top;top=p;,3.1 栈,(2)出栈算法主要语句 if(top=NULL)return(NULL);p=top;top=p-next;return(p);若带头结点L的链栈进栈、出栈算法主要语句？,小 结 1 栈是限定仅能在表尾一端进行插入、删除操作的线性表；2 栈的元素具有后进先出的特点；3 栈顶元素的位置由一个称为栈顶指针的 变量指示，进栈、出栈操作要修

8、改栈顶指针；,3.1 栈,3.2 栈的应用举例,例1 数制转换 对于输入的任意一个非负十进制数，显示输出与其等值的八进制数,数制转换方法 N=(Ndiv8)10 8+N mod 8 N：十进制数，div：整除运算，mod：求余运算；(1348)10=283+582+08+4=(2504)8 N 1348 168 21 2 N div 8 168 21 2 0 N mod 8 4 0 5 2,计算时从低位到高位顺序产生八进制数的各个数位,结果：2 5 0 4,显示时按从高位到低位的顺序输出,3.2 栈的应用举例,void conversion()InitStack(s);/建空栈 scanf(“

9、%d”,例 2.判括号匹配问题 设表达式中包含三种括号：圆括号、方括号和花括号，可互相嵌套，如()或()。算法思想：设一个栈，每读入一个括号，若是左括号，直接入栈，等待相匹配的同类右括号；若是右括号，且与当前栈顶的左括号同类型，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况。如果输入序列已读尽，而栈中仍有等待匹配的左括号，或者读入了一个右括号，栈中已无等待匹配的左括号，均属不合法的情况。当输入序列和栈同时变为空时，说明所有括号完全匹配。,void BracketMatch(char*str)/str中为输入的字符串，利用栈来检查该字符串中的括号是否匹配 InitStack(,else G

10、etTop(,例3.表达式求值,表达式求值是编译中的基本问题，是栈的典型应用。任何一个表达式是由操作数、运算符和界限符组成的。操作数可以是变量或常量；运算符分为算术运算符、关系运算符和逻辑运算符三类 界限符有左右括号和表达式结束符等。,表达式运算顺序：由于某些运算符可能有更高的优先级，因此表达式不可能严格的从左到右进行运算。#代表开始或结束符,表达式的求值：例 5+6(1+2)-4 按照四则运算法则，上述表达式的计算过程为：5+6(1+2)-4=5+6 3-4=5+18-4=23-4=19,3.2 栈的应用举例,1,2,3,4,带括号算术表达式 假设操作数是整型常数，运算符只含加、减、乘、除

11、界限符有左右括号和表达式起始、结束符“”，如：15*（23-28/4）。引入表达式起始、结束符是为了方便。算术四则运算的规则，即：(1)从左算到右；(2)先乘除，后加减；(3)先括号内，后括号外。,运算符和界限符统称为算符，它们构成的集合命名为OP。根据上述三条运算规则，在运算过程中，任意两个前后相继出现的算符1和2之间的优先关系必为下面三种关系之一：12，1的优先权高于2 1在左，2在右,算符之间的优先关系,算符优先算法需要两个工作栈：存放运算符的optr；存放操作数或中间结果的opnd。算法的基本思想：1、初始化操作数栈opnd和运算符栈optr，并将表达式起始符“”压入运算符栈optr；

12、2、依次读入表达式中的每个字符，若是操作数则入操作数栈opnd，若是运算符，则与运算符栈optr的栈顶运算符进行优先权比较：,(1)若栈顶运算符的优先级低于刚读入的运算符，则让刚读入的运算符进optr栈；(2)若栈顶运算符的优先级高于刚读入的运算符，则将栈顶运算符退栈，送入，同时将操作数栈opnd出栈两次，得到两个操作数a、b，对a、b进行运算，将运算结果作为中间结果入opnd栈；(3)若栈顶运算符的优先级与刚读入的运算符的优先级相同，说明左右括号相遇，将栈顶运算符（左括号）退栈。,3.2 栈的应用举例,表达式求值算法int express()/OP为运算符集合。InitStack(OPTR)

13、;Push(OPTR,#);InitStack(OPND);w=Getchar();While(w!=#|GetTop(OPTR)!=#)if(!In(w,OP)/判断W是否 是运算符 Push(OPND,w);w=getchar();/不是运算符则进栈 else,switch(Precede(GetTop(OPTR),w)case:/新输入的算符优先级低，取栈顶算符 运算Pop(OPTR，T);Pop(OPND，b);Pop(OPND，a);Push(OPND,Operate(a,T,b);break;return GetTop(OPND);,3.3 栈与递归,栈非常重要的一个应用是用来实现

14、子程序调用与递归。,3.3 栈与递归,一般函数的调用机制,A()B();,C(),B()C();,后调用的函数先返回,函数调用机制可通过栈来实现,计算机正是利用栈来实现函数的调用和返回的,3.3 栈与递归,1什么是递归在数学和程序设计等许多领域中都用到了递归。递归定义：一个用自己定义自己的概念,称为递归。例 n!=1*2*3*4*(n-1)*n n!递归定义:n!=1 当 n=1 时 n!=n*(n-1)!当n 1 时,用(n-1)!定义n!,3.3 栈与递归,2 递归函数：如果一个函数在其定义体内直接调用自己，则称为直接递归函数；如果一个函数通过其它函数间接调用自己，则称其为间接递归函数。,

15、A（）A();,B()C()C();B();,A 直接调用自己,B间接调用自己,3.3 栈与递归,3递归算法的编写将问题用递归的方式定义终止项：递归终止时问题的求解；递归项：问题分解为与原问题性质相同，但规模较小的问题；例 n!的递归定义：终止项：n!=1 当 n=1 递归项：n!=n*(n-1)!当 n 1,用(n-1)!定义n!,3.3 栈与递归,例 n!的递归算法int fact(int n)/求解并返回n的阶乘 if（n=1）return（1）；else return（n*fact(n-1)）；,很多数学函数是递归定义的，如二阶斐波那契数列(Fibonacci)：,斐波那契数列的递归算

16、法Fib(n)：,int Fib(int n)if（n=0|n=1）return n;/递归出口 else return Fib(n-1)+Fib(n-2);/递归调用,递归调用过程的实现 递归调用时系统需要做三件事：(1)将所有的实在参数、返回地址等信息传递给被调用函数保存；(2)为被调用函数的局部变量分配存储空间；(3)将程序转移到被调函数的入口。,从被调用函数返回调用函数之前，系统也完成三件工作：(1)保存被调函数的计算结果；(2)释放被调函数所占空间；(3)依照被调函数保存的返回地址，将控制转移回调用函数。,例：n阶Hanoi塔问题：设有三个分别命名为X、Y和Z的塔座，在塔座X上插有n

17、个直径大小各不相同、依小到大编号为1，2,，n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排。圆盘移动时必须遵循下列原则：(1)每次只能移动一个圆盘；(2)圆盘可以插在X、Y和Z中的任何一个塔座上；(3)任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。,如何实现移动圆盘的操作呢？当n=1时，将编号为1的圆盘从塔座X直接移动到塔座Z上。当n1时，需利用塔座Y辅助，（1）将上面n-1个圆盘从塔座X(依照上述原则)移至塔座Y上，（2）将编号为n的圆盘从塔座X 移至塔座Z上，（3）将塔座Y上的n-1个圆盘(依照上述原则)移至塔座Z上。而将n-1个圆盘从一个塔座移至另一个塔座问题是和原

18、问题具有相同特征属性的问题，只是问题的规模小个1，可以用同样方法求解。,void hanoi(int n,char x,char y,char z)/将X上的n个圆盘按规则搬到Z上，中间可用Y if(n=1)move(x,1,z);/将编号为1的圆盘从X移动Z else hanoi(n-1,x,z,y);/将X上n-1个圆盘移到Y,Z作辅助 move(x,n,z);/将编号为n的圆盘从X移到Z hanoi(n-1,y,x,z);/将Y上n-1个圆盘移动到Z，X作辅助,Hanoi塔的递归函数运行示意图,三个盘子搬动时hanoi(3,A,B,C)递归调用过程：,hanoi(2,A,C,B):han

19、oi(1,A,B,C)move(A-C)1号搬到C move(A-B)2号搬到B hanoi(1,C,A,B)move(C-B)1号搬到B move(A-C)3号搬到C hanoi(2,B,A,C):hanoi(1,B,C,A)move(B-A)1号搬到A move(B-C)2号搬到C hanoi(1,A,B,C)move(A-C)1号搬到C,递归算法的特点：(1)递归算法是一种分而治之、把复杂问题分解为简单问题的求解问题方法，对求解某些复杂问题，递归算法的分析方法是非常有效的。（2）递归算法的时间效率、空间效率较低，因为递归执行时需要系统提供隐式栈实现递归。,简单情况下，可将递归算法简化为线

20、性序列(递推)执行，如直接转换为循环实现。,例：n!n!=1 当 n=1 时 n!=n(n-1)!当n 1 时,阶乘问题用循环结构的算法Fact(n)：,long Fact(int n)fac=1;for(int i=1;i=n;i+)/依次计算f(1)，f(n)fac=fac*i;return fac;,小 结 1设计递归算法的方法：(1)寻找方法，将问题化为原问题的子问题求解（例n!=n*(n-1)!）。(2)设计递归出口，确定递归终止条件(例当n=1时，n!=1)。2 调用三件事：传递本层参数、返回地址；分配局部变量空间;控制转移。调用结束三件事：恢复上层；传递结果；转断点执行。,3.3

21、 栈与递归,3.4 队列3.4.1 队列的概念3.4.2 循环队列 队列的顺序存储和实现3.4.3 队列的链式存储和实现,34 队列,3.4.1 队列的概念一 什么是队列,队列是限定仅能在表头进行删除，表尾进行插入的线性表,（a1,a2,.,ai-1,ai,ai+1,an）,插入,删除,34 队列,a1 a2 a3 an,入队列,队头,队尾,出队列,队 列 的 示 意 图,队列的特点先进先出,第一个入队的元素在队头，最后一个入队的元素在队尾，第一个出队的元素为队头元素，最后一个出队的元素为队尾元素,34 队列,队列的基本操作1）初始化操作 2）置空操作3）判空、满操作 4）取队头元素操作5）入

22、队操作 6）出队操作,34 队列,队列类型定义#define MAXQSIZE 100 Typedef struct Sqqueue QelemType*base;int front;int rear;,rear,front,J1,rear,front,J2,（a)空队列,(b)J1,J2相继入队列,(c)J1出队,(d)J3,J4,J5和J6相继入队之后,J2出队,rear,front,3.4 队列,rear,front,J5,J4,J3,front,rear为整数,J2,J6,3.4 队列,3.4.2 循环队列,(b)队空,(a)队满,队空、队满都是front=rear,J7,3.4 队列

23、,判分队空、队满有两种方法：1）另设一个标志位以区分队空、队满。2）少用一个存储单元，队满条件：front=(rear+1)%MAXQSIZE;队空：front=rear队列中元素的个数？（rear front+MAXQSIZE）%MAXQSIZE,front,（c）,3.4 队列,循环队列的基本操作算法 P64-65,建一个空队列Q,3.4 队列,入队操作：将元素 x 插入队尾,元素 x 入队前,元素 x 入队后,3.4 队列,出队操作：删除队头元素；,3.4.3 链队列队列的链式存储结构和实现,front,rear,空链队列,front,rear,链队列图示,3.4 队列,3.4 队列,二

24、 链队列的类型定义,typedef struct Qnode QelemType data;struct Qnode*next;Qnode;QNODE*front,*rear;P61,3.4 队列,链队列的基本操作入队、出队算法 P62,3.4 队列,三 队列的应用,1）解决计算机主机与外设不匹配的问题；2）解决由于多用户引起的资源竞争问题；,3）离散事件的模拟-模拟实际应用中的各种排队现象；4）用于处理程序中具有先进先出特征的过程；,在操作系统课程中会讲到,队列的应用举例,打印杨辉三角,杨辉三角形,杨辉三角形元素入队顺序,打印杨辉三角形的前N行元素的算法：,void YangHuiTriangle()InitQueue(/打印第n-1行的最后一个元素 EnterQueue(&Q,1)/第n行的最后一个元素入队,小 结 1 队列是限定仅能在表尾一端进行插入，表头一端删除 操作的线性表；2 队列中的元素具有先进先出的特点；3 队头、队尾元素的位置分别由称为队头指针和队尾指针的变量指示，4 入队操作要修改队尾指针，出队操作要修改队头指针；,