北大数据结构课讲义课件

第四章栈和队列

4.1栈4.2栈的顺序存储结构和操作实现4.3栈的链接存储结构和操作实现4.4栈的简单应用举例 4.5算术表达式的计算 4.6栈与递归 4.7队列退出第四章栈和队列退出14.1

栈

栈的定义

栈（stack）又称堆栈，是限定只在表尾进行插入或删除操作的线性表。栈S=(a1,a2,…，an) 是按a1,a2,…，an次序进栈的，a1为栈底元素，an为栈顶元素。4.1栈2栈与递归 递归可使问题及求解步骤的描述变得简洁而清晰。特别是对于复杂问题，用递归方法分析描述，比较自然，利于理解。递归包括递归步骤和终止出口。

递归问题转化为非递归往往要用栈来实现,把在递归中用到的变量入栈出栈,如书上【习题4-4】之9,10栈与递归34.7

队列

队列是一种先进先出（FIFO）线性表。只允许在其一端删除元素，即队头（front），只允许在其另一端插入元素，即队尾（rear）。4.7队列4图4-10顺序队列的插入和删除操作图4-10顺序队列的插入和删除操作5……01234……

M-2M-101234M-1M-2::循环队列把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为循环队列。入队时需先修改入队指针（队尾指针） rear==(rear+1)%QueueMaxSize出队时需要修改队头指针front==(front+1)%QueueMaxSize……012346

初始时,队列为空,有

front=0rear=0测试队列为空的条件是

front=rear1Mabcdfrontrearad约定

rear指出实际队尾元素所在的位置,front指出实际队头元素所在位置的前一个位置.初始时,队列为空,有测试队列为空的条件是7

队列的静态数组一般是循环使用的。 为了判别队列满和队列空的指针状况，令front指向队首元素的前一个位置。 入队时需先修改入队指针（队尾指针） rear==(rear+1)%QueueMaxSize 然后判断队列满的条件

(rear+1)%QueueMaxSize==front 最后将元素入队。 出队时先 判断队列空的条件 front==rear 然后修改队头指针 front==(front+1)%QueueMaxSize 最后将元素出队。 队列的静态数组一般是循环使用的。8北大数据结构课讲义课件9在顺序队列中插入和删除，不需要比较和移动任何元素，只需修改队尾和队首指针，并向队尾写入元素或从队首取出元素时间复杂度为：O(1)若存储队列的数组的长度为N，则队列长度（即所含元素个数）为:(N+rear-front)%N在顺序队列中插入和删除，不需要比较和移动任何元素，只需修改队10（2）队列的链式存储结构

structLinkQueue{ LNode*front; LNode*rear; }; structLNode{ ElmeTypedata; LNode*next; };structLNode{ElemType data;//数据域Lnode* next;//指针域};

（2）队列的链式存储结构 structLNode{11北大数据结构课讲义课件12在链队中插入和删除，不需要比较和移动任何元素，只需修改个别相关指针和进行结点的动态分配或回收操作时间复杂度为：O(1)在链队中插入和删除，不需要比较和移动任何元素，只需修改个别相134.4.4队列运算的实现1.队列运算在顺序存储结构上的实现 （1）初始化队列 voidInitQueue(Queue&Q) { Q.MaxSize=10; Q.queue=newElemType[Q.MaxSiize]; Q.front=Q.rear=0; }

4.4.4队列运算的实现14 （2）将队列清空,并释放动态存储空间 voidClearQueue(Queue&Q) { if(Q.queue!=NULL)delete[]Q.queue; Q.front=Q.rear=0; Q.queue=NULL; Q.MaxSize=0; }

北大数据结构课讲义课件15（3）检查队列是否为空 intQueueEmpty(Queue&Q) { returnQ.front==Q.rear; }（4）读取队头元素//让front指针不是指向队首元素，而是指向它的前一个位置即：队首元素是队首指针front的下一个位置中的元素 ElemTypePeekQueue(Queue&Q){ if(Q.front==Q.rear){ cerr<<"QueueisEmpty."<<endl; exit(1);} returnQ.queue[(Q.front+1)%QueueMaxSize]; }（3）检查队列是否为空16（5）向队列插入新元素-1voidEnQueue(Queue&Q,constElemType&item){ intk=(Q.rear+1)%QueueMaxSize;//队尾的下一位置 if(k==Q.front){ cerr<<"Queueisoverflow."<<endl; exit(1); } Q.rear=k; Q.queue[k]=item;}入队时需先修改入队指针（队尾指针） rear==(rear+1)%QueueMaxSize然后判断队列满的条件

(rear+1)%QueueMaxSize==front最后将元素入队。（5）向队列插入新元素-1入队时需先修改入队指针（队尾指针）17（5）向队列插入新元素-2voidEnQueue(queue&Q,constElemType&item){ if((Q.rear+1)%QueueMaxSize==Q.front)

{//扩大2倍的存储空间 intk=sizeof(ElemType); Q.queue=(ElemType*)realloc(Q.queue, 2*Q.MaxSize*k); //把原队列尾部内容后移MaxSize个位置 if(Q.rear!=Q.MaxSize-1) （5）向队列插入新元素-218{ for(inti=0;i<=q.rear;i++) Q.queur[i+Q.MaxSize]=Q.queur[i]; Q.rear+=Q.MaxSize; } Q.MaxSize=2*Q.MaxSize;

} //求出队尾的下一个位置 Q.rear=(Q.rear+1)%Q.MaxSize; //把item的值赋给新的队尾位置 Q.queue[Q.rear]=item;}入队时需先修改入队指针（队尾指针） rear==(rear+1)%QueueMaxSize然后判断队列满的条件

(rear+1)%QueueMaxSize==front最后将元素入队。{ 入队时需先修改入队指针（队尾指针）19（6）从队列中删除元素ElemTypeOutQueue(Queue&Q){ if(Q.front==Q.rear){ cerr<<"Queueisempty."<<endl; exit(1); } Q.front=(Q.front+1)%QueueMaxSize;//队头指向下一位置 returnQ.queue[Q.front];}（7）检查队列是否已满intQueueFull(Queue&Q){ return(Q.rear+1)%QueueMaxSize==Q.front;}出队时先判断队列空的条件

front==rear然后修改队头指针front==(front+1)%QueueMaxSize最后将元素出队。（6）从队列中删除元素出队时先判断队列空的条件20

2.队列运算在链接存储结构上的实现（1）初始化链队voidInitQueue(LinkQueue&HQ){ HQ.front=HQ.rear=NULL;}（2）清空链队voidClearQueue(LinkQueue&HQ){ LNode*p=HQ.front; while(p!=NULL){ HQ.front=HQ.front->next; deletep; p=HQ.front; } HQ.rear=NULL;}structLNode{ElemType data;//数据域Lnode* next;//指针域};

2.队列运算在链接存储结构上的实现structLNo21（3）判断链队是否为空intQueueEmpty(LinkQueue&HQ){ returnHQ.front==NULL;}（4）读取队首元素ElemTypePeekQueue(LinkQueue&HQ){ if(HQ.front==NULL){ cerr<<“Linkedqueueisempty."<<endl; exit(1); } returnHQ.front->data;}（3）判断链队是否为空22（5）向链队中插入一个元素voidEnQueue(LinkQueue&HQ,constElemType&item){ LNode*newptr=newLNode; if(newptr==NULL){ cerr<<“Memoryalocationfailure."<<endl; exit(1); } newptr->data=item; newptr->next=NULL; if(HQ.rear==NULL) HQ.front=HQ.rear=newptr; elseHQ.rear=HQ.rear->next=newptr;}//不妨与书上P78的算法9(ppt4,算法9)：向单链表的末尾插入一个元素“相对照学习//思考与书上P137的算法2(ppt6,算法5)：向链栈中插入一个元素“的不同（5）向链队中插入一个元素23（6）从队列中删除一个元素ElemTypeOutQueue(LinkQueue&HQ){ if(HQ.front==NULL){ cerr<<“Linkedqueueisempty."<<endl; exit(1); } ElemTypetemp=HQ.front->data; Lnode*p=HQ.front; HQ.front=p->next; if(HQ.front==NULL) HQ.rear=NULL; deletep; returntemp;}//不妨与书上P79的算法10(ppt4,算法12)：从单链表中删除表头元素“相对照学习//也可对照书上P137的算法3(ppt6,算法6)：从链栈中删除一个元素”（6）从队列中删除一个元素244.4.6队列应用简介第一：解决主机与外设之间速度不匹配的问题如： 打印输出。设置一个打印数据缓冲区，用队列存储待输出的数据，解决主机与外设速度不匹配的问题。第二：解决多用户引起的资源竞争问题如： 多用户CPU资源竞争。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列4.4.6队列应用简介251.熟悉栈的含义，掌握基本概念、存储结构和运算的实现。2.熟悉队列的含义，掌握基本概念、存储结构和运算的实现。本章学习要点1.熟悉栈的含义，掌握基本概念、存储结构和运算的实现。2.26本章习题(第173－177页)(!!)4.1.1~4.1.4请独立完成该题4个问题(!!)4.2请独立完成该题(#)4.3课外思考该题(!)4.4.1~2,7能在书上程序的基础上编写程序实现(#)4.4.3~6,8~11有兴趣者课外思考本章习题(!!)4.1.1~4.1.4请独立完成该题4个27

书面回答,请以纸面形式上交课代表,要求整洁清楚，

时间期限: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，则栈S的容量至少应该是多少？（即至少应该容纳多少个元素？）3、设有算术表达式x+a*(y-b)-c/d，将其转换为后缀表达式。4、有字符串序列为3*-y-a/y↑2,试利用栈给出将次序改变为3y-*ay2↑/-的操作步骤。（用X代表扫描字符串函数中顺序取一字符进栈的操作，S代表从栈中取出一个字符加入到新字符串尾的出栈操作。）例如，ABC变为BCA，则操作步骤为XXSXSS。5、假设Q[0..10]是一个线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。（要求明确标出各元素在队列中的位置序号，头、尾指针） (a)d,e,b,g,h入队 (b)d,e出队 (c)i,j,k,l,m入队 (d)b出队 (e)n,o,p入队课后作业第四章

书面回答,请以纸面形式上交课代表,要求整洁清楚，

时间期限28约定:进栈X,出栈S4个元素依次进栈,任何时候都可以出栈,请写出所有可能的出栈序列XXXXSSSSXXXSXSSSXXXSSXSSXXXSSSXSXXSXXSSSXXSXSXSSXXSXSSXSXXSSXSXSXXSSXXSSXSXSXSXSXSXXXSSSXSXXSXSSXSXXSSXSXSXSXXSS方法提示约定:4个元素依次进栈,任何时候都可以出栈,请写出所有可能的29第五章树

5.1树的概念

5.2二叉树

5.3二叉树的遍历

5.4二叉树的其他运算

5.5树的存储结构和运算退出第五章树退出30校长一系二系三系六系教务处科研处总务处601602教务科603ABCD…………张三李四王五…例1…工厂校长一二三六教科总601602教603ABCD…………张李王31(根目录)

\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………(根目录)f1f2f3fnd1d2dm………例2f11f1232例3例333例4

au

ee

cn

edutsinghua

cspandabuaapku………………例4aueecnedutsinghuacspand34一个数据元素:一个结点A数据元素(结点)之间的关系:分支AB一个数据元素:一个结点A数据元素(结点)之间的355.1树的概念

5.1.1树的定义

树Tree：是由n0个结点组成的有穷集合以及结点之间关系组成的集合构成的结构。

递归的数据结构树的递归定义： （1）树由具有相同特性的数据元素（称为结点）组成，结点个数为0时，称为空树； （2）在一棵非空树中有且仅有一个根root结点，除根结点外，其余结点可分为m(m≥0)个互不相交的子集，每个子集也是一棵树，称为子树SubTree。5.1树的概念36北大数据结构课讲义课件37tree=(K,R) K={ki|1≤i≤n,n≥0,ki∈ElemType} R={r} ElemType是具有相同特性的数据元素。 关系r满足： （1）有且仅有一个结点没有前驱，这个结点即树根； （2）除树根外，其余结点有且仅有一个前驱； （3）包括根结点在内的所有结点都可以有任意个(含0个)后继。如上图：K={A，B，C，D，E，F，G，H，I}r={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<E,H>,<E,I>}tree=(K,R)38JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树树(逻辑上)的特点1.有且仅有一个结点没有前驱结点,该结点为树的根结点。2.除了根结点外,每个结点有且仅有一个直接前驱结点。3.包括根结点在内，每个结点可以有多个后继结点。JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子39

5.1.2树的表示 树有五种表示方式： （1）树形表示， （2）二元组表示， （3）集合图表示， （4）凹入表表示， （5）广义表表示。 5.1.2树的表示40JIHGFEACXB1.树形表示法

借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。JIHGFEACXB1.树形表示法借41tree=(K,R) K={ki|1≤i≤n,n≥0,ki∈ElemType} R={r}如上图：K={A，B，C，D，E，F，G，H，I}r={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<E,H>,<E,I>}2.二元组表示法

tree=(K,R)2.二元组表示法42北大数据结构课讲义课件431.

结点的度：2.

树的度：3.叶结点：4.分支结点:5.

层次的定义:JIHGFEACXB该结点拥有的子树的数目。树中结点度的最大值。度为0的结点.度非0的结点.根结点为第一层,若某结点在第i层,则其孩子结点(若存在)为第i+1层.5.1.3树的基本术语第1层第2层第3层1.结点的度：3.叶结点：5.层次的定义:JIHGFE447.

树林(森林):m0棵不相交的树组成的树的集合.8.

树的有序性:ABCDEABCDEFF6.

树的深度:树中结点所处的最大层次数.

若树中结点的子树的相对位置不能随意改变,则称该树为有序树，否则称该树为无序树。JIHGFEACXB有序树？无序树？深度为3的树7.树林(森林):m0棵不相交的树组成的树的集合.8455.1.4树的性质性质1树中结点个数等于所有结点的度数加1。性质2度为k的树中第i层上至多有ki-1个结点（i≥1）。性质3深度为h的k叉树中至多有(kh-1)/(k-1)结点。

满k叉树：结点个数等于(kh-1)/(k-1)的k叉树。性质4具有n个结点的k叉树的最小深度为logk(n(k-1)+1)。JIHGFEACXB5.1.4树的性质JIHGFEACXB465.2二叉树

5.2.1二叉树的定义

二叉树为度为2的有序树。5.2二叉树47

递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。 左孩子leftchild，左子树的根结点。 右孩子rightchild，右子树的根结点。 递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交48二叉树的基本形态：(空)根根左子树根右子树根左子树右子树

(a)空二叉树； (b)仅有一个根结点的二叉树； (c)右子树为空的二叉树； (d)左右子树均非空的二叉树； (e)左子树为空的二叉树。

二叉树的基本形态：(空)根根左根右根左右 (a)空二叉树49

1.度为2的树是二叉树。下面两种说法正确与否?应该怎样说才合适?

2.具有三个结点的树可以有以下五种形态:结论:子树有严格的左右之分的度为2的树是二叉树。结论:具有三个结点的树只有两种形态。1.度为2的树是二叉树。下面两种说法正确与否?应50两种特殊形态的二叉树

若一棵二叉树中的结点,或者为叶结点，或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.1.满二叉树若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树.2.完全二叉树两种特殊形态的二叉树若一棵二叉树中的结点,1.满511.一棵非空二叉树的第i层最多有2i–1个结点(i1)。证明(采用归纳法)(1).当i=1时,结论显然正确。非空二叉树的第1层有且仅有一个结点,即树的根结点.(2).假设对于第j层(1ji–1)结论也正确,即第j层最多有2j-1个结点.(3).有定义可知,二叉树中每个结点最多只能有两个孩子结点。若第i–1层的每个结点都有两棵非空子树,则第i层的结点数目达到最大.而第i–1层最多有2i–2个结点已由假设证明,于是,应有

22i–2=2i–1证毕.5.2.2二叉树的性质1.一棵非空二叉树的第i层最多有2i–1个结点(i1)522.

深度为h的非空二叉树最多有2h-1个结点.证明:

由性质1可知,若深度为h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。即有20+21+22+…+2i-1+…+2h-1=2h-1证毕.2.深度为h的非空二叉树最多有2h-1个结点.证明:533.

若非空二叉树有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+13.若非空二叉树有n0个叶结点,有n2个度为2的结点,证明545.若对具有n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为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)只有 左孩子,没有右孩子,其余分支结点左、右孩子都有.5.若对具有n个结点的完全二叉树按照层次从上到下,每层从5512345678910n=1012345678910n=1056换个说法5.若对具有n个结点的完全二叉树按照层次从上到下,每层从左到右的顺序进行编号,则编号为i的结点具有以下性质:(1)当i=1,则编号为i的结点为二叉树的根结点;若i>1,则编号为i的结点的双亲结点的编号为i/2.(2)若2i>n,则编号为i的结点无左子树;若2in,则编号为i的结点的左子树的根的编号为2i.(3)若2i+1>n,则编号为i的结点无右子树;若2i+1n,则编号为i的结点的右子树的根的编号为2i+1.换个说法5.若对具有n个结点的完全二叉树按照层次从上到下575.2.3二叉树的抽象数据类型 ADTBinaryTree Data：存储类型BTreeType，用BT标识符表示 Operations： voidInitBTree(BTreeType&BT); //初始化一棵二叉树，即置为空树 voidCreateBTree(BTreeType&BT,char*a); //根据字符串a建立一棵二叉树 intBTreeEmpty(BTreeTypeBT); //判断一棵二叉树是否为空树 voidTraverseBTree(BTreeTypeBT); //按照一定次序遍历二叉树 intBTreeDepth(BTreeTypeBT); //求一棵二叉树的深度 voidPrintBTree(BTreeTypeBT); //按照一种表示方法输出二叉树 voidClearBTree(BTreeType&BT); //清除二叉树中所有结点，使之为空树 endBinaryTree5.2.3二叉树的抽象数据类型585.2.4二叉树的存储结构一.二叉树的顺序存储结构12345678910ABCDEFGHIJ根据完全二叉树的性质5,对于深度为h的完全二叉树,将树中所有结点的数据信息按照编号的顺序依次存储到一维数组BT[2h-1]中,由于编号与数组的下标一一对应,该数组就是该完全二叉树的顺序存储结构.1.完全二叉树的顺序存储结构BT[15]0123456789101112131415ABCDEFGHIJ

5.2.4二叉树的存储结构一.二叉树的顺序存储结构123455912345678910ABCDEFGHIJ111213ABCDEFGHIJ2.一般二叉树的顺序存储结构BT[15]0123456789101112131415ABCDEFGHJ

IBT[15]ABCDEFGHJ

I12345678910ABCDEFGHIJ111213ABC60

对于一般二叉树,只须在二叉树中“添加”一些实际上二叉树中并不存在的“虚结点”(可以认为这些结点的数据信息为空),使其在形式上成为一棵“完全二叉树”,然后按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组BT[2h-1]中。对于一般二叉树,只须在二叉树中“添加”一些实际上61ABCBT[7]ABCDBT[15]ABCDACB对于一些称为“退化二叉树”的二叉树，顺序存储结构的空间开销浪费的缺点比较突出。ABCBT[7]ABCDBT[15]ABCDACB62二.二叉树的链式存储结构(二叉链表)链结点的构造为lchilddatarchild其中,data为数据域lchild与rchild分别为指向左、右子树的指针域.ABCDEFGIJABCDEFGJIT^^^^^^^^^^二.二叉树的链式存储结构(二叉链表)链结点的构造为lchil63 二叉链表：值域，左指针域，右指针域。leftdataright独立结点 structBTreeNode{ ElemTypedata;

BTreeNode*left,*right; }; 二叉链表：值域，左指针域，右指针域。leftdatarig64图5-11二叉树的链式存储结构图5-11二叉树的链式存储结构65第四章栈和队列

4.1栈4.2栈的顺序存储结构和操作实现4.3栈的链接存储结构和操作实现4.4栈的简单应用举例 4.5算术表达式的计算 4.6栈与递归 4.7队列退出第四章栈和队列退出664.1

栈

栈的定义

栈（stack）又称堆栈，是限定只在表尾进行插入或删除操作的线性表。栈S=(a1,a2,…，an) 是按a1,a2,…，an次序进栈的，a1为栈底元素，an为栈顶元素。4.1栈67栈与递归 递归可使问题及求解步骤的描述变得简洁而清晰。特别是对于复杂问题，用递归方法分析描述，比较自然，利于理解。递归包括递归步骤和终止出口。

递归问题转化为非递归往往要用栈来实现,把在递归中用到的变量入栈出栈,如书上【习题4-4】之9,10栈与递归684.7

队列

队列是一种先进先出（FIFO）线性表。只允许在其一端删除元素，即队头（front），只允许在其另一端插入元素，即队尾（rear）。4.7队列69图4-10顺序队列的插入和删除操作图4-10顺序队列的插入和删除操作70……01234……

M-2M-101234M-1M-2::循环队列把队列(数组)设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为循环队列。入队时需先修改入队指针（队尾指针） rear==(rear+1)%QueueMaxSize出队时需要修改队头指针front==(front+1)%QueueMaxSize……0123471

初始时,队列为空,有

front=0rear=0测试队列为空的条件是

front=rear1Mabcdfrontrearad约定

rear指出实际队尾元素所在的位置,front指出实际队头元素所在位置的前一个位置.初始时,队列为空,有测试队列为空的条件是72

队列的静态数组一般是循环使用的。 为了判别队列满和队列空的指针状况，令front指向队首元素的前一个位置。 入队时需先修改入队指针（队尾指针） rear==(rear+1)%QueueMaxSize 然后判断队列满的条件

(rear+1)%QueueMaxSize==front 最后将元素入队。 出队时先 判断队列空的条件 front==rear 然后修改队头指针 front==(front+1)%QueueMaxSize 最后将元素出队。 队列的静态数组一般是循环使用的。73北大数据结构课讲义课件74在顺序队列中插入和删除，不需要比较和移动任何元素，只需修改队尾和队首指针，并向队尾写入元素或从队首取出元素时间复杂度为：O(1)若存储队列的数组的长度为N，则队列长度（即所含元素个数）为:(N+rear-front)%N在顺序队列中插入和删除，不需要比较和移动任何元素，只需修改队75（2）队列的链式存储结构

structLinkQueue{ LNode*front; LNode*rear; }; structLNode{ ElmeTypedata; LNode*next; };structLNode{ElemType data;//数据域Lnode* next;//指针域};

（2）队列的链式存储结构 structLNode{76北大数据结构课讲义课件77在链队中插入和删除，不需要比较和移动任何元素，只需修改个别相关指针和进行结点的动态分配或回收操作时间复杂度为：O(1)在链队中插入和删除，不需要比较和移动任何元素，只需修改个别相784.4.4队列运算的实现1.队列运算在顺序存储结构上的实现 （1）初始化队列 voidInitQueue(Queue&Q) { Q.MaxSize=10; Q.queue=newElemType[Q.MaxSiize]; Q.front=Q.rear=0; }

4.4.4队列运算的实现79 （2）将队列清空,并释放动态存储空间 voidClearQueue(Queue&Q) { if(Q.queue!=NULL)delete[]Q.queue; Q.front=Q.rear=0; Q.queue=NULL; Q.MaxSize=0; }

北大数据结构课讲义课件80（3）检查队列是否为空 intQueueEmpty(Queue&Q) { returnQ.front==Q.rear; }（4）读取队头元素//让front指针不是指向队首元素，而是指向它的前一个位置即：队首元素是队首指针front的下一个位置中的元素 ElemTypePeekQueue(Queue&Q){ if(Q.front==Q.rear){ cerr<<"QueueisEmpty."<<endl; exit(1);} returnQ.queue[(Q.front+1)%QueueMaxSize]; }（3）检查队列是否为空81（5）向队列插入新元素-1voidEnQueue(Queue&Q,constElemType&item){ intk=(Q.rear+1)%QueueMaxSize;//队尾的下一位置 if(k==Q.front){ cerr<<"Queueisoverflow."<<endl; exit(1); } Q.rear=k; Q.queue[k]=item;}入队时需先修改入队指针（队尾指针） rear==(rear+1)%QueueMaxSize然后判断队列满的条件

(rear+1)%QueueMaxSize==front最后将元素入队。（5）向队列插入新元素-1入队时需先修改入队指针（队尾指针）82（5）向队列插入新元素-2voidEnQueue(queue&Q,constElemType&item){ if((Q.rear+1)%QueueMaxSize==Q.front)

{//扩大2倍的存储空间 intk=sizeof(ElemType); Q.queue=(ElemType*)realloc(Q.queue, 2*Q.MaxSize*k); //把原队列尾部内容后移MaxSize个位置 if(Q.rear!=Q.MaxSize-1) （5）向队列插入新元素-283{ for(inti=0;i<=q.rear;i++) Q.queur[i+Q.MaxSize]=Q.queur[i]; Q.rear+=Q.MaxSize; } Q.MaxSize=2*Q.MaxSize;

} //求出队尾的下一个位置 Q.rear=(Q.rear+1)%Q.MaxSize; //把item的值赋给新的队尾位置 Q.queue[Q.rear]=item;}入队时需先修改入队指针（队尾指针） rear==(rear+1)%QueueMaxSize然后判断队列满的条件

(rear+1)%QueueMaxSize==front最后将元素入队。{ 入队时需先修改入队指针（队尾指针）84（6）从队列中删除元素ElemTypeOutQueue(Queue&Q){ if(Q.front==Q.rear){ cerr<<"Queueisempty."<<endl; exit(1); } Q.front=(Q.front+1)%QueueMaxSize;//队头指向下一位置 returnQ.queue[Q.front];}（7）检查队列是否已满intQueueFull(Queue&Q){ return(Q.rear+1)%QueueMaxSize==Q.front;}出队时先判断队列空的条件

front==rear然后修改队头指针front==(front+1)%QueueMaxSize最后将元素出队。（6）从队列中删除元素出队时先判断队列空的条件85

2.队列运算在链接存储结构上的实现（1）初始化链队voidInitQueue(LinkQueue&HQ){ HQ.front=HQ.rear=NULL;}（2）清空链队voidClearQueue(LinkQueue&HQ){ LNode*p=HQ.front; while(p!=NULL){ HQ.front=HQ.front->next; deletep; p=HQ.front; } HQ.rear=NULL;}structLNode{ElemType data;//数据域Lnode* next;//指针域};

2.队列运算在链接存储结构上的实现structLNo86（3）判断链队是否为空intQueueEmpty(LinkQueue&HQ){ returnHQ.front==NULL;}（4）读取队首元素ElemTypePeekQueue(LinkQueue&HQ){ if(HQ.front==NULL){ cerr<<“Linkedqueueisempty."<<endl; exit(1); } returnHQ.front->data;}（3）判断链队是否为空87（5）向链队中插入一个元素voidEnQueue(LinkQueue&HQ,constElemType&item){ LNode*newptr=newLNode; if(newptr==NULL){ cerr<<“Memoryalocationfailure."<<endl; exit(1); } newptr->data=item; newptr->next=NULL; if(HQ.rear==NULL) HQ.front=HQ.rear=newptr; elseHQ.rear=HQ.rear->next=newptr;}//不妨与书上P78的算法9(ppt4,算法9)：向单链表的末尾插入一个元素“相对照学习//思考与书上P137的算法2(ppt6,算法5)：向链栈中插入一个元素“的不同（5）向链队中插入一个元素88（6）从队列中删除一个元素ElemTypeOutQueue(LinkQueue&HQ){ if(HQ.front==NULL){ cerr<<“Linkedqueueisempty."<<endl; exit(1); } ElemTypetemp=HQ.front->data; Lnode*p=HQ.front; HQ.front=p->next; if(HQ.front==NULL) HQ.rear=NULL; deletep; returntemp;}//不妨与书上P79的算法10(ppt4,算法12)：从单链表中删除表头元素“相对照学习//也可对照书上P137的算法3(ppt6,算法6)：从链栈中删除一个元素”（6）从队列中删除一个元素894.4.6队列应用简介第一：解决主机与外设之间速度不匹配的问题如： 打印输出。设置一个打印数据缓冲区，用队列存储待输出的数据，解决主机与外设速度不匹配的问题。第二：解决多用户引起的资源竞争问题如： 多用户CPU资源竞争。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列4.4.6队列应用简介901.熟悉栈的含义，掌握基本概念、存储结构和运算的实现。2.熟悉队列的含义，掌握基本概念、存储结构和运算的实现。本章学习要点1.熟悉栈的含义，掌握基本概念、存储结构和运算的实现。2.91本章习题(第173－177页)(!!)4.1.1~4.1.4请独立完成该题4个问题(!!)4.2请独立完成该题(#)4.3课外思考该题(!)4.4.1~2,7能在书上程序的基础上编写程序实现(#)4.4.3~6,8~11有兴趣者课外思考本章习题(!!)4.1.1~4.1.4请独立完成该题4个92

书面回答,请以纸面形式上交课代表,要求整洁清楚，

时间期限: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，则栈S的容量至少应该是多少？（即至少应该容纳多少个元素？）3、设有算术表达式x+a*(y-b)-c/d，将其转换为后缀表达式。4、有字符串序列为3*-y-a/y↑2,试利用栈给出将次序改变为3y-*ay2↑/-的操作步骤。（用X代表扫描字符串函数中顺序取一字符进栈的操作，S代表从栈中取出一个字符加入到新字符串尾的出栈操作。）例如，ABC变为BCA，则操作步骤为XXSXSS。5、假设Q[0..10]是一个线性队列，初始状态为front=rear=0，画出做完下列操作后队列的头尾指针的状态变化情况，若不能入队，请指出其元素，并说明理由。（要求明确标出各元素在队列中的位置序号，头、尾指针） (a)d,e,b,g,h入队 (b)d,e出队 (c)i,j,k,l,m入队 (d)b出队 (e)n,o,p入队课后作业第四章

书面回答,请以纸面形式上交课代表,要求整洁清楚，

时间期限93约定:进栈X,出栈S4个元素依次进栈,任何时候都可以出栈,请写出所有可能的出栈序列XXXXSSSSXXXSXSSSXXXSSXSSXXXSSSXSXXSXXSSSXXSXSXSSXXSXSSXSXXSSXSXSXXSSXXSSXSXSXSXSXSXXXSSSXSXXSXSSXSXXSSXSXSXSXXSS方法提示约定:4个元素依次进栈,任何时候都可以出栈,请写出所有可能的94第五章树

5.1树的概念

5.2二叉树

5.3二叉树的遍历

5.4二叉树的其他运算

5.5树的存储结构和运算退出第五章树退出95校长一系二系三系六系教务处科研处总务处601602教务科603ABCD…………张三李四王五…例1…工厂校长一二三六教科总601602教603ABCD…………张李王96(根目录)

\f1f2f3fnd1d2dm………例2f11f12f1kd11d12…………(根目录)f1f2f3fnd1d2dm………例2f11f1297例3例398例4

au

ee

cn

edutsinghua

cspandabuaapku………………例4aueecnedutsinghuacspand99一个数据元素:一个结点A数据元素(结点)之间的关系:分支AB一个数据元素:一个结点A数据元素(结点)之间的1005.1树的概念

5.1.1树的定义

树Tree：是由n0个结点组成的有穷集合以及结点之间关系组成的集合构成的结构。

递归的数据结构树的递归定义： （1）树由具有相同特性的数据元素（称为结点）组成，结点个数为0时，称为空树； （2）在一棵非空树中有且仅有一个根root结点，除根结点外，其余结点可分为m(m≥0)个互不相交的子集，每个子集也是一棵树，称为子树SubTree。5.1树的概念101北大数据结构课讲义课件102tree=(K,R) K={ki|1≤i≤n,n≥0,ki∈ElemType} R={r} ElemType是具有相同特性的数据元素。 关系r满足： （1）有且仅有一个结点没有前驱，这个结点即树根； （2）除树根外，其余结点有且仅有一个前驱； （3）包括根结点在内的所有结点都可以有任意个(含0个)后继。如上图：K={A，B，C，D，E，F，G，H，I}r={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<E,H>,<E,I>}tree=(K,R)103JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树树(逻辑上)的特点1.有且仅有一个结点没有前驱结点,该结点为树的根结点。2.除了根结点外,每个结点有且仅有一个直接前驱结点。3.包括根结点在内，每个结点可以有多个后继结点。JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子104

5.1.2树的表示 树有五种表示方式： （1）树形表示， （2）二元组表示， （3）集合图表示， （4）凹入表表示， （5）广义表表示。 5.1.2树的表示105JIHGFEACXB1.树形表示法

借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。JIHGFEACXB1.树形表示法借106tree=(K,R) K={ki|1≤i≤n,n≥0,ki∈ElemType} R={r}如上图：K={A，B，C，D，E，F，G，H，I}r={<A,B>,<A,C>,<B,D>,<B,E>,<B,F>,<C,G>,<E,H>,<E,I>}2.二元组表示法

tree=(K,R)2.二元组表示法107北大数据结构课讲义课件1081.

结点的度：2.

树的度：3.叶结点：4.分支结点:5.

层次的定义:JIHGFEACXB该结点拥有的子树的数目。树中结点度的最大值。度为0的结点.度非0的结点.根结点为第一层,若某结点在第i层,则其孩子结点(若存在)为第i+1层.5.1.3树的基本术语第1层第2层第3层1.结点的度：3.叶结点：5.层次的定义:JIHGFE1097.

树林(森林):m0棵不相交的树组成的树的集合.8.

树的有序性:ABCDEABCDEFF6.

树的深度:树中结点所处的最大层次数.

若树中结点的子树的相对位置不能随意改变,则称该树为有序树，否则称该树为无序树。JIHGFEACXB有序树？无序树？深度为3的树7.树林(森林):m0棵不相交的树组成的树的集合.81105.1.4树的性质性质1树中结点个数等于所有结点的度数加1。性质2度为k的树中第i层上至多有ki-1个结点（i≥1）。性质3深度为h的k叉树中至多有(kh-1)/(k-1)结点。

满k叉树：结点个数等于(kh-1)/(k-1)的k叉树。性质4具有n个结点的k叉树的最小深度为logk(n(k-1)+1)。JIHGFEACXB5.1.4树的性质JIHGFEACXB1115.2二叉树

5.2.1二叉树的定义

二叉树为度为2的有序树。5.2二叉树112

递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。 左孩子leftchild，左子树的根结点。 右孩子rightchild，右子树的根结点。 递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交113二叉树的基本形态：(空)根根左子树根右子树根左子树右子树

(a)空二叉树； (b)仅有一个根结点的二叉树； (c)右子树为空的二叉树； (d)左右子树均非空的二叉树； (e)左子树为空的二叉树。

二叉树的基本形态：(空)根根左根右根左右 (a)空二叉树114

1.度为2的树是二叉树。下面两种说法正确与否?应该怎样说才合适?

2.具有三个结点的树可以有以下五种形态:结论:子树有严格的左右之分的度为2的树是二叉树。结论:具有三个结点的树只有两种形态。1.度为2的树是二叉树。下面两种说法正确与否?应115两种特殊形态的二叉树

若一棵二叉树中的结点,或者为叶结点，或者具有两棵非空子树,并且叶结点都集中在二叉树的最下面一层.这样的二叉树为满二叉树.1.满二叉树若一棵二叉树中只有最下面两层的结点的度可以小于2,并且最下面一层的结点(叶结点)都依次排列在该层从左至右的位置上。这样的二叉树为完全二叉树.2.完全二叉树两种特殊形态的二叉树若一棵二叉树中的结点,1.满1161.一棵非空二叉树的第i层最多有2i–1个结点(i1)。证明(采用归纳法)(1).当i=1时,结论显然正确。非空二叉树的第1层有且仅有一个结点,即树的根结点.(2).假设对于第j层(1ji–1)结论也正确,即第j层最多有2j-1个结点.(3).有定义可知,二叉树中每个结点最多只能有两个孩子结点。若第i–1层的每个结点都有两棵非空子树,则第i层的结点数目达到最大.而第i–1层最多有2i–2个结点已由假设证明,于是,应有

22i–2=2i–1证毕.5.2.2二叉树的性质1.一棵非空二叉树的第i层最多有2i–1个结点(i1)1172.

深度为h的非空二叉树最多有2h-1个结点.证明:

由性质1可知,若深度为h的二叉树的每一层的结点数目都达到各自所在层的最大值,则二叉树的结点总数一定达到最大。即有20+21+22+…+2i-1+…+2h-1=2h-1证毕.2.深度为h的非空二叉树最多有2h-1个结点.证明:1183.

若非空二叉树有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+