数据结构期末直播复习课资料.pdf

《数据结构期末直播复习课资料.pdf》由会员分享，可在线阅读，更多相关《数据结构期末直播复习课资料.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第一章第一章1 1、数据结构是、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。数据结构数据结构(Data Structure)(Data Structure)：相互之间存在一种或多种特定关系的数据元素的集合。2 2、数据结构的形式定义：、数据结构的形式定义：二元组 Data_Structure=(D,S)其中，D 是数据元素的有限集，S 是 D 上关系的有限集。3 3、数据元素之间关系的映像：、数据元素之间关系的映像：、顺序映像(顺序存储结构)：以相对的存储位置表示后继关系。2、非顺序映像(链式存储结构)：借助指针元素存储地址的指针表示数据元素之

2、间的逻辑关系。任何一个算法的设计取决于数据任何一个算法的设计取决于数据(逻辑逻辑)结构，其实现取决于物理结构。结构，其实现取决于物理结构。4、算法的定义：算法的定义：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。特性：特性：有穷性、确定性、可行性、输入、输出5 5、算法的评价算法的评价衡量算法优劣的标准衡量算法优劣的标准正确性正确性(correctness):(correctness):满足具体问题的需求满足具体问题的需求可读性可读性(readability)(readability)：易读、易理解：易读、易理解健壮性健壮性(robustness):(ro

3、bustness):当输入数据非法时，算法能够做出反应或进行处理当输入数据非法时，算法能够做出反应或进行处理效率与低存储量效率与低存储量:执行时间短、存储空间小执行时间短、存储空间小第二章第二章1 1、线性表是一种最简单的线性结构。、线性表是一种最简单的线性结构。线性结构线性结构 是一个数据元素的有序（次序）关系是一个数据元素的有序（次序）关系特点：存在唯一的一个特点：存在唯一的一个“第一个第一个”的数据元素；存在唯一的一个的数据元素；存在唯一的一个“最后一个最后一个”的数据元素；除第一个数据元素外，的数据元素；除第一个数据元素外，均有唯一的前驱；除最后一个数据元素外，均有唯一的后继均有唯一的

4、前驱；除最后一个数据元素外，均有唯一的后继2 2、线性表类型的实现、线性表类型的实现顺序映像顺序映像定义：用一组地址连续的存储单元依次存放线性表中的数据元素。定义：用一组地址连续的存储单元依次存放线性表中的数据元素。以以“存储位置相邻存储位置相邻”表示有序对表示有序对 ，则有：，则有：LOCLOC(ai ai)=)=LOCLOC(ai ai-1)+-1)+l l其中其中l l是一个数据元素所占存储是一个数据元素所占存储量量LOCLOC(ai ai)=LOCLOC(a a1)1)+(i i-1-1)l l特点：特点：1 1、实现逻辑上相邻、实现逻辑上相邻物理地址相邻物理地址相邻 2 2、实现随机

5、存取、实现随机存取3 3、若若 假假 定定 在在 线线 性性 表表 中中任任 何何 一一 个个 位位 置置 上上进进 行行插插 入入 的的 概概 率率 都都 是是相相 等等的的，则则 移移 动动 元元 素素的的 期期望望 值值 为为：1n1Eis(ni1)n1i1n2若若 假假 定定 在在 线线 性性 表表 中中 任任 何何 一一 个个 位位 置置 上上 进进 行行 删删 除除 的的 概概 率率 都都 是是 相相 等等 的的，则则 移移 动动 元元 素素 的的 期期 望望 值值 为为：1nn1Edl(ni)ni124 4、线性表类型的实现线性表类型的实现链式映像链式映像线性链表线性链表特点：用

6、一组地址任意的存储单元存放线性表中的数据元素。特点：用一组地址任意的存储单元存放线性表中的数据元素。5 5、在单链表中第、在单链表中第 i i 个结点之前进行插入的基本操作为：找到线性表中第个结点之前进行插入的基本操作为：找到线性表中第 i-1i-1 个结点，然后修改其指向后继的指个结点，然后修改其指向后继的指针。针。s=(LinkList)malloc(sizeof(LNode);/s=(LinkList)malloc(sizeof(LNode);/生成新结点生成新结点s-data=e;s-next=p-next;s-data=e;s-next=p-next;p-next=s;/p-next

7、=s;/插入插入在单链表中删除第在单链表中删除第 i i 个结点的基本操作为个结点的基本操作为:找到线性表中第找到线性表中第 i-1i-1 个结点，修改其指向后继的指针。个结点，修改其指向后继的指针。q=p-next;q=p-next;p-next=q-next;p-next=q-next;e=q-data;free(q);free(q);5 5、循环链表：最后一个结点的指针域的指针又指回第一个结点的链表。循环链表：最后一个结点的指针域的指针又指回第一个结点的链表。和单链表的差别仅在于：和单链表的差别仅在于：判别链表中最后一个结点的条件不再是“后继是否为空”判别链表中最后一个结点的条件不再是“

8、后继是否为空”，而是“后继是否为头结点”，而是“后继是否为头结点”。6 6、双向链表的操作特点：双向链表的操作特点：1 1、“查询查询”和单链表相同；和单链表相同；2 2、“插入插入”和和“删除删除”时需要同时修改两个方向上的指针时需要同时修改两个方向上的指针1“插入插入”：s-next=p-next;s-next=p-next;p-next=s;p-next=s;s-next-prior=s;s-next-prior=s;s-prior=p;s-prior=p;（s s 是插入的结点）是插入的结点）删除：删除：p-next=p-next-next;p-next=p-next-next;p-n

9、ext-prior=p;p-next-prior=p;（要删除的是（要删除的是 p p 的下一个结点）的下一个结点）第三章第三章1 1、栈、队列的特点：、栈、队列的特点：从数据元素间的逻辑关系看从数据元素间的逻辑关系看 是线性表是线性表从操作方式与种类看从操作方式与种类看 不同于线性表：栈与队列是操作受限的线性表不同于线性表：栈与队列是操作受限的线性表2 2、栈的基本概念、栈的基本概念 栈栈-是限制仅在线性表的一端进行插入和删除运算的线性表。是限制仅在线性表的一端进行插入和删除运算的线性表。栈顶（栈顶（TOPTOP）-允许插入和删除的一端。允许插入和删除的一端。栈底（栈底（bottom)-bo

10、ttom)-不允许插入和删除的一端不允许插入和删除的一端。空栈空栈-表中没有元素。表中没有元素。栈栈-又称为后进先出的线性表又称为后进先出的线性表3 3、栈中元素的特性：栈中元素的特性：1 1、具有线性关系、具有线性关系 2 2、后进先出、后进先出4 4、栈的进栈出栈规则：栈的进栈出栈规则：a)a)按序进栈：有按序进栈：有 n n 个元素个元素 1 1，2 2，,n,n，它们按，它们按 1,2,1,2,n n 的次序进栈的次序进栈(i(i 进栈时，进栈时，1(i-1)1(i-1)应该已经进栈应该已经进栈)；b)b)栈顶出栈：栈底最后出栈；栈顶出栈：栈底最后出栈；c)c)时进时出：元素未完全进栈

11、时，即可出栈。时进时出：元素未完全进栈时，即可出栈。5 5、栈的表示与实现、栈的表示与实现顺序栈顺序栈 即栈的顺序存储结构：一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。即栈的顺序存储结构：一组地址连续的存储单元依次存放自栈底到栈顶的数据元素。1 1、附设一个栈底指针附设一个栈底指针 basebase，总是指向栈底。，总是指向栈底。2 2、附设一个栈顶指针附设一个栈顶指针 toptop。空栈时，。空栈时，top=basetop=base；非空栈时，总是指向栈顶元素；非空栈时，总是指向栈顶元素1 1 的位置。的位置。插入一个栈顶元素，指针插入一个栈顶元素，指针 toptop 增增 1 1

12、；删除一个栈顶元素，指针删除一个栈顶元素，指针 toptop 减减 1 1；非空栈中的栈顶指针始终在栈顶元素的下一个位置上非空栈中的栈顶指针始终在栈顶元素的下一个位置上链栈链栈：注意：注意:链栈中指针的方向指向前驱结点！链栈中指针的方向指向前驱结点！6 6、队列、队列队列：只允许在表的一端进行插入，而在表的另一端进行删除的线性表。队列：只允许在表的一端进行插入，而在表的另一端进行删除的线性表。队尾队尾(rear)(rear)允许插入的一端允许插入的一端队头队头(front)(front)允许删除的一端允许删除的一端队列特点：先进先出队列特点：先进先出(FIFO)(FIFO)7 7、队列类型的实

13、现、队列类型的实现链队列链队列队列的链式表示和实现队列的链式表示和实现顺序队列顺序队列队列的顺序表示和实现队列的顺序表示和实现用一组连续的存储单元依次存放队列中的元素用一组连续的存储单元依次存放队列中的元素8 8、顺序队列运算时的头、尾指针变化、顺序队列运算时的头、尾指针变化设两个指针设两个指针 front,rear,front,rear,约定：约定：rearrear 指示队尾元素；指示队尾元素；frontfront 指示队头元素前一位置初值指示队头元素前一位置初值 front=rear=0front=rear=0空队列条件：空队列条件：Q.front=Q.rearQ.front=Q.rear

14、队列满：队列满：Q.rear-Q.front=mQ.rear-Q.front=m入队列：入队列：Q.baserear+=x;Q.baserear+=x;出队列：出队列：x=Q.base+front;x=Q.base+front;存在问题：设数组维数为存在问题：设数组维数为 MM，则：，则：当当 rear-front=mrear-front=m时，再有元素入队发生溢出时，再有元素入队发生溢出真溢出真溢出当当 rearrear 已指向队尾，但队列前端仍有空位置时，再有元素入队发生溢出已指向队尾，但队列前端仍有空位置时，再有元素入队发生溢出假溢出！假溢出！29 9、循环队列：将数组首尾相接（即：循环

15、队列：将数组首尾相接（即：base0base0连在连在 basem-1basem-1之后之后)。入入/出队列运算出队列运算利用利用“模运算模运算”，则：，则：入队：入队：Q.rear=(Q.rear+1)%mQ.rear=(Q.rear+1)%m出队：出队：Q.front=(Q.front+1)%mQ.front=(Q.front+1)%m队满和队空判断条件：队满和队空判断条件：少用一个元素空间：少用一个元素空间：队空：队空：Q.rear=(Q.front)Q.rear=(Q.front)队满：队满：(Q.rear+1)%m=Q.front(Q.rear+1)%m=Q.front1010、栈和

16、队列是限定插入和删除只能在表的“端点”进行的线性表。栈和队列是限定插入和删除只能在表的“端点”进行的线性表。a)a)栈具有栈具有“后进先出后进先出”的特性；的特性；b)b)队列具有队列具有“先进先出先进先出”的特性。的特性。11、栈的链式存储不需头结点。栈的链式存储不需头结点。课后作业课后作业1.1.简述以下算法的功能简述以下算法的功能(栈和队列的元素类型均为栈和队列的元素类型均为 int)int)void algo3(Queue&Q)void algo3(Queue&Q)Stack S;int d;Stack S;int d;InitStack(S);InitStack(S);while(!

17、QueueEmpty(Q)while(!QueueEmpty(Q)DeQueue(Q,d);Push(S,d);DeQueue(Q,d);Push(S,d);while(!StackEmpty(S)while(!StackEmpty(S)Pop(S,d);EnQueue(Q,d);Pop(S,d);EnQueue(Q,d);第六章第六章本章小结本章小结二叉树的结构特性，各性质相应的证明方法。二叉树的结构特性，各性质相应的证明方法。二叉树的各种存储结构的特点及适用范围。二叉树的各种存储结构的特点及适用范围。遍历二叉树是二叉树各种操作的基础，遍历的具体算法与所采用的存储结构有关。遍历二叉树是二叉树

18、各种操作的基础，遍历的具体算法与所采用的存储结构有关。树和森林与二叉树的转换。树和森林与二叉树的转换。最优二叉树的特性，掌握建立最优树和哈夫曼编码的方法。最优二叉树的特性，掌握建立最优树和哈夫曼编码的方法。-、树的定义、树的定义1 1、树型结构：、树型结构：（非线性结构）至少存在一个数据元素有两个或两个以上的直接前驱（非线性结构）至少存在一个数据元素有两个或两个以上的直接前驱(或直接后继或直接后继)元素的数据结元素的数据结构。构。树的定义：是树的定义：是 n n(n n0)0)个结点的有限集合个结点的有限集合 T T，对于任意一棵非空树，它满足：有且仅有一个特定的称为根，对于任意一棵非空树，它

19、满足：有且仅有一个特定的称为根(root)(root)的结点；当的结点；当 n n1 1 时，其余结点可分为时，其余结点可分为 m m(m(m0)0)个互不相交的有限集个互不相交的有限集 T1T1，T2T2，.，T Tm m，其中每个集合本身又是，其中每个集合本身又是一棵树，称为根的子树。上述树的定义是一个递归定义。一棵树，称为根的子树。上述树的定义是一个递归定义。2 2、基本术语、基本术语结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树数。叶子结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树数。叶子(或终端或终端)结点：度为结点：度为零的结点。分支

20、零的结点。分支(或非终端或非终端)结点：度大于零的结点结点：度大于零的结点树的度：树中所有结点的度的最大值树的度：树中所有结点的度的最大值结点的层次：结点的层次：根结点的层次为根结点的层次为 1 1，第第 l l 层的结点的子树的根结点的层次为层的结点的子树的根结点的层次为 l l+1+1。树的深度：树的深度：树中叶子结点所在的最大层树中叶子结点所在的最大层次。次。任何一棵非空树是一个二元组任何一棵非空树是一个二元组 Tree=(rootTree=(root，F)F)其中：其中：rootroot 被称为根结点被称为根结点 F F 被称为子树森林被称为子树森林二、二叉树二、二叉树31、二叉树的定

21、义是二叉树的定义是 n n(n n=0)=0)个结点的有限集合，它或为空树个结点的有限集合，它或为空树(n n=0)=0)，或由一个根结点和至多两棵称为根的左子树，或由一个根结点和至多两棵称为根的左子树和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于和右子树的互不相交的二叉树组成。注：二叉树中不存在度大于2 2 的结点，的结点，并且二叉树的子树有左子树和右子树并且二叉树的子树有左子树和右子树之分。之分。2 2、二叉树的五种基本形态：二叉树的五种基本形态：空树空树只含根结点只含根结点右子树为空树右子树为空树左子树为空树左子树为空树左右子树均不为空树左右子树均不为空树3 3、二叉树的性质、

22、二叉树的性质性质性质 1 1：在二叉树的第：在二叉树的第 i i 层上至多有层上至多有 2 2i i-1-1 个结点个结点(i(i1)1)。其中。其中 2 2i i-1-1 为为 2 2 的的 i-1i-1 次方次方性质性质 2 2：深度为：深度为 k k 的二叉树上至多含的二叉树上至多含 2 2k k-1-1 个结点个结点(k(k1)1)。其中。其中 2 2k k-1-1 为为 2 2 的的 k k 次方减一次方减一性质性质 3 3：对任何一棵二叉树，若它含有：对任何一棵二叉树，若它含有 n n0 0 个叶子结点、个叶子结点、n n2 2 个度为个度为 2 2 的结点，则必存在关系式：的结点

23、，则必存在关系式：n n0 0=n=n2 2+1 1。证明：证明：设二叉树上结点总数设二叉树上结点总数 n=nn=n0 0+n+n1 1+n+n2 2，二叉树上分支总数二叉树上分支总数 b=nb=n1 1+2 2n n2 2，而而 b=nb=n-1-1=n=n0 0+n+n1 1+n+n2 2 1 1由，由，n n0 0=n=n2 2+1 1。除根结点外，其余结点都有一个分支进入，设除根结点外，其余结点都有一个分支进入，设 b b 为分支总数，则为分支总数，则 n n=b b+1+1性质性质 4 4：具有：具有 n n 个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log log2 2

24、n n +1 1。其中其中 log log2 2n n 为不大于为不大于 log2nlog2n 的最大整数的最大整数性质性质 5 5：若对含：若对含 n n 个结点的完全二叉树从上到下且从左至右进行个结点的完全二叉树从上到下且从左至右进行 1 1 至至 n n 的编号，则对完全二叉树中任意一个的编号，则对完全二叉树中任意一个编号为编号为 i i 的结点：的结点：(1)(1)若若 i i=1=1，则该结点是二叉树的根，无双亲，否则，编号为，则该结点是二叉树的根，无双亲，否则，编号为 i i/2/2 的结点为其双亲结点；的结点为其双亲结点；(2)(2)若若 2 2i i n n，则该结点无左孩子，

25、否则，编号为，则该结点无左孩子，否则，编号为 2 2i i 的结点为其左孩子结点；的结点为其左孩子结点；(3)(3)若若 2 2i i+1+1n n，则该结点无右孩子结点，否则，编号为，则该结点无右孩子结点，否则，编号为 2 2i i+1+1 的结点为其右孩子结点。的结点为其右孩子结点。4 4、两类特殊的二叉树：两类特殊的二叉树：满二叉树：指的是深度为满二叉树：指的是深度为 k k 且含有且含有 2 2k k-1-1 个结点的二叉树。其中个结点的二叉树。其中 2 2k k-1-1 为为 2 2 的的 k k 次方减一次方减一特点：是每一层上的结点数都是最大结点数。特点：是每一层上的结点数都是最

26、大结点数。完全二叉树：树中所含的完全二叉树：树中所含的 n n 个结点和满二叉树中编号为个结点和满二叉树中编号为 1 1 至至 n n 的结点一一对应。的结点一一对应。特点：叶子结点只可能在层次最大的两层出现；对任一结点，若其右分支下的子孙的最大层次为特点：叶子结点只可能在层次最大的两层出现；对任一结点，若其右分支下的子孙的最大层次为l l，则其，则其左左分支下的子孙的最大层次为分支下的子孙的最大层次为 l l 或或 l l+1+1。性质练习：性质练习：1.1.一棵二叉树在其第五层中有一棵二叉树在其第五层中有 1717 个结点，可不可能？个结点，可不可能？第第 i i 层上至多有层上至多有 2

27、 2i i-1-1 个结点，则个结点，则 25-1=1625-1=16。所以，不可能。所以，不可能。2.2.二叉树的根结点属于第二叉树的根结点属于第 0 0 层还是属于第层还是属于第 1 1 层？第层？第 1 1 层层3.3.已知一棵二叉树有已知一棵二叉树有 2020 个结点，个结点，其中其中 6 6 个结点为叶子，个结点为叶子，则该树中度为则该树中度为 2 2 的结点数为的结点数为5 5？度为？度为 0 0 的结点为的结点为 6 6？由性质由性质 3 3：n0=n2+1n0=n2+1，则，则 n2=n0-1=6-1=5n2=n0-1=6-1=5。4.4.已知一棵完全二叉树中编号为已知一棵完全

28、二叉树中编号为 101101 的结点有的结点有 LCLC 和和 RCRC 结点，则其结点，则其 LCLC 结点编号为结点编号为202202，RCRC 结点编号为结点编号为203203？由性质？由性质 5 5，可知左孩子为，可知左孩子为 2i 2i，右孩子为，右孩子为 2i+12i+15.5.一棵深度为一棵深度为 h h 的完全的完全 k k 叉树，如果按层次自顶向下、同一层自左向右、顺序从叉树，如果按层次自顶向下、同一层自左向右、顺序从 1 1 开始对全部结点进行编号，开始对全部结点进行编号，试问：该树上最多有多少个结点？最少有多少个结点？试问：该树上最多有多少个结点？最少有多少个结点？由性质

29、由性质 1 1 和定义，可知除第和定义，可知除第 h h 层外，其余各层都是满的，所以：层外，其余各层都是满的，所以：1+k+k2+.+kh-2=(kh-1-1)/(k-1)1+k+k2+.+kh-2=(kh-1-1)/(k-1)，则最多有：，则最多有：(kh-1-1)/(k-1)+kh-1=(kh-1)/(k-1)(kh-1-1)/(k-1)+kh-1=(kh-1)/(k-1)；最少有：最少有：(kh-1-1)/(k-1)+1(kh-1-1)/(k-1)+1三、二叉树的存储结构三、二叉树的存储结构1 1、顺序存储结构：、顺序存储结构：特点：一组地址连续的存储单元存储各结点特点：一组地址连续的

30、存储单元存储各结点(定义一个一维数组定义一个一维数组)；自根而下、自左而右存储结点；按完全二叉树；自根而下、自左而右存储结点；按完全二叉树上的结点位置进行编号和存储。上的结点位置进行编号和存储。缺点：空间利用率太低！缺点：空间利用率太低！2 2、链式存储结构：链式存储结构：二叉链表：结点结构至少包含：数据域和左右孩子指针域二叉链表：结点结构至少包含：数据域和左右孩子指针域lchildlchilddatadatarchildrchild4三叉链表：结点结构至少包含：数据域三叉链表：结点结构至少包含：数据域、左右孩子指针域、左右孩子指针域、双亲指针、双亲指针 parentparentlchildl

31、childdatadatarchildrchild四、遍历二叉树和线索二叉树四、遍历二叉树和线索二叉树1 1、遍历二叉树：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。、遍历二叉树：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。基本操作是访问结点基本操作是访问结点先先(根根)序的遍历算法：若二叉树为空树，则空操作；否则，序的遍历算法：若二叉树为空树，则空操作；否则，访问根结点；先序遍历左子树；先序遍历右子访问根结点；先序遍历左子树；先序遍历右子树。树。中中(根根)序的遍历算法：若二叉树为空树，则空操作；否则，中序遍历左子树

32、；访问根结点；中序遍历右子序的遍历算法：若二叉树为空树，则空操作；否则，中序遍历左子树；访问根结点；中序遍历右子树。树。后后(根根)序的遍历算法：若二叉树为空树，则空操作；否则，后序遍历左子树；后序遍历右子树；访问根结序的遍历算法：若二叉树为空树，则空操作；否则，后序遍历左子树；后序遍历右子树；访问根结点。点。2 2、建立二叉树的存储结构：、建立二叉树的存储结构：基本要点：基本要点：以以“遍历遍历”为基本出发点；不同的遍历方法相应地有不同的建立算法代码为基本出发点；不同的遍历方法相应地有不同的建立算法代码如何由二叉树的先序和中序序列建树？如何由二叉树的先序和中序序列建树？3 3、线索二叉树线索

33、二叉树指向该线性序列中的指向该线性序列中的“前驱前驱”和和“后继后继”的指针，称作的指针，称作“线索线索”。包含“线索”的存储结构，。包含“线索”的存储结构，称作“线索链表”称作“线索链表”。与其相应的二叉树，称作“线索二叉树”。与其相应的二叉树，称作“线索二叉树”遍历二叉树的结果是，求得结点的一个线性序列。遍历二叉树的结果是，求得结点的一个线性序列。线索化的实质是将二叉链表中的空指针改为指向前驱或着后续的线索，线索化的实质是将二叉链表中的空指针改为指向前驱或着后续的线索，而前驱或者后续的信息只有在遍历时才能而前驱或者后续的信息只有在遍历时才能得到，因而线索化的过程即为在遍历的过程中修改空指针

34、的过程。得到，因而线索化的过程即为在遍历的过程中修改空指针的过程。四、树和森林四、树和森林1 1、树的存储结构、树的存储结构双亲表示法：用一组连续空间存储树的结点，并附设一个指示器指示其双亲表示法：用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点双亲结点的位置。其中根节点的值为的位置。其中根节点的值为-1-1孩子链表表示法：树结点表和孩子链表表示法：树结点表和 孩子结点表为了快速查找每个结点的孩子结点孩子结点表为了快速查找每个结点的孩子结点树的二叉链表树的二叉链表(孩子孩子-兄弟兄弟)存储表示法：又称二叉树表示法，即以二叉链表作树的存储结构。链表中结点的两存储表示法：又称二叉树表示法

35、，即以二叉链表作树的存储结构。链表中结点的两个链域分别指向结点的第一个孩子结点和下一个兄弟结点。左边孩子右边兄弟个链域分别指向结点的第一个孩子结点和下一个兄弟结点。左边孩子右边兄弟与孩子兄弟链表对应的二叉树：转化后，二叉树的右子树必为空！与孩子兄弟链表对应的二叉树：转化后，二叉树的右子树必为空！2 2、森林与二叉树的转换、森林与二叉树的转换给定一棵树，可以找到惟一的一棵二叉树与之对应。给定一棵树，可以找到惟一的一棵二叉树与之对应。用二叉链表作为存储结构（依据）用二叉链表作为存储结构（依据）把森林中第二棵树的根结点看成第一棵树的根结点的兄弟，把森林中第二棵树的根结点看成第一棵树的根结点的兄弟，即

36、作为二叉树的右子树，即作为二叉树的右子树，则同样可以导出森林和二叉则同样可以导出森林和二叉树的对应关系。树的对应关系。注意：和树对应的二叉树，其左、右子树的概念已改变为：注意：和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟。左是孩子，右是兄弟。3 3、树和森林的遍历、树和森林的遍历两种遍历树的方法：两种遍历树的方法：先根先根(次序次序)遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根后根(次序次序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。遍历：若树不空，则先依次后根遍历各棵子树，然后访问

37、根结点。森林的遍历：森林的遍历：森林由三部分构成：森林中第一棵树的根结点；森林中第一棵树的子树森林；森林中其它树构成的森林。森林由三部分构成：森林中第一棵树的根结点；森林中第一棵树的子树森林；森林中其它树构成的森林。遍历森林：遍历森林：先序遍历：若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林先序遍历：若森林不空，则访问森林中第一棵树的根结点；先序遍历森林中第一棵树的子树森林；先序遍历森林中中(除第一棵树之外除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。其余树构成的森林。即：依次从左至右对森林中的每一棵树进行先根遍历。

38、中序遍历：若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中序遍历：若森林不空，则中序遍历森林中第一棵树的子树森林；访问森林中第一棵树的根结点；中序遍历森林中中(除第一棵树之外除第一棵树之外)其余树构成的森林。其余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。即：依次从左至右对森林中的每一棵树进行后根遍历。五、哈夫曼树及其应用五、哈夫曼树及其应用1 1、最优二叉树、最优二叉树(哈夫曼树哈夫曼树)5结点的路径长度：从根结点到该结点的路径上分支的数目。结点的路径长度：从根结点到该结点的路径上分支的数目。树的路径长度：树中每个结点的路径长度之和

39、。树的路径长度：树中每个结点的路径长度之和。树的带权路径长度：树中所有叶子结点的带权路径长度之和树的带权路径长度：树中所有叶子结点的带权路径长度之和WPL(T)=WPL(T)=wklkwklk(对所有叶子结点对所有叶子结点)在所有含在所有含 n n 个叶子结点、个叶子结点、并带相同权值的并带相同权值的 mm 叉树中，叉树中，必存在一棵其带权路径长度取最小值的树，必存在一棵其带权路径长度取最小值的树，称为称为“最优树最优树”。2 2、如何构造最优树？如何构造最优树？(赫夫曼算法赫夫曼算法)以二叉树为例：以二叉树为例：根据给定的根据给定的 n n 个权值个权值 w1,w2,wnw1,w2,wn，构

40、造，构造 n n 棵二叉树的集合棵二叉树的集合 F=T1,F=T1,T2,T2,Tn,Tn，其中每棵二叉树，其中每棵二叉树中均只含一个带权值为中均只含一个带权值为 wiwi 的根结点，其左、右子树为空树；的根结点，其左、右子树为空树；在在 F F 中选取其根结点的权值最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二中选取其根结点的权值最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；叉树根结点的权值为其左、右子树根结点的权值之和；从从 F F 中删去这两棵树，同时加入刚生成的新树；中删去这两棵树，同时加入

41、刚生成的新树；重复重复(2)(2)和和(3)(3)两步，直至两步，直至 F F 中只含一棵树为止。中只含一棵树为止。3 3、采用二叉树设计二进制前缀编码规定：左分支用、采用二叉树设计二进制前缀编码规定：左分支用“0”“0”表示；右分支用表示；右分支用“1”“1”表示。表示。4 4、算法实现：、算法实现：由于哈夫曼树中没有度为由于哈夫曼树中没有度为 1 1 的结点，则一棵有的结点，则一棵有 n n 个叶子结点的哈夫曼树共有个叶子结点的哈夫曼树共有 2n-12n-1 个结点（因个结点（因n2=n0-1)n2=n0-1)，可以存储在一个大小为，可以存储在一个大小为 2n-12n-1 的一维数组中。的

42、一维数组中。5 5、编码需要从叶子到根；译码需要从根到叶子、编码需要从叶子到根；译码需要从根到叶子作业：作业：1.1.某二叉树的先序遍历结点访问顺序是某二叉树的先序遍历结点访问顺序是 abdgcefhabdgcefh，中序遍历的访问顺序是，中序遍历的访问顺序是 dgbaechfdgbaechf，则其后序遍历的结点访问，则其后序遍历的结点访问顺序是（顺序是（）。第第 7 7 章章 图图本章小结本章小结图是一种复杂的非线性结构。图是一种复杂的非线性结构。图的存储表示方法：邻接矩阵图的存储表示方法：邻接矩阵邻接表邻接表十字链表十字链表有向图有向图 邻接多重表邻接多重表无向图无向图图的遍历：深度优先、

43、广度优先图的遍历：深度优先、广度优先图的遍历的应用：最小生成树、拓扑排序及关键路径、最短路径等问题各种算法思想图的遍历的应用：最小生成树、拓扑排序及关键路径、最短路径等问题各种算法思想一、图的定义和基本术语一、图的定义和基本术语1、图的定义图的定义图形结构：较线性表和树更为复杂的数据结构。结点之间的关系是任意的，图中任意两个数据元素都可能相图形结构：较线性表和树更为复杂的数据结构。结点之间的关系是任意的，图中任意两个数据元素都可能相关。关。图的结构定义：图：是由一个顶点集图的结构定义：图：是由一个顶点集 V V 和一个顶点间的关系集合组成的数据结构。和一个顶点间的关系集合组成的数据结构。Gra

44、ph=(V,VR)Graph=(V,VR)其中，其中，V V=x x|x x某个数据对象某个数据对象，是顶点的有穷非空集合；，是顶点的有穷非空集合；2 2、顶点之间关系的有穷集合，也叫做边、顶点之间关系的有穷集合，也叫做边(edge)(edge)或弧或弧(Arc)(Arc)集合。集合。“弧”是有方向的，“弧”是有方向的，3 3、由顶点集和弧集构成的图为有向图。由顶点集和边集构成的图称作无向图、由顶点集和弧集构成的图为有向图。由顶点集和边集构成的图称作无向图基本术语基本术语有有(无无)向网：弧向网：弧(边边)上带权的图上带权的图假设图中有假设图中有 n n 个顶点，个顶点，e e 条边，则含有条

45、边，则含有 e=n(n-1)/2e=n(n-1)/2 条边的无向图称作完全图；含有条边的无向图称作完全图；含有 e=n(n-1)e=n(n-1)条弧的有向图称作条弧的有向图称作有向完全图；若边或弧的个数有向完全图；若边或弧的个数 enlognen-1n-1 时，则形成环；边数时，则形成环；边数n-1n-1时则不连通时则不连通五、最小生成树五、最小生成树构造网的一棵最小生成树，即：在构造网的一棵最小生成树，即：在 e e 条带权的边中选取条带权的边中选取 n-1n-1 条边（不构成回路）条边（不构成回路），使，使“权值之和权值之和”为最小。为最小。1 1、普里姆算法：、普里姆算法：基本思想：基本

46、思想：第一步：取图中任意一个顶点第一步：取图中任意一个顶点 v v 作为生成树的根；作为生成树的根；第二步：往生成树上添加新的顶点第二步：往生成树上添加新的顶点 w w。在添加的顶点。在添加的顶点 w w 和已经在生成树上的顶点和已经在生成树上的顶点 v v 之间必定存在一条边，之间必定存在一条边，并且该边的权值在所有连通顶点并且该边的权值在所有连通顶点 v v 和和 w w 之间的边中取值最小；之间的边中取值最小；第三步：继续往生成树上添加顶点，直至生成树上含有第三步：继续往生成树上添加顶点，直至生成树上含有 n n 个顶点为止。个顶点为止。构造的最小生成树不一定唯一，但最小生成树的权值之和

47、一定是相同的。构造的最小生成树不一定唯一，但最小生成树的权值之和一定是相同的。2 2、克鲁斯卡尔算法：考虑问题的出发点克鲁斯卡尔算法：考虑问题的出发点:为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能地小。基本思想：值尽可能地小。基本思想：第一步：构造一个只含第一步：构造一个只含 n n 个顶点的子图个顶点的子图 SGSG；第二步：从权值最小的边开始，若它的添加不使第二步：从权值最小的边开始，若它的添加不使 SGSG 中产生回路，则在中产生回路，则在 SGSG 上加上这条边；上加上这条边；第三步：如此重复，直至加上

48、第三步：如此重复，直至加上 n-1n-1 条边为止条边为止比较两种算法：比较两种算法：普里姆算法：普里姆算法：O(n2)O(n2)、适用于稠密图、适用于稠密图克鲁斯卡尔算法：克鲁斯卡尔算法：O(eloge)O(eloge)、适用于稀疏图、适用于稀疏图六、有向无环图及其应用六、有向无环图及其应用定义：定义：一个无环的有向图称作有向无环图一个无环的有向图称作有向无环图1 1、拓扑排序、拓扑排序检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。检查有向图中是否存在回路的方法之一，是对有向图进行拓扑排序。7用顶点表示活动，用弧表示活动间的优先关系的有向图称为顶点表示活动的网用顶点表示活动，用

49、弧表示活动间的优先关系的有向图称为顶点表示活动的网(Activity On Vertex Network)(Activity On Vertex Network)，简称简称 AOV-AOV-网。在网。在 AOV-AOV-网中不应该出现有向环。对给定的网中不应该出现有向环。对给定的 AOV-AOV-网需首先判断网中是否有环。网需首先判断网中是否有环。如何进行拓扑排序？如何进行拓扑排序？从有向图中选取一个没有前驱的顶点，并输出之；从有向图中选取一个没有前驱的顶点，并输出之；从有向图中删去此顶点以及所有以它从有向图中删去此顶点以及所有以它为尾为尾的弧；重复上述两步，直至图空，或者图不空但找不到的弧；

50、重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。无前驱的顶点为止。在算法中需要用定量的描述替代定性的概念：在算法中需要用定量的描述替代定性的概念：没有前驱的顶点没有前驱的顶点 入度为零的顶点；删除顶点及以它为尾的弧入度为零的顶点；删除顶点及以它为尾的弧 弧头顶点的入度减弧头顶点的入度减 1 1。为避免每次都要搜索入度为零的顶点，在算法中设置一个为避免每次都要搜索入度为零的顶点，在算法中设置一个“栈栈”，以保存，以保存“入度为零入度为零”的顶点的顶点第第 9 9 章章 查找查找本章小结本章小结查找表是由同一类型的数据元素查找表是由同一类型的数据元素(或记录或记录)构成的集合。构成的集