第3章非线性数据结构精选文档.ppt

第第3章非线性数据结章非线性数据结构构本讲稿第一页，共一百六十二页第第3章章 非线性数据结构非线性数据结构 3.1 树及其基本概念树及其基本概念3.2 二叉树二叉树 3.3 二叉树的遍历二叉树的遍历 3.4 树的存储结构和遍历树的存储结构和遍历 3.5 树、森林与二叉树的转换树、森林与二叉树的转换 3.6 霍夫曼树及其应用霍夫曼树及其应用 本讲稿第二页，共一百六十二页3.7 图及其基本概念图及其基本概念 3.8 图的存储结构图的存储结构 3.9 图的遍历图的遍历 3.10 图的连通性及最小生成树图的连通性及最小生成树 习题习题 本讲稿第三页，共一百六十二页3.1 树及其基本概念树及其基本概念树型结构是一种应用十分广泛的非线性数据结构，它很类似自然界中的树，直观地讲，树型结构是以分支关系定义的层次结构。树(Tree)是n(n0)个结点的有限集合。当n=0时称为空树，否则在任一非空树中：本讲稿第四页，共一百六十二页(1)有且仅有一个称为该树之根的结点；(2)除根结点之外的其余结点可分为m(m0)个互不相交的集合T1，T2，Tm，且其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。本讲稿第五页，共一百六十二页图3-1树型结构本讲稿第六页，共一百六十二页这是一个递归定义，即在树的定义中又用到了树，它显示了树的固有特性。树中的每一个结点都是该树中某一棵子树的根。如图3-1所示的树中，A为根结点，其余的结点分为三个互不相交的有限集合：T1=B，E，F，T2=C，G，J，T3=D，H，I。T1、T2和T3都是A的子树，而它们本身也是一棵树。例如，T1是一棵以B为根的树，其余结点分为互不相交的两个集合E和F，而E和F本身又是仅有一个根结点的树。本讲稿第七页，共一百六十二页下面结合图3-1，给出树型结构中的一些基本术语。结点的度：一个结点拥有的子树数目。如A结点的度为3，它有三个子树T1、T2和T3。E、F结点的度为0，它们没有子树。叶子：度为零的结点称叶子或终端结点。树的度：一棵树上所有结点的度的最大值就是这棵树的度。本讲稿第八页，共一百六十二页结点的层次：根结点的层数为1，其它任何结点的层数等于它的父结点的层数加1。树的深度：一棵树中，结点的最大层次值就是树的深度。图3-1中树的深度为4。森林：森林是m(m0)棵互不相交的树的集合。孩子(child)：某结点子树的根称为该结点的孩子结点。本讲稿第九页，共一百六十二页双亲(parent)：一个结点是它的那些子树的根的双亲结点。兄弟(sibling)：同一个双亲的孩子之间互为兄弟。如A是B、C、D的双亲；B、C、D是A的孩子；B、C、D互为兄弟。堂兄弟(cousins)：其双亲在同一层的结点互为堂兄弟。如G与E、F、H、I互为堂兄弟。本讲稿第十页，共一百六十二页有序树：树T中各子树T1，T2，Tn的相对次序是有意义的，则称T为有序树。在有序树中，改变了子树的相对次序就变成了另一棵树。在计算机中表示一棵树时，就隐含着一种确定的相对次序，所以后面我们讨论的都是有序树。本讲稿第十一页，共一百六十二页3.2 二二 叉叉 树树3.2.1二叉树的定义及其性质1二叉树的定义一个二叉树是一个有限结点的集合，该集合或者为空，或由一个根结点和两棵互不相交的被称为该根的左子树和右子树的二叉树组成。这是一个递归定义，由定义可知二叉树有下面两个主要特点：本讲稿第十二页，共一百六十二页(1)每个结点最多只能有两个孩子，即二叉树中不存在度大于2的结点。(2)二叉树的子树有左、右之分，其次序不能任意颠倒。二叉树可以有五种基本形态，如图3-2所示。本讲稿第十三页，共一百六十二页图3-2二叉树的五种基本形态本讲稿第十四页，共一百六十二页例3-1画出具有3个结点的树和二叉树的所有不同形态。解：(1)具有3个结点的树有2种不同的形态，如图3-3所示。图3-3有3个结点的所有树的不同形态本讲稿第十五页，共一百六十二页图3-3有3个结点的所有树的不同形态本讲稿第十六页，共一百六十二页(2)具有3个结点的二叉树有5种不同的形态，如图3-4所示。图3-43个结点的所有二叉树的不同形态本讲稿第十七页，共一百六十二页注意：树和二叉树的区别主要是二叉树的结点的子树要区分左子树和右子树，即使在结点只有一个子树的情况下，也要明确指出该子树是左子树还是右子树。如二叉树T和T是不同的二叉树，但作为树，它们就是相同的。如图3-5所示。本讲稿第十八页，共一百六十二页图3-5二叉树与树的区别(a)二叉树T；(b)二叉树T；(c)树T本讲稿第十九页，共一百六十二页2二叉树的性质二叉树具有下列重要特性。性质1：在二叉树中，第i层的结点数最多有2i-1(i1)个。例如：层次i第i层最多结点数120=1221=2322=4k2k1此性质可以用数学归纳法证明。本讲稿第二十页，共一百六十二页性质2：在深度为k的二叉树中结点总数最多有2k1个。由性质1可见，深度为k的二叉树的最大结点数为：=2k1本讲稿第二十一页，共一百六十二页性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：(1)由于在二叉树中，任一结点的度数小于或等于2，所以其结点总数n=n0+n1+n2本讲稿第二十二页，共一百六十二页(2)设B为二叉树中总的分支数目，由于二叉树中除了根结点之外，其余结点都有一个分支进入，所以B=n1即n=B+1而这些分支只能是由度数为1或2的结点所发出，所以B=n1+2n2于是得：n=n1+2n2+1本讲稿第二十三页，共一百六十二页(3)由(1)和(2)得：n0+n1+n2=n1+2n2+1所以n0=n2+1证毕下面介绍两种特殊形态的二叉树，满二叉树和完全二叉树。如果一棵二叉树的深度为k，并且含有2k1个结点，则称此二叉树为满二叉树。图3-6是一棵深度为4的满二叉树。本讲稿第二十四页，共一百六十二页图3-6深度为4的满二叉树本讲稿第二十五页，共一百六十二页可以看出这种树的特点是每一层的结点数都是最大结点数。对满二叉树的结点进行连续编号：从根结点起，自上而下逐层从左到右给每个结点编一个从1开始的顺序号。图3-6就成为图3-7。本讲稿第二十六页，共一百六十二页图3-7深度为4的满二叉树本讲稿第二十七页，共一百六十二页深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中的编号从1到n的结点一一对应时，称之为完全二叉树。如图3-8所示是一棵深度为4的完全二叉树。本讲稿第二十八页，共一百六十二页图3-8深度为4的完全二叉树本讲稿第二十九页，共一百六十二页可以看出，完全二叉树有下面的特点：(1)叶子只可能在层次最大的两层上出现。(2)最下面一层的结点都集中在该层最左边的若干位置上。完全二叉树是一个十分重要的概念，在许多算法和算法分析中，都明显或隐含地用到了完全二叉树的概念。下面介绍完全二叉树的两个重要特性。性质4：具有n个结点的完全二叉树的深度为+1本讲稿第三十页，共一百六十二页证明：假设深度为k，则根据性质22k11n2k1或2k1n2k于是k1lbnk因为k是整数所以k=+1本讲稿第三十一页，共一百六十二页性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第+1层，每层从左到右)，则对任一结点i(1in)，有(1)如果i=1，则i是二叉树的根，无双亲；如果i1，则其双亲是结点。(2)如果2in，则结点i无左孩子；否则其左孩子是2i。(3)如果2i+1n，则结点i无右孩子；否则其右孩子是结点2i+1。证明从略。本讲稿第三十二页，共一百六十二页另外，还有两种特殊的二叉树，平衡二叉树和二叉排序树。二叉排序树将在第4章中介绍，这里只介绍平衡二叉树的概念。二叉树上任一结点的左子树深度减去右子树深度的差值，称为此结点的平衡因子。若一棵二叉树中，每个结点的平衡因子之绝对值都不大于1，则称这棵二叉树为平衡二叉树。本讲稿第三十三页，共一百六十二页例3-2图3-9中有两棵二叉树，试判定其是否是平衡二叉树？解：二叉树(a)是平衡二叉树。二叉树(b)中结点C的平衡因子为2，大于1，故不是平衡二叉树。本讲稿第三十四页，共一百六十二页图3-9两棵二叉树本讲稿第三十五页，共一百六十二页 3.2.2 二叉树的存储结构对于二叉树，我们既可采用顺序存储，又可采用链式存储。1顺序存储结构顺序存储就是将一棵二叉树的所有结点按照一定的次序顺序存放到一组连续的存储单元中，为此，必须把二叉树中所有结点构成一个适当的线性序列，以使各个结点在这个序列中的相互位置能反映出结点之间的逻辑关系。本讲稿第三十六页，共一百六十二页对于完全二叉树，按图3-8中的编号顺序，就能得到一个足以反映整个二叉树结构的线性序列。因此，可将完全二叉树中所有结点按编号顺序依次存储到一组连续的存储单元(即向量)中，这样既不浪费内存，又可以利用地址公式确定其结点的位置。但对于一般的二叉树，顺序分配常会造成内存的浪费，因为一般的二叉树也必须按完全二叉树的形式来存储。图3-8所示的完全二叉树，其顺序存储结构如图3-10(a)所示。本讲稿第三十七页，共一百六十二页而图3-10(b)所示的二叉树，其顺序存储结构如图3-10(c)所示，图中以“0”表示不存在此结点。在最坏情况下，一个深度为k且只有k个结点的单支树(树中无度为2的结点)却需要2k1个存储单元。可见，浪费很大。所以，一般情况下，还是用链表来表示二叉树。本讲稿第三十八页，共一百六十二页图3-10二叉树的顺序存储结构本讲稿第三十九页，共一百六十二页 2链式存储结构因为树型结构是非线性的结构，所以在存储器里表示树型结构的最自然的方法是链式存储。根据二叉树的特性，任何一个结点最多有左、右两棵子树，所以每个结点至少设有三个域：数据域和左、右指针域。其结点结构为：lchildDatarchild本讲稿第四十页，共一百六十二页其中，lchild是左指针域，指向结点的左子树的根；data是数据域；rchild是右指针域，指向结点的右子树的根。这种存储结构又称为二叉链表。在二叉链表中，我们可以比较方便地从某个结点出发，找到它的一个子结点，但如果要从某个结点找其父结点就比较麻烦了。有时为便于找到结点的双亲，还可增加一个指向其双亲的指针域(parent)，其结点结构如下：lchilddataparentrchild本讲稿第四十一页，共一百六十二页由这种结点结构所得的二叉树存储结构称为三叉链表。另外，还需设一个指针T指向树的根。若树为空，则T=NULL，否则T指向树的根。例3-3画出给定二叉树的二叉链表和三叉链表存储结构。结果如图3-11所示。本讲稿第四十二页，共一百六十二页图3-11二叉树及其链表存储结构本讲稿第四十三页，共一百六十二页3.3 二叉树的遍历二叉树的遍历遍历二叉树就是按一定的次序，系统地访问树中的所有结点，使每个结点恰好被访问一次。所谓访问结点，其含义是很广的，可以理解为对结点的增、删、修改等各种运算的抽象。在本节讨论中，假定访问结点即为输出结点数据域值。二叉树的遍历是最重要和最基本的运算，二叉树的许多操作都是以遍历为基础的。本讲稿第四十四页，共一百六十二页遍历二叉树的过程实际上就是按某种规律把二叉树的结点排成一个线性序列。由于二叉树是非线性结构，它的每个结点都可能有两个分支，也就是说一个结点可能有两个后继，所以，二叉树的遍历比较复杂，按照不同规则遍历得到的结果也就不同。令L、D、R分别表示遍历左子树、访问根结点和遍历右子树，则对二叉树的遍历有六种规律：DLR、LDR、LRD、DRL、RDL、RLD。若规定先左后右，则只有三种方案：DLR、LDR和LRD，按照访问根的先后，分别称之为二叉树的先序(根)遍历，中序(根)遍历和后序(根)遍历。本讲稿第四十五页，共一百六十二页基于二叉树的递归定义，可得下述遍历二叉树的递归算法定义。二叉树的三种遍历方式：(1)先序遍历：若二叉树为空，则空操作；否则访问根结点；先序遍历左子树；先序遍历右子树。本讲稿第四十六页，共一百六十二页(2)中序遍历：若二叉树为空，则空操作；否则中序遍历左子树；访问根结点；中序遍历右子树。(3)后序遍历：若二叉树为空，则空操作；否则后序遍历左子树；后序遍历右子树。访问根结点；本讲稿第四十七页，共一百六十二页二叉链表的C语言描述如下：structtnodeintdata;structtnode*lchild,*rchild;typedefstructtnodeTNODE;根据先序遍历的定义，先序遍历二叉树的递归算法如下：本讲稿第四十八页，共一百六十二页算法3-1先序遍历根结点指针为bt的二叉树。voidpreorder(TNODE*bt)if(bt!=NULL)printf(%dn,bt-data);preorder(bt-lchild);preorder(bt-rchild);本讲稿第四十九页，共一百六十二页根据中序遍历的定义，中序遍历二叉树的递归算法如下：算法3-2中序遍历根结点指针为bt的二叉树。voidinorder(TNODE*bt)if(bt!=NULL)inorder(bt-lchild);printf(%dn,bt-data);inorder(bt-rchild);本讲稿第五十页，共一百六十二页根据后序遍历的定义，后序遍历二叉树的递归算法如下：算法3-3后序遍历根结点指针为bt的二叉树。voidpostorder(TNODE*bt)if(bt!=NULL)postorder(bt-lchild);postorder(bt-rchild);printf(%dn,bt-data);本讲稿第五十一页，共一百六十二页下面重点以中序遍历为例，讨论二叉树的非递归遍历算法。利用一个辅助堆栈S，可以写出中序遍历二叉树的非递归算法。算法3-4 中序遍历bt所指二叉树，s为存储二叉树结点指针的工作栈。Step1.初始化 置堆栈s为空，设置临时指针变量p(btp)；Step2.判定p=NULL若p=NULL，则执行Step4；本讲稿第五十二页，共一百六十二页Step3.P进栈将p指针入栈，然后置p=p-lchild，返回Step2；Step4.取栈顶元素，并退栈若栈s为空，则算法结束，否则，将栈顶元素置指针变量P；Step5.访问结点p访问结点P，然后置p=p-rchild，并返回Step2。如果设定栈s采用顺序存储结构，则可给出C语言描述如下。本讲稿第五十三页，共一百六十二页#defineNm/*m为二叉树的结点个数*/voidinorderf(TNODE*pt)TNODE*p;TNODE*sN;inttop=1;p=bt;while(p!=NULL)|(top!=1)本讲稿第五十四页，共一百六十二页while(p!=NULL)top+;stop=p;p=p-lchild;if(top!=1)本讲稿第五十五页，共一百六十二页p=stop;top;printf(%dn,p-data);p=p-rchild;本讲稿第五十六页，共一百六十二页分析此算法的运算量，假定二叉树T有n个结点，每个结点都要入栈和出栈一次。因此，入栈和出栈都要执行n次，对结点的访问当然也需执行n次。这样，中序遍历二叉树算法的时间复杂度为O(n)。同理，只要改变对结点的访问位置，就可以容易地写出先序遍历二叉树的非递归算法。二叉树后序遍历的非递归算法要复杂一些，每个结点都要经过进栈出栈进栈出栈这样两个重复过程。第一次出栈是为了能访问右子树，第二次出栈才是访问结点本身。有兴趣的读者可以参阅有关书籍。本讲稿第五十七页，共一百六十二页例3-4 如图3-12所示的二叉树表示下述表达式：a+b*ce/f试写出它的三种遍历序列。解：先序遍历二叉树，按访问结点的先后次序将结点排列起来，可得先序遍历序列为：+a*bc/ef中序遍历序列为：a+b*ce/f本讲稿第五十八页，共一百六十二页后序遍历序列为：abc*+ef/从表达式来看，以上三个序列恰好为表达式的前缀表示(波兰式)、中缀表示和后缀表示(逆波兰式)。本讲稿第五十九页，共一百六十二页图3-12二叉树本讲稿第六十页，共一百六十二页3.4 树的存储结构和遍历树的存储结构和遍历树在计算机内存储，可以用顺序存储方式、也可以用链式存储方式，这主要取决于要对树结构进行什么运算。这里主要介绍链式分配的存储结构。树的链式分配也有几种不同的方式。从结点指针域的个数是否固定来区分，可分为定长结点和不定长结点两种；从一个结点的各指针域存放的指针值的性质来区分，可以分为指向其所有孩子的多重链表和指向长子(最左边的孩子)及次弟(右邻的兄弟)的二叉链表，下面只介绍二叉链表。本讲稿第六十一页，共一百六十二页 1二叉链表表示法二叉链表表示法又称二叉树表示法，或孩子兄弟表示法。即以二叉链表作为树的存储结构。链表中结点的两个指针域分别指向该结点的第一个孩子和下一个兄弟结点。图3-13是一棵树，该树的二叉链表如图3-14所示。利用这种存储结构便于实现各种树的操作，首先易于实现找结点孩子等的操作，如果再为每个结点增设一个PARENT域，则同样能方便地实现求某结点双亲的操作。本讲稿第六十二页，共一百六十二页图3-13树本讲稿第六十三页，共一百六十二页图3-14图3-13中树的二叉链表本讲稿第六十四页，共一百六十二页 2树的遍历树的遍历有两种次序：一种是先序遍历树；另一种是后序遍历树。(1)先序遍历树：先访问树的根结点，然后从左到右依次先序遍历根的每棵子树。如先序遍历图3-13所示的树，得到的结点序列为：ABDEGHICF。(2)后序遍历树：先从左到右依次后根遍历每棵子树，然后访问根结点。如后序遍历图3-13所示的树，得到的结点序列为：DGHIEBFCA。本讲稿第六十五页，共一百六十二页3.5 树、森林与二叉树的转换树、森林与二叉树的转换由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。也就是说，给定一棵树，可以找到惟一的一棵二叉树与之对应，从物理结构来看，它们的二叉链表是相同的，只是解释不同而已。图3-15给出了树与二叉树之间的对应关系。本讲稿第六十六页，共一百六十二页图3-15树与二叉树的对应关系本讲稿第六十七页，共一百六十二页下面给出树与二叉树之间的转换规则。1一般树转换为二叉树步骤：(1)加线：亲兄弟之间加一虚连线。(2)抹线：抹掉(除最左一个孩子外)该结点到其余孩子之间的连线。(3)旋转：新加上去的虚线改实线且均向右斜(rchild)，原有的连线均向左斜(lchild)。本讲稿第六十八页，共一百六十二页例3-5将图3-16(a)所示的一般树转换为二叉树。解：转换过程如图3-16(a)、(b)、(c)、(d)所示。将一棵由一般树转换来的二叉树还原为一般树的过程是上述过程的逆过程。本讲稿第六十九页，共一百六十二页图3-16一般树转换为二叉树的操作过程(a)一般树；(b)加线后；(c)抹线后；(d)旋转后本讲稿第七十页，共一百六十二页 2森林转换为二叉树森林是树的有限集合，利用树的转换思想，可以实现森林到二叉树的转换。步骤：(1)将各棵树分别转换为二叉树。(2)按给出森林中树的次序，依次将后一棵二叉树作为前一棵二叉树根结点的右子树，则第一棵树的根结点是转换后二叉树的根。本讲稿第七十一页，共一百六十二页如果想将一棵由森林转换得到的二叉树还原为森林，则可采用上述过程的逆过程来实现。例3-6将图3-17(a)的森林转换成二叉树。解：转换过程如图3-17(b)、(c)所示。本讲稿第七十二页，共一百六十二页图3-17森林转换成对应的二叉树的过程(a)森林；(b)各棵树对应的二叉树；(c)转换成的二叉树本讲稿第七十三页，共一百六十二页3.6 霍夫曼树及其应用霍夫曼树及其应用霍夫曼树(HuffmanTree)，又称最优树，是一类带权路径长度最短的树，有着广泛的应用。1树的路径长度和带权路径长度结点间的路径长度：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数称为这两个结点之间的路径长度。本讲稿第七十四页，共一百六十二页树的路径长度：从树根到树中每一个结点的路径长度之和称为树的路径长度，一般记作PL。如图3-18所示的两棵二叉树，其路径长度分别计算如下：(a)PL=0+1+1+2+2+2+2+3=13(b)PL=0+1+1+2+2+2+3=11本讲稿第七十五页，共一百六十二页图3-18二叉树的路径长度计算(a)PL=13；(b)PL=11本讲稿第七十六页，共一百六十二页容易知道，对于有n个结点的所有二叉树而言，满二叉树或者完全二叉树具有最小的路径长度。我们把路径长度的概念推广到带权的路径长度(WeightedPathLength)。所谓带权是给树的每个终端结点赋以权值，则树的带权路径长度为WPL=本讲稿第七十七页，共一百六十二页其中，n为树的终端结点个数；Wi为第i个终端结点的权值；Li为从根结点到第i个终端结点的路径长度。在图3-19中的三棵二叉树，都有四个终端结点，其权值分别为8、6、4、2，则它们的带权路径长度分别为(a)WPL=2*2+4*2+6*2+8*2=40(b)WPL=4*2+6*3+8*3+2*1=52(c)WPL=8*1+6*2+4*3+2*3=38本讲稿第七十八页，共一百六十二页由此可见，带权路径长度最小的二叉树不一定是完全二叉树。通常，在带权路径长度最小的二叉树中，权值越大的终端结点离二叉树的根越近。本讲稿第七十九页，共一百六十二页图3-19具有不同带权路径长度的二叉树本讲稿第八十页，共一百六十二页 2霍夫曼树和霍夫曼编码一般地，假设有一组权值W1，W2，Wn，如何构造有n个叶子结点的二叉树，使各个叶子结点的权值分别为Wi(i=1，2，3，n)，且其带权路径长度WPL为最小，这是一个很有实际意义的问题。霍夫曼在1952年首先提出了一个带有一般规律的算法，很好地解决了这个问题，因此人们把这种具有最小带权路径长度的二叉树称为霍夫曼树或者最优二叉树，相应的算法称为霍夫曼算法。该算法思想是：本讲稿第八十一页，共一百六十二页(1)设给定的一组权值为W1，W2，Wn，据此生成森林F=T1，T2，Tn，F中的每棵二叉树Ti只有一个带权为Wi的根结点(i=1，2，n)。(2)在F中选取两棵根结点的权值最小和次小的二叉树作为左、右子树构造一棵新的二叉树，新二叉树根结点的权值为其左、右子树根结点的权值之和。本讲稿第八十二页，共一百六十二页(3)在F中删除这两棵权值最小和次小的二叉树，同时将新生成的二叉树并入森林F中。(4)重复(2)和(3)，直到F中只有一棵二叉树为止。例如，给定一组权值2，7，4，8，图3-20给出了构造相应霍夫曼树的过程。本讲稿第八十三页，共一百六十二页图3-20霍夫曼树的构造过程本讲稿第八十四页，共一百六十二页霍夫曼树的应用很广，在不同的应用中叶子结点的权值可以有不同的解释。霍夫曼树应用到信息编码中，权值可看成是某个符号出现的频率；应用到判定过程中，权值可看成是某类数据出现的频率；应用到排序过程中，权值可看成是已排好次序而待合并的序列的长度等。本讲稿第八十五页，共一百六十二页下面简单地介绍一下霍夫曼树在信息通信中的应用不等长二进制前缀编码。在信息通信技术中，我们通常采用以二进制的0、1序列来传送通信信息。在发送端，必须将需传送的信息转换成二进制的0、1序列，然后通过调制解调器将二进制序列发送出去；在接收端，必须将接收到的0、1序列还原成相应的信息。在信息通信中，我们通常以字符传送为主。众所周知，字符集中的每个字符使用的频率是不等的。如果能让使用频率较高的字符的编码尽可能短，这样就可以缩短整个信息通信过程中所需传送的二进制编码序列的长度，从而达到节省通信资源的目的。本讲稿第八十六页，共一百六十二页设D=d1，d2，dn为需要编码的字符集合。又设Wi为di在文本中出现的次数，现要求对D进行二进制编码。解决此问题的方法就是以Wi为权值构造霍夫曼树。在生成的霍夫曼树中，令所有的左分支取编码为0，令所有的右分支取编码为1，将从根结点出发到叶子结点的路径上各左、右分支的编码顺序排列就得到了该叶子结点所对应的字符的二进制前缀编码，该编码也称为霍夫曼编码。本讲稿第八十七页，共一百六十二页例如，给出下面一个文本：CASTCATSSATATATASA则有D=C，A，S，T、W=2，7，4，5，构成的霍夫曼树如图3-21所示。由此得到D中每个字符的二进制前缀编码为C：110S：111A：0T：10本讲稿第八十八页，共一百六十二页图3-21 霍夫曼树应用于编码本讲稿第八十九页，共一百六十二页可以看出，出现次数最多的字符，其编码位数最少。相应文本的编码为110011110 11001011111101001001001110这种编码的优点是：(1)对于给出的文本，其编码长度是最短的；(2)任一字符的编码均不可能是另一字符编码的开始部分(前缀)。这样，两个字符之间就不需要分隔符，但是，两个词之间仍需要留空格，以起到分隔作用。本讲稿第九十页，共一百六十二页这种编码的缺点是：每个字符的编码长度不相等，译码时较困难。关于信息的编码还应考虑其它一些因素，如检测和纠错的能力等。总之，编码理论在它自己的领域里还有许多问题。这里仅是对霍夫曼树的应用举了一个简单的例子。本讲稿第九十一页，共一百六十二页3.7 图及其基本概念图及其基本概念图是一种重要的，比树更复杂的非线性数据结构。在树中，每个结点只与上层的父结点有联系，并可以与其下层的多个子结点有联系。但在图中，结点之间的联系是任意的，每个结点都可以与其它的结点相联系。图的应用极为广泛，特别是近年来发展迅速，已渗入到诸如语言学、逻辑学、物理、化学、电信工程、计算机、数学及其它分支中。本讲稿第九十二页，共一百六十二页图3-22有向图示例本讲稿第九十三页，共一百六十二页下面介绍图的一些常用的基本术语。(1)图。图G由两个集合V(G)和E(G)所组成，记作G=(V,E)。其中，V(G)是图中顶点的非空有限集合，E(G)是图中边的有限集合。(2)有向图。如果图中每条边都是顶点的有序对，即每条边都用箭头表明了方向，则此图为有向图。有向图中的边也称为弧，用尖括号括起一对顶点表示。本讲稿第九十四页，共一百六十二页图3-23无向图示例本讲稿第九十五页，共一百六十二页如图3-22所示G1为有向图，它由V(G1)和E(G1)组成。V(G1)=V1，V2，V3，V4E(G1)=，如其中弧，称V1为初始点或弧之尾，V2为终端点或弧之头。本讲稿第九十六页，共一百六十二页(3)无向图。如果图中每条边都是顶点的无序对，则称此图为无向图。无向边用圆括号括起的两个相关顶点来表示。如图3-23所示的G2为无向图。V(G2)=V1，V2，V3，V4E(G2)=(V1,V2)，(V1,V3)，(V3,V4)，(V4,V1)注意，在无向图中，(V1,V2)与(V2,V1)表示同一条边。本讲稿第九十七页，共一百六十二页(4)子图。设有两个图GA和GB，且满足V(GB)V(GA)E(GB)E(GA)则称GB是GA的子图。如图3-24所示。本讲稿第九十八页，共一百六十二页图3-24图与子图本讲稿第九十九页，共一百六十二页图3-25网(带权图)本讲稿第一百页，共一百六十二页(5)带权图。在图的边或弧上加上一个相关联的数(权)，称为带权图或网。如图3-25所示。(6)路径。图中一个顶点的序列称路径。如v到v的路径为(V=Vi0，Vi1，Vi2，Vin=V)，并且都属于集合E。路径上弧的数目称为该路径的长度。本讲稿第一百零一页，共一百六十二页在无向图中，若每一对顶点之间都有路径，则称此图为连通图。在有向图中，若每一对顶点u和v之间都存在v到u及u到v的路径，则称此图为强连通图。(7)邻接点。在无向图中，如果边(u,v)E，则u和v互为邻结点，即u是v的邻结点，v也是u的邻结点。在有向图中，如果弧E，则v是u的邻结点。称u邻接到v，或顶点v邻接自顶点u。本讲稿第一百零二页，共一百六十二页(8)顶点的度。在无向图中，顶点的度就是和该顶点相关联的边的数目，记为TD(V)。如图3-23中，TD(V3)=2。在有向图中，以某顶点为弧头的弧的数目，称为此顶点的入度，记作ID(V)；以某顶点为弧尾的弧的数目称为此顶点的出度，记作OD(V)。该顶点的度则是此顶点的入度与出度之和。如图3-24中G3，ID(V2)=1，OD(V2)=2，TD(V2)=ID(V2)+OD(V2)=3。本讲稿第一百零三页，共一百六十二页3.8 图的存储结构图的存储结构图的结构比较复杂，存储的方法也很多，需要根据具体的图形和将来所要做的运算选取适当的存储结构。这里只讨论两种最常用的表示方法：邻接矩阵表示法和邻接表表示法。本讲稿第一百零四页，共一百六十二页 3.8.1 邻接矩阵根据图的定义可知，一个图的逻辑结构分两部分，一部分是组成图的顶点的集合；另一部分是顶点之间的联系，即边或弧的集合。因此，在计算机中存储图只要解决对这两部分的存储表示即可。本讲稿第一百零五页，共一百六十二页可用一个一维数组存放图中所有顶点的信息；用一个二维数组来存放数据元素之间的关系的信息(即边或弧的集合E)。这个二维数组称之为邻接矩阵。邻接矩阵是表示顶点之间的邻接关系的矩阵。设G=(V，E)是有n(n1)个顶点的图，则G的邻接矩阵A是一个具有下列性质的nn阶矩阵若若本讲稿第一百零六页，共一百六十二页在一般情况下，我们不关心图中顶点的情况，若将顶点编号为1Vtxnum，设弧上或边上无权值，则图的存储结构可以简化为用一个二维数组表示：intadjmatrixvtxnumvtxnum；如图3-23中的G2和图3-24中的G3，其邻接矩阵分别如图3-26中A2、A3所示。本讲稿第一百零七页，共一百六十二页图3-26图G2和G3的邻接矩阵本讲稿第一百零八页，共一百六十二页借助于邻接矩阵，可以很容易地求出图中顶点的度。从上例可以很容易看出，邻接矩阵有如下结论：(1)无向图的邻接矩阵是对称的，而有向图的邻接矩阵不一定对称。对无向图可考虑只存下三角(或上三角)元素。(2)对于无向图，邻接矩阵第i行(或第i列)的元素之和是顶点Vi的度。(3)对于有向图，邻接矩阵第i行元素之和为顶点Vi的出度；第i列的元素之和为顶点Vi的入度。本讲稿第一百零九页，共一百六十二页网的邻接矩阵可定义为若或其中Wij是边(Vi,Vj)或弧上的权值。本讲稿第一百一十页，共一百六十二页 3.8.2 邻接表邻接表是一种顺序分配和链式分配相结合的存储结构。它包括两个部分：一部分是链表；另一部分是向量。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点包含了顶点Vi的所有邻接顶点。每个结点由三个域组成：adjvex、data和nextarc，如图3-27所示。本讲稿第一百一十一页，共一百六十二页图3-27邻接表中表结点的结点结构本讲稿第一百一十二页，共一百六十二页为便于邻接表操作，在每个单链表上附设一个头结点，在头结点中有两个域：vexdata和firstarc。如图3-28所示。图3-28邻接表中头结点的结点结构本讲稿第一百一十三页，共一百六十二页为了利用顺序存储结构的随机访问特性，邻接表中将每个单链表的头结点以顺序结构的形式存储，以便能随机访问任一顶点的单链表。邻接表的存储结构可以用C语言描述如下：#defineVTXUNMn/*n为图中顶点个数的最大可能值*/本讲稿第一百一十四页，共一百六十二页structarcnodeintadjvex;floatdata;structarcnode*nextarc;typedefstructarcnodeARCNODE;structheadnodeintvexdata;ARCNODE*firstarc;adjlistVTXUNM;本讲稿第一百一十五页，共一百六十二页对于图3-29中的图G4和图3-30中的图G5，其邻接表存储结构如图3-29(b)和图3-30(b)所示。图3-29有向带权图及其邻接表本讲稿第一百一十六页，共一百六十二页图3-30无向图及其邻接表本讲稿第一百一十七页，共一百六十二页在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点，但要判定任意两个顶点(Vi和Vj)之间是否有边或弧相连，则需搜索第i个或第j个链表，因此不及邻接矩阵方便。对一个图来说，邻接表不是惟一的，它取决于建立邻接表时，结点在每个单链表中的插入策略。另外，对于有向图，其邻接表中第i个单链表的结点个数就是此结点的出度；对于无向图，其邻接表中第i个单链表的结点个数就是此结点的度。本讲稿第一百一十八页，共一百六十二页3.9 图图 的的 遍遍 历历和树的遍历类似，从图中某一顶点出发访问图中其余的顶点，使每个顶点都被访问且仅被访问一次，这个过程就叫做图的遍历(traversinggraph)。图的遍历算法是求解图的连通性问题、拓扑排序和求关键路径等算法的基础。本讲稿第一百一十九页，共一百六十二页然而，图的遍历要比树的遍历复杂得多，因为图中任一顶点都可能和其余的顶点相邻接，所以在访问了某个顶点之后，可能沿着某条路径搜索之后，又回到该顶点上。为避免同一顶点被访问多次，在遍历图的过程中，必须记下每个已访问过的顶点。为此，设一个辅助数组visitedn，它的初值为“假”或者零，一旦访问了顶点Vi，便置visitedi为“真”或者为被访问时的次序号。通常有两种遍历图的方法，深度优先搜索和广度优先搜索。本讲稿第一百二十页，共一百六十二页 1深度优先搜索图的深度优先搜索遍历(depth-firstsearch)类似于树的先序遍历，是树的先序遍历的推广。深度优先搜索的基本思想是：(1)首先访问图G的指定起始点V0；(2)从V0出发，访问一个与V0邻接的顶点W1后，再从W1出发，访问与W1邻接且未被访问过的顶点W2。从W2出发，重复上述过程，直到遇到一个所有与之邻接的顶点均被访问过的顶点为止；本讲稿第一百二十一页，共一百六十二页(3)沿着刚才访问的次序，反向回退到尚有未被访问过的邻接点的顶点，从该顶点出发，重复步骤(2)、(3)，直到所有被访问过的顶点的邻接点都已被访问过为止；若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。本讲稿第一百二十二页，共一百六十二页显然，这个遍历过程是个递归过程。在设计具体算法时，首先要确定图的存储结构，下面以邻接表为例，讨论深度优先搜索法。例3-7连通图G6的邻接表表示如图3-31所示，以顶点V1为始点，按深度优先搜索遍历图中所有顶点，写出顶点的遍历序列。本讲稿第一百二十三页，共一百六十二页图3-31G6及其邻接表本讲稿第一百二十四页，共一百六十二页解：先访问V1，再访问与V1邻接的V2，再访问V2的第一个邻接点，因V1已被访问过，则访问V2的下一个邻接点V4，然后依次访问V8，V5。这时，与V5相邻接的顶点均已被访问，于是反向回到V8去访问与V8相邻接且尚未被访问的V6，接着访问V3，V7，至此，全部顶点均被访问。相应的访问序列为：V1V2V4V8V5V6V3V7。本讲稿第一百二十五页，共一百六十二页下面给出dfs的算法。算法3-5深度优先搜索的递归算法。#defineVTXUNMn/*n为图中顶点个数的最大可能值*/structarcnodeintadjvex;floatdata;structarcnode*nextarc;本讲稿第一百二十六页，共一百六十二页typedefstructarcnodeARCNODE;structheadnodeintvexdata;ARCNODE*firstarc;structheadnodeGVTXUNM+1;intvisitedVTXUNM+1;本讲稿第一百二十七页，共一百六十二页voiddfs(structheadnodeG,intv)ARCNODE*p;printf(%d-,Gv.vexdata);visitedv=1;p=Gv.firstarc;while(p!=NULL)/*当邻接点存在时*/if(visitedp-adjvex=0)dfs(G,p-adjvex);本讲稿第一百二十八页，共一百六十二页p=p-nextarc;/*