数据结构实用教程(C语言版)中ppt.ppt

数据结构实用教程 C语言版 中 第五章树第六章图 第五章树 树形结构的逻辑特征是 有且仅有一个开始结点 可有若干个终端结点 其余的内部结点都有且仅有一个前趋结点 可以有若干个后继结点 也就是说结构中的数据元素间存在着一对多的层次关系 本章首先简单介绍树的基本概念 然后重点讨论二叉树的逻辑结构 存储结构及其运算 线索二叉树和线索二叉链表以及如何利用线索来实现遍历运算 并分析树 森林与二叉树之间的相互转换问题 最后介绍二叉树和树的典型应用 主要内容 5 1树的定义5 2二叉树二叉树的定义及性质二叉树的存储二叉树的遍历及实现算法5 3线索二叉树中序线索二叉树的定义中序线索二叉树上遍历的实现利用中序线索实现前序遍历和后序遍历5 4树和森林5 5哈夫曼树 5 1树的定义 一 树的定义1 树的二元组定义 设tree D S 其中D是数据元素的集合 S是D中数据元素之间关系的集合 设关系r S 相对r 满足下列条件 1 D中有且仅有一个开始结点 该结点被称为树的根 Root 2 除树根结点外 D中其余的结点有且仅有一个前趋结点 3 从根到其余结点都有路径 则称tree是相对r的树形结构 如图所示的树 该树采用二元组表示如下 设tree D S r SD A B C D E F G H I r 其中A是开始结点 即树的根 除根A外 其余的结点有且仅有一个前趋结点 但对于后继结点却没有限制 A有三个后继结点B C和D B和G分别有两个后继结点 D只有一个后继结点 剩下的结点E F C H I都没有后继 属于终端结点 树形结构与线性结构比较 在线性结构中 有且仅有一个开始结点和一个终端结点 其余的内部结点都有且仅有一个前趋和一个后继 在树形结构中也是有且仅有一个开始结点 称为根 但终端结点 称为叶子 可以为任意多个 其余的内部结点都有且仅有一个前趋 但可以有任意多个后继 树形结构中放宽了对结点的后继的限制 线性结构中每个元素的后继最多为一个 而树形结构的后继可以为多个 若树中每个非终端结点的后继刚好为一个时 就是线性表 线性结构是树形结构的一种特殊形式 2 树的递归定义树是一种递归的数据结构 也可以用递归的形式来定义树 树的递归定义如下 树是n n 0 个结点的有限集合 记作T 它满足两个条件 1 有且仅有一个特定的称为根的结点 2 其余的结点可分为m m 0 个互不相交的有限集合T1 T2 Tm 其中每个集合又是一棵树 并称其为根的子树 Subtree 3 树的表示方法除了前面介绍的树形表示法和二元组表示法外 还有其他三种常用的表示方法 凹入表表示法 嵌套集合表示法和广义表表示法 其中 树形表示法是最常用的表示方法 本书主要采用树形表示法 由于连线的箭头全部向下 所以省略箭头 4 树中常用的一些基本术语 1 与层次相关的术语 在树中 有且仅有一个开始结点 称为根结点 Root 在树中处于最上层 除根结点外的其余所有结点都有且仅有一个前趋 每个结点的前趋结点称为该结点的父 双亲 结点 Parent 在树中处于该结点的上一层 树中的每个结点都可以有若干个后继结点 每个结点的后继点称为该结点的子 孩子或子女 结点 Child 在树中处于该结点的下一层 它们是该结点的子树的根 没有后继的结点称为叶子结点 Leaf 叶子结点是树的终端结点 可以为多个 双亲相同的结点互称为兄弟 Silbing 在树中处于同一层 2 树中结点之间具有分支 一个结点的子树的个数 称为该结点的度 Degree 树中度最大的结点的度数称为该树的度 3 路径 Path 是树中结点的序列 设结点序列为b1 b2 bj 若序列中任意两个相邻结点都满足bi是bi 1的双亲 1 i j 1 则称该结点序列为从b1到bj的路径 路径长度为序列中结点总数减1 即所经过的边的数目 若树中存在一条从b到bj的路径 则称b是bj的祖先 Ancestor 而bj是b的子孙 Descendant 4 如果树中所有子树都看成是从左到右的次序排列 子树不能互换 则称此树为有序树 OrderedTree 而不考虑子树排列顺序的树 称为无序树 UnorderedTree 5 森林 Forest 是m m 0 棵互不相交的树的集合 5 2二叉树 一 二叉树的定义及性质1 二叉树 BinaryTree 是n n 0 个结点的有限集合 满足 当n 0时 为空二叉树 当n 0时 是由一个根结点和两棵互不相交的分别称作这个根的左子树和右子树的二叉树组成 在二叉树中 每个结点左子树的根为该结点的左孩子 LeftChild 右子树的根为该结点的右孩子 RightChild 2 二叉树通常有五种基本形态 3 二叉树具有以下重要的性质 性质1二叉树第i层上最多有2i 1 i 1 个结点 性质2深度为k的二叉树最多有2k 1 i 1 个结点 性质3在任意一棵二叉树中 若叶子结点数为n0 度为2的结点数为n2 则n0 n2 1 两种特殊的二叉树 满二叉树和完全二叉树每层结点数都达到最大值的二叉树称为满二叉树 FullBinaryTree 除最下面一层外其余各层的结点数都达到最大值 并且最下一层上的结点都集中在最左边的若干位置上 则此二叉树为完全二叉树 CompleteBinaryTree a 满二叉树 b 完全二叉树 c 类似完全二叉树显然 满二叉树是完全二叉树 但完全二叉树不一定是满二叉树 如果将满二叉树的最下层上结点从最右边开始连续删去若干个 就可以得到一棵完全二叉树 性质4具有n个结点的完全二叉树的深度为或 性质5对一棵具有n个结点的完全二叉树 按照层次从上到下 每一层从左到右的次序 亦称二叉树的层次次序 将所有结点依次排列 可得到结点的层序序列 其中根结点的序号为1 其余结点的序号连续排列 对任一序号为i的结点 称结点i 有 1 若结点i有双亲 除根结点外 即i 1 则双亲的序号为 i 2 2 若结点i有左孩子 即2i n时 则左孩子为2i 即任意结点左孩子的序号一定为偶数 3 若结点i有右孩子 即2i 1 n时 则右孩子为2i 1 即任意结点右孩子的序号一定为奇数 4 当i为偶数且i n时 它有右兄弟 右兄弟为i 1 当i为奇数且i 1时 它有左兄弟 左兄弟为i 1 二 二叉树的存储1 顺序存储 1 完全二叉树的顺序存储对一棵具有N个结点的完全二叉树 将所有结点按照从上到下 从左到右的次序依次排列 得到完全二叉树中结点的层序序列 其中根结点的序号为1 然后将这个序列依次存储在长度为N 1的数组bt中 为了保持序号和下标一致 下标为0的单元不用 完全二叉树及其顺序存储结构如图所示 2 一般二叉树的顺序存储一般二叉树与完全二叉树对照 在空缺的位置处添加虚点 用特殊字符 如 表示 从而将一般的二叉树扩充成完全二叉树 然后将扩充后的完全二叉树顺序存储 即带着添加的虚点一起将完全二叉树中的结点按层序排列 按照序号将所有结点依次存放在一维数组中 其中根结点的编号为1 2 链接存储每个结点除了存储本身的数据外 需要附加两个指针域分别指向该结点的左孩子和右孩子 这就是二叉链表 有时为了运算方便 每个结点再附加一个指针域存储双亲结点的指针 即带父指针的二叉链表 也称为三叉链表 二叉链表是二叉树的链接存储结构中为最常用的一种 其中lchild和rchild分别表示指向结点左 右孩子的指针 二叉链表存储结构的C语言描述为 typedefcharDataType typedefstructNode DataTypedata structNode lchild rchild BiTree BiTree root 根结点的指针 二叉树中的每个结点都为BiTree类型 它们之间通过lchild指针和rchild指针联系在一起 可以通过保存根结点的指针root来唯一标识一棵二叉树 3 二叉链表的建立算法的实现步骤如下 1 初始化队列和二叉链表 2 读取用户输入的结点信息 若不是虚点 则建立一个新结点 同时将结点的地址入队 3 新结点若为第一个结点 则将此结点的地址存入根指针中 否则 从队头中取出双亲结点的指针 将此结点作为左孩子 或右孩子 链接到双亲结点上 若此结点的编号为偶数则为左孩子 否则为右孩子 当一个结点的两个孩子都已链接完毕 即结点编号为奇数时 队头元素出队 此时的队头元素必定是下一个新结点的双亲结点 4 重复步骤2 3 直到遇到结束标志符 defineMAXSIZE100typedefstruct 顺序队列的定义 BiTree data MAXSIZE intfront rear SeQueue BiTree createTree SeQueueQ q 三 二叉树的遍历及实现算法二叉树的遍历 Traversal 是指沿着某条搜索路径访问二叉树中的每个结点 且每个结点仅访问一次 访问 是指对结点的操作 其含义可以很广 如可以是输出结点的信息 修改结点数据等 二叉树由根结点 左子树 右子树三个基本部分组成 遍历一棵非空二叉树的问题可分解为 访问根结点 遍历左子树和遍历右子树 若分别用L D R分别表示上述三个子问题 则可有6种不同的遍历次序 DLR LDR LRD DRL RDL RLD 约定左子树的访问在右子树之前 则讨论三种遍历方法 DLR 前序遍历 PreOrderLDR 中序遍历 InOrder LRD 后序遍历 PostOrder 二叉树是递归的数据结构 因为它的左 右子树也是二叉树 因此对左 右子树的遍历仍然是遍历二叉树的问题 要用相同的次序来完成 所以 可以用递归的方法来定义二叉树的遍历运算 1 前序遍历二叉树 DLR若二叉树非空 则 1 访问根结点 2 前序遍历左子树 3 前序遍历右子树 2 中序遍历二叉树 LDR若二叉树非空 则 1 中序遍历左子树 2 访问根结点 3 中序遍历右子树 3 后序遍历二叉树 LRD若二叉树非空 则 1 后序遍历左子树 2 后序遍历右子树 3 访问根结点 编写递归算法需要把握两个方面内容 递归项和递归出口 亦称终止条件 这里的递归项比较明显 由于对左 右子树的遍历就是对二叉树的遍历 则遍历左子树和遍历右子树都为递归项 另外 只要二叉树不为空 就可以将其分成根 左子树 右子树三个部分 分别进行访问 但若二叉树为空树 遍历运算就结束了 所以递归出口是二叉树为空 由此 可以得出二叉树遍历的递归算法 voidPreOrder BiTree T 前序遍历二叉树 if T 当二叉树非空 进入递归过程 否则 遍历运算结束 printf c T data 访问根结点 PreOrder T lchild 前序遍历左子树 PreOrder T rchild 前序遍历右子树 voidInOrder BiTree T 中序遍历二叉树 if T InOrder T lchild 中序遍历左子树 printf c T data 访问根结点 InOrder T rchild 中序遍历右子树 voidPostOrder BiTree T 后序遍历二叉树 if T PostOrder T lchild 后序遍历左子树 PostOrder T rchild 后序遍历右子树 printf c T data 访问根结点 二叉树的中序遍历递归算法的执行过程 中遍历算法执行时的系统栈变化 仿照系统栈在实现递归过程中的作用 自己定义一个栈将递归算法转化为非递归的算法 非递归算法的C函数如下 defineMAXSIZE100typedefBiTree SElemType typedefstruct SElemTypedata MAXSIZE 顺序栈中保存的是结点指针 inttop SeqStack voidInOrder BiTree p SeqStack s s initSeqStack while 1 while p push s p p p lchild if empty s break p top s pop s printf c p data p p rchild 5 3线索二叉树 当结点的左指针域为空 无左孩子 时 用它的左指针域存放该点在某种遍历次序下的前趋结点的指针 当结点的右指针域为空 无右孩子 时 用它的右指针域存放该点在某种遍历次序下的后继结点的指针 简单地说 左空指前趋 右空指后继 以这种结点构成的二叉链表称为线索二叉链表 指向前趋或后继的指针称为线索 Thread 加上线索的二叉树称为线索二叉树 以某种次序遍历 使二叉树变为线索二叉树的过程称作线索化 对每个指针域再附加一个标志 当指针域中存放的是孩子指针时 标志为0 当指针域中存放的是线索时 标志为1 线索二叉链表存储结构的C语言描述如下 typedefcharDataType typedefstructNode DataTypedata structNode lchild rchild intltag rtag BiThrTree 一 中序线索二叉树的定义若线索二叉树的线索中保存的是结点在前序遍历下的前趋和后继的指针 则这种线索称为前序线索 同理 若保存的是中序遍历下的前趋和后继的指针 称为中序线索 若保存的是后序遍历下的前趋和后继的指针 称为后序线索 对应的线索二叉树有前序线索二叉树 中序线索二叉树和后序线索二叉树 线索链表有前序线索链表 中序线索链表和后序线索链表 若要实现中序线索化的运算 在内存中建立中序线索二叉链表 需要先按照线索树中的结点结构建立二叉链表存储结构 即每个结点的左 右标志域均为0 在这样的存储结构上进行中序线索化 只要按中序遍历二叉链表 在遍历过程中用线索取代空指针即可 设两个指针 一个指针pre始终指向刚刚访问过的结点 一个指针p指向当前正在访问的结点 具体方法是 1 若结点 p有空指针域 则将相应的标志域置为1 2 若结点 p有中序前趋结点 pre pre NULL 则 1 若结点 pre的右标志为1 pre rtag 1 则令pre rchild为指向其中序后继结点 p的指针 右线索 即pre rchild p 2 若结点 p的左标志为1 p ltag 1 则令p lchild为指向其中序前趋结点 pre的指针 左线索 即p lchild pre 3 将pre指向刚刚访问过的结点 p 即pre p 保留前趋结点指针 中序线索化算法的C函数 BiThrTree pre NULL 全局变量 前趋指针 voidinthreaded BiThrTree p 中序线索化 if p inthreaded p lchild 线索化左子树 if p lchild NULL p ltag 1 根据左右孩子修改当前结点 p的标志域 if p rchild NULL p rtag 1 if pre NULL 当前结点 p有前趋 只有中序遍历的第一个结点无前趋 if pre rtag 1 pre rchild p 设置前趋结点 pre的后继 if p ltag 1 p lchild pre 设置当前结点 p的前趋 pre p 保存刚刚访问的结点指针 inthreaded p rchild 线索化右子树 二 中序线索二叉树上遍历的实现首先要找到中序遍历的第一个结点 二叉树中最左下点 其左线索为空 然后依次找到该结点的中序后继 直到中序遍历的最后一个结点 其右线索为空 算法结束 同理 可从中序遍历的最后一个结点出发 依次找该结点的中序前趋 直到中序遍历的第一个结点 算法结束 在中序线索下查找 p结点的中序后继有两种情况 1 若 p的右标志为1 p rtag 1 右子树为空 则p lchild为右线索 指向 p结点的中序后继 2 若 p的右标志为0 p rtag 0 右子树非空 则 p的中序后继为右子树的最左下结点 也就是从 p的右孩子开始 沿左指针往下找 直到找到一个没有左孩子的结点 q q ltag 1 则 q就是 p的中序后继 中序遍历算法的C函数如下 voidInOrderThread BiThrTree root 中序线索下的中序遍历 BiThrTree p p root while p ltag 0 p p lchild 找中序遍历的第一个结点 二叉树的最左下点 while p printf c p data 输出结点 if p rtag 1 p p rchild 分两种情况查找结点后继 else p p rchild while p ltag 0 p p lchild 三 利用中序线索实现前序遍历和后序遍历利用中序线索不但能方便地进行中序遍历 还可以方便地进行前序和后序遍历 如果可以利用中序线索找到每个结点在前序遍历下的前趋或后继 便可以进行前序遍历 由于前序遍历的次序为根结点 左子树 右子树 所以利用中序线索找 p结点前序遍历下的后继的方法为 1 若 p有左孩子 则左孩子为前序后继 2 若 p无左孩子但有右孩子 则右孩子为前序后继 3 若 p既无左孩子也无右孩子 则沿着 p结点的右线索 q rtag 1 一直向上走 直到找到 q结点 q rchild不是线索是指针 q rtag 0 此时 q rchild 结点就是 p的前序后继 同理 根据中序线索可以找到每个结点后序遍历下的前趋 从而进行后序遍历 利用中序线索进行前序遍历算法的C函数如下 voidPreOrderThread BiThrTree root 中序线索下的前序遍历 BiThrTree p p root 查找前序序遍历的第一个结点 根结点 while p 不断找前序后继 printf c p data 输出结点 if p ltag 0 p p lchild 查找结点前序后继 else while p 利用中序线索进行后序遍历算法的C函数如下 voidPostOrderThread BiThrTree root 中序线索下的后序遍历 BiThrTree p p root 查找后序遍历的最后一个结点 根结点 while p 不断找后序前趋 printf c p data if p rtag 0 p p rchild 查找结点前趋 else while p 5 4树和森林 一 树和森林的遍历树的先根遍历定义为 若树非空 先访问根结点 然后从左到右依次先根遍历每棵子树 树的后根遍历定义为 若树非空 先从左到右依次后根遍历每棵子树 最后访问根结点 显然 树的先根遍历和后根遍历过程都是递归过程 图中树的先根遍历序列为 A B F D C G E H 后根遍历序列为 F B D G H E C A 先根遍历森林定义为 若森林非空 则首先先根遍历森林中的第一棵树 然后从左到右依次先根遍历除第一棵树外其它树组成的森林 后根遍历森林定义为 若森林非空 则首先后根遍历森林中的第一棵树 然后从左到右依次后根遍历除第一棵树外其它树组成的森林 同样 森林的先根遍历和后根遍历过程也都是递归过程 先根序列 A B F D C G E H I J K L M N O后根序列 F B D G H E C A J L K I O N 二 森林与二叉树的转换森林转化为二叉树的定义为 1 若森林为空 则二叉树为空 2 若森林不空 则二叉树的根为森林中第一棵树的根 二叉树的左子树为第一棵树去掉根之后的子树森林转换成的二叉树 二叉树的右子树为森林除去第一棵树后剩下的树组成的森林转化成的二叉树 简单的转换规则 1 在森林中的所有兄弟之间添加一条连线 所有的根结点认为是兄弟 2 保留父点与第一个孩子之间的连线 去掉父点与其他孩子之间的连线 3 将此时树中的水平连线和垂直连线顺时针旋转45 整理成二叉树中的左右子女 二叉树也可以转化为森林 其转换规则为 1 若二叉树为空 则对应的森林为空 2 若二叉树不空 则森林中第一棵树的根即为二叉树的根 第一棵树根的各个子树为二叉树的左子树对应的森林 森林中其余的树为二叉树的右子树对应的森林 三 树的存储1 双亲表示法用一组连续的存储空间 一维数组 存储树中的各个结点 数组中的一个元素存储树中的一个结点 数组元素为结构体类型 其中包括结点本身的信息以及结点的双亲在数组中的序号 树的这种存储方法称为双亲表示法 2 孩子链表表示法将结点的所有孩子用链接方式存储在一个单链表中 没有孩子的结点后面的单链表为空 树中结点用顺序方式存储在一个长度为n n为树中结点数 的数组中 数组的每一个元素由两个域组成 一个域用来存放结点信息 另一个用来存放该结点的孩子链表的头指针 单链表的结构也由两个域组成 一个存放孩子结点在一维数组中的序号 另一个是指针域 指向下一个孩子结点 3 树的二叉链表 孩子 兄弟链 表示法实际上就是将树转换为对应的二叉树 然后再采用二叉链表存储结构 将树转换为对应的二叉树后 树中每个结点的第一个孩子是对应二叉树中该结点的左孩子 而每个结点的右兄弟对应二叉树中该结点的右孩子 所以该方法又称孩子 兄弟链表示法 每个结点除其信息域外 再增加两个指针域 分别指向该结点的第一个孩子结点和下一个兄弟结点 5 5哈夫曼树 一 哈夫曼树的定义及建立结点的路径长度就是从根结点到每个结点的路径长度 其值为路经上的结点数减1 赋予了权值的结点的路径长度与该结点权值的乘积即为结点的带权路径长度 WeightedPathLengthofNode 树的带权路径长度 WeightedPathLengthofTree 缩写为WPL 定义为 树中所有叶子结点的带权路径长度之和 记为 其中n表示叶子结点数 wi表示第i个叶子结点的权值 li代表第i个叶子结点的路径长度 WPLa 2 2 3 2 6 2 8 2 38WPLb 8 1 6 2 2 3 3 3 35WPLc 2 1 6 3 8 3 3 2 50WPLd 8 1 2 3 3 3 6 2 35哈夫曼树 HuffmanTree 又称最优二叉树 是在含有n个叶子结点 权值分别为w1 w2 wn的所有二叉树中 带权路径长度WPL最小的二叉树 哈夫曼 D A Huffman 在上世纪五十年代初便提出了一个非常简单的算法来建立哈夫曼树 其算法描述如下 1 将给定的n个权值 w1 w2 wn 作为n个根结点的权值 构造一个具有n棵二叉树的森林 T1 T2 Tn 其中每棵二叉树只有一个根结点 2 在森林中选取两棵根点权值最小的二叉树分别作为左 右子树 增加一个新结点作为根 从而将两棵树合并成一棵树 新根结点的权值为左右子树根结点权值之和 森林中因此也减少了一棵树 3 重复上面步骤 2 的处理过程 直到森林中只有一棵二叉树为止 这棵二叉树就是哈夫曼树 从哈夫曼树构造过程和生成结果可知 哈夫曼树具有以下特点 1 哈夫曼树不唯一 2 哈夫曼树中只包含度为0和度为2的结点 3 树中权值越大的叶子结点离根结点越近 例5 1假设树中叶子结点的权值为 5 29 7 8 14 23 3 11 构造一棵哈夫曼树 1 将给定的8个权值作为根结点 构造具有8棵树的森林 2 从森林中选取根点权值最小的两棵二叉树3 5 分别作为左右子树 构造一棵新的二叉树 新树根点权值为8 森林中减少一棵树 3 重复步骤 2 直到森林中只剩一棵二叉树为止 为方便查找双亲 将哈夫曼树的存储结构设计为三叉链表 每个结点包含四个域 weight为结点的权值 lchild rchild parent分别为左 右孩子和双亲结点的指针 含有N个叶子结点的哈夫曼树共有2N 1个结点 由此可定义一个长度为2N 1的数组tree来存储哈夫曼树 下标从1开始 0代表指针空 NULL 存储结构用C语言描述为 defineN7 叶子结点数 defineM2 N 1 总结点数 typedefstruct 哈夫曼树结点的存储结构 floatweight 结点的权值 intparent 双亲在数组中的下标 intlchild rchild 左 右孩子在数组中的下标 叶结点的这两个指针值为0 HufmTree HufmTreetree M 1 哈夫曼树的静态链表存储结构 下标为0的单元空出 在上述存储结构上实现哈夫曼算法的过程如下 1 将哈夫曼树数组tree中的2N 1个结点初始化 即将各结点的权值 双亲 左孩子 右孩子均置为0 2 读入N个叶子结点的权值 分别存入数组tree i 1 i N 的权值域中 构造包含N棵树的初始森林 森林中的每棵树只有一个根结点 3 循环N 1次 对森林中的树进行N 1次合并 产生N 1个新结点 依次放入数组tree i 中 N 1 i 2N 1 每次合并的步骤是 1 在当前森林的所有结点tree j 1 j i 1 中 选取具有最小权值和次小权值的两个根结点 parent域为0的结点 分别用p1和p2记住这两个根结点在数组tree中的下标 2 将根为tree p1 和tree p2 的两棵树合并 使其成为新结点tree i 的左 右孩子 得到一棵以新结点tree i 为根的二叉树 即将tree i weight赋值为tree p1 weight和tree p2 weight之和 tree i 的左指针赋值为p1 tree i 的右指针赋值为p2 同时将tree p1 和tree p2 的双亲域均赋值为i 使其指向新结点tree i 即它们在当前森林中已不再是根结点 二 哈夫曼编码及译码在进行文字传输时 数据通信的发送方需要将原文中的每一个文字转换成对应的二进制0 1序列 编码 进行发送 接收方接收到二进制的0 1串后再还原成原文 译码 其编码和译码的过程如下所示 原文 电文 二进制的0 1序列 原文常用的编码方式有两种 等长编码和不等长编码 等长编码 ASC 码 其特点是每个字符的编码长度相同 编码简单且具有唯一性 当字符集中的字符在电文中出现的频度相等时 它是最优的编码 不等长编码 字符的编码长度不等 因此称这种编码方式为不等长编码 为了使译码唯一 则要求字符集中任一字符的编码都不是其他字符编码的前面一部分 这种编码叫做前缀 编 码 利用二叉树来对叶子结点进行编码 所得的编码一定为前缀码 若要使报文总长最短 则利用哈夫曼树对叶子结点进行编码一定是最优的编码 哈夫曼编码的实现方法如下 1 利用字符集中每个字符的使用频度作为权值构造一个哈夫曼树 2 从根结点开始 与左孩子的连线标上0 与右孩子的连线标上1 3 由根到某叶子结点的路经上的0 1序列组成该叶子结点的编码 例5 2假设有一个字符集包含8个字符 a b c d e f g h 每个字符的使用频度 权值 分别为 5 29 7 8 14 23 3 11 为每个字符设计哈夫曼编码 哈夫曼编码的实现算法首先根据字符的权值构建哈夫曼树 然后从每个叶子结点开始不断的向上搜索双亲结点 直到根点为止 得出字符的哈夫曼编码 编码的存储结构及实现算法的C函数描述如下 typedefstruct 哈夫曼编码的存储结构 charbits N 保存编码的数组 intstart 编码的有效起始位置 从该位置之后的01串为字符的编码 charch 字符 CodeType CodeTypecode N 1 字符编码数组 下标为0的单元空出 huffmanCode HufmTreetree CodeTypecode 利用哈夫曼树求字符的哈夫曼编码 inti c p for i 1 i N i N次循环 分别得到N个字符的编码 code i start N c i p tree i parent 获取字符的双亲 while p 0 一直往上层查找 直到根结束 code i start if tree p lchild c code i bits code i start 0 elsecode i bits code i start 1 c p p tree p parent 3 译码与编码过程相反 译码过程是从哈夫曼树的根结点出发 逐个读入电文中的二进制码 若读入0 则走向左孩子 否则走向右孩子 一旦达到叶结点 便译出相应的字符 然后 重新从根结点出发继续译码 直到二进制电文结束 decode HufmTreetree CodeTypecode 已知哈夫曼树和哈夫曼编码 对输入的01码进行译码 inti m b tree m 中保存的是哈夫曼树的根 i m表示从根点出发进行译码 intendflag 1 标识是否结束 intyiflag 标识是否刚好译出一个字符 scanf d 若输入的01码序列不规范 则会提示译码错误 第六章图 6 1图的概念图 Graph 是一种结点之间为多对多关系的数据结构 逻辑特征是 可以有任意个开始结点和任意个终端结点 其余各个结点可以有任意个前趋和任意个后继 图中的结点常称为顶点 图的逻辑结构可以用二元组表示 Graph V E V是顶点 vertex 的集合 E是边 edge 的集合 有向图 Digraph 若图G中的每条边都是有方向的 则称图G为有向图 例 G1 V1 E1 V1 v1 v2 v3 E1 G2 V2 E2 V2 v1 v2 v3 E2 无向图 Undigraph 若图G中的每条边都是没有方向的 则图G称为无向图 例 G3 V3 E3 V3 v1 v2 v3 v4 E3 v1 v2 v1 v3 v1 v4 v2 v3 v2 v4 G4 V4 E4 V4 v1 v2 v3 E4 v1 v2 v1 v3 v2 v3 顶点的度有向图中 顶点的度分成入度与出度入度 该顶点入边的数目出度 该顶点出边的数目无向图中 顶点的度为与该顶点相连的边数 邻接点与关联边有向图中 若是有向图中的一条边 则顶点x和顶点y称为邻接点 称x邻接到y或y邻接于x 同时称边是顶点x和顶点y相关联的边 Incident 无向图中 若 x y 是无向图中的一条边 则顶点x和顶点y互为邻接点 并且称边 x y 是顶点x和顶点y相关联的边 子图 设有图G V E 如果满足 V VE EE 中边所邻接的点均在V 中出现则G V E 也是一个图 并且称之为G的子图 有向完全图 n个顶点的有向图最大边数是n n 1 无向完全图 n个顶点的无向图最大边数是n n 1 2路径 有向图G V E 中 若存在一个顶点序列vp vi1 vi2 vin vq 使得 均是图中的边 则称此序列是从顶点vp到vq一条路径 路径长度 该路径上经过边的数目 回路 一条路径第一个顶点和最后一个顶点相同的叫 简单路径 序列中顶点不重复出现的路径叫 简单回路 除了第一个顶点和最后一个顶点外 其余顶点不重复出现的回路叫 有根图 若存在一个顶点v 从该顶点到其余各个顶点都有路径 则称此图为有根图连通 从顶点x到顶点y有一条路径 则说x和y是连通的连通图 图中任意两个顶点都是连通的叫连通图连通分量 无向图G的极大连通子图称为G的连通分量强连通图 若G中任意两个顶点都是强连通的 则称图G是强连通图强连通分量 有向图G的极大强连通子图称为G的强连通分量权 与图的边相关的数值叫权值 网络 边上带权的图称为网络 6 2图的存储结构邻接矩阵 表示顶点之间邻接关系的矩阵设G V E 是具有n个顶点的图 则G的邻接矩阵是一个n阶方阵A A中元素的值aij可以定义为 特点 无向图的邻接矩阵对称 有n个顶点的无向图需存储空间为n 有向图邻接矩阵不一定对称 有n个顶点的有向图需存储空间为n 无向图中顶点Vi的度是邻接矩阵A中第i行元素之和有向图中 顶点Vi的出度是A中第i行元素之和顶点Vi的入度是A中第i列元素之和网的邻接矩阵可定义为 可以得到邻接矩阵存储结构C语言描述如下 definen5 图的顶点数 definee6 图的边数 definemax10000 设置一个极大数无穷大 typedefcharvextype 顶点类型 typedefintadjtype 权值类型 typedefstruct vextypevertex n 1 顶点数组 adjtypeedge n 1 n 1 邻接矩阵 adj matrix 邻接表邻接表法 AdjacencyList 是图的一种链式存储结构 顶点采用顺序方式进行存储 用n个单链表来存储图中的边 第i个单链表是所有与第i个顶点相关联的边链接而成的 称此单链表为第i个顶点的边表 边表中的每个结点称为边表结点 在顶点的顺序表中 每个元素增加一个指针域用来存放各个边表的头指针 称此顺序表为顶点表 而顺序表中的每个元素称为顶点表结点 顶点表和各顶点的边表一起组成图的邻接表 邻接表存储结构C语言描述如下 typedefstructnode intadjvex 邻接点域 structnode next 指针域 edgenode 定义边表结点 typedefstruct vextypevertex 顶点域 edgenode link 指针域 vexnode 定义顶点表结点 vexnodeadjlist n 1 特点无向图中顶点Vi的度为第i个单链表中的结点数有向图中顶点Vi的出度为第i个单链表中的结点个数顶点Vi的入度为整个单链表中邻接点域值是i的结点个数逆邻接表 有向图中对每个结点建立以Vi终点的单链表 边集数组 edgesetarray 是图的一种顺序存储方式 利用一维数组来存储图中所有的边 数组中的每个元素用来存储图中的一条边 包括 始点 终点的序号及权值 该数组中所含元素的个数要大于等于图中边的条数 边集数组邻接表法 AdjacencyList 是图的一种链式存储结构 typedefstructedge intfromvex 边的始点域 intendvex 边的终点域 intweight 边的权值域 edgeset 定义边集数组类型 edgesetge e 1 边集数组全局量 6 3图的遍历深度优先遍历 DFS 方法 对于给定的图G 假设初始时所有顶点均未被访问过 则可从G中任选一顶点vi做为初始出发点 深度优先搜索可定义为 访问出发点vi 置访问标记为1 然后依次从vi的未被访问过的邻接点vj出发 继续进行深度优先搜索 直至图中所有和vi有路径相通的顶点均被访问过 很显然图的深度优先搜索过程是递归的 它的特点是尽可能先对图从纵深方向进行搜索 故称为深度优先搜索 DFS序列为 v1 v2 v4 v8 v5 v3 v6 v7 深度优先遍历算法递归算法 voidDFS inti intj printf 输出序号为 d的顶点 c n i adj vertex i visited i 1 标记vi已经访问过 for j 1 jedge i j voidDFSL inti edgenode p printf 输出序号为 d的顶点 c n i adjlist i vertex visited i 1 标记vi已经访问过 p adjlist i link p为vi的边表头指针 while p 依次搜索vi的邻接点 if visited p adjvex DFSL p adjvex p p next 在邻接矩阵上实现遍历的过程 生成树 连通图G的一个子图如果是一棵包含G的所有顶点的树 则该子图称为G的生成树 SpanningTree 广度优先遍历 BFS 方法 对于给定图G 假设初始时的所有顶点均未被访问过 从图G中任选一顶点vi为初始出发点 广度优先搜索遍历可定义为 首先访问出发点vi 接着依次访问vi的所有的邻接的未被访问过的点w1 w2 wt 然后 再依次访问与w1 w2 wt相邻接的未被访问过的顶点 依此类推 直至图中所有和初始出发点vi有路径相通的顶点都已访问到为止 显然 此方法的特点是尽可能先对横向进行搜索 故称之为广度优先搜索 BFS序列为 v1 v2 v3 v4 v5 v6 v7 v8 广度优先遍历算法 在广度优先遍历中 先被访问的顶点 其邻接点亦先被访问 所以在算法的实现中需要使用一个队列 用来依次记住被访问过的顶点 算法开始时 将初始点Vi访问后插入队列中 以后每从队列中删除一个元素 就依次访问它的每一个未被访问过的邻接点 并令其进队 这样当队列为空时 表明所有与初始点有路径相通的顶点都已访问完毕 算法到此结束 邻接表法广度优先 voidBFSL intk 用adjlist存储 inti edgenode p SETNULL Q printf 输出序号为 d的顶点 c n k adjlist k vertex 访问出发点vk visited k 1 标记vk已经访问过 ENQUEUE Q k 顶点vk的序号k入队 while EMPTY Q 队列非空执行 i DEQUEUE Q 队头元素顶点序号出队 p adjlist i link while p NULL if visited p adjvex printf 输出序号为 d的顶点 c n p adjvex adjlist p adjvex vertex visited p adjvex 1 ENQUEUE Q p adjvex p p next 深度优先生成树与广度优先生成树说明一个图可以有许多棵不同的生成树所有生成树具有以下共同特点 生成树的顶点个数与图的顶点个数相同生成树是图的极小连通子图一个有n个顶点的连通图的生成树有n 1条边生成树中任意两个顶点间的路径是唯一的在生成树中再加一条边必然形成回路含n个顶点n 1条边的图不一定是生成树 生成树 连通图G的一个子图如果是一棵包含G的所有顶点的树 则该子图称为G的生成树 SpanningTree 6 4最小生成树问题提出 要在n个城市间建立通信联络网 顶点 表示城市权 城市间建立通信线路所需花费代价希望找到一棵生成树 它的每条边上的权值之和 即建立该通信网所需花费的总代价 最小 最小代价生成树 问题分析 n个城市间 最多可设置n n 1 2条线路n个城市间建立通信网 只需n 1条线路问题转化为 如何在可能的线路中选择n 1条 能把所有城市 顶点 均连起来 且总耗费 各边权值之和 最小 定义 连通网络的所有生成树中边上权值之和最小的生成树称为最小生成树 MinimunSpanningTree MST性质 假设G V E 是一个连通网络 U为顶点集V的一个非空子集 若边 u v 是所有的一个端点在U中 即u U 另一个端点不在U中 即v V U 的这些边里面 权值最小的一条 则一定存在一棵G的最小生成树包括此边 u v 构造最小生成树方法方法一 普里姆 Prim 算法算法思想 设G V E 是连通网 T U TE 是G的最小生成树 其中U是T的顶点集 TE是T的边集 U和TE的初值均为空集 初始令U u0 u0 V TE 在所有u U v V U的边 u v E中 找一条代价最小的边 u0 v0 将 u0 v0 并入集合TE 同时v0并入U重复上述操作直至U V为止 则T V TE 为G的最小生成树 用Prim算法构造最小生成树的过程 生成树T的边集数组数组变化过程 方法二 克鲁斯卡尔 Kruskal 算法算法思想 设连通网G V E 令最小生成树T U TE 初始状态U V TE 将图G中的边按权值从小到大的顺序依次选取 若选取的边使生成树T不形成回路 则把它并入TE中 保留作为T的一条边 若选取的边使生成树T形成回路 则将其舍弃 依此类推 直至TE中包含n 1条边为止 此时的T即为最小生成树 用Kruskal算法构造最小生成树的过程 7 5拓扑排序问题提出 学生选修课程问题顶点 表示课程有向边 表示先决条件 若课程i是课程j的先决条件 则图中有边学生应按怎样的顺序学习这些课程 才能无矛盾 顺利地完成学业 拓扑排序定义AOV网 用顶点表示活动 用有向边表示活动的先后关系的有向图称为顶点活动网 ActivityOnVertexnetwork 简称AOV网若是图中有向边 则vi是vj的直接前驱 vj是vi的直接后继AOV网中不允许有回路 6 5最短路经最短路径问题通常是指如何从图中某一顶点 称为源点 到达另一顶点 称为终点 的多条路径中 找到一条路径 使得此路径上经过的各边上的权值总和达到最小 最短路径问题通常可以分成四种不同情况 单源点 单目标点最短路径问题 单源点 多目标点最短路径问题 多源点 单目标点最短路径问题 多源点 多目标点最短路径问题 我们讨论最常见的两种情况 单源点最短路径和任意两点间的最短路径 单源最短路经 从源点1到其余各顶点的最短路径 迪杰斯特拉 Dijkstra 算法 初始化 集合S中只有一个源点 其余顶点都在集合V S中 此时S中源点的距离值 最短路径 为0 V S中各个顶点的距离值为 只经过源点到达该顶点的当时最短路径 即从源点到达该顶点的边长 无边时 距离值为 当某点的距离值不等于 时 可以得到该点的路径 一条边 首先 从V S中选择一个距离值最小的顶点v 将其加入到S中 扩充集合S 此时该点的距离值就是最短路径长度 然后 对集合V S中剩余顶点的距离值进行修正 方法是 假设u是V S中的一个顶点 u点当前的距离值为len u 而新加入S的点m的最短路径len m加上