考研数据结构cha.ppt

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

2、本运算 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.

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 栈的表示和实现,入栈函数push(S，x)的实现 算法思想：若栈满返回false；否则将x入栈，并返回true。 FUNC push_stack (V

4、AR s：sqstktp；x：elemtp)：boolean； IF stop = armax THEN RETURN（false） ELSE stop：=stop+1； selemstop：= x； RETURN（true） ENDF；push_stack ,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 ） E

5、NDF；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 递归结构 后面将要介绍的二叉树，广义表结

6、构本身固有递归特性，操作也可递归描述。 用递归求解更简单,例：计算两个非负整数a*b的算法 1. 递归方式：a*b = b+ (a-1)*b FUNC mul1(a，b：integer)：integer； IF a = 0 THEN RETURN(0) ELSE RETURN( b + mul1( a-1，b) ENDF；mul1,3.2 递归过程,2. 迭代方式：a*b = a个b之和 FUNC mul2(a，b：integer)：integer； z：= 0； FOR i：=1 TO a DO z：= 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个直径各不相同的圆盘，各圆盘按直径从小到大编为1n。 要求：将X 塔上的n个圆盘按规则移至Z上，并仍按同样顺序叠排。 移动规则： 每次只能移动一个圆盘；移动的圆盘可以插在任一塔座上，但是在任一时刻都不能将大盘压在小盘上。,算法思想：当n=1：只需将该圆盘从X移到Z即可； 当n1：若能将压在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上的

9、n号盘移到Z上 hanoi(n-1，Y，X，Z),3.2 递归过程,PROC hanoi(n：integer；X，Y，Z：char)； IF n=1 THEN move(X，n，Z) ELSE hanoi(n-1，X，Z，Y)； move(X，n，Z)； hanoi(n-1，Y，X，Z) ENDP；hanoi,一、队列的概念 队列（queue）是限定仅在一端插入,另一端删除的线性表。 允许插入的一端叫队尾( rear), 允许删除的一端叫队头(front), 不含元素的空表称为空队列 队列的运算特性是先进先出(First In First Out-FIFO),3.3 队列的表示和实现,二、队列

10、的基本运算 INIQUEUE（Q） 初始化操作，设置一个空队列 EMPTY(Q) 判定队列是否为空函数（true/false） ENQUEUE(Q，x) 入队列操作，队尾插入元素x DLQUEUE(Q) 出队函数 GETHEAD(Q) 取队头元素且删除 CLEAR(Q) 队列置空操作 CURRENT-SIZE(Q) 求队列Q当前元素个数,3.3 队列的表示和实现,三、队列的链式存储结构链队列 1存储结构 链队列需要队头和队尾两个指针来确定。 TYPE queueptr = queuenode queuenode = RECORD data：elemtp； next：queueptr END；

11、linkedquetp = RECORD front，rear：queueptr END； 给链队列添加个头结点，并令头指针指向头结点。 空链队列有头尾指针均指向头结点 即qfront = qrear,3.3 队列的表示和实现,. . .,2出队算法 FUNC dl_linkedque(VAR q:linkedquetp):elemtp； IF q.front=q.rear THEN RETURN(NULL) ELSE s:= q.front.next； q.front.next:=s.next； IF s.next=NIL THEN q.rear:=q.front； x:=s.data； d

12、ispose(s)； RETURN(x) ENDF； dl_linkedque 删除时的三种情形： a.删除前已空； b.删除前只有一个结点，删除后为空队列； c.其他情形（删除前结点数1）,3.3 队列的表示和实现,思考：在什么情况下出队要修改q.rear (队尾)指针？为什么？,3 入队算法 PROC en_linkedque(VAR q：linkedquetp； x：elemtp)； new(p)； p.data：= x； p.next：= NIL； q.rear.next：= p；q.rear：= p ENDP；,3.3 队列的表示和实现,思考： 如果将空队列定义为q.front.ne

13、xt = NIL, 出队和入队算法需要做哪些修改？,四、队列的顺序存储结构 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 T

14、HEN 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时，是否整个存储空间都已占用？,3.3 队列的表示和实现,2. 循环队列结构 把队列视为一个循环表，即sq.elemmaxsize之后是数组的第一个元素。 CONST maxsize = 队列的最大容量； m=maxsize-1； TYPE cy

15、clicquetp=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.f

16、ront=cq.rear,例. m=5,初始状态和操作过程如下:,3.3 队列的表示和实现,队满和队空时，均有cq.front=cq.rear。 因此，只凭cq.front=cq.rear还无法区分是满还是空。 如何判定队满还是空？是循环队列要解决的新问题。,3.3 队列的表示和实现,方法一 ：用一个计数变量来记载队列中的元素个数。 初始化队列时c:=0; 当入队时，计数变量1（ c:=c+1 ） 当出队时，计数变量1 （c:=c-1） 当计数变量maxsize时，队满 当计数变量0时，队空,方法二：设一个标志位用来区别队列是空还是满。 初始化队列时：cq.front=cq.rear，标志位为

17、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。 初值