1、 数据结构课程设计报告数据结构课程设计报告 压缩软件压缩软件 -采用哈夫曼编码技术采用哈夫曼编码技术 学学 号：号： 二八二八年九月三日星期三年九月三日星期三 目录目录 课程设计课题课程设计课题3 设计要求及分析设计要求及分析3 软件开发软件开发3 类的结构图类的结构图4 程序类的说明程序类的说明4 较有特色的函数较有特色的函数5 测试结果测试结果6 收获与体会收获与体会7 【一】【一】课程设计课题：课程设计课题： 压缩软件 【二】【二】设计要求及分析：设计要求及分析： 要求：要求： 建立一个文本文件 A，统计该文件中各字符的频率，对各字符进行 Huffman 编码， 将该文件翻译成 Huff
2、man 编码文件 B，再将 Huffman 编码文件译码成文件 C，并对 文件 A 与 C 进行比较。 数据压缩理论数据压缩理论：数据压缩有 2 种基本类型：无损压缩和有损压缩,使用无损压缩方法压缩的 文件不会丢失任何信息,他与原文件具有可逆性,就是可以通过解压缩的方法恢复原 来的数据,通常对文本文件,字处理文件,应用程序等采用这种算法。有损压缩算法在 压缩时回丢失一些信息，压缩后不能完整恢复出原有信息，较多应用于音频，视频 图象数据的处理。 哈夫曼树简介：哈夫曼树简介：标准 ASCII 码把每个字符分别用一个 7 位的二进制数表示，这种方法使用 最少的位表示了所有 ASCII 码中的 128
3、 个字符，称为等长编码，如果每个字符的使 用频率相等，等长编码是空间效率最高的方法。如果字符出现的频率不同，可以让 频率高的字符采用尽可能短的编码，频率低的字符采用稍长的编码，来构造一种不 等长编码，则会获得更好的空间效率。而此处我们所实现的哈夫曼算法，就是一种 不等长编码，用于数据的无损压缩。术语是指用一张特殊的编码表对源字符进行编 码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起 来的，同时保持编码的唯一可解性，这种方法是由美国科学家 David.A.Huffman 发 展起来的。 哈夫曼树是哈夫曼算法的理论描述工具，也称最优二叉树，是一种加权路径长 度最短的二叉树
4、。加权路径长度是指树中所有叶子结点的权值乘上其到根结点的路 径长度。N 个叶子结点的哈夫曼树共有 2n-1 个结点，这个性质将运用于使用数组结 构存储哈夫曼树，从根结点开始，左分支结点分配 0，右分支结点分配 1，沿着树根 到各个结点就得到了哈夫曼编码，因为所有被编码的字符都作为叶子结点出现而每 个叶子结点路径又是独立的，保障了每个编码都不会四其余码的前缀，这样的编码 又称“哈夫曼无重复前缀编码” ，这在下面的程序段会应用到。哈夫曼树也应用于译 码过程，译码过程中逐一扫描码文，从哈夫曼的根结点开始，根据每一位的值是 0 还是 1 确定选择左分支还是右分支直到到达一个叶子结点， 然后再从根出发， 开始下一个字符的翻
