哈夫曼编码解码器的实现课程设计

1、课程设计报告 院（系）:_电气与信息工程学院_ 专业班级: 计科普 学生姓名: 学 号: 设计地点（单位）_计算机基础自主学习中心_ _设计题目:_哈夫曼编码解码器的实现 _ _ 完成日期： 指导教师评语: _ _ _ 成绩（五级记分制）:_ _ 指导教师（签字）:_ _ 课程设计任务书设计题目：哈夫曼编码解码器的实现学生姓名课程名称数据结构课程设计专业班级计科地 点计算机基础自主学习中心起止时间设计内容及要求功能：利用哈夫曼编码对数据进行无损压缩，实现Huffman压缩的编码器和译码器。1. 首先读入待压缩源文件。2. 然后建立并分析字母表，对每种字符的出现频度进行统计，以频度作为建立Huf

2、fman树的权值。3.频度表建好后，就可以根据算法建立Huffman树，对出现的每种字符进行Huffman编码。4. 此时，再次读入源文件，逐字节编码，将得到的编码流写入到磁盘文件，并且计算压缩率。5. 译码过程先读入被压缩的文件，将其解释为比特流，根据Huffman树，对比特流逐位译码，将译码结果逐次写入到磁盘文件。要求：完成编码译码功能。设计参数 测试数据要求：自行设计。 输出数据要求：输出每个字符（或是词）的使用频率，及编码规则。进度要求2011.1.4 星期二（上午教师指导，下午学生独立完成）、完成任务的讲解、并接受课程设计任务，选定课程设计的题目2011.1.5 星期三（上午教师指导

3、，下午学生独立完成）、了解任务的算法、并画出算法的程序流程图2011.1.6 星期四（上午教师指导，下午学生独立完成）、对任务的关键技术进行验证、并确定解决办法2011.1.7 星期五（上午教师指导，下午学生独立完成）、编制任务的程序2011.1.10 星期一（上午教师指导，下午学生独立完成）、编制任务的程序2011.1.11 星期二（上午教师指导，下午学生独立完成）、对程序的调试，并试运行。2011.1.12 星期三（上午教师指导，下午学生独立完成）、整理课程设计过程中的各个参数、并进行总结，提出改进意见2011.1.13 星期四（上午教师指导，下午学生独立完成）、编写课程设计报告、准备答辨

4、2011.1.14 星期五（上午答辨）、进行答辨验收工作。参考资料其它说明.本表应在每次实施前一周由负责教师填写二份，院系审批后交院系办备案，一份由负责教师留用。.若填写内容较多可另纸附后。3.一题多名学生共用的，在设计内容、参数、要求等方面应有所区别。教研室主任： 指导教师： 摘要 哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。哈夫曼编码算法使用字符在文件中出现的频率，并用哈夫曼树来建立一个用01串表示各字符的最优表示方式。通过0，1串替换字符，并压缩为bit流写入文件，从而实现文件的压缩，解压则通过读取文件头和文件尾的解码规则，实现文件的解压。本程序就是基于以上原理设计了压缩、解压

5、和打印哈夫曼编码的功能。本程序经过测试后，功能均能实现，运行稳定。关键词：哈夫曼编码 压缩 01串 bit流 二叉树 目录 TOC o 1-3 h z u HYPERLINK l _Toc282707582 摘要 PAGEREF _Toc282707582 h I HYPERLINK l _Toc282707583 1需求分析 PAGEREF _Toc282707583 h 1 HYPERLINK l _Toc282707584 2系统分析与设计 PAGEREF _Toc282707584 h 1 HYPERLINK l _Toc282707585 算法设计 PAGEREF _Toc28270

6、7585 h 1 HYPERLINK l _Toc282707586 程序流程图 PAGEREF _Toc282707586 h 1 HYPERLINK l _Toc282707587 程序模块图 PAGEREF _Toc282707587 h 1 HYPERLINK l _Toc282707588 2.2.3 Compress()函数流程图 PAGEREF _Toc282707588 h 2 HYPERLINK l _Toc282707589 2.2.4 Uncompress()函数流程图 PAGEREF _Toc282707589 h 3 HYPERLINK l _Toc282707590

7、 2.2.4 文本存储示意图 PAGEREF _Toc282707590 h 4 HYPERLINK l _Toc282707591 2.3 关键代码分析 PAGEREF _Toc282707591 h 4 HYPERLINK l _Toc282707592 结构体定义 PAGEREF _Toc282707592 h 5 HYPERLINK l _Toc282707593 数组的初始化 PAGEREF _Toc282707593 h 5 HYPERLINK l _Toc282707594 2.3.3 生成Huffman树 PAGEREF _Toc282707594 h 6 HYPERLINK

8、l _Toc282707595 2.3.4 生成Huffmancode PAGEREF _Toc282707595 h 7 HYPERLINK l _Toc282707596 3软件测试 PAGEREF _Toc282707596 h 9 HYPERLINK l _Toc282707597 测试压缩功能 PAGEREF _Toc282707597 h 9 HYPERLINK l _Toc282707598 测试解压功能 PAGEREF _Toc282707598 h 9 HYPERLINK l _Toc282707599 测试Huffmancode打印功能 PAGEREF _Toc282707

9、599 h 10 HYPERLINK l _Toc282707600 4总结 PAGEREF _Toc282707600 h 11 HYPERLINK l _Toc282707601 5软件使用说明书 PAGEREF _Toc282707601 h 13 HYPERLINK l _Toc282707602 致谢 PAGEREF _Toc282707602 h 14 HYPERLINK l _Toc282707603 参考文献 PAGEREF _Toc282707603 h 15 HYPERLINK l _Toc282707604 附录 PAGEREF _Toc282707604 h 161需求

10、分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码，是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。哈夫曼编码使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而

11、达到无损压缩数据的目的）。哈夫曼编码的应用很广泛，利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是哈夫曼编码。哈夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串。哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从

12、哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。本程序具有对文本压缩和解压的功能，并能打印出哈夫曼编码。2系统分析与设计算法设计Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffman算法的最根本的原则是：累计的(字符的统计数字*字符的编码长度)为最小，也就是权值(字符的统计数字*字符的编码长度)的和最小。权值统计：因为是处理文本文件，本程序定义了512个结构体数组

13、，因为一个字节存储的范围是0255，及256个字符（包括汉字的半个编码），根据定义Huffman树的节点个数m=2*n-1,所以512个数组刚好能把所有字符统计出来。在逐个读取文本字符的时候，根据字符的ASCII码做为数组下标，同时初始化512个数组，并将文件中存在的字符的ASCII码存入对应的结构体中。生成Huffman树：每次取最小的那两个节点(node)合并成一个节点(node)，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点(root) 注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表。生成Huffmancode：根据Huffman树中个节点的

14、关系生成Huffmancode，规则为左节点编码0，右节点编码1.将编码装入结构体。写入文件：读取文件中字符，按照对应的编码和文件中的字符顺序，拼接成大于8的字符串，使用位操作转化为bit流。满一个字节就写入压缩后的文件中，重复上述过程。解压：首先读取解压文件的文件头和尾部的解压法则，按照解压法则，将文件恢复到解压的文件中。解压法则实际上就是字符对应的Huffman编码。程序流程图.1程序模块图以下为主函数对个函数的调用关系图，其中Compress()为文本压缩函数，Uncompress()为文本解压函数，printHUMcode()为哈夫曼编码打印函数，printMenu()为菜单显示函数。

15、Main()Compress()Uncompress()printHUMcode()printMenu()图2.1 模块图.2程序流程图程序开始后，提示用户选择操作功能。1：压缩文件；2：解压文件；3：打印哈夫曼编码；0：退出程序。当功能完成后，继续循环（0除外）。开始C=Getch()TC=1Compress()breakFTUncompres()breakC=2FTC=3printHUMcode()breakFFC=0输入有误breakT结束图2.2 程序流程图.3 Compress()函数流程图调用Compress()函数，输入源文件地址，和目标文件地址后。函数开始读取字符进行频率统计，

16、根据频率从大到小对512个数组排序。接下来用排序后的数组生成Huffman树，然后根据Huffman中的各元素的关系生成Huffmancode,然后根据编码对文件中的字符进行替换，并压缩为bit流写入目标文件。开始输入源文件和目标文件统计频率数组排序生成Huffman树生成Huffmancode转化bit流写入文件结束图2.3 Compress()函数流程图.4 Uncompress()函数流程图 Uncompress()函数先读取解压文件头和尾部的解压法则，对文件中间的字符进行解压。开始输入源文件和目标文件读取解压法则对文本中间的数据解压写入目标文件结束图2.4 Uncompress()函数

17、流程图.4 文本存储示意图字符在存储的时候，前04个字节存储源文件字符个数，58个字节存储压缩后字符个数。接下来存储压缩后的字符及01串，紧接着是字符种类，然后是字符，再然后是字符对应编码的长度，最后是字符对应的编码。源文件字符个数压缩后字符个数010101字符种类字符字符编码长度字符对应编码图2.5 文本存储示意图2.3 关键代码分析结构体定义typedef struct HuffmanTree unsigned char b; /记录字符的ASC码long count; /字符出现频率（权值） long parent,lch,rch; /定义哈夫曼树指针变量char bits256; /定

18、义存储哈夫曼编码的数组Huffman;数组的初始化 此段代码不但实现了对512个数组的初始化，还实现了将文件中出现的字符放入以字符ASCII码确定下标的数组中，方便查找。while(!feof(ifp) fread(&c,1,1,ifp); headerc.count+; /字符重复出现频率+1 flength+; /字符出现原文件长度+1flength-; /文件末尾读了两次length1=flength; /原文件长度用作求压缩率的分母headerc.count-; for(i=0;i512;i+) /初始化数组 if(headeri.count!=0) headeri.b=(unsign

19、ed char)i; /记录该数组对应的字符的ASC码 else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /对结点进行初始化 生成Huffman树每次取最小的那两个节点合并成一个节点，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点。新生成的节点全部放在紧接在数组中存储节点的最后一个后面 注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表。for(i=0;in;i+) f=i; headeri.bits0=0; /起始符为空 while(headerf.parent!=-1) j

20、=f; f=headerf.parent; if(headerf.lch=j) /判断是否为左孩子 j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=0; else /置右分支编码1 j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=1; 生成Huffmancode 生成Huffman的原理是通过位操作，将01的字符串，转换为bit流，如果当前为0的话则向左移以为，若为1的话则

21、向左移以为并或上1。while(!feof(ifp) c=fgetc(ifp); f+; for(i=0;i=8) /对哈夫曼编码位操作进行压缩存储 for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c0) /对哈夫曼编码位操作进行压缩存储strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); pt1+; 3软件测试 为源文件，为压缩后的文件。图3.2 压缩后文件对比图3.3 解压功能测试图3.4 解压后文件对比Huffmancode打印

22、功能图3.4 哈夫曼编码打印4总结由于本课题中的许多知识点都没有学过都要靠自己到课外的资料中去查找。在用的时候难免出现这样那样的错误。回顾起此次课程设计，至今我仍感慨颇多，的确，从拿到题目到完成整个编程，从理论到实践，在将近半个月的日子里，可以学到很多很多的东西，同时不仅可以巩固了以前所学过的知识，而且学到了很多在书本上所没有学到过的知识。通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结论，才能提高自己的实际动手能力和独立思考的能力。在设计的过程中遇到问题，可以说得是困难重重，这毕竟第一次做的，难免会遇到过各种

23、各样的问题，同时在设计的过程中发现了自己的不足之处，对以前所学过的知识理解得不够深刻，掌握得不够牢固，比如说文本操作通过这次课程设计之后，一定把以前所学过的知识巩固一下。本次课程设计结束了，对于我的影响很大。我通过这次实践学到了许多知识。学到了设计一个程序。要注意哪些方面。也使我知道自己哪些方面做得还不够。5软件使用说明书1)选择1：压缩功能。 若源文件在根文件夹中直接输入文件如1.txt。如果在其它地方，这注明路径如e:1.txt。 2)选择2：解压功能。 解压时直接输入解压文件名，如a，程序会自动个a加上.hub的后缀名。存储文件可以写为X.txt.图3.3 解压功能测试3)选择3：打印哈

24、夫曼编码。4)选择0：退出程序。致谢首先感谢我的父母，没有他们辛勤的付出也就没有我的今天，在这一刻，将最崇高的敬意献给你们！同时感谢向毅、陈刘奎、熊茜老师，他们不求回报，无私奉献的精神很让我感动，再次向他表示由衷的感谢。在这几学期中结识的各位生活和学习上的挚友让我得到了人生最大的一笔财富。在此，也对他们表示衷心感谢。本文参考了大量的文献资料，在此，向各学术界的前辈们致敬！签名： 付作辉 日期 2011/1/12参考文献1 严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.2 严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.3 DATA STRUCTURE WITH C+. Wil

25、liam Ford,William Topp .清华大学出版社（影印版）. 4 谭浩强.c语言程序设计. 清华大学出版社. 5 数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译 电子工业出版社 2001 年1月6 附录程序代码/主函数#include #include #include #include #includeHuffmantype.h#includeprintMenu.h#in

26、cludecompress.h#includeuncompress.h#includeprintHUMcode.h/*主函数*/int main() int c;Huffman header512=0;Huffman header1512=0;Huffman tmp;while(1) printMenu();/菜单工具栏 do printf(nt*请选择相应功能(0-3):); c=getch(); printf(%cn,c); if(c!=0 & c!=1 & c!=2 & c!=3) printf(t请检查您的输入在03之间！n); printf(t请再输入一遍！n); while(c!=

27、0 & c!=1 & c!=2 & c!=3); if(c=1) compress(header,header1,tmp); /调用压缩子函数 else if(c=2) uncompress(header,tmp); /调用解压缩子函数 else if(c=3) printHUMcode(header1); /调用打印编码子函数 else printf(t欢迎您再次使用n); exit(0); /退出该工具 system(pause); /任意键继续 system(cls); /清屏return 0;/void compress(Huffman *header,Huffman *header1

28、,Huffman &tmp) char filename255,outputfile255,buf100; unsigned char c; long i,j,m,n,f; long min1,pt1,flength,length1,length2; double div;FILE *ifp,*ofp; printf(t请您输入需要压缩的文件：); gets(filename); ifp=fopen(filename,rb); if(ifp=NULL) printf(nt文件打开失败!nn); return; printf(t请您输入压缩后的文件名：); gets(outputfile); o

29、fp=fopen(strcat(outputfile,.hub),wb); if(ofp=NULL) printf(nt压缩文件失败!nn); return; flength=0; while(!feof(ifp) fread(&c,1,1,ifp); headerc.count+; /字符重复出现频率+1 flength+; /字符出现原文件长度+1flength-; /文件末尾读了两次length1=flength; /原文件长度用作求压缩率的分母headerc.count-; for(i=0;i512;i+) /初始化数组 if(headeri.count!=0) headeri.b=(

30、unsigned char)i; /记录该数组对应的字符的ASC码 else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /对结点进行初始化 for(i=0;i256;i+) /根据频率（权值）大小，对结点进行排序，选择较小的结点进树 for(j=i+1;j256;j+) if(headeri.countheaderj.count)/从大小 tmp=headeri; headeri=headerj; headerj=tmp; for(i=0;i256;i+) if(headeri.count=0) break; n=i;

31、 /外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1. m=2*n-1;for(i=n;im;i+) /构建哈夫曼树 min1=999999999; /预设的最大权值，即结点出现的最大次数 for(j=0;jheaderj.count) /找权值最小的那个数组 pt1=j; min1=headerj.count; continue; headeri.count=headerpt1.count; /在原有的基础上向后面添加数组 headerpt1.parent=i; /记录parent的下标 headeri.lch=pt1; /记录左孩子的下标 min1=999

32、999999; for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count+=headerpt1.count; headeri.rch=pt1; /记录右分支下标 headerpt1.parent=i; /记录parent下标/*生成哈夫曼编码*/for(i=0;in;i+) f=i; headeri.bits0=0; /起始符为空 while(headerf.parent!=-1) j=f; f=headerf.parent; if(headerf.lch=j) /判断是否为左孩子 j=strlen(h

33、eaderi.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=0; else /置右分支编码1 j=strlen(headeri.bits); memmove(headeri.bits+1,headeri.bits,j+1); headeri.bits0=1; for(i=0;headeri.b!=0;i+)header1i=headeri;/ fseek(ifp,0,SEEK_SET);/文件定位 fwrite(&flength,sizeof(int),1,ofp); fseek(ofp,8,SEEK_SET);

34、buf0=0; f=0; /记录字符 pt1=8; while(!feof(ifp) c=fgetc(ifp); f+; for(i=0;i=8) /对哈夫曼编码位操作进行压缩存储 for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c0) /对哈夫曼编码位操作进行压缩存储 strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c1; fwrite(&c,1,1,ofp); pt1+; fseek(ofp,4,SEEK_SET); fwrite(&pt1,sizeof(long),1,

35、ofp); fseek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(long),1,ofp); for(i=0;in;i+) fwrite(&(headeri.b),1,1,ofp); c=strlen(headeri.bits); fwrite(&c,1,1,ofp); j=strlen(headeri.bits); if(j%8!=0) /若存储的位数不是8的倍数，则补0 for(f=j%8;f8;f+) strcat(headeri.bits,0); while(headeri.bits0!=0) /判断是否为空 c=0; for(j=0;j8;j+) /字符

36、的有效存储不超过8位，则对有效位数左移实现两字符编码的连接 if(headeri.bitsj=1) c=(c1)|1; /|1不改变原位置上的01值 else c=c1; strcpy(headeri.bits,headeri.bits+8); /把字符的编码按原先存储顺序连接 fwrite(&c,1,1,ofp); length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /计算文件的压缩率fclose(ifp); fclose(ofp); printf(nt压缩文件成功!n); printf(t压缩率为 %f%nn

37、,div*100); return; /*解压缩*/void uncompress(Huffman *header,Huffman &tmp) char filename255,outputfile255,buf255,bx255; unsigned char c; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; printf(t请您输入需要解压缩的文件：); gets(filename); ifp=fopen(strcat(filename,.hub),rb); if(ifp=NULL) printf(nt文件打开失败!n); return

38、; printf(t请您输入解压缩后的文件名：); gets(outputfile); ofp=fopen(outputfile,wb); if(ofp=NULL) printf(nt解压缩文件失败!n); return; fread(&flength,sizeof(long),1,ifp); /读取原文件长度，对文件进行定位fread(&f,sizeof(long),1,ifp); fseek(ifp,f,SEEK_SET); fread(&n,sizeof(long),1,ifp); for(i=0;i0) m=p/8+1; else m=p/8; for(j=0;jf;l-) strcat(headeri.bits,0); /处理编码全为零的 strcat(headeri.bits,buf); headeri.bitsp=0; for(i=0;in;i+) /根据哈夫曼编码的长短，对结点进行排序