文档详情

数据结构树和二叉树分析.ppt

发布:2016-11-26约2.25万字共118页下载文档
文本预览下载声明
6.6 赫夫曼树及其应用---赫夫曼树编码的存储表示 typedef struct { unsigned int weight; unsigned int parent, lchild, rchild; } HTNode, *HuffmanTree; //动态分配数组存储赫夫曼树 typedef char **HuffmanCode; //动态分配数组存储赫夫曼编码表 void Huffmacoding(HuffmanTree HT, Huffmancode HC, int *w, int n) 6.6 赫夫曼树及其应用 --- 赫夫曼树构造及编码算法 建立初始森林 m=2*n-1; //其中n是待编码的字符(权值)的数量,本例n=8 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); R L P W 8 7 6 5 4 3 2 R L P W 15 14 13 12 11 10 9 1 0 共有2*8-1=15个结点 6.6 赫夫曼树及其应用 --- 赫夫曼树构造及编码算法 建立初始森林 m=2*n-1; //其中n是待编码的字符(权值)的数量,本例n=8 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for (p=HT+1, i=1; i=n; ++i, ++p, ++w) *p = {*w, 0, 0, 0 }; 0 0 0 11 0 0 0 3 0 0 0 23 0 0 0 14 0 0 0 8 0 0 0 7 0 0 0 29 0 0 0 5 R L P W 8 7 6 5 4 3 2 R L P W 1 0 共有2*8-1=15个结点 R L P W 15 14 13 12 11 10 9 6.6 赫夫曼树及其应用 --- 赫夫曼树构造及编码算法 建立初始森林 m=2*n-1; //其中n是待编码的字符(权值)的数量,本例n=8 HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for (p=HT+1, i=1; i=n; ++i, ++p, ++w) *p = {*w, 0, 0, 0 }; for ( ; i=m; ++i, ++p) *p = { 0, 0, 0, 0 }; 0 0 0 11 0 0 0 3 0 0 0 23 0 0 0 14 0 0 0 8 0 0 0 7 0 0 0 29 0 0 0 5 R L P W 8 7 6 5 4 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 R L P W 15 14 13 12 11 10 9 1 0 共有2*8-1=15个结点 6.6 赫夫曼树及其应用 ---赫夫曼树构造及编码算法 构造赫夫曼树 树中共有m-n个分支结点(本例:15 - 8 = 7,存放在HT的第9~ 第15个分量中) 重复m-n次:“选择 – 造树 –加入–删除”操作,完成目标赫夫曼树的构造(本例: 根节点存放在HT的 第15个分量中) for ( i = n+1; i=m; ++i ) { Select( HT, i-1, s1, s2 ); HT[s1].parent = i; HT[s2].parent=i; HT[i].lchild = s1; HT[i].rchild=s2; HT[i].weight = HT[s1].weight + HT[s2].weight; } //for 6.6 赫夫曼树及其应用 ---赫夫曼树构造及编码算法 造树过程(HT中的内容变化) 当前森林 T 0 0 0 11 0 0 0 3 0 0 0 23 0 0 0 14 0 0 0 8 0 0 0 7 0 0 0 29 0 0 0 5 R L P W 8 7 6 5 4 3 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 R L P W 15 14 13 12 11 10 9 1 0 6.6 赫夫曼树及其应用 ---赫夫曼
显示全部
相似文档