北大数据结构课讲义.pptx

《北大数据结构课讲义.pptx》由会员分享，可在线阅读，更多相关《北大数据结构课讲义.pptx（65页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、4.1 栈 栈的定义栈（stack）又称堆栈，是限定只在表尾进行插入或删除操作的线性表。栈S=(a1,a2,，an)是按a1,a2,，an次序进栈的，a1为栈底元素，an为栈顶元素。第1页/共65页栈与递归递归可使问题及求解步骤的描述变得简洁而清晰。特别是对于复杂问题，用递归方法分析描述，比较自然，利于理解。递归包括递归步骤和终止出口。递归问题转化为非递归往往要用栈来实现,把在递归中用到的变量入栈出栈,如书上【习题4-4】之9,10第2页/共65页4.7 队列队列是一种先进先出（FIFO）线性表。只允许在其一端删除元素，即队头（front），只允许在其另一端插入元素，即队尾（rear）。第3页

2、/共65页图 4-10 顺序队列的插入和删除操作第4页/共65页0 1 2 3 4 M-2 M-101234M-1M-2:循环队列循环队列 把队列把队列(数组数组)设想成头尾相连的循环表，使得数组前设想成头尾相连的循环表，使得数组前部由于删除操作而导致的无用空间尽可能得到重复利用，部由于删除操作而导致的无用空间尽可能得到重复利用，这样的队列称为这样的队列称为循环队列循环队列。入队时需先修改入队指针（队尾指针）rear=(rear+1)%QueueMaxSize出队时需要修改队头指针front=(front+1)%QueueMaxSize第5页/共65页 初始时初始时,队列为空队列为空,有有 f

3、ront=0 rear=0测试队列为空的条件是测试队列为空的条件是 front=rear 1 Mab c dfrontrearad约定约定 rear 指出实际队尾元素所在的位置指出实际队尾元素所在的位置,front 指出实际队头元素所在位置的前一个位置指出实际队头元素所在位置的前一个位置.第6页/共65页队列的静态数组一般是循环使用的。队列的静态数组一般是循环使用的。为了判别队列满和队列空的指针状况，令为了判别队列满和队列空的指针状况，令front指向队指向队首元素的前一个位置。首元素的前一个位置。入队时需先修改入队指针（入队时需先修改入队指针（队尾指针）队尾指针）rear=(rear+1)%

4、QueueMaxSize 然后判断队列满的条件然后判断队列满的条件(rear+1)%QueueMaxSize=front最后将元素入队。最后将元素入队。出队时先出队时先判断队列空的条件判断队列空的条件 front=rear然后修改队头指针然后修改队头指针 front=(front+1)%QueueMaxSize 最后将元素出队。最后将元素出队。第7页/共65页第8页/共65页在顺序队列中插入和删除，不需要比较和移动任何元素，只需修改队尾和队首指针，并向队尾写入元素或从队首取出元素时间复杂度为：O(1)若存储队列的数组的长度为N，则队列长度（即所含元素个数）为:(N+rear-front)%N第

5、9页/共65页（2）队列的链式存储结构struct LinkQueue LNode*front;LNode*rear;struct LNode ElmeType data;LNode*next;struct LNode ElemTypedata;/数据域 Lnode*next;/指针域 ;第10页/共65页第11页/共65页在链队中插入和删除，不需要比较和移动任何元素，只需修改个别相关指针和进行结点的动态分配或回收操作时间复杂度为：O(1)第12页/共65页4.4.4 队列运算的实现1.队列运算在顺序存储结构上的实现（1）初始化队列void InitQueue(Queue&Q)Q.MaxSiz

6、e=10;Q.queue=new ElemTypeQ.MaxSiize;Q.front=Q.rear=0;第13页/共65页（2）将队列清空,并释放动态存储空间void ClearQueue(Queue&Q)if(Q.queue!=NULL)delete Q.queue;Q.front=Q.rear=0;Q.queue=NULL;Q.MaxSize=0;第14页/共65页（3）检查队列是否为空int QueueEmpty(Queue&Q)return Q.front=Q.rear;（4）读取队头元素/让front指针不是指向队首元素，而是指向它的前一个位置即：队首元素是队首指针front的下一

7、个位置中的元素ElemType PeekQueue(Queue&Q)if(Q.front=Q.rear)cerrQueue is Empty.endl;exit(1);return Q.queue(Q.front+1)%QueueMaxSize;第15页/共65页（5）向队列插入新元素-1void EnQueue(Queue&Q,const ElemType&item)int k=(Q.rear+1)%QueueMaxSize;/队尾的下一位置if(k=Q.front)cerrQueue is overflow.endl;exit(1);Q.rear=k;Q.queuek=item;入队时入队

8、时需先修改入队指针（队尾指针）rear=(rear+1)%QueueMaxSize 然后判断队列满队列满的条件(rear+1)%QueueMaxSize=front最后将元素入队。第16页/共65页（5）向队列插入新元素-2void EnQueue(queue&Q,const ElemType&item)if(Q.rear+1)%QueueMaxSize=Q.front)/扩大2倍的存储空间int k=sizeof(ElemType);Q.queue=(ElemType*)realloc(Q.queue,2*Q.MaxSize*k);/把原队列尾部内容后移MaxSize个位置if(Q.rear

9、!=Q.MaxSize-1)第17页/共65页 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;入队时入队时需先修改入队指针（队尾指针）rear=(rear+1)%QueueMaxSize 然后判断队列满队列满的条件(rear+1)%QueueMaxSize=front最后将元素入队。第18页/共65页（6）从队列

10、中删除元素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;/指针域 ;第20页/共65页（3）判断链队是否为空int QueueEmpty(LinkQueue&HQ)return HQ.front=NULL;（4）读取队首元素ElemType PeekQueue(LinkQueue&HQ)if(HQ.front=NULL)cerr“Linked queue i

11、s empty.data;第21页/共65页（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=newptr;else HQ.rear=HQ.rear-next=newptr;/不妨与书上P78的算法9(ppt4,算法9)：向单链表的末尾插入一个元素“相对照学习/思考与书上P1

12、37的算法2(ppt6,算法5)：向链栈中插入一个元素“的不同第22页/共65页（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 temp;/不妨与书上P79的算法10(ppt4,算法12)：从单链表中删除表头元素“相对照学习/也可对照书上P137的算法3(ppt6,算法6)：从链栈中删除一个元素”第23

13、页/共65页4.4.6 队列应用简介第一：解决主机与外设之间速度不匹配的问题如：打印输出。设置一个打印数据缓冲区，用队列存储待输出的数据，解决主机与外设速度不匹配的问题。第二：解决多用户引起的资源竞争问题如：多用户CPU资源竞争。操作系统通常按照每个请求在时间上的先后顺序，把它们排成一个队列第24页/共65页1.熟悉栈的含义，掌握基本概念、存储结构和运算的实现。2.熟悉队列的含义，掌握基本概念、存储结构和运算的实现。本章学习要点本章学习要点第25页/共65页本章习题本章习题(第第173177页页)(!)4.1.14.1.4 请独立完成该题4个问题(!)4.2 请独立完成该题(#)4.3 课外思

14、考该题(!)4.4.12,7 能在书上程序的基础上编写 程序实现(#)4.4.36,811 有兴趣者课外思考第26页/共65页书面回答,请以纸面形式上交课代表,要求整洁清楚，时间期限: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-

15、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,g,h入队(b)d,e出队(c)i,j,k,l,m入队(d)b出队(e)n,o,p入队课课后

16、后作作业业 第第四四章章 第27页/共65页约定约定:进栈进栈X,X,出栈出栈S S4个元素依次进栈个元素依次进栈,任何时候任何时候都可以出栈都可以出栈,请写出所有请写出所有可能的出栈序列可能的出栈序列1.XXXXSSSS2.XXXSXSSS3.XXXSSXSS4.XXXSSSXS5.XXSXXSSS6.XXSXSXSS7.XXSXSSXS8.XXSSXSXS9.XXSSXXSS10.XSXSXSXS11.XSXXXSSS12.XSXXSXSS13.XSXXSSXS14.XSXSXXSS方法提示方法提示第28页/共65页第五章 树5.1 树的概念5.2 二叉树5.3 二叉树的遍历 5.4 二叉

17、树的其他运算5.5 树的存储结构和运算退出第29页/共65页校长校长一一系系二二系系三三系系六六系系教教务务处处科科研研处处总总务务处处601 602教教务务科科603ABCD张张三三李李四四王王五五例例1工工厂厂第30页/共65页(根目录)f1f2f3fnd1d2dm例例2f11f12f1kd11d12 第31页/共65页例例3第32页/共65页例例4 au ee cn edutsinghua cspandabuaapku第33页/共65页一个数据元素一个数据元素:一个一个结点结点A数据元素数据元素(结点结点)之间的关系之间的关系:分支分支AB第34页/共65页5.1树的概念5.1.1 树的

18、定义 树Tree：是由n0 个结点组成的有穷集合以及结点之间关系组成的集合构成的结构。递归的数据结构树的递归定义：（1）树由具有相同特性的数据元素（称为结点）组成，结点个数为0时，称为空树；（2）在一棵非空树中有且仅有一个根root结点，除根结点外，其余结点可分为m(m 0)个互不相交的子集，每个子集也是一棵树，称为子树SubTree。第35页/共65页第36页/共65页tree=(K,R)K=ki|1in,n0,ki ElemTypeR=rElemType是具有相同特性的数据元素。关系r满足：（1）有且仅有一个结点没有前驱，这个结点即树根；（2）除树根外，其余结点有且仅有一个前驱；（3）包括

19、根结点在内的所有结点都可以有任意个(含0个)后继。如上图：K=A，B，C，D，E，F，G，H，I r=,第37页/共65页JIHGFEACXBA的第1棵子树A的第3棵子树A的第2棵子树树树(逻辑上逻辑上)的特点的特点1.有且仅有一个结点没有前驱结点有且仅有一个结点没有前驱结点,该结点为树的根结点。该结点为树的根结点。2.除了根结点外除了根结点外,每个结点有且仅有一个直接前驱结点。每个结点有且仅有一个直接前驱结点。3.包括根结点在内，每个结点可以有多个后继结点。包括根结点在内，每个结点可以有多个后继结点。第38页/共65页5.1.2 树的表示树的表示树有五种表示方式：（1）树形表示，（2）二元组

20、表示，（3）集合图表示，（4）凹入表表示，（5）广义表表示。第39页/共65页JIHGFEACXB1.树形表示法树形表示法 借助自然界中一棵倒置的树的形状来表示借助自然界中一棵倒置的树的形状来表示数据元素之间层次关系的方法。数据元素之间层次关系的方法。第40页/共65页tree=(K,R)K=ki|1in,n0,ki ElemTypeR=r如上图：K=A，B，C，D，E，F，G，H，I r=,2.二元组表示法二元组表示法 第41页/共65页第42页/共65页1.结点的度：结点的度：2.树的度：树的度：3.叶结点：叶结点：4.分支结点分支结点:5.层次的定义层次的定义:JIHGFEACXB该结点

21、拥有的子树的数目。该结点拥有的子树的数目。树中结点度的最大值树中结点度的最大值。度为度为0 的结点的结点.度非度非0 的结点的结点.根结点为第一层根结点为第一层,若某结点在第若某结点在第i 层层,则其孩子结点则其孩子结点(若存在若存在)为第为第i+1层层.5.1.3树的基本术语树的基本术语第第1层层第第2层层第第3层层第43页/共65页7.树林树林(森林森林):):m 0 棵不相交的树组成的树的集合棵不相交的树组成的树的集合.8.树的有序性树的有序性:ABCDEABCDEFF6.树的深度树的深度:树中结点所处的最大层次数树中结点所处的最大层次数.若树中结点的子树的相对位置不能若树中结点的子树的

22、相对位置不能 随意改变随意改变,则称该树为则称该树为有序树有序树，否，否 则称该树为则称该树为无序树无序树。JIHGFEACXB有序树？无序树？有序树？无序树？深度为深度为3的树的树第44页/共65页5.1.4 树的性质树的性质性质1 树中结点个数等于所有结点的度数加1。性质2 度为k的树中第i层上至多有k i-1个结点（i1）。性质3 深度为h的k叉树中至多有(kh-1)/(k-1)结点。满k叉树：结点个数等于(kh-1)/(k-1)的k叉树。性质4 具有n个结点的k叉树的最小深度为logk(n(k-1)+1)。JIHGFEACXB第45页/共65页5.2 二叉树二叉树5.2.1 二叉树的定

23、义二叉树的定义二叉树为度为2的有序树。第46页/共65页递归定义：或者是一棵空树，或者是一棵由根结点和两棵互不相交的左、右子树组成的非空树。左、右子树同样也是二叉树。左孩子left child，左子树的根结点。右孩子right child，右子树的根结点。第47页/共65页二叉树的基本形态：二叉树的基本形态：(空空)根根根根左左子子树树根根右右子子树树根根左左子子树树右右子子树树(a)空二叉树；(b)仅有一个根结点的二叉树；(c)右子树为空的二叉树；(d)左右子树均非空的二叉树；(e)左子树为空的二叉树。第48页/共65页 1.度为度为2 的的树树是二叉树。是二叉树。下面两种说法正确与否下面两

24、种说法正确与否?应该怎样说才合适应该怎样说才合适?2.具有三个结点的具有三个结点的树树可以有以下五种形态可以有以下五种形态:结论结论:子树有严格的左右子树有严格的左右之分的度为之分的度为2的树是二叉树。的树是二叉树。结论结论:具有三具有三个结点的个结点的树树只有只有两种形态。两种形态。第49页/共65页两种特殊形态的二叉树两种特殊形态的二叉树 若一棵二叉树中的结点若一棵二叉树中的结点,或者为叶结点，或者为叶结点，或者具有两或者具有两棵非空子树棵非空子树,并且叶结点都集并且叶结点都集中在二叉树的最下面一层中在二叉树的最下面一层.这这样的二叉树为满二叉树样的二叉树为满二叉树.1.满二叉树满二叉树

25、若一棵二叉树中只有最下若一棵二叉树中只有最下面两层的结点的度可以小于面两层的结点的度可以小于2,并且最下面一层的结点并且最下面一层的结点(叶结叶结点点)都依次排列在该层从左至都依次排列在该层从左至右的位置上。这样的二叉树为右的位置上。这样的二叉树为完全二叉树完全二叉树.2.完全二叉树完全二叉树第50页/共65页1.一棵非空二叉树的第一棵非空二叉树的第i 层最多有层最多有2i1个结点个结点(i 1)。证明证明(采用归纳法采用归纳法)(1).).当当i=1=1时时,结论显然正确。非空二叉树的第结论显然正确。非空二叉树的第1层有且层有且 仅有一个结点仅有一个结点,即树的根结点即树的根结点.(2).)

26、.假设对于第假设对于第j层层(1 j i1)结论也正确结论也正确,即第即第j层最层最多多 有有2j-1个结点个结点.(3).).有定义可知有定义可知,二叉树中每个结点最多只能有两个二叉树中每个结点最多只能有两个 孩子结点。若第孩子结点。若第i1层的每个结点都有两棵非空子层的每个结点都有两棵非空子 树树,则第则第i层的结点数目达到最大层的结点数目达到最大.而第而第i1层最多层最多 有有2i2个结点已由假设证明个结点已由假设证明,于是于是,应有应有 2 2i2=2i1证毕证毕.5.2.2二叉树的性质二叉树的性质第51页/共65页2.深度为深度为h 的非空二叉树最多有的非空二叉树最多有2h-1-1个

27、结点个结点.证明证明:由性质由性质1 1可知可知,若深度为若深度为h h的二叉树的每一层的结点数的二叉树的每一层的结点数目都达到各自所在层的最大值目都达到各自所在层的最大值,则二叉树的结点总数一定则二叉树的结点总数一定达到最大。即有达到最大。即有 20+21+22+2i-1+2h-1=2h-1证毕证毕.第52页/共65页3.若非空二叉树有若非空二叉树有n0个叶结点个叶结点,有有n2个度为个度为2的结点的结点,则则 n0=n2+1 证明证明:设该二叉树有设该二叉树有n1个度为个度为1的结点的结点,结点总数为结点总数为n,有有 n=n0+n1+n2 -(1)设二叉树的分支数目为设二叉树的分支数目为

28、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+1第53页/共65页5.若对具有若对具有n个结点的完全二叉树按照层次从上到下个结点的完全二叉树按照层次从上到下,每层从每层从 左到右的顺序进行编号左到右的顺序进行编号,则编号为则编号为i 的结点具有以下性质的结点具有以下性质

29、:(1)若编号为若编号为i的结点有左孩子的结点有左孩子,则左孩子结点的编号为则左孩子结点的编号为2i;若编号为若编号为i i的结点有右孩子的结点有右孩子,则右孩子结点的编号为则右孩子结点的编号为2i+1.2i+1.(2)除树根结点外除树根结点外,若一个结点的标号为若一个结点的标号为i,则它的双亲结点的则它的双亲结点的编号为编号为i/2,也就是说也就是说,当当i为偶数时为偶数时,其双亲结点的编号为其双亲结点的编号为i/2,它是双亲结点的左孩子它是双亲结点的左孩子,当当i为奇数时为奇数时,其双亲结点的编号其双亲结点的编号为为(i-1)/2,它是双亲结点的右孩子它是双亲结点的右孩子.(3)若若i i

30、|_n/2n/2_|,即即2i 2i n,n,则编号为则编号为i i的结点为分支结点的结点为分支结点,否则为叶子结点否则为叶子结点.(4)(4)若若n n为奇数为奇数,则每个分支结点都既有左孩子则每个分支结点都既有左孩子,又有右孩子又有右孩子;若若n n为偶数为偶数,则编号最大的分支结点则编号最大的分支结点(编号为编号为n/2)n/2)只有只有左孩子左孩子,没有右孩子没有右孩子,其余分支结点左、右孩子都有其余分支结点左、右孩子都有.第54页/共65页12345678910n=10第55页/共65页换个说法换个说法5.若对具有若对具有n个结点的完全二叉树按照层次从上到下个结点的完全二叉树按照层次

31、从上到下,每层从每层从 左到右的顺序进行编号左到右的顺序进行编号,则编号为则编号为i 的结点具有以下性质的结点具有以下性质:(1)当当i=1,则编号为则编号为i的结点为二叉树的根结点的结点为二叉树的根结点;若若i1,则编号为则编号为i 的结点的双亲结点的编号为的结点的双亲结点的编号为i/2.(2)若若2in,则编号为则编号为i 的结点无左子树的结点无左子树;若若2i n,则编号为则编号为i 的结点的左子树的根的编号为的结点的左子树的根的编号为2i.(3)若若2i+1n,则编号为则编号为i 的结点无右子树的结点无右子树;若若2i+1 n,则编号为则编号为i 的结点的右子树的根的编号为的结点的右子

32、树的根的编号为2i+1.第56页/共65页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)

33、;/求一棵二叉树的深度void PrintBTree(BTreeType BT);/按照一种表示方法输出二叉树void ClearBTree(BTreeType&BT);/清除二叉树中所有结点，使之为空树end BinaryTree第57页/共65页5.2.4二叉树的存储结构二叉树的存储结构一一.二叉树的顺序存储结构二叉树的顺序存储结构12345678910ABCDEFGHIJ 根据完全二叉树的性质根据完全二叉树的性质5,对于深度为对于深度为h 的完全二叉树的完全二叉树,将树中所有结点的数据信息按照编号的顺序依次存储到将树中所有结点的数据信息按照编号的顺序依次存储到一维数组一维数组BT2h-1

34、中中,由于编号与数组的下标一一对应由于编号与数组的下标一一对应,该该数组就是该完全二叉树的顺序存储结构数组就是该完全二叉树的顺序存储结构.1.完全二叉树的顺序存储结构完全二叉树的顺序存储结构BT150 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E F G H I J 第58页/共65页12345678910ABCDEFGHIJ111213ABCDEFGHIJ 2.一般二叉树的顺序存储结构一般二叉树的顺序存储结构BT150 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B C D E F G H J IBT15A B C D

35、 E F G H J I第59页/共65页 对于一般二叉树对于一般二叉树,只须在二叉树中只须在二叉树中“添加添加”一些实际一些实际上上二叉树中并不存在的二叉树中并不存在的“虚结点虚结点”(可以认为这些结点的数可以认为这些结点的数据据信息为空信息为空),使其在形式上成为一棵使其在形式上成为一棵“完全二叉树完全二叉树”,然然后后按照完全二叉树的顺序存储结构的构造方法将所有结点的按照完全二叉树的顺序存储结构的构造方法将所有结点的数据信息依次存放于数组数据信息依次存放于数组BT 2h-1中。中。第60页/共65页ABCBT 7ABCDBT15ABCDACB 对于一些称为对于一些称为“退化二叉树退化二叉

36、树”的二叉树，的二叉树，顺序存储结构的空间开销浪费的缺点比较突出。顺序存储结构的空间开销浪费的缺点比较突出。第61页/共65页二二.二叉树的链式存储结构二叉树的链式存储结构(二叉链表二叉链表)链结点的构造为链结点的构造为lchild datarchild 其中其中,data 为数据域为数据域 lchild 与与rchild 分别为指向左、右子树的指针域分别为指向左、右子树的指针域.ABCDEFGIJABCDEFGJIT第62页/共65页二叉链表：值域，左指针域，右指针域。leftdataright独立结点struct BTreeNodeElemType data;BTreeNode*left,*right;第63页/共65页图 5-11 二叉树的链式存储结构第64页/共65页谢谢您的观看！第65页/共65页