北大数据结构课讲义7

1、第四章 栈和队列 4.1 栈 4.2 栈的顺序存储结构和操作实现 4.3 栈的链接存储结构和操作实现 4.4 栈的简单应用举例4.5 算术表达式的计算4.6 栈与递归4.7 队列退出4.1 栈 栈的定义栈（stack）又称堆栈，是限定只在表尾进行插入或删除操作的线性表。栈S = ( a1, a2, ，an )是按a1, a2, ，an次序进栈的，a1为栈底元素，an为栈顶元素。 栈与递归递归可使问题及求解步骤的描述变得简洁而清晰。特别是对于复杂问题，用递归方法分析描述，比较自然，利于理解。递归包括递归步骤和终止出口。递归问题转化为非递归往往要用栈来实现,把在递归中用到的变量入栈出栈,如书上【习

2、题4-4】之9,104.7 队列队列是一种先进先出（FIFO）线性表。只允许在其一端删除元素，即队头（front），只允许在其另一端插入元素，即队尾（rear）。图 4-10 顺序队列的插入和删除操作0 1 2 3 4 M-2 M-101234M-1M-2: 循环队列 把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为循环队列。入队时需先修改入队指针（队尾指针） rear = = (rear +1)% QueueMaxSize出队时需要修改队头指针front = (front +1)% QueueMaxSize 初始时, 队列为空,

3、 有 front=0 rear=0测试队列为空的条件是 front=rear 1 Mabcdfrontrearad约定 rear 指出实际队尾元素所在的位置,front 指出实际队头元素所在位置的前一个位置.队列的静态数组一般是循环使用的。为了判别队列满和队列空的指针状况，令front指向队首元素的前一个位置。入队时需先修改入队指针（队尾指针） rear = = (rear +1)% QueueMaxSize 然后判断队列满的条件 (rear+1)% QueueMaxSize = front最后将元素入队。出队时先判断队列空的条件 front = rear然后修改队头指针 front = (f

4、ront +1)% QueueMaxSize 最后将元素出队。在顺序队列中插入和删除，不需要比较和移动任何元素，只需修改队尾和队首指针，并向队尾写入元素或从队首取出元素时间复杂度为：O(1)若存储队列的数组的长度为N，则队列长度（即所含元素个数）为:(N+rear-front)%N（2）队列的链式存储结构struct LinkQueue LNode* front;LNode* rear;struct LNode ElmeType data;LNode* next;struct LNode ElemTypedata; / 数据域 Lnode*next; / 指针域 ; 在链队中插入和删除，不需要

5、比较和移动任何元素，只需修改个别相关指针和进行结点的动态分配或回收操作时间复杂度为：O(1)4.4.4 队列运算的实现1. 队列运算在顺序存储结构上的实现（1）初始化队列void InitQueue(Queue& Q)Q.MaxSize=10;Q.queue=new ElemTypeQ.MaxSiize;Q.front=Q.rear=0;（2）将队列清空,并释放动态存储空间void ClearQueue(Queue& Q)if(Q.queue!=NULL) delete Q.queue;Q.front=Q.rear=0;Q.queue=NULL;Q.MaxSize=0;（3）检查队列是否为空i

6、nt QueueEmpty(Queue& Q)return Q.front=Q.rear;（4）读取队头元素/让front指针不是指向队首元素，而是指向它的前一个位置即：队首元素是队首指针front的下一个位置中的元素ElemType PeekQueue(Queue& Q) if(Q.front=Q.rear)cerrQueue is Empty.endl;exit(1); return Q.queue(Q.front+1)%QueueMaxSize;（5）向队列插入新元素-1void EnQueue(Queue& Q, const ElemType& item)int k=(Q.rear+1

7、)%QueueMaxSize;/队尾的下一位置if(k=Q.front)cerrQueue is overflow.endl;exit(1);Q.rear=k;Q.queuek=item;入队时需先修改入队指针（队尾指针） rear = (rear +1)% QueueMaxSize 然后判断队列满的条件 (rear+1)% QueueMaxSize = front最后将元素入队。（5）向队列插入新元素-2void EnQueue(queue& Q, const ElemType& item)if(Q.rear+1)%QueueMaxSize=Q.front) /扩大2倍的存储空间int k=

8、sizeof(ElemType);Q.queue=(ElemType*)realloc(Q.queue, 2*Q.MaxSize*k); /把原队列尾部内容后移MaxSize个位置if(Q.rear!=Q.MaxSize-1) for(int i=0; i=q.rear; i+)Q.queuri+Q.MaxSize=Q.queuri;Q.rear+=Q.MaxSize; Q.MaxSize=2*Q.MaxSize;/求出队尾的下一个位置Q.rear=(Q.rear+1)%Q.MaxSize;/把item的值赋给新的队尾位置Q.queueQ.rear=item;入队时需先修改入队指针（队尾指针）

9、 rear = (rear +1)% QueueMaxSize 然后判断队列满的条件 (rear+1)% QueueMaxSize = front最后将元素入队。（6）从队列中删除元素ElemType OutQueue(Queue& Q) if(Q.front=Q.rear)cerrQueue is empty.next;delete p;p=HQ.front;HQ.rear=NULL;struct LNode ElemTypedata; / 数据域 Lnode*next; / 指针域 ; （3）判断链队是否为空int QueueEmpty(LinkQueue & HQ)return HQ.f

10、ront=NULL;（4）读取队首元素ElemType PeekQueue(LinkQueue& HQ)if (HQ.front=NULL) cerr“Linked queue is empty.data;（5）向链队中插入一个元素void EnQueue (LinkQueue& HQ,const ElemType& item)LNode* newptr=new LNode;if (newptr =NULL) cerr“Memory alocation failure.data=item;newptr-next =NULL;if (HQ.rear=NULL) HQ.front=HQ.rear=

11、newptr;else HQ.rear=HQ.rear-next=newptr;/不妨与书上P78的算法9(ppt4,算法9)：向单链表的末尾插入一个元素“相对照学习/思考与书上P137的算法2(ppt6,算法5)：向链栈中插入一个元素“的不同（6）从队列中删除一个元素ElemType OutQueue(LinkQueue& HQ)if (HQ.front=NULL) cerr“Linked queue is empty.data;Lnode* p=HQ.front;HQ.front=p-next;if (HQ.front=NULL)HQ.rear=NULL;delete p;return t

12、emp;/不妨与书上P79的算法10(ppt4,算法12)：从单链表中删除表头元素“相对照学习/也可对照书上P137的算法3(ppt6,算法6)：从链栈中删除一个元素”4.4.6 队列应用简介第一：解决主机与外设之间速度不匹配的问题如：打印输出。设置一个打印数据缓冲区，用队列存储待输出的数据，解决主机与外设速度不匹配的问题。第二：解决多用户引起的资源竞争问题如：多用户CPU资源竞争。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列1. 熟悉栈的含义，掌握基本概念、存储结构和运算的实现。2.熟悉队列的含义，掌握基本概念、存储结构和运算的实现。本章学习要点本章习题(第173177页)

13、(!) 4.1.14.1.4 请独立完成该题4个问题(!) 4.2 请独立完成该题(#) 4.3 课外思考该题(!) 4.4.12,7 能在书上程序的基础上编写 程序实现(#) 4.4.36,811 有兴趣者课外思考书面回答,请以纸面形式上交课代表,要求整洁清楚，时间期限:5月10日 格式提头:学号/序号/姓名/第四章1、对于一个栈，如果输入项序列由A，B，C组成，给出全部可能和不可能的输出序列。2、设栈S和队列Q的初始状态为空，元素a1,a2,a3,a4,a5,a6,a7,a8依次通过栈S，一个元素出栈后立即进入队列Q，若8个元素出队列的次序是a3,a6,a7,a5,a8,a4,a2,a1，

14、则栈S的容量至少应该是多少？（即至少应该容纳多少个元素？）3、设有算术表达式x+a*(y-b)-c/d，将其转换为后缀表达式。4、有字符串序列为3*-y-a/y2,试利用栈给出将次序改变为3y-*ay2 /-的操作步骤。（用X代表扫描字符串函数中顺序取一字符进栈的操作，S代表从栈中取出一个字符加入到新字符串尾的出栈操作。）例如，ABC变为BCA，则操作步骤为XXSXSS。5、假设Q0.10是一个线性队列，初始状态为front=rear=0， 画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。（要求明确标出各元素在队列中的位置序号，头、尾指针）(a)d,e,b

15、,g,h入队(b)d,e出队(c)i,j,k,l,m入队(d)b出队(e)n,o,p入队课后作业 第四章 约定:进栈X,出栈S4个元素依次进栈,任何时候都可以出栈,请写出所有可能的出栈序列XXXXSSSSXXXSXSSSXXXSSXSSXXXSSSXSXXSXXSSSXXSXSXSSXXSXSSXSXXSSXSXSXXSSXXSSXSXSXSXSXSXXXSSSXSXXSXSSXSXXSSXSXSXSXXSS方法提示第五章 树5.1 树的概念5.2 二叉树5.3 二叉树的遍历 5.4 二叉树的其他运算5.5 树的存储结构和运算退出校长一系二系三系六系教务处科研处总务处601602教务科603A

16、BCD张三李四王五例1工厂(根目录) f1f2f3fnd1d2dm例2f11f12f1kd11d12 例3例4 au ee cn edutsinghua cspandabuaapku一个数据元素 : 一个结点A数据元素(结点)之间的关系 : 分支AB5.1树的概念5.1.1 树的定义 树Tree：是由n0 个结点组成的有穷集合以及结点之间关系组成的集合构成的结构。 递归的数据结构树的递归定义：（1）树由具有相同特性的数据元素（称为结点）组成，结点个数为0时，称为空树；（2）在一棵非空树中有且仅有一个根root结点，除根结点外，其余结点可分为m( m 0)个互不相交的子集，每个子集也是一棵树，称

17、为子树SubTree。tree = (K, R)K = ki | 1in, n0, ki ElemTypeR = rElemType是具有相同特性的数据元素。 关系r满足：（1）有且仅有一个结点没有前驱，这个结点即树根；（2）除树根外，其余结点有且仅有一个前驱；（3）包括根结点在内的所有结点都可以有任意个(含0个)后继。如上图：K = A，B，C，D，E，F，G，H，I r = , , , , , , , JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树树(逻辑上)的特点1. 有且仅有一个结点没有前驱结点,该结点为树的根结点。2. 除了根结点外,每个结点有且仅有一个直接前驱结点。

18、3. 包括根结点在内，每个结点可以有多个后继结点。5.1.2 树的表示树有五种表示方式：（1）树形表示，（2）二元组表示，（3）集合图表示，（4）凹入表表示，（5）广义表表示。JIHGFEACXB1. 树形表示法 借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。tree = (K, R)K = ki | 1in, n0, ki ElemTypeR = r如上图：K = A，B，C，D，E，F，G，H，I r = , , , , , , , 2. 二元组表示法 1. 结点的度：2. 树的度：3. 叶结点：4. 分支结点:5. 层次的定义:JIHGFEACXB该结点拥有的子树的数目

19、。树中结点度的最大值。度为0 的结点.度非0 的结点. 根结点为第一层,若某结点在第i 层, 则其孩子结点(若存在)为第i+1层.5.1.3树的基本术语第1层第2层第3层7. 树林(森林): m0 棵不相交的树组成的树的集合.8. 树的有序性:ABCDEABCDEFF6. 树的深度:树中结点所处的最大层次数. 若树中结点的子树的相对位置不能 随意改变, 则称该树为有序树，否 则称该树为无序树。JIHGFEACXB有序树？无序树？深度为3的树5.1.4 树的性质性质1 树中结点个数等于所有结点的度数加1。性质2 度为k的树中第i层上至多有k i -1个结点（i1） 。性质3 深度为h的k叉树中至

20、多有(kh-1)/(k-1) 结点。满k叉树：结点个数等于(kh-1)/(k-1) 的k叉树。性质4 具有n个结点的k叉树的最小深度为logk(n(k-1)+1)。JIHGFEACXB5.2 二叉树5.2.1 二叉树的定义二叉树为度为2的有序树。递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。左孩子left child，左子树的根结点。右孩子right child，右子树的根结点。二叉树的基本形态：(空)根根左子树根右子树根左子树右子树(a) 空二叉树；(b) 仅有一个根结点的二叉树；(c) 右子树为空的二叉树；(d) 左右子树均非

21、空的二叉树；(e) 左子树为空的二叉树。 1. 度为2 的树是二叉树。下面两种说法正确与否? 应该怎样说才合适? 2. 具有三个结点的树可以有以下五种形态:结论:子树有严格的左右之分的度为2的树是二叉树。 结论:具有三个结点的树只有两种形态。两种特殊形态的二叉树 若一棵二叉树中的结点,或者为叶结点， 或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.1. 满二叉树 若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树.2.完全二叉树1. 一棵非空二叉树的第i 层最多有2i1个

22、结点(i1)。证明(采用归纳法) (1).当i=1时,结论显然正确。非空二叉树的第1层有且 仅有一个结点,即树的根结点.(2).假设对于第j层(1ji1)结论也正确,即第j层最多 有2j-1个结点.(3).有定义可知, 二叉树中每个结点最多只能有两个 孩子结点。若第i1层的每个结点都有两棵非空子 树,则第i层的结点数目达到最大. 而第i1层最多 有2i2个结点已由假设证明,于是,应有 22i2 = 2i1证毕.5.2.2二叉树的性质2. 深度为h 的非空二叉树最多有2h -1个结点.证明: 由性质1可知,若深度为h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最

23、大。即有 20+21+22+2i-1+ +2h-1 = 2h-1证毕.3. 若非空二叉树有n0个叶结点,有n2个度为2的结点, 则 n0=n2+1 证明: 设该二叉树有n1个度为1的结点,结点总数为n,有 n=n0+n1+n2 -(1) 设二叉树的分支数目为B,有 B=n-1 -(2)这些分支来自度于为1的结点与度度为2结点,即 B=n1+2n2 -(3)联列关系(1),(2)与(3),可得到 n0=n2+1证毕.4. 具有n个结点的完全二叉树的深度h=log2n+1.证明: (略) 推论： n0=n2+2n3+3n4+ +(m-1)nm +15. 若对具有n个结点的完全二叉树按照层次从上到下

24、,每层从 左到右的顺序进行编号, 则编号为i 的结点具有以下性质: (1) 若编号为i的结点有左孩子,则左孩子结点的编号为2i; 若编号为i的结点有右孩子,则右孩子结点的编号为2i+1. (2) 除树根结点外,若一个结点的标号为i,则它的双亲结点的编号为i/2,也就是说,当i为偶数时,其双亲结点的编号为i/2,它是双亲结点的左孩子,当i为奇数时,其双亲结点的编号为(i-1)/2,它是双亲结点的右孩子. (3) 若i|_n/2_|,即2i n,则编号为i的结点为分支结点,否则为叶子结点. (4) 若n为奇数,则每个分支结点都既有左孩子,又有右孩子;若n为偶数,则编号最大的分支结点(编号为n/2)

25、只有左孩子,没有右孩子,其余分支结点左、右孩子都有.12345678910n=10换个说法5. 若对具有n个结点的完全二叉树按照层次从上到下,每层从 左到右的顺序进行编号, 则编号为i 的结点具有以下性质: (1) 当i=1, 则编号为i的结点为二叉树的根结点; 若i1, 则编号为i 的结点的双亲结点的编号为i/2. (2) 若2in, 则编号为i 的结点无左子树; 若2in, 则编号为i 的结点的左子树的根的编号为2i. (3) 若2i+1n, 则编号为i 的结点无右子树; 若2i+1n, 则编号为i 的结点的右子树的根的编号为2i+1.5.2.3 二叉树的抽象数据类型ADT BinaryTreeData：存储类型BTreeType，用BT标识符表示Operations：void InitBTree(BTreeType & BT);/初始化一棵二叉树，即置为空树void CreateBTree(BTreeType& BT, char* a);/根据字符串a建立一棵二叉树int BTreeEmpty(BTreeType BT);/判断一棵二叉树是否为空树void TraverseBTree(BTreeType BT);/按照一定次序遍历二叉树int BTreeDepth(BTreeType BT);/求一棵二叉树的深度void PrintBT