中文版教材主要数据结构.ppt

哈夫曼树与

哈夫曼编码如何构造最优树最优树的定义前缀编码树的路径长度定义为：树中每个结点的路径长度之和。从根结点到该结点的路径上结点的路径长度定义为：分支的数目。最优树的定义树的带权路径长度定义为：01树中所有叶子结点的带权路径长度之和02WPL(T)=?wklk(对所有叶子结点)。03在所有含n个叶子结点、并带相同权04值的m叉树中，必存在一棵其带权路径05长度取最小值的树，称为“最优树”。06例如：0727975492WPL(T)=7?2+5?2+2?3+4?3+9?2=60WPL(T)=7?4+9?4+5?3+4?2+2?1=8954根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点，其左、右子树为空树；0102(赫夫曼算法)以二叉树为例：03如何构造最优树在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和；040301从F中删去这两棵树，同时加入刚生成的新树；重复(2)和(3)两步，直至F中只含一棵树为止。029例如:已知权值W={5,6,2,9,7}5627527697671395276713952795271667132900001111000110110111指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。前缀编码图的数组(邻接矩阵)存储表示Aij={0(i,j)?VR1(i,j)?VRBACDFE定义:矩阵的元素为01有向图的邻接矩阵为非对称矩阵02A03B04E05C06FtypedefstructArcCell{//弧的定义1VRTypeadj;//VRType是顶点关系类型。2//对无权图，用1或0表示相邻否；3//对带权图，则为权值类型。InfoType*info;//该弧相关信息的指针4}ArcCell,AdjMatrix[MAX_VERTEX_NUM]5[MAX_VERTEX_NUM];6typedefstruct{1}SqList;//俗称顺序表2#defineLIST_INIT_SIZE1003//线性表存储空间的初始分配量4#defineLISTINCREMENT105//线性表存储空间的分配增量6ElemType*elem;//存储空间基址7intlength;//当前长度8intlistsize;//当前分配的存储容量9//(以sizeof(ElemType)为单位)10线性表的顺序存储结构TypedefstructLNode{ElemTypedata;//数据域structLnode*next;//指针域}LNode,*LinkList;线性表的链式存储结构LinkListL；//L为单链表的头指针010203040506#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号单元存储根结点SqBiTreebt;二叉树的顺序存储表示例如:ABCDEFABDCEF0123456789101112131401326ABCDEFGABCED