《数据结构》课程设计
数学与应用数学一班    胡耕岩    2012214147
一、问题分析和任务定义
1.1设计任务
采用哈夫曼编码思想实现文件的压缩和恢复功能，并提供压缩前后的占用空间之比。要求
（1）运行时的压缩原文件的规模应不小于5K。
（2）提供恢复文件与原文件的相同性对比功能。
1.2问题分析
本课题是利用哈夫曼编码思想，设计对一个文本文件（.txt）中的字符进行哈夫曼编码，生成编码压缩文件，并且还可将一个压缩后的文件进行解码还原为原始文本文件（.txt）。
在了解哈夫曼压缩解压缩原理之前，首先让我们来认识哈夫曼树。哈夫曼树又称最优二叉树，
是带权路径长度最小的二叉树。
在文本文件中多采用二进制编码。为了使文件尽可能的缩短，可以对文件中每个字符出现的次数进行统计。设法让出现次数多的字符二进制码短些，而让那些很少出现的字符二进制码长一些。若对字符集进行不等长编码，则要求字符集中任一字符的编码都不是其它字符编码的前缀。为了确保哈夫曼编码的唯一性，我们可以对它的左右子树的大小给予比较限定，如：左子树的权值小于右子树的权值。哈夫曼树中的左右分支各代表‘0’和‘1’,则从根节点到叶子节点所经历的路径分支的‘0’和‘1’组成的字符串，为该节点对应字符的哈夫曼编码。
统计字符中每个字符在文件中出现的平均概率（概率越大，要求编码越短）。利用哈夫曼树的特点：权越大的叶子离根越近，将每个字符的概率值作为权值，构造哈夫曼树。则概率越大的节点，路径越短。哈夫曼译码是从二进制序列的头部开始，顺序匹配成共的部分替换成相应的字符，直至二进制转换为字符序列。
哈夫曼用于文件解压缩的基础是在压缩二进制代码的同时还必须存储相应的编码，这样就可以根据存储的哈夫曼编码对压缩代码进行压缩。总之，该课题的任务应该是首先要打开要压缩的文本文件并读出其字符出现的频率，以其为权值构建哈夫曼树。其次要到构建压缩功字符串长度压缩
能的方法，在构建哈夫曼树的基础上进行编码，改变字符原先的存储结构，以达到压缩文件的目的，以外还有存储相应的哈夫曼编码，为解压缩做准备。
1.3测试用数据
本实验的数据是通过读入一个名为的文本文档，文档中内容为字符型数据。
二、概要设计和数据结构的选择
以下是在任务分析对题意的理解做出的概要设计和对数据结构的选择：
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树可用于构造代码总长度最短的编码方案。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。