基于哈夫曼树的哈夫曼编译码器设计与实现

1、长春建筑学院数据结构课程设计（论文）基于哈夫曼树的哈夫曼编基于哈夫曼树的哈夫曼编/ /译码器设计与实现译码器设计与实现With the implementation of decoder design based on Huffman tree Huffman encoding 年 级: 学 号: 姓 名: 专 业: 指导老师: 二零一三年十二月长春建筑学院数据结构课程设计（论文）I摘 要随着计算机应用技术的快速发展和日益普及，网络也遍及到我们生活的每个角 落，为我们的学习和工作带来极大的方便。很多人都使用过传统的文字输入聊天方式，与之不同的另外一种聊天方式就是语音聊天。主要对那些不会使用键盘

2、的老年用户和追求时尚的年轻人，语音聊天是一种非常好的聊天方式，它能增加聊天双方的亲切感和真实感，语音聊天就涉及到语音的传输。 本系统主要讨论了 Windows系统下网络语音的传输，主要利用 Windows 系统下的 API 函数和 SOCKET 函数以及VC 开发平台的强大功能来实现。本系统可以实现网络间文字、语音信息的传输。信息社会的高科技，商品经济化的高效益，使计算机的应用已普及到经济和社会生活的各个领域。计算机虽然与人类的关系愈来愈密切，还有人由于计算机操作不方便继续用手工劳动。为了适应现代社会人们高度强烈的时间观念，学生成绩管理系统软件为教学办公室带来了极大的方便。该软件是以 C 语言

3、为实现语言，其功能在系统内部有源代码直接完成。通过操作目录，管理者和老师可以了解本软件的基本工作原理。管理者和老师只需输入一些简单的汉字、数字，即可达到自己管理学生成绩的目标。 关键字关键字: : 哈夫曼树 编码 解码 数据压缩技术长春建筑学院数据结构课程设计（论文）IIAbstractWith the rapid development of computer technology and popularization, network throughout each corner of ourlife, brings great convenience for our study and

4、work.Many people use the traditional text input chat mode,unlike another chat mode is the voice chat. Mainly to the young people who do not use the keyboard to elderly users and the pursuit of fashion, voice chat is a very goodchat mode, it can increase the intimacy and realistic chatbetween the two

5、 sides, voice chat is involved in the transmission of voice. This system is mainly discussed under the Windows system transmission of voice, the main use of Windows system under the API function and SOCKET function as well as the powerful features of the VC platform to achieve. This system can reali

6、ze thenetwork transmission of text, voice information.Information society technology, high benefit of commodity economy, causes the computer the application to the economical and social life each domain.Although the computer and human relations more closely, it was inconvenient for computer operator

7、s continue to use manual labor. In order to adapt to modern society was highly strong concept of time, has brought great convenience to student achievement management system software for teachingoffice. The software is based on C language for the realization of language, its function within the syst

8、em active code directly completed. Through the operation of the directory, administrators and teachers can understand the basic working principle of the software. Managers and teachers only need to input some simple Chinese characters, numbers, and can achieve their goal ofthe management of student

9、achievement.Keywords: Huffman tree coding and decoding data compression长春建筑学院数据结构课程设计（论文）目 录摘 要 .IABSTRACT.II第 1 章 绪 论.- 1 -1.1 需求分析.- 1 -1.2 实验目的 .- 1 -1.3 实验内容.- 2 -第 2 章 系统总体设计.- 3 -2.1 基本要求.- 3 -2.2 算法设计思想.- 3 -2.3 设计要求.- 3 -第三章 系统详细设计.- 4 -哈夫曼编码/译码器源代码 .- 4 -第四章 总体设计.- 12 -4.1 设计概述.- 12 -4.2 系统

10、结构图.- 13 -第五章 系统测试.- 13 -5.1 实验结果.- 14 -实验总结.- 17 -收获与心得.- 18 -参考文献.- 19 -长春建筑学院数据结构课程设计（论文）- 1 -第 1 章 绪 论引言：引言： 在当今信息爆炸时代，如何采用有效的数据压缩技术来节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视。电报通信是传递文字的二进制码形式的字符串。但在信息传递时，总希望总长度尽可能最短，即采用最短码。1.1 需求分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常

11、有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈弗曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。1

12、.2 实验目的1.掌握建立哈夫曼树和哈夫曼编码的方法2.掌握哈夫曼编码的实际应用方法长春建筑学院数据结构课程设计（论文） - 2 -1.3 实验内容 利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每端都需要一个完成的编译码系统。试为这样的信息收发站写一个哈夫曼的编译码系统长春建筑学院数据结构课程设计（论文） - 3 -第 2 章 系统总体设计2.1 基本要求1.硬件：微机和打印机一台各2.软件：Visual C+ windows72.2

13、 算法设计思想1) 分析程序的功能要求，划分程序功能模块2) 画出系统流程3) 代码的编写，定义数据结构和各个功能子函数4) 程序的功能调试2.3 设计要求1. 写出系统需求分析,并建模。 2. 编程实现,界面友好。 3. 输出操作前后的结果。4. 提供测试报告长春建筑学院数据结构课程设计（论文） - 4 -第三章 系统详细设计哈夫曼编码哈夫曼编码/译码器源代码译码器源代码void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n) int m,i,s1,s2,start; int c,f; HuffmanTr

14、ee p; char *cd; if(n=1) return; m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;iweight=*w; p-parent=0; p-lchild=0; p-rchild=0; 长春建筑学院数据结构课程设计（论文） - 5 - for(;iparent=0; for(i=n+1;i=m;+i) select(HT,i-1,s1,s2); HTs1.parent=HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs

15、1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); cd=(char*)malloc(n*sizeof(char); cdn-1=0; for(i=1;i=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent) if(HTf.lchild=c) cd-start=0; else长春建筑学院数据结构课程设计（论文） - 6 - cd-start=1; HCi=(char*)malloc(n-start)*sizeof(char); strcpy(HCi,

16、&cdstart); free(cd); void Initialization() flag=1; int num2; cout下面初始化哈夫曼链表endl; w=(int*)malloc(n*sizeof(int); z=(char*)malloc(n*sizeof(char); coutn 依次显示n个字符与其权值和编码nendl; char base2;/?ifstream fin(abc.txt); for(i=0;ibase;长春建筑学院数据结构课程设计（论文） - 7 - *(z+i)=*base;/? finnum2; *(w+i)=num2; HuffmanCodin

17、g(HT,HC,w,n); cout字符setw(6)权值setw(11)编码endl; for(i=1;i=n;i+) coutsetw(3)*(z+i-1); coutsetw(6)*(w+i-1)setw(12)HCiendl; cout下面将哈夫曼编码写入文件endl.endl; FILE *htmTree; char r= ,0; if(htmTree=fopen(htmTree.txt,w)=NULL) cout不能打开文件 endl; return; 长春建筑学院数据结构课程设计（论文） - 8 - for(i=0;in;i+) fputc(*(z+i),htmTree); fp

18、uts(r,htmTree); for(i=0;in;i+) fprintf(htmTree,%6d,*(w+i); fputs(r,htmTree); for(i=1;i=n;i+) fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree); cout已将字符与对应编码写入根目录下文件 htmTree.txt 中endlendl;void Tree_printing(HuffmanTree HT,int w) HuffmanTree p;长春建筑学院数据结构课程设计（论文） - 9 - p=HT+w; cout下面打印哈夫曼树endl; co

19、print(p,HT); cout打印工作结束endl;void main() coutendl; cout 此程序实现哈夫曼编码解码功能 endl; char choice; while(choice!=q) coutn*endl; cout 哈夫曼编码解码 endl; cout* endl; cout(i)初始化哈夫曼表 endl; cout(w)输入待编码的字符 endl; cout(e)进行编码、译码、打印编码 endl; cout(t)打印哈夫曼树 endl;长春建筑学院数据结构课程设计（论文） - 10 - cout(q)离开 endl; if(flag=0)coutn 请先初始化

20、哈夫曼链表,输入iendl;cout(程序将从根目录下的 abc.txt 文件中读出 26 个字母及其权值并对字母进行编码)choice; switch(choice) case i: Initialization(); break; case w: InputCode(); break; case e: Encoding(); Decoding();长春建筑学院数据结构课程设计（论文） - 11 - Code_printing(); break; case t: Tree_printing(HT,2*n-1); break; case q: break; default: cout输入命令错

21、误 endl; free(z); free(w); free(HT);长春建筑学院数据结构课程设计（论文） - 12 -第四章 总体设计4.1 设计概述 1)问题分析哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如 JPEG 中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到

22、的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。分析此次设计，是关于实现利用哈夫曼算法编码和译码功能的问题，要求能重复地显示并处理以下项目，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个哈夫曼的编/译码器。长春建筑学院数据结构课程设计（论文） - 13 -4.2 系统结构图 main()Initialization（）初始化函数Input()输入待编码字符函数Encoding（）编码函数Decoding（）译码函数Code_printing()

23、打印编码函数Tree_printing()打印哈夫曼树第 5 章 系统测试 此次测试举例为对输入的英文 HAPPYNEWYEAR 应用创建的哈夫曼编译码器进行编码再译码。声明：程序预先将 Huffman 编码解码所需的 26 个字母和权值保存在根目录下的abc.txt 文件下。a.按照程序提示输入 i 对 Huffman 进行初始化。b.初始化后程序对 abc.txt 文件中的数据进行读取并运行编码函数进行哈夫曼编码。然后将字母、权值和哈夫曼编码存在根目录下的 htmTree.txt 文件中。在屏幕显示出字符、权值、编码。c.输入 w 进入待编码字符输入窗口，并键入字符串（注意单词间无空格）“

24、happynewyear” 。 d.可以看出所获得的字符串已经存入根目录下的 tobetran.txt 文件中。 e.输入 e 进行编码、译码和打印编码功能。f.输入 t 打印哈夫曼树。长春建筑学院数据结构课程设计（论文） - 14 -g.输入 q 退出程序。5.1 实验结果长春建筑学院数据结构课程设计（论文） - 15 -长春建筑学院数据结构课程设计（论文） - 16 -长春建筑学院数据结构课程设计（论文） - 17 -实验总结通过这次课程设计使我充分的理解了哈夫曼编译码问题的基本原理，知道了树的不同存储结构的定义和算法描述，同时也学会了编写简单的哈夫曼编译码程序。虽然这个程序不是最好的，但是总体还是一个比较能体现数据结构知识点能力的程序，当然只是相对于我这个初学者来说。在刚开始