多媒体课程设计报告
基于哈夫曼树的文件压缩解压程序
20091110
f一
需求分析
1课题要求（实现文件的压缩与解压并计算压缩率）
A描述压缩基本符号的选择方法B运行时压缩原文件的规模应不小于5K
2设计目标
A软件名称：基于哈夫曼编码的文件压缩实用程序系统B软件组成：huffma
exeC制作平台及相关调试工具：Wi
dowsXPsp3MicrosoftVisualC60
D运行环境：doswi
2Kwi
2003wi
xpE性能特点：1软件由一个可执行文件组成huffma
exe为dos系统应用程序，体积小，高效快捷，适用范围广。2对单字节（256叶子）进行哈夫曼编码，压缩率良好3使用二级缓冲压缩解压技术，速度比一般算法高4可压缩最大体积为4G的文件，达到Fat32文件系统极限5文件索引体积比常规算法小50
二概要设计
1相关函数介绍
2
f1boolI
itFromFilestri
gfileadd从文件中初始化哈夫曼树函数2voidHTCreatHTNodehti
t
构造哈夫曼树函数3voidHCCreatHTNodehtHCodehcdi
t
构造哈夫曼编码函数4voidCo
vertFileHCodehcdstri
gfileaddstri
gfileadd2压缩a
d写入文件函数5voidDecompressio
Filestri
gfileadd2stri
gfileadd3文件解压函数6stri
gCompressio
stri
gfileadd压缩函数7stri
gDecompressio
stri
gfileadd2解压函数
2函数调用示意图
I
itfromfileHtcreatCompressio
HccreatCo
vertfileClockClock
Mai

Decompressio

Decompressio
file
Clock
Exit
三
详细设计
3
f1压缩算法部分
A核心算法：
Huffma
编码是一种可变长编码方式，是由美国数学家DavidHuffma
创立的，是二叉树的一种特殊转化形式。编码的原理是：将使用次数多的代码转换成长度较短的代码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。Huffma
算法的最根本的原则是：累计的字符的统计数字字符的编码长度为最小，也就是权值字符的统计数字字符的编码长度的和最小。
B哈夫曼树构造算法：
Huffma
树是二叉树的一种特殊转化形式。以下是构件Huffma
树的例子：比如有以下数据，ABFACGCAHGBBAACECDFGFAAEABBB先进行统计A8B6C4D1E2F3G3H1括号里面的是统计次数生成Huffma
树：每次取最小的那两个节点
ode合并成一个节点
ode，并且将累计数值相加作为新的接点的累计数值，最顶层的是根节点root注：列表中最小节点的是指包括合并了的节点在内的所有节点，已经合并的节点不在列表中运算的过程如下：1DH22DEH43FG64CDEH85BFG126ACDEH167ACDEHBFG28那么转化为Huffma
树就是Huffma
树Root┌┴┐ACDEHBFG┌┴┐┌┴┐CDEHABFG┌┴┐r