数据结构哈夫曼编码

1、摘要 利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原），将所得结果存储到已开辟空间中。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。本程序可以对任何大小的字符型文件进行Huffman编码，生成一个编码文件。并可以在程序运行结束后的任意时间对它解码还原生成字符文件。即：先对一条电文进行输入，并实现Huffman编码，然后对Huffman编码生成的代码串进行译码，最后输出电文数字 Abstract Use hoffmann code was communication can

2、 improve the utilization rate of channel, shorten the information transmission time, reduce the transmission cost. This requirement in the sending end through a coding system in advance to transmit data coding, in the receiver will spread of the data decoding (restoration), will the results of open

3、space to store already. Try for such information sending and receiving station write a hoffmann yards of make up/decoding system. This program can on any of the size of the file type character Huffman coding, generates a code files. And can the running of the application at any time after the end of

4、 the reduction of decoding it generated character files. Namely: first to a message for input, and realize the Huffman coding, and then to Huffman coding generated code string decode, finally digital output message 关键字 哈夫曼编码； 哈夫曼译码 Keywords Hoffmann code; Hoffmann decode 1 设计要求 对输入的一串电文字符实现哈夫曼编码，输出电

5、文字符串。通常我们把数据压缩的过程称为编码。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi，编码长度为Li，电文中有n种字符，则电文编码总长度为WiLi。若将此对应到二叉树上，Wi为叶结点的权，Li为根结点到叶结点的路径长度。那么，WiLi恰好为二叉树上带权路径长度。因此 ，设计电文总长最短的二进制前缀编码，就是以n种字符出现的频率作权，构造一棵哈夫曼树，此构造过程称为哈夫曼编码。设计实现的功能： (1) 哈夫曼树的建立； (2) 哈夫曼编码的生成；(3) 对编码文件的译码。 2 系统结构图 （功能模块图）哈

6、夫曼编码/译码器建立哈夫曼树哈夫曼编码哈夫曼译码 图2-1 哈夫曼结构图 3 详细设计 3.1 哈夫曼树的建立 3.1.1哈夫曼树的存储结构描述为： #define N 50 / 叶子结点数 #define M 2*N-1 / 哈夫曼树中结点总数 typedef struct int weight; / 叶子结点的权值 int lchild, rchild, parent; / 左右孩子及双亲指针 HTNode; / 树中结点类型 typedef HTNode HuffmanTreeM+1; 3.1.2哈夫曼树的算法:void CreateHT(HTNode ht,int n) /调用输入的数

7、组ht和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weightmin1) /

8、若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点3.2哈夫曼编码void CreateHCode

9、(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-=0; else /处理右孩子结点 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode h

10、t,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf( 输出哈夫曼编码:n); for (i=0;in;i+) /输出data中的所有数据，即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /输出所有data中数据的编码 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要进行编码的字符串存

11、入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#为终止标志for (j=0;jn;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号，相同的就输出这个字符的编码for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /输出完成后跳出当前for循环3.3哈夫曼译码void deHCode(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要进行译

12、码的字符串存入code数组中while(code0!=#)for (i=0;in;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已经使用过的code数组里的字符串删除codex=codex+j;3.4主函数void main() int n=26,i; ch

13、ar orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立结构体 HCode hcdN; /建立结构体 for (i=0;in;i+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fnumi; while (flag) /菜单函数，

14、当flag为0时跳出循环 3.5显示部分源程序： printf(n); printf( *); printf(n * 1-显示编码 *); printf(n * 2-进行编码 *); printf(n * 3-进行译码 *); printf(n * 4-退出 *n); printf( * *); printf(n); printf( 请输入选择的编号:); scanf(%c,&orz); switch(orz) case a: case A: system(cls); /清屏函数 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n

15、); printf(n按任意键返回.); getch(); system(cls); break; case b: case B: system(cls); printf(请输入要进行编码的字符串(以#结束):n); editHCode(ht,hcd,n); printf(n按任意键返回.); getch(); system(cls); break; case c: case C: system(cls); DispHCode(ht,hcd,n); printf(请输入编码(以#结束):n); deHCode(ht,hcd,n); printf(n按任意键返回.); getch(); syst

16、em(cls); break; case d: case D: flag=0; break; default: system(cls); 4 程序运行结果进入主菜单图4-1选A时的显示结果图4-2选B时的显示结果图4-3选C时的显示结果图4-45 心得体会 通过这次课程设计，我们学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。我们认识到根据不同的需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数组，只要运用得当，也能达到相同的效果，甚至更佳，就如这次的课程设计，通过

17、用for的多重循环，舍弃多余的循环，提高了程序的运行效率。这次课程设计，我们在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存数据，对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏，我们的程序有了更高的质量。另外，互帮互助让我们的程序设计更加完善。参考文献1 徐孝凯编著，数据结构课程实验，清华大学出版 2002年第一版2 张乃笑编著，数据结构与算法，电子工业出版社 2004年10月3 严蔚敏 数据结构（C语言版） 清华大学出版社4 李春葆 数据结构（C语言篇）习题与解析（修订版）清华大学出版 2002年4月第一版附录源程序如下：#include #include /要用sy

18、stem函数要调用的头文件#include /用getch()要调用的头文件#include #define N 50 /义用N表示50叶节点数#define M 2*N-1 /用M表示节点总数 当叶节点数位n时总节点数为2n-1#define MAXSIZE 100typedef struct char data; /结点值 int weight; /权值 int parent; /双亲结点 int lchild; /左孩子结点 int rchild; /右孩子结点HTNode; typedef struct char cdN; /存放哈夫曼码 int start; /从start开始读cd

19、中的哈夫曼码HCode;void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k=i-1;k+) if (ht

20、k.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weightmin1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti

21、.rchild=rnode; /父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-=0; else /处理右孩子结点 hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码h

22、c.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf( 输出哈夫曼编码:n); for (i=0;in;i+) /输出data中的所有数据，即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /输出所有data中数据的编码 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZ

23、E; int i,j,k;scanf(%s,string); /把要进行编码的字符串存入string数组中printf(n输出编码结果:n);for (i=0;stringi!=#;i+) /#为终止标志for (j=0;jn;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号，相同的就输出这个字符的编码for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /输出完成后跳出当前for循环void deHCode(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int

24、 i,j,l,k,m,x;scanf(%s,code); /把要进行译码的字符串存入code数组中while(code0!=#)for (i=0;in;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;k=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已经使用过的code数组里的字符串删除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,5