哈夫曼编码与译码的实现

1、次砺理n孽傥数据结构课程设计设计说明书哈夫曼编码与译码的实现学生姓名 万永馨学号1021024016班级 信管101成绩指导教师 余冬梅数学与计算机科学与技术学院2012年3月2日数据结构课程设计评阅书题目哈夫曼编码与译码的实现学生姓名万永馨学号 1021024016指导教师评语及成绩指导教师签名：年 月 日答辩评语及成绩答辩教师签名：年 月 日教研室意见总成绩：室主任签名：年 月日20112012学年第一学期专业：信息管理与信息系统学号:1021024016 姓名： 万永馨课程设计名称：数据结构课程设计设计题目： 哈夫曼编码与译码的实现完成期限：自 2012 年 2 月 20 日至 2012

2、 年 3 月 2日共工 周设计依据、要求及主要内容（可另加附页）：该设计题目将按以下要求完成：哈夫曼编码与译码是信息传输中应用的经典算法，运用c或vc+吉合数据结构等基础知识，按以下要求编程实现各种进制的转换。任务要求：1）阐述设计思想，画出流程图；2）需要对哈夫曼编码/译码的相关原理有所了解，设计数 据结构，建立必要的信息数据文件（最好存储成外部文件），并分析完成用户所需的基本操作功能；3）实现给定信息的编码和译码功能；4）应有较好的界面设计，说明程序测试方法；5）按照格式要求完成课程设计说明书。设计要求：1）问题分析和任务定义： 根据设计题目的要求， 充分地分析和理解问题， 明确问题要求做

3、什么？ （而不是怎么做？）限制条件是什么？确定问题的输入数据集合。2）逻辑设计：对问题描述中涉及的操作对象定义相应的数据类型，并按照以数据结构为中心的 原则划分模块，定义主程序模块和各抽象数据类型。逻辑设计的结果应写出每个抽象数据类型的定 义（包括数据结构的描述和每个基本操作的功能说明），各个主要模块的算法，并画出模块之间的调用关系图；3）详细设计：定义相应的存储结构并写出各函数的伪码算法。在这个过程中，要综合考虑系统 功能，使得系统结构清晰、合理、简单和易于调试，抽象数据类型的实现尽可能做到数据封装，基 本操作的规格说明尽可能明确具体。详细设计的结果是对数据结构和基本操作做出进一步的求精，

4、写出数据存储结构的类型定义，写出函数形式的算法框架；4）程序编码：把详细设计的结果进一步求精为程序设计语言程序。同时加入一些注解和断言，使程序中逻辑概念清楚；5）程序调试与测试：能够熟练掌握调试工具的各种功能，设计测试数据确保程序正确。调试正 确后，认真整理源程序及其注释，形成格式和风格良好的源程序清单和结果；6）结果分析：程序运行结果包括正确的输入及其输出结果和含有错误的输入及其输出结果。算法的时间、空间复杂性分析；7）编写课程设计报告；以上要求前三个阶段的任务完成后，将设计说明书的草稿交指导老师面审，审查合格方可进入 后续阶段的工作。设计工作结束，经指导老师验收合格后将设计说明书装订，并答

5、辩。指导教师（签字）： 教研室主任（签字）： 批准日期：年 月 日摘要在当今信息爆炸时代，如何采取有效的数据压缩技术来节省数据文件的储存空间越来越引起人们的重视。本次课程设计的实验题目为哈夫曼编码与译码的实现。利用哈夫曼树求得的用于通讯的二进制编码称为哈弗曼编码。通常我们将文字转化为二进制称为编码，而将二进制转化为文字称为译码。此次程序就是将一个简单的文件进行编码转化为二进制数存入文件并进行译码进而输出。而将文件转化为二进制编码运用哈夫曼树的相关知识可以有效的节省存储空间与时间。关键词 ： 哈夫曼树 ; 哈夫曼树的编码; 哈夫曼树的译码 ; 哈夫曼树初始化 ; 哈夫曼树的建立开发工具： vis

6、ual c+1 .引 言62 . 课题描述 73 . 程序设计 83.1 实验目的与基本要求83.2 部分函数介绍 83.3 主要模块程序流程图 94 系统实现 134.1 主函数 （菜单函数） 134.2 建立 huffmantree 134.3 生成 huffman 编码并写入文件 154.4 对文件 哈夫曼译码 .txt 进行译码译码 165 系统调试 17附录 源程序 23121 .引 言在课程设计过程中，我们四个人一组选择一个课题，认真研究，根据课堂讲授内容，借助书本， 自己动手实践。 这样不但有助于我们消化课堂所讲解的内容， 还可以增强我们的独立思考能力和动手能力；通过编写实验代码

7、和调试运行，我们可以逐步积累调试c程序的经验并逐渐培养我们的编程能力、用计算机解决实际问题的能力。在课程设计过程中， 我们不但有自己的独立思考， 还借助各种参考文献来帮助我们完成系统。 更为重要的是， 我们同学之间加强了交流， 在对问题的认识方面可以交换不同的意见。同时， 师生之间的互动也随之改善， 我们可以通过具体的实例来从老师那学到更多的实用的知识。数据结构课程具有比较强的理论性， 同时也具有较强的可应用性和实践性。 课程设计是一个重要的教学环节。我们在一般情况下都能够重视实验环节，但是容易忽略实验的总结，忽略实验报告的撰写。 通过这次实验让我们明白： 作为一名大学生必须严格训练分析总结能

8、力、书面表达能力。 需要逐步培养书写科学实验报告以及科技论文的能力。 只有这样， 我们的综合素质才会有好的提高。2 .课题描述课 题：哈夫曼编码与译码的实现问题描述：对文件哈夫曼.txt 中的字符串进行编译，统计其中的字符种类、个数作为权值。1. 从d盘的数据结构课程设计文件夹中建立哈夫曼.txt文件里读出文章(必须大写)；2. 运用 jsp 函数统计这篇文章中的每个字符出现的次数；3. 以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储结构的初态和终态进行输出；4. 对每个字符进行编码并将所编码写入程序，然后对另一文件中的编码编码进行破译。具体介绍：在本课题中，我们在硬盘d盘中预先建立

9、一个哈夫曼.txt 文档，在里面编辑一篇文章 ( 大写 ) 。 然后运行程序， 调用 fileopen() 函数读出该文章， 显示在界面； 再调用 jsq()函数对该文章的字符种类进行统计， 并对每个字符的出现次数进行统计， 并且在界面上显示；然后以每个字符出现次数作为权值，调用 chuffmantree() 函数构建哈夫曼树；并调用print1() 和 print2() 函数将哈夫曼的存储结构的初态和终态进行输出。然后哈夫曼树进行编码， 再对另一文件 哈夫曼译码.txt 编码进行译码，再输出至界面。至此，整个工作就完成了。3.程序设计3.1 实验目的与基本要求利用赫夫曼编码进行通信可以大大提

10、高信道利用率， 缩短信息传输时间， 降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码， 在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编 / 译码系统。试为这样的信息收发站编写一个赫夫曼码的编 / 译码系统。一个完整的系统应具有以下功能：（1） 初始化（ initialization ） 。从文件 哈夫曼 .txt 读入字符集 , ，统计字母个数作为权值，建立赫夫曼树。（2） 编码（ encoding ） 。利用已建好的赫夫曼树（如不在内存，则从文件中读入） ，对哈夫曼树进行编码，然后将结果存入文件 哈夫曼译码.txt 中。

11、（3） 译码（ decoding ） 。利用已建好的赫夫曼树将文件 哈夫曼译码.txt 中的代码进行译码3.2 部分函数介绍从硬盘读取字符串fileopen（ 参数 ）建立 huffmantree通过三个函数来实现：void select（ 参数 ）说明：在 ht1k 中选择 parent 为 0 且权值最小的两个根结点的算法int jsq（ 参数 ）说明：统计字符串中各种字母的个数以及字符的种类void chuffmantree（）说明：构造哈夫曼树输出哈夫曼树的存储结构的初态和终态分别调用 print1（）和print2（） 来实现void print1（ 参数）说明：输出哈夫曼树的初态v

12、oid print2（ 参数）说明：输出哈夫曼树的终态哈夫曼编码和译码void huffmanencoding（ 参数 ）说明：哈夫曼编码char*decode（ 参数 ）说明：哈夫曼译码3.3主要模块程序流程图主函数流程图:图3.1流程图注释：图3.1比较简单，由该图可知主要是调用各个函数模块，首先代开已经存在的文件,然后才开始建立哈夫曼树，计总的字符数以及出现的各个字符和频率。然后统接着在哈夫曼树的基础上对其进行编码，编码之后才是译码。最后输出结束。图3.214构造哈夫曼树:开始结束流程图注释：图3.2是表示构造哈夫曼树的过程。首先输入num个叶结点的权值，当i=num是循环结束。然后进行

13、哈夫曼树的构建，当 i=2*num-1是循环结束。最后输出所得到的字符统计情况。哈夫曼编码：开始流程图解释:流程图3.3表示哈夫曼编码情况。首先初始化，cd-start=0,start=numo然后从首地址0,反之为1.依次开始上溯。将编码存入 哈夫曼译码：hi.bits 。开始进行比较，找节点的父母地址然后看节点为父母地址的左孩子是的话为流程图解释：流程图 3.4 表示哈夫曼译码情况。首先讲哈夫曼编码存入的文件打开，将哈夫曼编码导出。然后将文件中读出的字符与哈夫曼编码cd 进行比较 strcmp(hcj.bits,cd=0 ，相等的话开始译出 strk=hcj.ch 。4 系统实现各模块关键

14、代码及算法的解释：4.1 主函数 (菜单函数)主函数相对简单，只需了解顺序，依次调用即可。这里不做解释4.2 建立 huffmantree代码解释： 该函数为在 ht1k 中选择 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.weightmin1 &ti.parent=0)j=i;min1=ti.weight;s1=j;min1=32767;for (i=1;i=k;i+)if(

15、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&*p=z) k=*p-64;tempk+;统计各种字符的个数送对应的字母到数组中存入对应字母的权值是输入字母总数/for(i=1,j=0;

16、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*num-1 是指哈夫曼/ 所有的结点数目hti.lchild=0;hti.rchild=0;hti.parent=0;hti.weigh

17、t=0;for(i=1;i=num;i+) /hti.weight=cnti;输入num个叶结点的权值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;/ 在 ht1k 中选择 parent 为 0且权值最小/ 的两个根结点 , 其序号为 s1 和 s2,i 为双亲for(i=0;i=num;i+) /输入字符集的中字符hci.ch=stri; /字符的种类i=1;whi

18、le(i=num)printf( 字符 c次数:dn,hci.ch,cnti+);/输出统计的情况4.3 生成 huffman 编码并写入文件代码解释：根据哈夫曼树t 求哈夫曼编码h。void huffmanencoding(huffmantree t,huffmancode h)和 p 分别指示 t 中孩子和双亲临时存放编码串指示码在 cd 中的起始位置最后一位（第num个）放上串结束符初始位置从叶子结点ti开始上溯直至上溯到tc是树根为止int c,p,i;/cchar cdn;/int start;/cdnum=0;/for(i=1;i0) / cd-start=(tp.lchild=c

19、) ? 0 : 1;c=p;/若 tc 是 tp 的左孩子/则生成0;否则生成底码1strcpy(hi.bits,&cdstart);hi.len=num-start;void coding(huffmancode hc ,char *str)/对 str 所代表的字符串进行编码并写入文件int i,j;file *fp;数据结构课程设计 哈夫曼译码.txt,w);while(*str)for(i=1;i=num;i+)for(j=0;jhci.len;j+)if(hci.ch=*str)fputc(hci.bitsj,fp);/将编码写入文件str+;fclose(fp);4.4 对文件 哈

20、夫曼译码.txt 进行译码译码代码解释：代码文件哈夫曼译码.txt 的译码，将翻译的二进制码译成原来的字符。假设远文本文件不超过254 个字符char*decode(huffmancode hc) file *fp;char str254;/char *p;int i,j,k=0,cjs;数据结构课程设计while(!feof(fp) /feof(fp)/feof(fp)=1static char cdn+1;哈夫曼译码 .txt,r);/ 打开文本文档 txt判断文件是否真正结束，时文件结束cjs=0;for(i=0;inum & cjs=0 & !feof(fp);i+)cdi= ;cdi

21、+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运行程序后，我们可以见到一下的运行界面。哈夫曼编码与译码的实现ml打开d盘的的数据结构，t社文件2 一初始化并建立哈夫曼树3 .进行哈二曼编码 ，,进行哈夫曼译码 el退

22、出编码译码器请输入所4.选择要执行的操作工.首先选择1打开文件 哈夫曼.txt37 kd adadebu gd a da.exeh读出文才为； (ongvongkab继续. . .然后选择2初始化并建立哈夫曼树六口 a daxde bugdada. ee请按任意键继塞hu nan t re e 的建i：110011002120111h21302130214fl111a112021412154315941654167517118171313015接下来选择3开始对已经建立的哈夫曼树进行编码并写入文件哈夫曼译码.txttr tr v v + 马3马马马3马马马 5 ? 5- 5- 5-tleci厢

23、 =冏-n 啊 nfl-n 叼二厢 n.ffl 出出出由 蒯1110 till 011 00s ibb 101 110 q01 010哈夫曼译码”t中hi最后对文件哈夫曼译码.txt进行编译选择4开始进行译码的运算由此可见此次程序圆满成功。本程序能够有效的多文件进行编码，并且在译码文件中至于要输入你想要的子母编码，在最后即可输出。总结通过两周的课程设计使我对哈夫曼树以及哈夫曼编码有了更深的认识和理解， 也使我更加明白哈夫曼编码译码在信息技术中的重要性和地位。首先我谈谈我在设计期间我遇到的难点。 开始的时候， 代码中有许多的错误， 其中之一便是部分信息无法有效的传递，不过在后面的改正中我发现的我

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

25、 还学会了系统的做一份课程设计报告， 明白了做事情只有认真，才能真正做得更好！参考文献1 严蔚敏 . 吴伟民 . 数据结构 （c 语言版 ）. 清华大学出版社2 施伯乐. 数据结构. 复旦大学出版社3 谭浩强 .c 语言程序设计教程. 高等教育出版社4 金远平. 数据结构. 清华大学出版社5 王燕 . 面向对象的理论与 c+ 实践 . 清华大学出版社6李春葆.c+语言习题与解析.清华大学出版社7 殷人昆，陶永雷，谢若阳等. 数据结构 . 清华大学出版社8 朱战立，张选平. 数据结构学习指导与典型题解 . 西安：西安交通大学出版社，9 罗文劼，王苗，石强. 数据结构习题解答与实验指. 中国铁道出

26、版社附录 源程序#include #include #include #include#define n 100/#define m 2*n-1int 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;int num;叶子结点数哈夫曼树中的结点树存放编码位串权值左右孩子几双亲指针/0号单元不用/*

27、建立huffmantree*void select(huffmantree t,int k,int &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

28、 *s,int cnt,char str) / 统计字符串中各种字母的个数以及字符的种类int i,j,k;char *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.rchil

29、d=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;void huffmanencoding(huffmantree t,huffmancode h) / 生成哈夫曼编码 int c,p,i;/c和 p 分别指示 t 中孩子

30、和双亲char cdn;int start;cdnum=0;for(i=1;i0) cd-start=(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)/file *fp;char str254;/char *p;static char cdn+1;int i,j,k=0,cjs;代码文件哈夫曼译码.txt 的译码假设文本文件不超过254 个字符打开文本文档 txt数据

31、结构课程设计 哈夫曼译码.txt,r);/while(!feof(fp)/feof(fp)判断文件是否真正结束， 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 存储结构 *v

32、oid print1(huffmantree ht)/初建哈夫曼int x;for(x=1;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);n);printf(/void dhuffmantree(huffmantree ht,int cnt)初始化哈夫曼树int i;for(i=1;i=num;i+)/输入num个叶结点的权值hti.weight=cnti;/*打开文本 *int open(char string)file *fp;数据结构课程设计 哈夫曼 .txt,r)=null)printf( 不能打开文件!n);exit(1);while(fgets(string,100,fp)!=null)printf(%sn,string);f