第03章-栈和队列-数据结构-(第二版)-教学.ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第三章 栈和队列,3.1栈的表示和实现,3.2递归过程,3.3队列的表示和实现,栈和队列的逻辑结构、物理结构，以及它们之间的相互关系；,定义与之相适应的运算；,设计相应的算法；,分析算法的效率。,一、栈的概念,栈,（,stack）,是,插入,和,删除,操作限定在,表尾,进行的,线性表,。,栈的逻辑表示为：,S=,（a,1,a,2,a,n,）,表尾元素,a,n,称为,栈顶,(,top),表头元素,a,1,称为,栈底,(,bottom),不含元素的空表称为,空栈,栈的运算特性是后进先出(,Last In First Out-,LIFO,),或先进后出(,First,In Last Out-,FILO,),3.1 栈的表示和实现,3.1 栈的表示和实现,二、栈的基本运算,INISTACK(S),初始化操作，设定一个空栈,S,EMPTY(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.1 栈的表示和实现,三.栈的表示和实现,1.顺序栈的存储结构描述及出入栈运算,CONST arrmax=,栈允许存放元素个数的最大值；,TYPE sqstktp=RECORD,elem：ARRAY1arrmax OF elemtp；,top：0arrmax,END；,S=sqstktp；,Selemi,表示第,i,个进栈的元素,SelemStop,表示栈顶元素,当,Stop=0,表示空栈,当,Stop=arrmax,表示栈满,3.1 栈的表示和实现,出栈函数,pop(S),的实现,算法思想,：,若栈空则返回空元素,NULL；,否则返回栈顶元素。,FUNC,pop_stack(,VAR,s：sqstktp)：elemtp；,IF,stop=0,THEN,RETURN,（NULL）,ELSE,stop：=stop-1；,RETURN,（selemstop+1）,ENDF,；pop_stack,3.1 栈的表示和实现,2.链栈的存储结构描述,TYPE pointer=nodetype；,nodetype=RECORD,data：elemtp；,next：pointer,END；,linkstktp=pointer；,3.2 递归过程,递归是栈的另一个重要应用，也是程序设计的一个强有力的工具,。,1.,应用递归的原因和领域,递归定义,1,当,n=0,阶乘,n!=,n*(n-1)!,当,n 0,0 n=0,Fibonacci,数列,Fib(n)=,1,n=1,Fib(n-1)+Fib(n-2)n 1,递归结构,后面将要介绍的二叉树，广义表结构本身固有递归特性，操作也可递归描述。,用递归求解更简单,3.2 递归过程,2.递归过程的特点：,是程序设计的一个强有力的工具，它具有结构清晰，程序易编、易读、易调试，程序正确性易证明等优点；但运行效率低。,3.基本原理：,基本原理是重复地把问题转化为与原问题相似的新问题，直到问题可解决为止。,4.关键点,：,用较简单的新问题来表示较复杂的原问题 例如：,n！,=,n(n-1)！，,或,n!=(n+1)！/(n+1),前者(,n-1)！,较原问题,n！,简单，可行；而后者(,n+1)！,较,n！,更复杂，不可行。,不能产生自己调用自己的无穷序列，即必须有一个递归调用序列的“出口”，来终止递归调用。,5.实现：,递归过程都是通过栈来实现的，并且任何递归算法均可通过栈改写为非递归算法。,3.2 递归过程,6.汉诺（,Hanoi),塔问题,设,：有,X、Y、Z,三个塔座，在,X,上按直径大小递减次序依次插有,n,个直径各不相同的圆盘，各圆盘按直径从小到大编为1,n。,要求,：将,X,塔上的,n,个圆盘按规则移至,Z,上，并仍按同样顺序叠排。,移动规则,：每次只能移动一个圆盘；移动的圆盘可以插在任一塔座上，但是在任一时刻都不能将大盘压在小盘上。,X,Y,Z,1,n,一、队列的概念,队列,（,queue）,是限定仅在一端插入,另一端删除的线性表。,允许插入的一端叫,队尾,(,rear),允许删除的一端叫,队头,(,front),不含元素的空表称为,空队列,队列的运算特性是先进先出(,First In First Out-,FIFO,),3.3 队列的表示和实现,出队列,入队列,a,1,a,2,.a,n,队头,队尾,三、队列的链式存储结构链队列,1,存储结构,链队列需要队头和队尾两个指针来确定。,TYPE,queueptr=queuenode,queuenode=RECORD,data：elemtp；,next：queueptr,END；,linkedquetp=RECORD,front，rear：queueptr,END；,给链队列添加个头结点，并令头指针指向头结点。,空链队列有头尾指针均指向头结点,即,qfront=qrear,3.3 队列的表示和实现,1）,3.3 队列的表示和实现,思考：,在什么情况下出队要修改,q,.,rear(,队尾)指针？为什么？,四、队列的顺序存储结构,1.一般顺序存储结构,用一个向量来存放队列元素，并用两个指针来指示队头和队尾。并约定：头指针,sq.front,总是指向队头元素的前一个位置；尾指针,sq.rear,指向队尾元素。,TYPE sequeuetp=RECORD,elem:ARRAY1.maxsize 0F elemtp；,front,rear:0.maxsize,END；,3.3 队列的表示和实现,初始时,：,sq.front=sq.rear=0,空队列条件,：,sq.front=sq.rear,出队时,：,IF sq.rear=sq.front THEN ERROR(,队空）,ELSE sq.front:=sq.front+1,入队时,：,IF sq.rear=maxsize THEN ERROR(,队满),ELSE sq.rear:=sq.rear+1；,sq.elemsq.rear:=x,3.3 队列的表示和实现,3.3 队列的表示和实现,考虑队满条件，即当,sq.rear=maxsize,时，是否整个存储空间都已占用,？,maxsize,1,sq,.,rear,sq,.,front,此时，,sq.rear=maxsize,且队满。,maxsize,1,sq,.,rear,sq,.,front,此时，尽管,sq.rear=maxsize,但队列中实际元素并不足,maxsize,个，仍有,sq.front,个空闲单元，称这种情形为“假溢出”。,3.3 队列的表示和实现,2.循环队列结构,把队列视为一个循环表，即,sq.elemmaxsize,之后是数组的第一个元素。,CONST maxsize=,队列的最大容量；,m=maxsize-1；,TYPE cyclicquetp=RECORD,elem:ARRAY 0.m OF elemtp,rear，front：0.m,END；,可采用,mod,运算（取余数）来实行循环队列的运算,:,入队时：,cq,.,rear,:,=(cq,.,rear+1)mod maxsize；,cq,.,elemcq,.,rear,:,=x；,出队时：,cq,.,front,:,=(cq,.,front+1)mod maxsize,IF sq,.,rear+1=maxsize,THEN sq,.,rear,:,=0,ELSE sq,.,rear,:,=sq,.,rear+1,此时,队空.有,cq.front=cq.rear,此时,队满.有,cq.front=cq.rear,例.,m,=5,初始状态和操作过程如下:,3.3 队列的表示和实现,A,B,C,E,D,cq.front,cq.rear,A,B,C,E,D,cq.front,cq.rear,F,将,F,入队,E,cq.front,cq.rear,连续4次出队,cq.front,cq.rear,再出队,方法二：,设一个标志位用来区别队列是空还是满。,初始化队列时：,cq.front=cq.rear，,标志位为,false,入队后，使,cq.front=cq.rear，,则置标志位为,true,出队后，将标志位置为,false,当,cq.front=cq.rear,且标志位为,true,时，,队满,。,当,cq.front=cq.rear,但标志位为,false,时，,队空,。,其他为非空非满。,3.3 队列的表示和实现,方法三,：,牺牲一个元素空间，来区别队空或队满。,入队前，先判,cq.rear+1,是否等于,cq.front,，,若是则为队满。,而当,cq.front=cq.rear,时，为队空。,前例：当,E,入队后，就认为队已满，,而当,F,再要入队时，就拒绝入队。,3.3 队列的表示和实现,方法四,：,扩大,rear,和,front,的,定义域为0.,maxsize,。,初值,rear=0；front=maxsize,入队前，先判,rear,是否=,maxsize,是则为对满。,当入队后,使得,cq.rear=cq.front,，,则令,cq.rear=maxsize,，,表示队满。,若,cq.front=maxsize,则,cq.front:=cq.rear-1,出队前，先判,front,是否=,maxsize,是则为队空。,当出队后，使得,cq.front=cq.rear,则令,cq.,front:=maxsize,表示队空。,若,cq.,rear=maxsize,则,cq.rear:=cq.front-1,3.3 队列的表示和实现,