电子科数据结构pascal版课件ds第三章

第三章 栈和队列3.1 栈的表示和实现3.2 递归过程3.2 队列的表示和实现栈和队列的逻辑结构、物理结构，以及它们之间的相互关系；定义与之相适应的运算；设计相应的算法；分析算法的效率。

一、栈的概念

栈（stack）是插入和删除操作限定在表尾进行的线性表。

栈的逻辑表示为：S=（a1,a2,…,an）表尾元素an称为栈顶(top)

表头元素a1称为栈底(bottom)不含元素的空表称为空栈栈的运算特性是

后进先出(LastInFirstOut——LIFO)

或先进后出(First

InLastOut——FILO)

3.1栈的表示和实现

3.1栈的表示和实现二、栈的基本运算INISTACK(S)初始化操作，设定一个空栈SEMPTY(S)判栈S是否为空函数（true/false）PUSH(S,x)入栈操作，在栈S顶部插入元素x，相当于线性表的INSERT(L,n+1,x)POP(S)出栈函数，若S不空，则返回栈顶元素，并删除栈顶元素；否则返回空元素(NULL)，相当于线性表的DELETE(L,n)GETTOP(S)取栈顶元素函数，与POP(S)的差别在不删除栈顶元素，相当于线性表的GET(L,n)CURRENT-SIZE(S)求S栈中当前元素个数函数，相当于线性表的LENGTH(L)CLEAR(S)置栈空操作3.1栈的表示和实现三.栈的表示和实现1.顺序栈的存储结构描述及出入栈运算

CONSTarrmax=栈允许存放元素个数的最大值；

TYPEsqstktp=RECORD

elem：ARRAY[1..arrmax]OFelemtp；top：0..arrmaxEND；VARS:sqstktp；S.elem[i]表示第i个进栈的元素

S.elem[S.top]表示栈顶元素当S.top=0表示空栈当S.top=arrmax表示栈满3.1栈的表示和实现入栈函数PUSH(S，x)的实现算法思想：若栈满返回false；否则将x入栈，并返回true。

FUNC

push_stack(VARs：sqstktp；x：elemtp)：boolean；IFs．top=arrmax

THEN

RETURN（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=0

THEN

RETURN（NULL）

ELSE[s．top：=s．top-1；RETURN（s．elem[s．top+1]）]

ENDF；{pop_stack}3.1栈的表示和实现2.链栈的存储结构描述

TYPEpointer=↑nodetype；nodetype=RECORDdata：elemtp；next：pointerEND；linkstktp=pointer；3.1栈的表示和实现栈(a1,a2,…,an)表示为...anan-1a1top单链表不带头结点栈顶在链表的头，用top指向栈顶元素结点^3.1栈的表示和实现PUSH(S,x)的实现

new(s);s.data:=x;s.next:=top;top:=s;POP(S)的实现

IFtop=NILTHENRETURN(NULL)ELSE[p:=top;top:=top.next;x:=p.data;dispose(p);RETURN(x)]3.2递归过程

递归是栈的另一个重要应用，也是程序设计的一个强有力的工具。1.应用递归的原因和领域

递归定义

┏1当n=0

阶乘n!=┃┗n*(n-1)!当n>0┏0n=0Fibonacci数列Fib(n)=┃1

n=1┗Fib(n-1)+Fib(n-2)n>1

递归结构

后面将要介绍的二叉树，广义表结构本身固有递归特性，操作也可递归描述。用递归求解更简单

例：计算两个非负整数a*b的算法1.递归方式：a*b=b+(a-1)*b

FUNCmul1(a，b：integer)：integer；IFa=0THENRETURN(0)ELSERETURN(b+mul1(a-1，b))ENDF；{mul1}3.3递归过程迭代方式：a*b=a个b之和FUNCmul2(a，b：integer)：integer；z：=0；FORi：=1TOaDOz：=z+b；RETURN(z)ENDF；{mul2}3.3递归过程2.递归过程的特点：是程序设计的一个强有力的工具，它具有结构清晰，程序易编、易读、易调试，程序正确性易证明等优点；但运行效率低。3.基本原理：基本原理是重复地把问题转化为与原问题相似的新问题，直到问题可解决为止。4.关键点：①用较简单的新问题来表示较复杂的原问题例如：n！=n(n-1)！，或n!=(n+1)！/(n+1)

前者(n-1)！较原问题n！简单，可行；而后者(n+1)！较n！更复杂，不可行。②不能产生自己调用自己的无穷序列，即必须有一个递归调用序列的“出口”，来终止递归调用。5.实现：递归过程都是通过栈来实现的，并且任何递归算法均可通过栈改写为非递归算法。3.3递归过程6.汉诺（Hanoi)塔问题

设：有X、Y、Z三个塔座，在X上按直径大小递减次序依次插有n个直径各不相同的圆盘，各圆盘按直径从小到大编为1~n

要求：将X塔上的n个圆盘按规则移至Z上，并仍按同样顺序叠排

移动规则：①每次只能移动一个圆盘；②移动的圆盘可以插在任一塔座上，但是在任一时刻都不能将大盘压在小盘上。XYZ1n算法思想：当n=1：只需将该圆盘从X移到Z即可；当n>1：若能将压在n号盘上的n-1个圆盘按规则移至Y，然后把n号盘从X移到Z上，最后再将Y上的n-1个圆盘按规则移至Z上。原问题为：hanoi(n，X，Y，Z)

化简为：hanoi(n-1，X，Z，Y)

move(X，n，Z)把X上的n号盘移到Z上

hanoi(n-1，Y，X，Z)3.3递归过程PROChanoi(n：integer；X，Y，Z：char)；IFn=1THENmove(X，n，Z)ELSE[hanoi(n-1，X，Z，Y)；

move(X，n，Z)；

hanoi(n-1，Y，X，Z)]ENDP；{hanoi}3.3递归过程例:三个盘子的移动过程(1)XZ(2)XY(3)ZY(4)XZ(5)YX(6)YZ(7)XZ12131213.3递归过程(3,x,y,z)(2,x,z,y)(1,x,y,z)——move(x,1,z)move(x,2,y)(1,z,x,y)——move(z,1,y)move(x,3,z)(2,y,x,z)(1,y,z,x)——move(y,1,x)move(y,2,z)(1,x,y,z)——move(x,1,z)一、队列的概念队列（queue）是限定在一端插入,另一端删除的线性表。允许插入的一端叫队尾(rear),允许删除的一端叫队头(front),不含元素的空表称为空队列队列的运算特性是先进先出(FirstInFirstOut--FIFO)

3.3队列的表示和实现出队列入队列a1a2…...an队头队尾

二、队列的基本运算

INIQUEUE（Q）

初始化操作，设置一个空队列

EMPTY(Q)

判定队列是否为空函数（true/false）

ENQUEUE(Q，x)

入队列操作，队尾插入元素x

DLQUEUE(Q)

出队函数（删除）

GETHEAD(Q)

取队头元素函数

CLEAR(Q)

队列置空操作

CURRENT-SIZE(Q)

求队列Q当前元素个数

3.4队列的表示和实现三、队列的链式存储结构——链队列

1．存储结构链队列需要队头和队尾两个指针来确定。TYPEqueueptr=queuenodequeuenode=RECORDdata：elemtp；next：queueptrEND；linkedquetp=RECORDfront，rear：queueptrEND；给链队列添加个头结点，并令头指针指向头结点。链队列为空时，头尾指针均指向头结点即q．front=q．rear（且q.front.next=NIL）

3.4队列的表示和实现<队头指针q．front队尾指针q．rear...a1an

2．出队算法

FUNCdl_linkedque(VARq:linkedquetp):elemtp；IFq.front=q.rearTHENRETURN(NULL)

ELSE[s:=q.front↑.next；q.front↑.next:=s↑.next；IFs↑.next=NILTHENq.rear:=q.front；x:=s↑.data；dispose(s)；RETURN(x)]ENDF；{dl_linkedque}删除时的三种情形：a.删除前已空；b.删除前只有一个结点，删除后为空队列；c.其他情形（删除前结点数>1）

3.4队列的表示和实现思考：在什么情况下出队要修改q.rear(队尾)指针？为什么？3.入队算法PROCen_linkedque(VARq：linkedquetp；x：elemtp)；new(p)；p↑.data：=x；p↑.next：=NIL；q.rear↑.next：=p；q.rear：=pENDP；

3.4队列的表示和实现思考：如果将空队列定义为q.front↑.next=NIL,出队和入队算法需要做哪些修改？四、队列的顺序存储结构1.一般顺序存储结构用一个向量来存放队列元素，并用两个指针来指示队头和队尾。并约定：头指针sq.front总是指向队头元素的前一个位置；尾指针sq.rear指向队尾元素。

CONST=…；TYPEsequeuetp=RECORDelem:ARRAY[1..maxsize]0Felemtp；front,rear:0..maxsizeEND；

3.4队列的表示和实现初始时：sq.front=sq.rear=0空队列条件：sq.front=sq.rear出队时：IFsq.rear=sq.frontTHENRETURN（NULL）

ELSE[sq.front:=sq.front+1；RETURN（sq.elem[sq.front]）]入队时：IFsq.rear=maxsizeTHENERROR(`队满`)

ELSE[sq.rear:=sq.rear+1；sq.elem[sq.rear]:=x]

3.4队列的表示和实现

3.4队列的表示和实现考虑队满条件，即当sq.rear=maxsize时，是否整个存储空间都已占用？maxsize1sq.rearsq.front此时，sq.rear=maxsize且队满。maxsize1sq.rearsq.front此时，尽管sq.rear=maxsize,但队列中实际元素并不足maxsize个，仍有sq.front个空闲单元，称这种情形为“假溢出”。

3.4队列的表示和实现2.循环队列结构把队列视为一个循环表，即sq.elem[maxsize]之后是数组的第一个元素。CONSTmaxsize=队列的最大容量；m=maxsize-1；TYPEcyclicquetp=RECORDelem:ARRAY[0..m]OFelemtp

rear，front：0..mEND；可采用mod运算（取余数）来实行循环队列的运算:入队时：cq.rear:=(cq.rear+1)modmaxsize；cq.elem[cq.rear]:=x；

出队时：

cq.front:=(cq.front+1)modmaxsizeIFsq.rear+1=maxsizeTHENsq.rear:=0ELSEsq.rear:=sq.rear+1此时,队空.有cq.front=cq.rear此时,队满.有cq.front=cq.rear例.m=5,初始状态和操作过程如下:

3.4队列的表示和实现ABCEDcq.frontcq.rearABCEDcq.frontcq.rearF将F入队Ecq.frontcq.rear连续4次出队cq.frontcq.rear再出队

队满和队空时，均有cq.front=cq.rear。

因此，只凭cq.front=cq.rear还无法区分是满还是空。如何判定队满还是空？是循环队列要解决的新问题。

3.4队列的表示和实现方法一：用一个计数变量来记载队列中的元素个数。初始化队列时c:=0;当入队时，计数变量＋1（c:=c+1）当出队时，计数变量－1（c:=c-1）当计数变量＝maxsize时，队满当计数变量＝0时，队空方法二：设一个标志位用来区别队列是空还是满。初始化队列时：cq.front=cq.rear，标志位为false

入队后，使cq.front=cq.rear，则置标志位为true

出队后，将标志位置为false

当cq.front=cq.rear,且标志位为true时，队满。

当cq.front=cq.rear,但标志位为false时，队空。