哈夫曼编码与译码的实现

1、 数据结构 课程设计评阅书题目哈夫曼编码与译码的实现学生姓名万永馨学号指导教师评语及成绩指导教师签名： 年 月 日答辩评语及成绩答辩教师签名： 年 月 日教研室意见总成绩： 室主任签名： 年 月 日20112012学年第一学期专业： 信息管理与信息系统 学号： 姓名： 万永馨 课程设计名称： 数据结构课程设计 设计题目： 哈夫曼编码与译码的实现 完成期限：自 2012 年 2 月 20 日至 2012 年 3 月 2 日共 2 周设计依据、要求及主要内容（可另加附页）：该设计题目将按以下要求完成：哈夫曼编码与译码是信息传输中应用的经典算法， 运用C或VC+结合数据结构等基础知识，按以下要求编程

2、实现各种进制的转换。任务要求：1）阐述设计思想,画出流程图;2）需要对哈夫曼编码/译码的相关原理有所了解，设计数据结构，建立必要的信息数据文件（最好存储成外部文件），并分析完成用户所需的基本操作功能； 3）实现给定信息的编码和译码功能；4）应有较好的界面设计，说明程序测试方法；5）按照格式要求完成课程设计说明书。设计要求:1）问题分析和任务定义：根据设计题目的要求，充分地分析和理解问题，明确问题要求做什么？（而不是怎么做？）限制条件是什么？确定问题的输入数据集合。2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的原则划分模块，定义主程序模块和各抽象数据类型。逻

3、辑设计的结果应写出每个抽象数据类型的定义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，写出数据存储结构的类型定义，写出函数形式的算法框架；4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5）程序调试与测试：能够熟练掌握调试工具的各种功能

4、，设计测试数据确保程序正确。调试正确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；以上要求前三个阶段的任务完成后，将设计说明书的草稿交指导老师面审，审查合格方可进入后续阶段的工作。设计工作结束，经指导老师验收合格后将设计说明书装订，并答辩。指导教师（签字）： 教研室主任（签字）： 批准日期： 年 月 日摘 要在当今信息爆炸时代，如何采取有效的数据压缩技术来节省数据文件的储存空间越来越引起人们的重视。本次课程设计的实验题目为哈夫曼编码与译码的实现

5、。利用哈夫曼树求得的用于通讯的二进制编码称为哈弗曼编码。通常我们将文字转化为二进制称为编码，而将二进制转化为文字称为译码。此次程序就是将一个简单的文件进行编码转化为二进制数存入文件并进行译码进而输出。而将文件转化为二进制编码运用哈夫曼树的相关知识可以有效的节省存储空间与时间。关键词：哈夫曼树;哈夫曼树的编码;哈夫曼树的译码;哈夫曼树初始化;哈夫曼树的建立 开发工具：visual C+目 录 1.引 言62.课题描述73.程序设计83.1实验目的与基本要求83.2部分函数介绍83.3主要模块程序流程图94 系统实现134.1 主函数 （菜单函数）134.2 建立HuffmanTree134.3生

6、成Huffman编码并写入文件154.4对文件 哈夫曼译码.txt 进行译码译码165 系统调试17附录 源程序231.引 言在课程设计过程中，我们四个人一组选择一个课题，认真研究，根据课堂讲授内容，借助书本，自己动手实践。这样不但有助于我们消化课堂所讲解的内容，还可以增强我们的独立思考能力和动手能力；通过编写实验代码和调试运行，我们可以逐步积累调试C程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。在课程设计过程中，我们不但有自己的独立思考，还借助各种参考文献来帮助我们完成系统。更为重要的是，我们同学之间加强了交流，在对问题的认识方面可以交换不同的意见。同时，师生之间的互动也随

7、之改善，我们可以通过具体的实例来从老师那学到更多的实用的知识。数据结构课程具有比较强的理论性，同时也具有较强的可应用性和实践性。课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。通过这次实验让我们明白：作为一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。只有这样，我们的综合素质才会有好的提高。2.课题描述课 题：哈夫曼编码与译码的实现问题描述：对文件哈夫曼.txt中的字符串进行编译，统计其中的字符种类、个数作为权值。1. 从D盘的数据结构课程设计文件夹中建立哈夫曼.txt文件里读出文章

8、（必须大写）；2. 运用jsp函数统计这篇文章中的每个字符出现的次数；3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储结构的初态和终态进行输出；4. 对每个字符进行编码并将所编码写入程序，然后对另一文件中的编码编码进行破译。具体介绍：在本课题中，我们在硬盘D盘中预先建立一个 哈夫曼.txt 文档，在里面编辑一篇文章(大写)。然后运行程序，调用fileopen()函数读出该文章，显示在界面；再调用jsq()函数对该文章的字符种类进行统计，并对每个字符的出现次数进行统计，并且在界面上显示；然后以每个字符出现次数作为权值，调用ChuffmanTree()函数构建哈夫曼树；并调用prin

9、t1()和print2()函数将哈夫曼的存储结构的初态和终态进行输出。然后哈夫曼树进行编码，再对另一文件 哈夫曼译码.txt 编码进行译码，再输出至界面。至此，整个工作就完成了。3.程序设计3.1实验目的与基本要求利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。一个完整的系统应具有以下功能：(1) 初始化（Initialization）。从文件 哈夫

10、曼.txt 读入字符集,，统计字母个数作为权值，建立赫夫曼树。(2) 编码（Encoding）。利用已建好的赫夫曼树（如不在内存，则从文件中读入），对哈夫曼树进行编码，然后将结果存入文件 哈夫曼译码.txt中。(3) 译码（Decoding）。利用已建好的赫夫曼树将文件 哈夫曼译码.txt 中的代码进行译码3.2部分函数介绍从硬盘读取字符串fileopen(参数)建立HuffmanTree通过三个函数来实现：void select(参数)说明：在ht1.k中选择parent为0且权值最小的两个根结点的算法int jsq(参数)说明：统计字符串中各种字母的个数以及字符的种类void Chuffm

11、anTree()说明：构造哈夫曼树输出哈夫曼树的存储结构的初态和终态分别调用print1()和print2()来实现void print1(参数)说明：输出哈夫曼树的初态void print2(参数)说明：输出哈夫曼树的终态哈夫曼编码和译码void HuffmanEncoding(参数)说明：哈夫曼编码char*decode(参数)说明：哈夫曼译码3.3主要模块程序流程图主函数流程图： 图 3.1流程图注释：图3.1比较简单，由该图可知主要是调用各个函数模块，首先代开已经存在的文件，然后统计总的字符数以及出现的各个字符和频率。然后才开始建立哈夫曼树，接着在哈夫曼树的基础上对其进行编码，编码之后

12、才是译码。最后输出结束。构造哈夫曼树： 图 3.2流程图注释：图3.2是表示构造哈夫曼树的过程。首先输入num个叶结点的权值，当i=num是循环结束。然后进行哈夫曼树的构建，当i=2*num-1是循环结束。最后输出所得到的字符统计情况。哈夫曼编码： 图 3.3流程图解释： 流程图3.3表示哈夫曼编码情况。首先初始化，Cd-start=0,start=num。然后从首地址开始进行比较，找节点的父母地址然后看节点为父母地址的左孩子是的话为0,反之为1.依次开始上溯。将编码存入Hi.bits。哈夫曼译码： 图 3.4流程图解释： 流程图3.4表示哈夫曼译码情况。首先讲哈夫曼编码存入的文件打开，将哈夫

13、曼编码导出。然后将文件中读出的字符与哈夫曼编码cd进行比较strcmp(HCj.bits,cd=0，相等的话开始译出strk=HCj.ch。4 系统实现各模块关键代码及算法的解释：4.1 主函数 （菜单函数） 主函数相对简单，只需了解顺序，依次调用即可。这里不做解释4.2 建立HuffmanTree 代码解释：该函数为在ht1.k中选择parent为0且权值最小的两个根结点的算法，其序号为s1和s2。void select(HuffmanTree T,int k,int &s1,int &s2) int i,j;int min1=32767; for(i=1;i=k;i+)if(Ti.weig

14、htmin1 &Ti.parent=0) j=i;min1=Ti.weight;s1=j;min1=32767;for (i=1;i=k;i+)if(Ti.weightmin1 & Ti.parent=0 & i!=s1)j=i;min1=Ti.weight;s2=j;代码解释：下面函数用来统计字符串中各种字母的个数以及字符的种类。当字符在A和z之间时即被计数，并用strj保存字母到数组中，用cntj统计每种字符个数。j返回总共读取的字符数目。int jsq(char *s,int cnt,char str) int i,j,k; char *p;int temp53; for(i=1;i=A

15、&*p=z)k=*p-64;tempk+; /统计各种字符的个数for(i=1,j=0;i=52;+i)if(tempi!=0 ) j+;strj=i+64; /送对应的字母到数组中cntj=tempi; /存入对应字母的权值 return j; /j是输入字母总数代码解释：下面函数用来构造哈夫曼树HT。首先初始化哈夫曼树，然后输入前面统计的各结点的权值，用for循环来构造哈夫曼树。void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str)int i,s1,s2;for(i=1;i=2*num-1;i+)/初始化HT，2*

16、num-1是指哈夫曼/所有的结点数目HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.weight=0;for(i=1;i=num;i+) /输入num个叶结点的权值HTi.weight=cnti;for(i=num+1;i=2*num-1;i+)select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/在ht1.k中选择parent为0且权值最小/的两个根结点,其序号为s1和s2,i为双亲

17、for(i=0;i=num;i+) /输入字符集的中字符HCi.ch=stri; /字符的种类i=1;while(i=num)printf(字符%c次数:%dn,HCi.ch,cnti+); /输出统计的情况4.3生成Huffman编码并写入文件 代码解释：根据哈夫曼树T求哈夫曼编码H。 void HuffmanEncoding(HuffmanTree T,HuffmanCode H)int c,p,i; /c和p分别指示t中孩子和双亲char cdn; /临时存放编码串int start; /指示码在cd中的起始位置cdnum=0; /最后一位（第num个）放上串结束符for(i=1;i0)

18、 /直至上溯到tc是树根为止cd-start=(Tp.lchild=c) ? 0 : 1;c=p; /若tc是tp的左孩子/则生成0;否则生成底码strcpy(Hi.bits,&cdstart);Hi.len=num-start;void coding(HuffmanCode HC ,char *str) /对str所代表的字符串进行编码 并写入文件int i,j;FILE *fp;fp=fopen(D:数据结构课程设计哈夫曼译码.txt,w);while(*str)for(i=1;i=num;i+)for(j=0;jHCi.len;j+)if(HCi.ch=*str)fputc(HCi.bi

19、tsj,fp);/将编码写入文件str+;fclose(fp);4.4对文件 哈夫曼译码.txt 进行译码译码代码解释：代码文件哈夫曼译码.txt的译码，将翻译的二进制码译成原来的字符。char*decode(HuffmanCode HC)FILE *fp;char str254; /假设远文本文件不超过254个字符char *p;static char cdn+1;int i,j,k=0,cjs;fp=fopen(D:数据结构课程设计哈夫曼译码.txt,r);/打开文本文档txtwhile(!feof(fp) /feof(fp)判断文件是否真正结束， /feof(fp)=1时文件结束cjs=

20、0;for(i=0;inum & cjs=0 & !feof(fp);i+)cdi= ;cdi+1=0;cdi=fgetc(fp); /数组接受从fp指针所指向文件中读 /入的一个字符 for(j=1;j=num;j+)if(strcmp(HCj.bits,cd)=0)strk=HCj.ch;k+;cjs=1;break; /haffman编码和密码译码相比较 strk=0;p=str; return p;5 系统调试本次测试是在我的电脑的D盘中建立一个名为哈夫曼.txt的文本文档，其中有大写字母KONGYONGKAISB运行程序后，我们可以见到一下的运行界面。首先选择1打开文件 哈夫曼.tx

21、t然后选择2初始化并建立哈夫曼树接下来选择3开始对已经建立的哈夫曼树进行编码并写入文件 哈夫曼译码.txt 最后对文件 哈夫曼译码.txt进行编译选择4开始进行译码的运算由此可见此次程序圆满成功。本程序能够有效的多文件进行编码，并且在译码文件中至于要输入你想要的子母编码，在最后即可输出。总结通过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解，也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。首先我谈谈我在设计期间我遇到的难点。开始的时候，代码中有许多的错误，其中之一便是部分信息无法有效的传递，不过在后面的改正中我发现的我的错误。还有很多很多，例如，在树的初始化输出中，没有

22、权值的节点却出现乱码，这个问题我最终是换了一种方法输出才成功余兴了，还有就是循环中出现的错误。比如将哈夫曼编码写入文件，就因为多了一个等号以至于哈夫曼译码总是不能成功译出。许多的错误让我明白了一个道理-细心是非常重要的。同时，对于编程者而言，思路清晰是相当重要的。在适当的时候和同学一起交流探讨是一个十分好的学习机会。请教老师也很重要，因为毕竟我们是新手，对于某些问题很难弄清楚。而且，某些错误对于我们来说有时候想半天都弄不来，但老师几下下就搞好了，这样就更加有效地节约了时间。这次课程设计不但让我学得了一些编程知识，还学会了系统的做一份课程设计报告，明白了做事情只有认真，才能真正做得更好！参考文献

23、1 严蔚敏.吴伟民.数据结构(C语言版).清华大学出版社2 施伯乐.数据结构.复旦大学出版社3 谭浩强.C语言程序设计教程.高等教育出版社4 金远平.数据结构.清华大学出版社 5 王燕 . 面向对象的理论与 C+ 实践.清华大学出版社6 李春葆.C+ 语言习题与解析.清华大学出版社7 殷人昆，陶永雷，谢若阳等.数据结构.清华大学出版社8 朱战立，张选平 . 数据结构学习指导与典型题解.西安：西安交通大学出版社， 9 罗文劼，王苗，石强 . 数据结构习题解答与实验指 .中国铁道出版社附录 源程序#include #include #include #include#define n 100 /叶

24、子结点数#define m 2*n-1 int g; /哈夫曼树中的结点树typedef structchar ch;char bits9; /存放编码位串int len; CodeNode;typedef CodeNode HuffmanCoden+1;typedef struct int weight; /权值int lchild,rchild,parent; /左右孩子几双亲指针 HTNode;typedef HTNode HuffmanTreem+1; /0号单元不用int num;/*建立HuffmanTree*void select(HuffmanTree T,int k,int

25、&s1,int &s2) /选择parent为0且权值最小的两个根结点的算法/其为s1和s2int i,j;int min1=32767; for(i=1;i=k;i+)if(Ti.weightmin1 &Ti.parent=0) j=i;min1=Ti.weight;s1=j;min1=32767;for (i=1;i=k;i+)if(Ti.weightmin1 & Ti.parent=0 & i!=s1)j=i;min1=Ti.weight;s2=j;int jsq(char *s,int cnt,char str) /统计字符串中各种字母的个数以及字符的种类int i,j,k; char

26、 *p;int temp53; for(i=1;i=A&*p=z)k=*p-64;tempk+;for(i=1,j=0;i=52;+i)if(tempi!=0 ) j+;strj=i+64; cntj=tempi; return j; /j是输入字母总数void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt) /构造哈夫曼树HTint i,s1,s2;for(i=1;i=2*num-1;i+)HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.weight=0;for(i=1;i=num;i+) /输入n

27、um个叶结点的权值HTi.weight=cnti;for(i=num+1;i=2*num-1;i+) select(HT,i-1,s1,s2);HTs1.parent=i;HTs2.parent=i;HTi.lchild=s1; HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;void HuffmanEncoding(HuffmanTree T,HuffmanCode H) /生成哈夫曼编码 int c,p,i; /c和p分别指示t中孩子和双亲char cdn; int start; cdnum=0; for(i=1;i0) cd-start=

28、(Tp.lchild=c) ? 0 : 1;c=p;strcpy(Hi.bits,&cdstart);Hi.len=num-start;for(i=1;i=num;i+)printf(输出编码：%sn,Hi.bits);char*decode(HuffmanCode HC) /代码文件哈夫曼译码.txt的译码FILE *fp;char str254; /假设文本文件不超过254个字符char *p;static char cdn+1;int i,j,k=0,cjs; fp=fopen(D:数据结构课程设计哈夫曼译码.txt,r);/打开文本文档txtwhile(!feof(fp)/feof(f

29、p)判断文件是否真正结束，feof(fp)=1时文件结束cjs=0;for(i=0;inum & cjs=0 & !feof(fp);i+)cdi= ;cdi+1=0;cdi=fgetc(fp);/数组接受从fp指针所指向文件中读入的一个字符 for(j=1;j=num;j+)if(strcmp(HCj.bits,cd)=0)/haffman编码和密码译码相比较strk=HCj.ch;k+;cjs=1;break; strk=0;p=str;return p;/*输出HuffmanTree存储结构*void print1(HuffmanTree HT)/初建哈夫曼int x; for(x=1;

30、xnum)printf(t t%dt %dt %dn,HTx.parent,HTx.lchild,HTx.rchild);elseprintf(t%-6d %dt %dt %dn,HTx.weight,HTx.parent,HTx.lchild,HTx.rchild);printf(-n); void print2(HuffmanTree HT)int k;for(k=1;k=2*num-1;k+) printf( t%dt %dt %dt %dn,HTk.weight,HTk.parent,HTk.lchild,HTk.rchild);printf(-n); void DhuffmanTre

31、e(HuffmanTree HT,int cnt) /初始化哈夫曼树int i;for(i=1;i=num;i+) /输入num个叶结点的权值HTi.weight=cnti;/*打开文本*int open(char string)FILE *fp; if(fp=fopen(D:数据结构课程设计哈夫曼.txt,r)=NULL)printf(不能打开文件!n);exit(1);while(fgets(string,100,fp)!=NULL) printf(%sn,string);fclose(fp);return 0;void main() char string100;char *s,str53;int cnt53;int choice;int i; Huffman