数据结构：面向对象语言描述Bppt.ppt

1 版权所有 1997 c DaleCarnegie Associates Inc 数据结构面向对象语言描述 朱振元 2 版权所有 1997 c DaleCarnegie Associates Inc 数据结构广义表 朱振元 3 广义表的初步认识 广义表 又称为列表 是n n 0 个数据元素a1 a2 ai an的有限序列 一般记作 ls a1 a2 ai an 其中 ls是广义表 a1 a2 an 的名称 n是它的长度 每个ai 1 i n 是ls的成员 它可以是单个元素 也可以是一个广义表 分别称为广义表ls的单元素和子表 当广义表ls非空时 称第一个元素a1为ls的表头 head 称第其余元素组成的表 a2 a3 an 为ls的表尾 tail 4 广义表的初步认识 例 A A是空表 其长度为0 B e B中只有一个单元素e 长度为1 C a b c d D A B C D的长度为3 三个元素都是列表 D e a b c d E a E E是一个长度为2的递归的广义表 E相当于一个无穷表E a a a F F的长度为1 其中的一个元素为一个空表 5 广义表的初步认识 特性 1 广义表是一个多层次的结构 因为广义表的元素可以是一个子表 而子表的元素还可以是子表 2 广义表可以为其它广义表所共享 例如在上述的例子中 广义表A B C为D的子表 则在D中可以不必列出子表的值 而是通过子表的名称来引用 3 广义表可以是一个递归表 即广义表也可以是本身的一个子表 例如广义表E就是一个递归表 6 二个重要的基本操作 取头操作head取尾操作tail对于广义表ls a1 a2 an head ls a1tail ls a2 a3 an 对于任意一个非空的列表 其表头可能是单元素也可能是列表 而其表尾必为列表 例如 head C atail C b c d head D Atail D B C head F tail F 7 取头去尾复合操作 用H表示取头操作head 用T表示取尾操作tail 对于广义表ls a b c d 执行一系列的基本操作 其结果如下 H ls aT ls b c d H T ls b c d T T ls H H T ls bT H T ls c d 8 广义表抽象数据类型 数据元素 D ei i 1 2 n n 0 ei AtomSet或ei GList 结构关系 R1 ei 1 ei D 2 i n 基本操作 对广义表可执行以下的基本操作 InitGList L 初始化 创建一个空的广义表L CopyGList L L0 复制 由广义表L0复制得到一个广义表L GListDepth L 求深度 求广义表L的深度 GListLength L 求长度 求广义表L的长度 即元素个数 GlistEmpty L 判空表 判广义表L是否为空 GetHead L 取头 取广义表L的头 GetTail L 取尾 取广义表L的尾 InsertFirst L e 插入元素 插入元素e作为广义表L的第一元素 9 广义表与其他数据结构的关系 1与线性表的关系当限定广义表的每一项只能是基本元素而非子表时 广义表就退化为线性表 a1 a2 an 2与二维数组的关系当将数组的每行 或每列 看作为子表时 数组即为一个广义表 a11 a12 a1n a21 a22 a2n an1 an2 ann 3与树的关系树也可以用广义表来表示 例如图7 1所表示的树可以用如下的广义表来表示 a b c d e f g 4 在LISP语言中 使用函数嵌套的形式来构造程序 例如 op opAB opCD 在这种情形下 程序本身就是一个广义表 10 存储方式 头尾表示法 二类节点表节点元素节点typedefcharTatom structGListNode inttag union Tatomdata GListNode hp GListNode tp 11 存储方式 头尾表示法 C a b c d b c d b c d c d d 12 存储方式 儿子兄弟表示法 二类节点有儿子无儿子类型定义与头尾表示法的类型定义是一致的 只不过各字域所代表的含义有所不同 13 存储方式 儿子兄弟表示法 C a b c d 最高层结点的tp域必为nil b c d 14 互动环节 G a b c d 的存储结构使用头尾表示法画出G a b c d 的存储结构 15 互动环节 G a b c d 的存储结构 C a b c d c d c d d a b b 16 广义表的类定义 classGList GListNode ls public GList GListNode ls0 NULL copyls0 ls ls0 GList String 17 取头 取尾操作 取头操作成员函数GListNode head 功能 返回指向当前广义表头的指针 程序代码如下 GListNode GList head if ls tag 1 returnls hp elsereturnNULL 取尾操作成员函数GListNode tail 功能 返回指向当前广义表尾的指针 程序代码如下 GListNode GList tail if ls tag 1 returnls tp elsereturnNULL 18 插入 删除操作 voidinsertFirst GList 19 广义表递归算法 递归定义 递归算法 递归函数递归函数 直接或间接地调用自己递归算法特点结构清晰 程序简练易读 其正确性也容易证明 但递归过程的执行效率较低递归定义由基本项和归纳项两部分组成 基本项描述递归过程的终结状态 终结状态是指不需要继续递归而可直接求解的状态 归纳项描述了如何实现从当前状态到终结状态的转化 20 广义表的相等比较 boolequal GListNode ls1 GListNode ls2 功能 对广义表ls1与ls2进行比较 若相等则返回函数值true 否则返回函数值false 分析 1 若两者都为NIL 则返回true 2 若一方NIL而另一方不为NIL或两者tag不相等则返回false 3 若tag相等且为0 则可比较结点中的data 4 若tag相等且为1 则可比较表头与表尾是否都相同 并返回一个相应的函数值 处理过程 1 对一些特殊情形作处理 若两者都为NULL 则返回true 若一方NULL而另一方不为NULL或两者tag不相等则返回false 2 若tag相等且为0 则比较结点中的data是否相同并返回值 若tag相等且为1 则通过递归调用比较表头与表尾是否都相同 并返回一个相应的函数值 21 相等比较程序代码 boolGList equal GListNode ls1 GListNode ls2 boolb1 b2 if ls1 NULL 22 相等比较实例函数 上述equal函数是静态成员函数 它不涉及当前对象 而equal函数的另一种形式是实例函数 涉及到当前对象 其形式如下 boolequal GList 23 成员判别 boolmember GListNode ls1 GListNode ls2 功能 判别ls2是否为ls1的成员 若是则返回函数值true 否则返回函数值false 其处理过程为 1 若ls1为NULL或但元素则返回false 否则 2 调用equal判别ls1的第一个成员是否与ls2相等 调用本递归函数判别ls1的其它成员中是否含有与ls2相等的成员 并将这两者的结果逻辑加后作为最后返回的函数值 boolGList member GListNode ls1 GListNode ls2 boolb1 b2 if ls1 NULL ls1 tag 0 return false else b1 equal ls1 hp ls2 b2 member ls1 tp ls2 return b1 b2 24 成员判别实例函数 上述member函数是静态成员函数 它不涉及当前对象 而member函数的另一种形式是实例函数 涉及到当前对象 其形式如下 boolmember GList 25 求广义表的深度 定义 对于广义表ls a1 a2 ai an 当ls为单元素时 depth ls 0 当ls为空表时 depth ls 1 否则 depth ls max 1 i n depth ai 1 可以作简单的理解 广义表的深度定义为广义表中括号的层数例如 depth 1 depth a 0 depth a b c d 2 depth x x x x x x 3 26 求广义表的深度 intdepth GListNode ls 其中参数ls表示指定的广义表的结点指针 该函数的功能为 求由结点指针ls所指向的广义表的深度 并作为函数值返回之 对于广义表ls 若为单元素时其深度为0 若为空表时其深度为1 否则可分别求出其头的深度h及尾的深度t 当h小于t时其深度为t 否则其深度为h 1 按这种分析可知其处理过程为 1 若ls指向单元素或空表则分别返回函数值为0或1 否则 2 调用本递归函数分别求出其头的深度存入h及尾的深度存入t 3 若h t则返回t 否则返回h 1 27 求广义表的深度 intGList depth GListNode ls inth t if ls NULL return 1 elseif ls tag 0 return 0 else h depth ls hp t depth ls tp if h t return t elsereturn h 1 实例函数intGList depth return depth ls 28 广义表递归算法互动环节 广义表复制 设计一个拷贝构造函数 其功能为按一个指定的广义表来创建一个新的广义表 voidcopyls GListNode ls1 GListNode ls2 功能 复制广义表ls2的一个副本并由ls1指向该广义表的头结点 设计思想 分别复制其表头和表尾 然后合成即可 其处理过程为 1 若ls1为NULL则ls2也为NULL 否则 2 创建一个广义表结点 并按原表是单元素或列表二种情形分别处理 若原表是单元素 则复制元素值 若原表是列表 则分别复制其表头和表尾 并分别挂在新生结点的头尾指针域上 复制表头并将新表头的指针挂在新生结点的头指针域上由copyls ls1 hp ls2 hp 来完成 复制表尾并将新表尾的指针挂在新生结点的尾指针域上由copyls ls1 tp ls2 tp 来完成 29 广义表复制程序代码 voidGList copyls GListNode 30 建立广义表的存储结构 建立广义表的存储结构书写形式st a b prnt ls ls 存储形式 crtlists st ls 31 打印广义表 voidprnt GListNode ls 其中参数ls表示已建立存储结构的广义表 其类型为广义表的结点指针类型 该函数的功能是以书写形式输出广义表ls 其处理过程为 当ls非空时分以下二种情形进行处理 当ls tag 0时 输出ls data 当ls tag 1时 进行以下处理 1 输出 并输出该广义表的第一个成员 2 输出一个 与广义表的下一个成员 3 重复过程 2 的处理 直至所有的成员都处理完 最后再输出一个 32 打印广义表程序代码 voidGList prnt GListNode ls GListNode p if ls NULL couttag 1 couthp p ls tp while p NULL couthp p p tp coutdata 实例函数voidGList prnt prnt ls cout endl 33 广义表类功能测试 编写一个测试程序测试广义表类Glist的构造函数 拷贝构造函数 插入第一元素 删除第一元素 求深度等项功能 voidmain Stringst1 a b c st2 x y z GListgyb1 st1 gyb1 prnt GListgyb2 st2 gyb2 prnt GListgyb3 gyb1 gyb3 prnt gyb2 insertFirst gyb1 gyb2 prnt gyb2 deleteFirst gyb2 prnt cout dep gyb2 depth endl 程序的运行结果如下 a b c x y z a b c a b c x y z x y z dep 3 34 后记 结束 35 版权所有 1997 c DaleCarnegie Associates Inc 数据结构树 朱振元 36 树的初步认识 树的定义 树 tree 是n 0个结点的有限集合 当n 0时称为空树 当n 1时只包含一个根节点当n 0时除根结点外 其余的结点T t 被分割成m 0个不相交的有穷子集T1 Tm 其中每个这样的子集Ti i m 本身又是一棵树 称为根结点的子树 由此可见 树的定义是一个递归定义 37 树的逻辑表示 树形表示文氏图表示凹入表示嵌套括号表示 A B C D E C D E B A C B A D E A B C D E 38 树的基本术语 结点的度和树的度每个结点具有的子树数或者说后继结点数被定义为该结点的度 degree 所有结点的度的最大值被定义为该树的度 分支结点和叶结点度大于0的结点称作分支结点或非终端结点 度等于0的结点称作叶结点或终端结点 39 树的基本术语 儿结点 父结点和兄弟结点每个结点的子树的根 或者说每个结点的后继 被习惯地称作该结点的儿结点 child 相应地 该结点被称作儿结点的父结点 具有同一父结点的儿结点 互称兄弟 sibiling 结点的层数和树的高度树既是一种递归结构 也是一种层次结构 树中的每个结点都处在一定的层次上 结点的层数 level 从树根开始定义 根结点为第一层 它的孩子结点为第二层 以此类推 树中结点的最大层数称为树的深度 depth 或高度 height 40 树的基本术语 有序树和无序树若树中各结点的子树是按照一定的次序从左向右安排的 则称之为有序树 否则称之为无序树 森林森林是m m 0 棵互不相交的树的集合 树当节点个数n 0时由更节点与M棵子树构成的森林所构成 上述叙述就是树与森林的递归定义 41 二叉树的定义 二叉树 binarytree 是指树的度为2的有序树 它是一种最简单 而且最重要的树 递归定义为 二叉树或者是一棵空树 或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树 左子树和右子树又同样都是二叉树 42 二叉树的五种基本形态 a 空 b 只有一个根结点 c 只有左子树 d 只有右子树 e 为左 右子树均为非空的二叉树 空 43 二叉树的基本性质1 任意非空二叉树中 若叶结点的数目为n0 度为2的结点数目为n2 则有关系 n0 n2 1证明 二叉树的结点总数n为n n0 n1 n2n B 1 n1 2n2 1所以n0 n1 n2 n1 2n2 1即n0 n2 1 44 二叉树的基本性质2 一棵非空二叉树的第i层最多有2i 1个结点 i 1 45 二叉树的基本性质3 高度为k的二叉树最多有2k 1个结点 k 1 显然 高度为k的二叉树只有在每一层都达到最大结点数时 整个二叉树的结点数才能达到最大 即当每层的结点数目都达到该层的最大结点数2i 1时 性质2 对应的二叉树的结点数目取得最大值 等比数列求和 46 满二叉树和完全二叉树 若一棵二叉树高度为k且有2k 1个结点 则称该二叉树为满二叉树 满二叉树的特点就是每层的结点数目都达到该层的最大结点数 若在一棵二叉树中 除最后一层外 若其余层都是满的 结点数目达到该层的最大结点数 并且最后一层或者是满的 或者是在右边缺少连续若干个结点 则称此树为完全二叉树 一个深度为K具有N个节点的二叉树 若其节点的编号与深度为K的满二叉树编号为1 n的节点完全对应 则称之为完全二叉树 47 完全二叉树的基本性质 高度规律具有n 0个结点的完全二叉树的高度k log2n 1 根据完全二叉树定义以及二叉树的性质3 有 2k 1 1 n 2k 1或2k 1 n 2k由上式可推出k 1 log2n k由于k为正整数 因此k log2n 1 k log2n 1k log2n 48 完全二叉树的基本性质 父子序号规律若对具有n个结点的完全二叉树按层次从上到下 每层从左至右的规则对结点编号 则序号为i的结点具有以下性质 若i 1 则序号为i的结点的双亲结点的序号为 i 2 当i 1时 则对应结点为二叉树的根结点 没有双亲结点 若2i n 则序号为i的结点的左孩子结点的序号为2i 若2i n 则序号为i的结点无左孩子 若2i 1 n 则序号为i的结点的右孩子结点的序号为2i 1 若2i 1 n 则序号为i的结点无右孩子 49 二叉树的存储结构 一维数组表示法 用一组连续的存储单元存储二叉树的数据元素 为了反映各结点在二叉树中的位置及相互关系 必须适当安排各结点的存储次序 A B C D E 50 二叉树的链式存储结构 二叉链表 structBTreeNode Tdata BTreeNode lchild rchild 三叉链表 structBTreeNode Tdata BTreeNode parent lchild rchild A B C D E 51 二叉树结点类的定义 templateclassBTree templateclassBSTree templateclassBTreeNode friendclassBTree friendclassBSTree Tdata BTreeNode lchild rchild public BTreeNode lchild NULL rchild NULL BTreeNode Td BTreeNode l NULL BTreeNode r NULL data d lchild l rchild r Tgetdata returndata BTreeNode getleft returnlchild BTreeNode getright returnrchild 52 二叉树类的定义 templateclassBTree T a intn BTreeNode build0 inti protected BTreeNode root public BTree BTreeNode p NULL copybt root p BTree Ta intn intnum staticintnum BTreeNode p intdep staticintdep BTreeNode p boolequal BTree 53 建立二叉链表 D H I A B C F G 54 建立二叉链表构造函数 templateBTree BTree Ta intn this a a this n n root build0 1 BTreeNode build0 inti 功能为 以数组a中的第i个元素 下标为i 1 为根结点 递归地创建二叉链表 并返回指向该链表的指针 其处理过程为 1 若序号为i的数组元素存在 即i小于等于数组的长度且数组的第i个元素非空 则创建一个结点作为根结点 在其数据域中存放数组的第i个元素 2 以2 i为参数 调用build0创建左子树 并挂在该结点的左支上 3 以2 i 1为参数 调用build0创建右子树 并挂在该结点的右支上 55 建立二叉链表递归函数的程序代码 templateBTreeNode BTree build0 inti BTreeNode p intl r if i p data a i 1 l 2 i r 2 i 1 p lchild build0 l p rchild build0 r return p elsereturn NULL 56 计算二叉树结点个数 intnum BTreeNode p 其功能为返回p所指向的二叉树的结点个数 其处理过程为 1 若p为NULL则返回0 否则 2 通过递归调用求出左 右子树的结点个数 并返回两者之和加1templateintBTree num BTreeNode p if p NULL return 0 elsereturn num p lchild num p rchild 1 实例函数 求当前对象中的结点个数 templateintBTree num return num root 57 互动环节 计算二叉树的高度 intdep BTreeNode p 功能 返回p所指向的二叉树的高度 其处理过程为 1 若p为NULL则返回0 否则 2 求出左 右子树的高度l1 l2并返回max l1 l2 1 58 互动环节 计算二叉树的高度 templateintBTree dep BTreeNode p intmax if p NULL return 0 else max dep p lchild if dep p rchild max max dep p rchild return max 1 实例函数求当前对象中的高度 templateintBTree dep return dep root 59 树 二 判断两个二叉树相等 boolequal BTreeNode p BTreeNode q 其功能为判断p q所指向的两棵二叉树是否相等 若相等则返回true否则返回false 其处理过程为 1 若p q均为空 则返回true 否则 2 若p q中有一个为空 则返回false 否则 处理p q均非空的情形 3 若结点数据和左右子树均相等 则返回true否则返回false templateboolBTree equal BTreeNode p BTreeNode q boolb if p NULL 60 判断两个二叉树相等 equal函数的另一种形式是实例函数 boolequal BTree 61 复制二叉树 拷贝函数 voidcopybt BTree 62 复制二叉树 递归函数 voidcopybt BTreeNode 要注意的是参数p是结点指针类型 其值会有所改变 因此必修加上引用符号 63 二叉树的遍历 二叉树的遍历是指按照一定次序访问树中所有结点 并且每个结点仅被访问一次的过程 按根节点被访问的先后可分为先序 中序 后序先序 根节点 左子树 右子树中序 左子树 根节点 右子树后序 左子树 右子树 根节点显然 遍历左 右子树的问题仍然是遍历二叉树的问题 所以二叉树的这三种遍历方式可以用递归算法实现 64 二叉树的遍历 先序 根节点 左子树 右子树ABDHICFG中序 左子树 根节点 右子树HDIBAFCG后序 左子树 右子树 根节点HIDBFGCA D H I A B C F G 65 中序遍历的递归函数与实例函数 voidinorder BTreeNode p voidvisit BTreeNode p 其功能为对p所指的二叉树进行中序遍历 对每个结点执行visit函数的操作 其处理过程为 若p非空 则 1 中序遍历p所指结点的左子树 2 对根结点执行visit函数的操作 3 中序遍历p所指结点的右子树 另一种形式的inorder函数不设置结点指针参数 是对当前二叉树进行中序遍历 称为实例函数 voidBTree inorder voidvisit BTreeNode p 66 中序遍历的递归函数与实例函数 templatevoidBTree inorder voidvisit BTreeNode p inorder root visit coutvoidBTree inorder BTreeNode p voidvisit BTreeNode p if p NULL inorder p lchild visit visit p inorder p rchild visit 先序 后序遍历的递归函数也与之类似 67 中序遍历递归函数的执行过程 执行过程 In In C 显示 In 显示 a 显示 显示 b 显示 C In b In a C a b 68 表达式的逆波兰表示 a b c d 先序遍历 先序序列中序遍历 中序序列后序遍历 后序序列 逆波兰表示 ab cd a b c d 69 中序遍历的非递归函数 voidinorder1 voidvisit BTreeNode p 其功能为对当前二叉树进行非递归的中序遍历 执行visit函数的操作 其处理过程为 1 栈初始化 根结点进栈 2 若栈非空 则栈顶结点的左儿子相继进栈 直至NULL退栈 访问栈顶结点 执行visit函数的操作 并使栈顶结点的右儿子成为栈顶结点 3 重复执行步骤 2 直至栈为空 70 中序遍历的非递归函数 templatevoidBTree inorder1 voidvisit BTreeNode p BTreeNode stack 10 p inttop s top 0 stack top root while top 0 while stack top NULL p stack top lchild stack top p top if top 0 p stack top visit p stack top p rchild cout endl 71 互动环节 二叉树显示 为二叉树类增设一个打印二叉树的成员函数 按二叉树的凹入表示法打印二叉树 其输出的形式相当于把二叉树逆时针旋转90度 设计思想 该算法的设计思想与中序遍历二叉树相类似 由于把二叉树逆时针旋转90度后显示在上方的右子树 然后是根节点 最后是左子树 所以该算法是一种特殊的中序遍历算法 为了使不同层次中的结点显示在不同的位置上 在递归函数中设置一个表示递归调用深度的参数 递归打印函数的程序代码如下 72 互动环节 二叉树显示 templatevoidBTree prnt BTreeNode p intl if p NULL prnt p rchild l 1 for inti 0 idatalchild l 1 voidprnt prnt root 1 73 互动环节 重置函数及其测试 templatevoidBTree setroot BTreeNode p dest root copybt root p voidmain char str2 abcdf BTreebt2 str2 6 bt2 prnt BTreeNode p1 newBTreeNode x NULL NULL BTreeNode p2 newBTreeNode y NULL NULL BTreeNode p3 newBTreeNode z p1 p2 bt2 setroot p3 bt2 prnt c f a b d y z x 74 排序二叉树的定义 排序二叉树或为空树或为满足具有以下特点的二叉树 1 所有结点的 数据 值均不相同 2 若左子树为非空 则左子树中所有结点的值均小于根结点的值 3 若右子树为非空 则右子树中所有结点的值均大于根结点的值 4 左子树和右子树均是排序二叉树 75 排序二叉树的动态生成过程 32 16 43 14 25 57 18 52 61 32 57 43 18 61 52 16 25 14 P nil 32 16 32 43 16 25 14 32 76 排序二叉树类的定义 templateclassBSTree publicBTree public BSTree BTreeNode p NULL root p Tminv Tmaxv BTreeNode sear Tel 查找实例函数BTreeNode sear1 Tel 非递归查找函数staticBTreeNode sear Tel BTreeNode bst 递归查找函数voidinst Tel 插入实例函数voidinst1 Tel 非递归插入函数staticvoidinst BTreeNode p BTreeNode 77 求排序二叉树的最值 Tminv 其功能为返回当前排序二叉树中结点关键码的最小值 其处理过程为 使p root 若p为空 则显示相应的信息 否则 1 若p所指结点有左儿子 则令p指向该结点 2 重复 1 直至p所指结点的左儿子链为空 3 返回p所指结点的关键码 程序代码为 templateTBSTree minv BTreeNode p root if p NULL coutlchild NULL p p lchild returnp data 78 树与森林 森林森林是m m 0 棵互不相交的树的集合 树当节点个数n 0时由根节点与M棵子树构成的森林所构成 7 3 6 2 5 4 1 79 树的存储结构 儿子双亲表示法 把树中每个结点的儿子节点排列起来 用单链表来存储 而每个单链表的头指针又组成一个线性表 同时在线性表的元素中又增加父节点的序号 构成儿子双亲表示法 7 3 6 2 5 4 1 80 树的存储结构 儿子兄弟表示法 依据 从最先的祖先开始 只要能确定家属中每个人的儿子与兄弟 即可找到家属中的每个人 e d a c b 81 树 森林转换成二叉树 树转换成二叉树转换方法 用儿子兄弟表示法表示一棵树 并将儿子链看作为左子树 将兄弟链看作为右子树 e d a c b e d a c b 82 树 森林转换成二叉树 森林转换成二叉树 转换方法 将第一棵树转换成二叉树 将第二棵树转换成二叉树 并掛在第一棵二叉树的右子树上 将第三棵树转换成二叉树 并掛在第二棵二叉树的右子树上 互动环节 e d a c b e d a c b f g f g 83 树的应用 哈夫曼树 哈夫曼树的定义节点的路径长度 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 路径上的分支数目称做路径长度树的路径长度 从树根到每一结点的路径长度之和树的带权路径长度 被定义为从各叶结点到树根之间的路径长度与结点上权的乘积和 84 树的应用 哈夫曼树 a WPL 9 2 6 2 5 2 3 2 46 b WPL 6 1 3 2 9 3 5 3 54 c WPL 9 1 6 2 5 3 3 3 45 b 5 3 c 6 d a 9 a 6 5 b 9 c d 3 a 5 6 c 9 b d 3 85 哈夫曼树的定义 具有n个带权叶节点的二叉树中WPL最小的二叉树称为哈夫曼树意义 用于编码设计编码长度 路径长度使用频率 权值报文总长 WPL报文总长最短 WPL最小 86 各类编码 87 哈夫曼树的构造 设给定叶结点的个数n及权值集合 w1 w2 wn 为使二叉树的带权路径长度达到最小 权值越大的叶结点应越靠近根结点 而权值越小的叶结点则离根结点越远 构造方法如下 互动环节 a 6 5 b 9 c d 3 a 5 6 c 9 b d 3 a 6 b 9 c d a 9 5 6 c b d 3 88 哈夫曼树的建树过程 89 哈夫曼树的建树过程 2 6 5 3 3 6 2 2 1 7 4 1 8 4 12 10 8 9 11 13 90 哈夫曼编码的确定 由已形成的哈夫曼树求哈夫曼编码 对每个叶结点都进行如下的处理 扫描由叶结点到根结点的各条分支 若分支中的当前结点与双亲结点是左支关系 则生成编码0 若分支中的当前结点与双亲结点是右支关系 则生成编码1 由此生成的二进制码的序列即为该结点的哈夫曼编码 91 树的应用 哈夫曼编码生成程序 在程序中要使用到两种结构类型 一种是哈夫曼树的结点类型 另一种是哈夫曼编码的结构类型 structHaffNode intweight intparent intlchild intrchild structHaffCode intbit maxlen intstart intweight 92 树的应用 哈夫曼编码生成程序 voidHaffman intw intn HaffNodeht HaffCodehc inti j m1 m2 x1 x2 m1 m2分别表示最小 次小的权值 x1 x2分别表示当前分支结点的左右儿子 步骤1构造哈夫曼树for i 0 i 2 n 1 i 哈夫曼树初始化 if i n ht i weight w i elseht i weight 0 ht i parent 0 ht i lchild 1 ht i rchild 1 在构造某一个分支结点时使用了一个循环for j 0 j n i j 表示从根结点到当前已生成的分支结点中找出两个权值最小的结点 当然应该在还没有确定父结点的结点中进行查找 93 树的应用 哈夫曼编码生成程序 for i 0 i n 1 i 构造哈夫曼树的n 1个分支结点 m1 m2 1000 x1 x2 0 for j 0 j n i j if ht j weight m1 94 树的应用 哈夫曼编码生成程序 步骤2由哈夫曼树生成哈夫曼编码HaffCodecd intchild parent for i 0 i n i 由哈夫曼树生成哈夫曼编码 cd start n 1 cd weight ht i weight child i parent ht child parent while parent 0 if ht parent lchild child cd bit cd start 0 elsecd bit cd start 1 cd start child parent parent ht child parent for j cd start 1 j n j hc i bit j cd bit j hc i start cd start hc i weight cd weight 95 哈夫曼编码生成程序 执行实例 设有字符集 A B C D E F G 各字符对应的权值分别为4 2 6 8 3 2 1 设计各字符的哈夫曼编码 程序代码如下 voidmain intw 4 2 6 8 3 2 1 intn 7 i j HaffNode ht newHaffNode 2 n 1 HaffCode hc newHaffCode n Haffman w n ht hc for i 0 i n i cout weight hc i weight code for j hc i start 1 j n j cout hc i bit j cout endl weight 4code 101weight 2code 1001weight 6code 01weight 8code 11weight 3code 001weight 2code 100weight 1code 1000 96 后记 结束 97 版权所有 1997 c DaleCarnegie Associates Inc 数据结构图 朱振元 98 图的定义 图 graph 是由顶点的有限集合V 顶点数n 0 与边的集合E 顶点之间的关系 构成的 可形式化地定义如下 G V E 其中 V vi vi dataobject E vi vj vi vj VandP vi vj 若P vi vj 表示一条连线 则称G为无向图若P vi vj 表示一条弧 则称G为有向图 99 图的定义 V G1 1 2 3 4 5 E G1 1 2 1 3 2 3 2 4 2 5 3 5 4 5 4 1 5 3 2 图与树的比较 树 一对多 树中的每一个节点最多只有一个父节点 图 多对多 顶点间的关系是任意的 100 图有关的基本术语 图中的每一个数据元素vi称为顶点 vertex 无向图中点的连线 vi vj 称为边 vi vj为此边的两个端点 并称它们互为邻接点 adjacent 而有向图中点的连线则称为弧 并称顶点vi为弧头 始点 顶点vj为弧尾 终点 并称此边是顶点vi的一条出弧 顶点vj的一条入弧 101 图有关的基本术语 顶点的度 入度 出度无向图中顶点v的度 degree 定义为以该顶点为一个端点的边的数目 简单地说 就是该顶点的边的数目 记为d v 如图G1中顶点1的度为2 顶点2的度为4 有向图中顶点的度有入度和出度之分 入度是该顶点的入边的数目 出度是该顶点的出边的数目 顶点v的度等于它的入度和出度之和 102 图有关的基本术语 路径和回路若存在顶点的序列 v1 v2 vm 其中 vi vj E i 1 2 m 1 则称v1到vm存在一条路径 路径长度即为边或弧的数目 特别地当v1 vm时 则称次路径为回路或环 103 图有关的基本术语 子图设有两个图G V E 和G V E 若V 是V的子集 且E 是E的子集 则称G 是G的子图 直观地看 子图就是将原来的图中的部分点和边去掉后所得到的图 4 1 5 3 2 4 1 3 2 104 图有关的基本术语 权和网在一个图中 每条边可以标上具有某种含义的数值 此数值称为该边的权 weight 例如 用权值来标记距离或花费等 边上带有权的图称作带权图 也常称作网 4 1 3 2 2 4 1 3 2 5 3 4 3 3 3 4 4 5 5 2 105 存储方式 邻接矩阵 对于有向图 若图G V E 是一个有n个顶点的图 则G的邻接矩阵A是一个n n的二维数组 且 4 1 5 3 2 106 存储方式 邻接矩阵 对于无向图 邻接矩阵A是一个对称矩阵 即 A i j a j i 4 1 5 3 2 107 存储方式 邻接矩阵 对于带权图 网 我们也可以用邻接矩阵来表示 4 1 5 3 2 3 1 7 4 2 5 2 108 存储方式 邻接链表 constintmax 100 n为图中允许的最大顶点数structArcNode 弧结点类型定义 intadjvex ArcNode nextarc structVexNode 顶点结点类型定义 intvexdata ArcNode firstarc VexNodeadjlist max 邻接表adjlist的定义 4 1 5 3 2 109 存储方式 邻接链表 有向图邻接链表对于出弧建立弧节点 4 1 5 3 2 110 存储方式 邻接链表 有向图逆邻接链表对于入弧建立弧节点 4 1 5 3 2 111 存储方式 邻接链表 对于无向图每一条边生成二个边节点 分别挂在对方节点的链上 4 1 5 3 2 112 存储方式 邻接链表 对于有向网在弧节点中增设权值域 4 1 5 3 2 3 1 7 4 2 5 2 113 互动环节 画出以下有向图的 1 连接矩阵 邻接链表 逆邻接链表 2 深度及广度优先序列 4 1 5 3 2 6 114 图的遍历 概述含义 从指定的某个顶点 称为初始点 出发 按照一定的搜索方法访问对图中的所有顶点且每个节点只访问一次复杂性 因为存在着多条路径 可能被多次访问 因而要设置标记向量visited 1 n 种类 一种是深度优先搜索遍历 另一种是广度优先搜索遍历 115 边结点 顶点结点的类型定义 structArcNode intadjvex ArcNode nextarc structVexNode intvexdata intox oy ArcNode firstarc 116 邻接链表图类Graph classGraph private staticStringstr bool visited VexNode adjlist intn voiddfs0 intv0 voidvisit int 117 邻接链表图类的构造函数 构造函数Graph VexNodeadjl intl 功能是构造一个由adj1表示的顶点个数为l的邻接链表对象 实际上是将参数中指定的邻接链表复制到当前对象中 构造函数Graph intvex intarc intn 功能是按参数中给出的顶点数据和邻接矩阵生成邻接链表的存储结构 其中参数vex给出各顶点中的数据元素值 arc是邻接矩阵的一维排列 n是顶点的个数 118 深度优先遍历 从确定的某一顶点v0开始 按先纵向后横向的次序访问与v0有路径相通的所有的顶点 直观理解 连长 1排长 1班长 2班长 3班长 2排长 4班长 5班长 6班长 3排长 7班长 8班长 9班长 119 深度优先遍历接口函数 Stringdfs intv0 voidvisit int 120 深度优先遍历递归函数 voiddfs0 intv0 voidvisit int v 功能 从v0开始对邻接表adjlist所表示的图按深度优先规则进行遍历 1 访问顶点v0 执行visit操作 并作访问标记 2 按邻接链表取v0的一个未访问的邻接点w 从w出发进行深度优先遍历 3 重复过程 2 直至v0的所有邻接点均被访问 121 深度优先遍历递归函数程序代码 voidGraph dfs0 intv0 voidvisit int 122 广度优先遍历 从确定的某一顶点v0开始 按路径长度由近至远的次序 依次访问与v0有路径相通的所有的顶点 直观理解 连长 1排长 2排长 3排长 1班长 2班长 3班长 4班长 5班长 6班长 7班长 8班长 9班长 123 广度优先遍历 涉及的变量已在类中说明bool visited VexNode adjlist 层次队列intq 100 front rear 作用 记录已被访问但其下一层尚未访问的顶点 以便实现逐层访问 使用方法 访问后进队列 出队列时依次访问各邻接点 访问后进队列 124 广度优先遍历接口函数 Stringbfs intv0 voidvisit int 125 广度优先遍历函数 voidbfs0 intv0 voidvisit int v 功能 从v0开始对邻接表adjlist所表示的图进行广度优先遍历 即从v0开始由近至远依次访问和v0路径相通的顶点 1 置层次队列初态 2 访问顶点v0 执行visit操作 作访问标记并将v0放进队列 从队列中取出一个顶点 依次访问 标记它的每一个未访问的邻接点 并在访问后进队列 4 重复上述过程 3 直至队列为空队列 126 广度优先遍历程序代码 voidGraph bfs0 intv0 voidvisit int 处理v的一个邻接点 取点号 adjv 若未访问过则进行处理 127 图的应用拓扑排序 有向无环图 不存在回的有向图这是拓扑排序的前提AOV网 是一个有向图 其顶点表示活动 弧表示活动间先后关系 3 2 5 4 1 128 图的应用拓扑排序 拓扑排序的含义 偏序 全序即将图之所有的顶点排成一个线性序列 并使各顶点间的先后关系都得到满足 例如 在下图中 顶点表示课程 有向边表示课程之间的先后关系 拓扑排序要确定所有课程的安排为 12345或12435 3 2 5 4 1 129 拓扑排序的方法 l 在AOV网中选一个没有直接前驱 入度为0 的顶点 并访问 2 从图中删去该顶点 同时删去它所发出的所有弧 3 重复 1 2 直到图中不存在入度为0的点 C B D E F C B D E A F C B D F 130 拓扑排序的实现 顶点的存储形式在顶点节点中增加一个入度域表示入弧的个数structArcNode intadjvex ArcNode nextarc structVexNode intvexdata intindegree ArcNode firstarc VexNodeadjlist