内容发布更新时间 : 2024/12/22 17:07:18星期一 下面是文章的全部内容请认真阅读。

《数据结构》 课程设计报告

设计题目：哈夫曼编码压缩解压缩 学生姓名：

专 业：计算机科学与技术 班 级： 学 号： 指导老师： 完成日期：

合肥工业大学计算机与信息学院

一、 问题分析和任务定义 1.1设计任务

采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。要求

（1）描述压缩基本符号的选择方法。

（2）运行时的压缩原文件的规模应不小于5K。 （3）提供恢复文件与原文件的相同性对比功能。 1.2问题分析

本课题是利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（.txt）。

在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。哈夫曼树又称最优二叉树，是带权路径长度最小的二叉树。

在文本文件中多采用二进制编码。为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。

统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。

哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。其次要找到构建压缩功能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。

1.3测试用数据

本实验的数据是通过读入一个名为huffman.txt的文本文档，文档中内容为字符型数据。

二、 概要设计和数据结构的选择

以下是在任务分析对题意的理解做出的概要设计和对数据结构的选择： 1、 数据结构定义

//huffman树的结点结构体

typedef struct HTnode {

long weight; //记录结点的权值

int parent; //记录结点的双亲结点位置 int lchild; /结点的左孩子 int rchild; //结点的右孩子 int *code; //记录该结点的huffman编码

int codelen; //记录该结点huffman编码的长度

//初始化结点，令其权值为无穷大，无双亲及左右孩子 HTnode() { weight = MAX; parent = -1; lchild = -1; rchild = -1; codelen = 0; }

}HTnode;

2、 定义huffman数类及其函数

class huffmanTree {

public:

huffmanTree();

virtual ~huffmanTree();

bool count(char *input); //压缩时统计各字符出现的次数，将其写入对应结点的权值 void create(); //压缩时根据各结点的权值构造huffman树

void code(); //压缩时利用huffman树计算每个字符的huffman编码 void printcode(); //列出每个字符的huffman编码

void addbit(int bit); //压缩时对一个未满8个bit的byte中加入一个bit void resetbyte(); //将byte清空

bool compress(char *input, char *output);//压缩函数,成功返回 true 失败 false bool decompress(char *input, char *output); //恢复函数,成功返回 true 失败false void compare(char *input, char *output); //将原文件与压缩后的文件比较 void compare2(char *input, char *output); //将原文件与恢复后的文件比较 private:

int root; //记录根结点的位置

int leafnum; //记录不同字符的个数

HTnode HT[leaf*2-1]; //HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1

char byte; //压缩文件时用来缓冲bit的变量 int bitsnum; //byte中bit的个数

int lacknum; //压缩到最后byte中的bit不满8个时填充的0的个数 };

3、 主程序的流程及模块间关系

主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句进行分支执行huffmanTree类中功能函数：

1:压缩函数 bool compress(char *input, char *output) 2:恢复函数 bool decompress(char *input, char *output)

3:恢复文件与原文件的对比函数 void compare2(char *input, char *output) 并可在完成相应功能后安全退出，压缩或恢复的文件在同文件夹下生成。

三、 详细设计和编码

核心算法----huffman算法：

（1） 根据给定的n个权值｛w1,w2,……,wn｝构成n棵二叉树的集合F=｛T1,T2,……,Tn｝,

其中每棵二叉树T1中只有一个带权的 w1的根据点，其左右子树均空。 （2） 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉

树，且置新的二叉树的根结点的权值为其左右树上根结点的权值之和。

（3） 在F中删除这两棵树，同时将所得到的二叉树加入F中。

（4） 重复（2）(3),直到F中只含一棵树为止。这棵树便是Huffman树。Huffman

树可用于构造代码总长度最短的编码方案。

为了详细说明这个问题，特以下面例子来说明：有四个叶子结点A,B,C,D,分别带权为9,4,5,2，可以构成许多种不同的带权二叉树，但各个带权二叉树的WPL（树的带权路径长度）不同，要想由n个带权叶子结点所构成的二叉树中，满二叉树或完全二叉树不一定是最优树。权值越大的结点离根越近的二叉树才是最优二叉树（huffman树）。按照上面的算法，则可按照下面图的构造过程生成huffman树。

Huffman树产生流程:

图1 Huffman树产生流程

主程序模块:

主函数 菜 单

huffmanTree类 压缩函数 compress 对比函数 compare2 恢复函数 decompress 图2 程序模块