2022年2022年哈夫曼树编码译码 .pdf

《2022年2022年哈夫曼树编码译码 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年哈夫曼树编码译码 .pdf（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、实 验三哈夫 曼编码 / 译码 器1 问题利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道）每端都需要一个完整的编/译码系统。试为这样的信息收发站写一哈夫曼编/译码系统。基本要求：（1）初始化 ;从终端输入字符集的大小n，以及 n 个字符和 n 个权值建立哈夫曼树。（2）输出哈夫曼树，及各字符对应的编码。（3）编码： 利用建好的哈夫曼树，对输入的待发送电文进行编码。同时输入原文及编码串。（4）译码： 利用建好的哈夫曼树，对输入的已接收

2、电文进行译码。同时输入编码串及原文。2 解题思路 : （ 1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值w1,w2, ， wN 构成 n棵二叉树的集合F=T1,T2, ， Tn 把它们保存到结构体数组HTn中,其中 Ti 是按它们的ASC码值先后排序。其中每棵二叉树Ti 中只有一个带权为Wi 的根结点的权值为其左、右子树上根结点的权值之和。（2）在 HT1.i 中选取两棵根结点的权值最小且没有被选过的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。（3）哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。3.结构

3、体定义typedef struct float weight; unsigned int parent, lchild, rchild; HTNode, *HuffmanTree; typedef char *HuffmanCode ; 4.代码#include stdio.h #include stdlib.h #include string.h #include conio.h #define MAXSIZE 60 /*定义赫夫曼树结构体*/ typedef struct float weight; unsigned int parent, lchild, rchild; HTNode,

4、*HuffmanTree; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 17 页 - - - - - - - - - typedef char *HuffmanCode ; /*定义堆结构体*/ typedef struct float key; /关键字项int otherinfo; /其他数据项（此题目中用不到）RedType; typedef struct RedType rMAXSIZE+1; /r0 闲置用作哨兵int length; /顺序表长度SqLis

5、t; /*全局变量*/ HuffmanTree HT; /赫夫曼树HuffmanCode HC; /码值FILE *fp, *fp1, *fp2; int a30 = 0; float b30; float *w; /权/*测试解码（可以输入一个不正确的二进制码串） */ void testdecode() char str200; /存放自己输入的码子int p, p1, i; /解码的线索char ch; printf(n 请根据以上各个字符的编码输入一串二进制码字(200 个以内 ):n); gets(str); printf( 以上码子解码后为:n); p = 59; /最初令 p 为

6、树根整数，p 由根顺着树枝一直到树叶名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 17 页 - - - - - - - - - i = 0; ch = stri+; while (ch!=0) for ( ; ch!=0 & (HTp.lchild!=0|HTp.rchild!=0) ; ) if (ch = 0) p = HTp.lchild; else if(ch = 1) p = HTp.rchild; else printf(n 你输入了 0,1之外的字符，无法

7、正确译码，请检查!n); return ; /直接结束 ch = stri+; /下一个码字不断的取下一个 if(p 30) printf(n 以上正确译出了前面的字符，由于你输入的二进制码不完整，最后一位字符无法译出，请检查!n); /*下面是解码*/ void decode() int p; char ch; printf(nn对码子解码后的如下:n); fp1 = fopen(bianma.txt,r); if(!fp1) printf(can not open this file!n); exit(0); p = 59; /最初令 p 为任意一个非零整数，p 由根顺着树枝一直到树叶ch

8、 = fgetc(fp1); fp2 = fopen(jiema.txt,w); if (!fp2) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 17 页 - - - - - - - - - printf(can not open this file!n); exit(0); while (ch!=EOF) for ( ; HTp.lchild!=0|HTp.rchild!=0 ; ) if (ch = 0) p = HTp.lchild; else p = HTp.

9、rchild; ch = fgetc(fp1); /下一个码字不断的取下一个 switch (p) case 27 : printf(,); fprintf(fp2,); break; case 28 : printf(.); fprintf(fp2, .); break; case 29 : printf( ); fprintf(fp2, ); break; case 30 : printf(n); fprintf(fp2, n); break; default : printf(%c, p+96); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

10、- - - - - - 名师精心整理 - - - - - - - 第 5 页，共 17 页 - - - - - - - - - fprintf(fp2, %c, p+96); p = 59; /这里 p 要重置为59，因为经过上面的程序 p已经变化了， 不重置为 1则 HTp.lchild!=0|HTp.rchild!=0所以 for 语句无法进行 ! /while 循环printf(n); fprintf(fp2, n); fclose(fp1); fclose(fp2); /*求最小权值*/ void minweight() float Weight = 0; int i; for (i

11、= 0 ; i 96 & ch 64 & ch 91) /大小字母 printf(%s, HCch-64); fputs(HCch-64, fp1); /输出到文件里面ch = fgetc(fp); continue; if (ch = ,) printf(%s, HC27); fputs(HC27, fp1); ch = fgetc(fp); continue; if (ch = .) printf(%s, HC28); fputs(HC28, fp1); ch = fgetc(fp); continue; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

12、 - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 17 页 - - - - - - - - - if (ch = ) printf(%s, HC29); fputs(HC29, fp1); ch = fgetc(fp); continue; if (ch = n) printf(%s, HC30); fputs(HC30, fp1); ch = fgetc(fp); continue; printf(nn); fclose(fp); fclose(fp1); /*堆排序*/ void HeapAdjust(SqList &L, int s, int m)

13、RedType rc; int j; rc = L.rs; for (j = 2 * s ; j = m ; j*=2) if (j L.rj+1.key) /即使等于也不要动，不用加1 +j; if (rc.key = L.rj.key) /即使等于也不要动，直接跳出来break; L.rs = L.rj; s = j; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 17 页 - - - - - - - - - L.rs = rc; void select(Huffm

14、anTree t, int i, int &s1, int &s2) /此函数被调用一次则就用堆排序选择两个最小的赋给s1 和 s2 SqList L; RedType rc; int j, k, n = 1; L.length = 0; for (j = 1 ; j 0 ; -k) HeapAdjust(L,k,L.length); s1 = L.r1.otherinfo; /最小的选出来了！/* 把最小的换到最下面*/ rc = L.r1; L.r1 = L.rL.length; /此次的 select 函数，进行堆排序的只有L.length 个（ parent！=0 的没有在里面） ，所

15、以这里是L.length 而不是 i L.rL.length = rc; HeapAdjust(L,1,L.length-1); s2 = L.r1.otherinfo; /次小的选出来了(这里当输入1 4 2 8 四个数时，第一次选出的s1=1,s2=3 是对的，但第二次选出的s1=5，但 s2 是随机数 ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 17 页 - - - - - - - - - /*赫夫曼编码*/ void HuffmanCoding(Huffm

16、anTree &HT, HuffmanCode &HC, float *w, int n) / 算法 6.12 / w 存放 n 个字符的权值(均0),构造赫夫曼树 HT,并求出 n 个字符的赫夫曼编码HC int m, i, s1, s2, start, k; unsigned c, f; HuffmanTree p; char *cd; if (n = 1) return; m = 2 * n - 1; w = (float *)malloc(30*sizeof(float); for (i = 0 ; i 30 ; i+) *(w+i) = bi; HT = (HuffmanTree)m

17、alloc(m+1)*sizeof(HTNode); / 0号单元未用for (p = HT + 1, i = 1 ; i = n ; +i, +p, +w) (*p).weight = *w; (*p).parent = 0; (*p).lchild = 0; (*p).rchild = 0; for (i = n + 1 ; i = m ; +i, +p) (*p).parent=0; for (i = n + 1 ; i = m ; +i) / 建赫夫曼树 / 在 HT1i-1 中选择 parent 为 0 且名师资料总结 - - -精品资料欢迎下载 - - - - - - - - -

18、- - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 17 页 - - - - - - - - - weight 最小的两个结点,其序号分别为s1 和 s2 select(HT, i-1, s1, s2); HTs1.parent = i; HTs2.parent = i; /最小的和次小的双亲已经不为0 了，下次就不在它两中间找最小的和次小的了。HTi.lchild = s1; HTi.rchild = s2; HTi.weight = HTs1.weight + HTs2.weight; /建立赫夫曼树也容易， 关键是 select这个子函数 !

19、printf( 赫夫曼树如下表:n) ; printf(_n) ; printf(|_number_|_name_|_weight_|_parent_|_lchild_|_rchild_|n); for(k = 1 ; k = m ; k+) if (k 30) printf(|_%2d_|_|_%f_|_%2d_|_%2d_|_%2d_|n,k,HTk.weight,HTk.parent,HTk.lchild,HTk.rchild); printf(n) ; HC = (HuffmanCode)malloc(n+1)*sizeof(char*); cd = (char*)malloc(n*s

20、izeof(char); cdn-1 = 0; for (i = 1 ; i = n ; i+) start = n-1; /这里 f=HTf.parent是很巧妙的 ! for (c = i, f = HTi.parent ; f!=0 ; c = f, f = HTf.parent)/f=HTi.parent f!=0 是结束条件，所有的编码最后都要回到HTm, 而只有 HTm 的 parent 是 0! / 从叶子到根逆向求编码if (HTf.lchild=c) /c 是左孩子则码值是0 cd-start = 0; /这样逆着输，当我们正序输出的时候就恰好是想要的编码了! else cd

21、-start = 1; HCi = (char*)malloc(n-start)*sizeof(char); / 为第 i 个字符编码分配空间strcpy(HCi,&cdstart); /从 cd 复制编码 (串)到 HC，这里的 &cdstart是一个地址 free(cd); / 释放工作空间printf( 经赫夫曼编码后码值如下:n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 17 页 - - - - - - - - - for (i = 1 ; i %f-

22、, i+64, i+96, HTi.weight); puts(HCi); printf( , -%f-%sn, HT27.weight, HC27); printf( . -%f-%sn, HT28.weight, HC28); printf( 空格 -%f-%sn, HT29.weight, HC29); printf( 换行 -%f-%sn, HT30.weight, HC30); /*输出各个字符的次数，比例*/ void showdetail() int i; printf( 此英文文章中各个字母,个数，比例如下表:n); printf(_n); printf(|_ 字母 _|_个数

23、 _|_比例 _|n); for (i = 0 ; i = a & ch = A & ch = Z) ach-A+; count+=1; if (ch = ,) a26+; /逗号放在27 号单元if (ch = .) a27+; /句号放在28 号单元if (ch = ) a28+; /空格符放在29 号单元if (ch = n) a29+; /换行符放在30 号单元ch = fgetc(fp); /a的零号单元放a 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 1

24、7 页 - - - - - - - - - printf(nn); for (i = 0 ; i 30 ; i+) bi = ai/count; fclose(fp); /文件用完就关闭 /*主函数*/ void main() char c; char s200= 1.查看原文 .n 2.字符统计 .n 3.赫夫曼编码并输出内容.n 4.输出整篇文章的码字.n 5.求最小权值 .n 6.对码子进行解码.n 7.测试解码.n 8.退出.n; printf(nn); printf( *n); printf( * *n); printf( * 说明 :本程序只对英文文章的52 个大小写字母，逗号，句

25、*n); printf( * 号，空格符，换行符进行赫夫曼编码，并且大小写字母不*n); printf( * 区分，其它字符因为出现的概率太低，故本程序没有考虑*n); printf( * ，各个字符出现的频率对应他们的权值，解码时可能与原*n); printf( * 文 有 少 量 的 失 真 ， 希 望 用 户 理 解 和 支 持 ， 谢 谢 ! *n); printf( * *n); printf( *n); printf(nn); printf( *n); printf( * 注意 :必须按顺序先进行1，2，3 项的操作 ,否则会有错误! *n); printf( * 当 1,2,3

26、项顺次进行完后可以任意选择这8 种操作 . *n); printf( *n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 17 页 - - - - - - - - - printf( 请认真阅读以上注意的内容，如果已经读完请按任意键开始操作:n); c=getch(); system(cls); do printf(n 请选择你要的操作:nn); puts(s); c=getch(); switch (c) case 1 : showpassage(); /这里必

27、须先按顺序进行1，2，3 的操作，否则有问题break; /1，2，3 先按顺序操作完后，则可以任意选择这8 项操作case 2 : showdetail(); break; case 3 : HuffmanCoding(HT, HC, w, 30); break; case 4 : printcode(); break; case 5 : minweight(); break; case 6 : decode(); break; case 7 : testdecode(); break; case 8 : break; default : putch(7); printf( 请输入正确的选项

28、!n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 17 页 - - - - - - - - - while(c!=8); printf(nnBye Bye _ .!nn); 5 测试数据：权值的个数是N=8 测试数据为7 19 2 6 32 3 21 10 结果是：哈夫曼树 : 5 (2, 3) 11 (5, 6) 17 (7, 10) 28 (11, 17) 40 (19, 21) 60 (28, 32) 100 (40, 60) 7 的哈夫曼编码是1010 19 的哈夫曼编码是00 2 的哈夫曼编码是10000 6 的哈夫曼编码是1001 32 的哈夫曼编码是11 3 的哈夫曼编码是10001 21 的哈夫曼编码是01 10 的哈夫曼编码是1011 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 17 页 - - - - - - - - -