48 福 建 电 脑 福 建 电 脑 福 建 电 脑 2012 年第 期 1 用 Huffman 编码对文件进行压缩的 语言实现 C 路 炜 门玉梅 李建俊 ， ， 河北师范大学附属民族学院 河北 石家庄 （ 050091 ） 摘 要 【 】： 本文介绍了采用 Huffman ASCII 编码对 现了这个压缩过程 文中给出了比较完整的 语言程序代码 码文件进行压缩的基本原理 ， 可以直接用于调试实验 。 】： Huffman 编码 哈夫曼编码 哈夫曼树 文件压缩 C ， 语言 数据结构 C 并用 C 语言程序实 。 关键词 【 引言 1、 ， 在 使用 Huffman 数据结构 。 具有压缩速度快 为了减少文件的存储空间或者在传输文件时减少 编码 网络流量 经常要对文件进行压缩 进行压缩是一种很好的压缩方法 算 必然会遇到 法简单等优点 让学生利用 编码进行文件压缩这样的课题 Huffman 由于教材上只给出了 因此 很多老师和学生在完成这个课题都时感觉比较困难 本文将给出利用 缩的 。 码文件进行压 树的定义和编码 语言程序实现 以供大家参考 实践教学中 Huffman Huffman 编码对 ASCII ， ， ， 、 。 《 》 。 ， ， 。 C 基本原理 2、 ；3 ASCII Huffman 编码是一种常用的压缩编码方法 ， 本原理是将频繁使用的数据用较短的代码代替 使用的数据用较长的代码代替 这些代码都是二进制码 相同 的 对 文 件 进 行 压 缩 的 过 程 大 致 分 为 四 个 步 骤 ， 它的实现主要借助于 其基 较少 每个数据的代码各不 且代码的长度是可变 树 编码 创 建 打 开 需 要 压 缩 的 文 码 对 应 的 将 需 要 压 缩 的 文 件 中 的 每 个 树 并 生 成 哈 夫 曼 编 码 Huffman ：1 Huffman 件 Huffman 用 ；2 ， ， ， 。 , 。 。 。 ， 3 ；4 树 其中 步骤 Huffman bit 1 和步骤 单位输出 编码按 步骤 文件压缩结束 是压缩过程的关键 1 数中各叶子结点字符出现 统计字符出 Huffman 如每次创建前扫描被创建 或者是创建 ； 统计了十余篇 将 编 两个关 树 字符出现的频率 。 码对应的 3 Huffman 所要做工作是得到 Huffman 的频率并根据这个频率创建 现的频率可以有很多方法 的文件 实时 前即做好统计 不同的文章中各个 ASCII 需要压缩的文件中的每个 码按 bit 键步骤 来找到每个字符对应的哈夫曼编码 单位输出 转换 地生成各字符的出现频率 本文采用后一种的方案 ， 部分大可不必去通过遍历 可以将每个 这里涉及到 Huffman ASCII 步骤 输出 转换 和 ：“ ，“ ， ： ” 。 “ ” “ ” ” Huff- 码存放于如下所示的结构 ， 码值及其对应的 man 体中 ： ASCII typedef struct { char asciiCode; unsigned long huffCode; int huffCodeLen; }HuffCode; 创建由该结构体结点所组成的 长度为 128 ， 中 的 下 标 和 的一 asci- ：codeList[i].asciiCode= 编 码 的 的 维数组 codeList[128]， codeList 满足下面的顺序存放关系 且 查 找 某 个 字 符 这 样 的 话 iCode i； 工作便变得相当轻松了 数组 ， ， 如下 Char].huffCode; 某种遍历方式下的按找到的字符进行置数的方式 分的方便 codeList[128] ， ：sHuffCode=codeList[in- 的创 建 可 以 采 用 十 inChar huffman 。 编程准备 3、 本程序将预先统计好的各个 即 树的叶子节点权值 ASCII 放在 ( key.txt 然后将这些权值读取出来保存到一个数组中 ) 码字符出现的 文件 然后 Huffman 频率 中 再根据此数组构造 编码值 ， 。 Key.txt 树 ， 文件内容如下 Huffman ： 得出各字符的 ， Huffman 0,0,0,0,0,0,0,0,0,869,389,0,0,385,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 281,5,98,14,0,27,3,2,144,145,31,41,65,112,41,46,28,38,11,7,1,2,2,1,0,0,41, 190,16,89,4,0,0,0,2,3,3,15,61,1,5,47,0,0,52,34,33,18,74,18,39,98,64,70,5,5, 0,0,9,49,56,49,0,0,0,347,66,111,102,637,149,157,42,408,0,22,141,114,370, 180,189,5,265,251,416,210,7,30,34,57,31,27,2,26,0,0; 4、C 语言代码实现 本程序中生成 Huffman 和编码生成的代码请见参考文献 件进行压缩的核心代码如下 [1] 结构体的声明 、Huffman 中相应算法 树 对文 ， ： 主函数 函数入口 注意 ， ： 需要被压 ， void main(int argc,char* argv[])/* 缩文件名作为参数 */ 注 ： {/* 本程序中变量的声明省略 while(! feof(inputFile)) /* { count=0; 。 */ 对文件进行压缩 */ outputData=0x01; while(count<8) { if(curIndex==curLen) { if(feof(inputFile)) break; inData=fgetc(inputFile); 注 ： 河北师范大学附属民族学院校本科研课题 基于项目导向的 《 数据结构 " " 课程教学研究 课题编号 》， ：201010Y06-3 

2012 年第 期 1 福 建 电 脑 福 建 电 脑 49 if(inData==-1&&feof(inputFile)) { if(count==0) outputData=-1; else { for(i=0;i<8-count;i++) fclose(inputFile); fclose(outputFile); return; ((rearCode>>(rearCodeLen-1-i))&0x01); } } break; } {outputData <<=1; outputData |= 5、 } 程序运行结果 压缩前文件 curCode=huffList[inData].huffCode; curLen=huffList[inData].huffCodeLen; realLen=getBinLen(curCode); 此处省略 函数是自定义函数 ， 用于获取 ， Huffman 编码 i=curLen-realLen; curIndex=0; } if(i>0) { outputData<<=1; i--; } /*getBinLen 的长度 &0x01; */ } /* outputData<<=1; outputData|=(char)tmpBinData; } curIndex++; count++; } fputc(outputData,outputFile); 文件压缩完成 */ 的大小是 maintest.txt 的 大 小 是 后 文 件 maintest.rer 码文件的压缩 5.40KB， 是对 没有丢失原文件的信息 压缩过程中 。 ， ， 。 ASCII 一一对应的转换 缩 式 开 外还可以用来对 ， ， 在解压缩压缩后的文件时 用其他软件都不能打开 ， 所以本程序除了可以对 ， 必须有 ASCII 码文件进行加密 。 ASCII ASCII 8.18KB， 压缩以 成 功 实 现 对 码进行 属于无损压 格 文件才能打 key.txt 码文件进行压缩之 *.rer ， 文件类型变为 参考文献 : 2007 严蔚敏 [2] 出版社 . 2007 吴伟民 米宁 . ， ， 数据结构题集 语言版 :C [M]. 清华大学 徐 翠 霞 数 据 结 构 案 例 教 程 [3] . 语 言 版 :C [M]. 北 京 大 学 出 版 社 . 谭浩强 . C 语言程序教程 第二版 ( ) [M ] . 北京 : 高 等 教 育 出 2009.3 [4] 版社 . 1998 else { tmpBinData =(curCode >>(curLen -curIndex -1)) 严 蔚 敏 ， [1] 吴 伟 民 数 据 结 构 语 言 版 :C [M]. . 清 华 大 学 出 版 社 . !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 上接第 页 ) 。 ， ， “ ， ”。 11 45 3.3 年 于 2011 笔者所在院系 。 襄樊学院大学生物理实验创新设计大赛 ( 创新大赛 举办了 者鼓励教授的学生积极参加 一组学生获得三等奖 奖 。 生对学习基础物理的兴趣 识进行创造发明的平台 改变期末考试内容 针对传统基础物理考试主要考查学生识记能力 月联合教务处 笔 并有一组学生或者二等 ， 通过大赛的开展 提高了学 也给学生一个应用所学知 。 增加和生活相关的物理考题 而轻能力的弊端 并选择了几个知识点进行了命 、 笔者在期末命题 大量查阅和生活有关的大学物理知识和相关应用 圆 “ 为什 而不是设计成凹形的 和 其目的是考查学生将普通的物理知 解释生活中的物理原理现象的能力 解题能力 时 ， 实例 。 周运动 么桥都设计成凸形 呢 ？ ”。 知识 圆周运动 “ 识应用到生活中 题目解答如下 出了一道这样的简答题 这道题目知识点不难 ， 主要用到 这个知识点时 力的合成 ， 拱形 重知识 在考查 例如 的 ：“ ”、 ， ， ， ， 。 ： ” 。 “ ” 。 ， 。 ( ) 车重为 F， Mg， 车对桥的压力为 则 N。 ：F=Mg-N>0 ∴ N0 ∴ N>Mg 汽车经过拱形桥中部时 桥所承受的 ， 压力较小 所以出于安全考虑 ， 从这题学生的解答来看 桥都设计成拱形桥 ， 考查的效果达到了 。 学生 。 ， ： 设向心力为 在拱形桥 在凹形桥 从上面看出 ， ， 。 另一部分学生虽然错了 充分发挥了他们的想象力和创造力 。 但错得 了 从他们的错误中 通过考试内容的改变 习时 活应用中体现出的物理原理 其综合能力的目的 一部分学生答对 可爱 因为可以 看到想象的翅膀和认真思考的影子 。 使得学生在平时学习和期末复 以及多思考生 提高 多关注物理知识在生活中的应用 从而达到学以致用 ”。 “ ， 。 ， ， 。 ， 。 结语 4、 通过基础物理考试的改革 有利于督促学生学习 有利于提高学生运用知识进行创新的能力 ， ， 、 使考试多样化 灵活 有利于提高学生学习的积极 也给学 这对学生的结合素质提高是 笔 至少如何把握各种考核手段 。 ， ， ， 化 性 生提供更多拓展的机会 大有好处的 者的考试改革是有效的 的应用方式和深度 。 ， 。 通过学生评教和学生干部的反馈证明 还有待进一步研究 ， 。 参考文献 赵纯 : . 高等理科教育 [1] 例 [J]. 胡南 [2] ， 学院学报 张三慧 . [3] 社 , 1999: 379. 关于大学物理考试改革的探索 以华南理工大学为 ——— . 2003(S1): 137-138. 李锐锋 刘琴 关于大学物理考试改革的探索 ， . 重庆工 [J]. . 2005(05): 110-112. 大学物理学 第一册 力学 ： [M]. 第 版 . 2 清华大学出版