软件开发技术基础第2版课件作者赵英良第2章节数据结构及其应用2_非线性结构.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * 2．广度优先有哪些信誉好的足球投注网站 */61 2.3.7 树和图的应用 举例 霍夫曼编码 最小生成树 */61 哈夫曼树和哈夫曼编码 设计二进制编码方案时要考虑不同字符的使用频率，使用频率高的字符编码应当尽量短一些。但是仅仅考虑使用频率也是不够的。 例如：某个文件由A、B、C、D四个字符组成，其中A用得最多，C次之。 方案1: A — 1 C — 0 B — 10 D — 11 那么象1100这样的二进制数据具有二义性，既代表AACC，又可代表ABC，还可代表DCC。 为了不使二进制编码具有二义性，每个字符编码都不能与其他字符编码的前面若干位重合。 */61 假设二叉树中的左分支代表0，右分支代表1，则不论字符是采用何种0、1组合形式构成的编码，它必然对应二叉树中的某一个结点。 */61 B D C A 0 0 1 1 A B 0 1 D C 0 0 1 1 (a)有二义性的编码系统对应的二叉树 (b)无二义性的编码系统对应的二叉树 任何一个无二义性的二进制字符编码系统必然与这样一颗二叉树对应，该二叉树的叶子结点对应着所有需要转换的字符，并且按照左分支代表0、右分支代表1的规则，从根到该叶子的分支对应的0、1序列就构成叶子对应字符的二进制编码。 二叉树带权路径长度：设二叉树有n个带有权值的叶子结点，每个叶子到根的路径长度乘以其权值之和称为二叉树带权路径长度。一般记作： 其中，wi为第i个叶子的权重，li为第i个叶子到根的路径长度。 哈夫曼树：以一些带有固定权值的结点作为叶子所构造的，具有最小带权路径长度的二叉树称为哈夫曼树。 */61 */61 假定有一段报文由a、b、c、d四个字符构成，它们的使用频率比为6﹕4﹕2﹕1，则用a、b、c、d作为叶子结点构造哈夫曼树的过程如图所示。 若二叉树中的左分支代表0，右分支代表1,则a、b、c、d的哈夫曼编码分别为0、10、110、111。 【例26】假定编码系统中有五个字符X、S、D、E、A，它们的使用频率比为2﹕9﹕5﹕7﹕8，以这些频率值作叶子的权构造哈夫曼树，并输出哈夫曼编码。 */61 最小生成树 假定在多个城市间建立通信网络，将城市作为顶点，将所有可能的通信线路作为边，就构成一个图结构。 再以通信线路的造价作为边的权重就构成一个无向网络。 在保证通信功能的前提下，为了使总造价最小，需要寻找网络中权重之和最小的连通子图。 */61 （1）普里姆算法 假定G={ V, E }为连通网络，其中V为顶点集合，E为带权边集合。 设置生成树顶点集合U，最初它只包含某一个顶点。设置生成树边集合T，最初为空集。 而后考察这样的边，它的一个顶点u∈U，另一个顶点v∈V-U，每次从所有这样的边中选择权值最小的边(u, v)加入集合T，并把顶点v加入到集合U中。 如此不断重复，直到所有顶点都加入到集合U中为止。 */61 */61 */61 （2）克鲁斯卡尔算法 假定G={ V, E }为连通网络，其中V为顶点集合，E为带权边集合。 先构造一个包含所有顶点，没有边的非连通图T={ V, {} }，图中每个顶点自成一个连通分量。 当在E中选到一条具有最小权值的边时,若该边的两个顶点落在T的不同的连通分量上，则将此边加入到T中；否则将此边舍去，重新选择一条权值最小的边。 如此重复下去，直到所有顶点在同一个连通分量上为止。 */61 */61 谢谢 * * * * * * * * * * * * * * * * * * * 尚辅网 / 第2章 数据结构及其应用非线性数据结构 西安交通大学 计算机教学实验中心 软件开发技术基础 2.3 非线性数据结构 多维数组 树、二叉树 图 */61 2.3.1 多维数组 二维数组 行优先顺序存储 ? 列优先顺序存储 */61 二维数组 ? 压缩存储 对称矩阵 三角矩阵 稀疏矩阵 三元组（i,j,aij） */61 2.3.2 二叉树的基本概念 树？ 树是由n个具有相同特性的数据元素组成的集合。若n=0，则称其为空树。一棵非空树T必须满足： */61 G A C F D E B 树的一般形式 1）其中有一个特定的元素称为T的根root。 2）除根以外的集合可被划分为m个不相交的子集T1，T2，…，Tm，其中每个子集都是树。它们称为根root的子树。 与树相关的术语 结点 结点的度 树的度 叶子结点 分支结点 孩子结点和父结点 */61 G A C F D E B 树的一般形式 兄弟结点： 结点的层次： 树的深度： 有序树和无序树： 森林： 二叉树 二叉树或者是为空，