精华内容
下载资源
问答
  • 基于哈夫曼编码的文本文件压缩与解压缩,使用c语言,实际只是编码解码,不应该称为解压缩,因为编码后文件会更大
  • 哈夫曼编码实现文件压缩 二、实验目的 了解文件概念 掌握线性链表插入、删除等算法 掌握Huffman树概念及构造方法 掌握二叉树存储结构及遍历算法 利用Huffman树及Huffman编码,掌握实现文件...

    一、实验题目

    用哈夫曼编码实现文件压缩

    二、实验目的

    了解文件的概念

    掌握线性链表的插入、删除等算法

    掌握Huffman树的概念及构造方法

    掌握二叉树的存储结构及遍历算法

    利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理

    三、实验设备与环境

    微型计算机

    Windows 系列操作系统

    Visual C++6.0软件

    四、实验内容

    根据ascii码文件中各ascii字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩。

    五、概要设计

    5.1 构造Hufffman树的方法—Hufffman算法

    构造Huffman树步骤:

    根据给定的n个权值{w1,w2,……wn},构造n棵只有根结点的二叉树,令起权值为wj

    在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和

    在森林中删除这两棵树,同时将新得到的二叉树加入森林中

    重复上述两步,直到只含一棵树为止,这棵树即哈夫曼树

    点击此处下载源码

    转载于:https://my.oschina.net/u/4185264/blog/3087696

    展开全文
  • 根据ASCII码文件中各ASCII字符出现频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩
  • 哈夫曼编码实现文件压缩 二、实验目的 了解文件概念 掌握线性链表插入、删除等算法 掌握Huffman树概念及构造方法 掌握二叉树存储结构及遍历算法 利用Huffman树及Huffman编码,...

    一、实验题目

    用哈夫曼编码实现文件压缩

    二、实验目的

    • 了解文件的概念

    • 掌握线性链表的插入、删除等算法

    • 掌握Huffman树的概念及构造方法

    • 掌握二叉树的存储结构及遍历算法

    • 利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理

    三、实验设备与环境

    微型计算机、Windows 系列操作系统 、Visual C++6.0软件

    四、实验内容

    根据ASCII码文件中各ASCII字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩。

    五、概要设计

    5.1 数据结构类型定义

    点击此处下载文档和源码

    展开全文
  • 基于哈夫曼编码实现文件压缩 是在学习数据结构(严蔚敏版)书中哈夫曼树及其应用后对书中伪代码的实现和完善,采用哈夫曼静态编码的方式,通过对数据进行两遍扫描,第一次统计出现的字符频次,进而构造哈夫曼树,第...
        

    基于哈夫曼编码实现文件压缩

    是在学习数据结构(严蔚敏版)书中哈夫曼树及其应用后对书中伪代码的实现和完善,采用哈夫曼静态编码的方式,通过对数据进行两遍扫描,第一次统计出现的字符频次,进而构造哈夫曼树,第二遍扫描数据根据得到的哈夫曼树对数据进行编码。

    对于其中的加密编码只是简单的将用户输入的密码用特殊的标识位拼接成字符串加入需要统计的数据,可以在拥有哈夫曼编码表以及加密后的文本情况下进行解密

    哈夫曼树

    给定n个权值作为n个叶子结点,构造一棵二叉树,若带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。

    哈夫曼树的构造过程

    假设有n个权值,则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn,则哈夫曼树的构造规则为: (1)
    将w1、w2、…,wn看成是有n 棵树的森林(每棵树仅有一个结点); (2)
    在森林中选出两个根结点的权值最小的树合并,作为一棵新树的左、右子树,且新树的根结点权值为其左、右子树根结点权值之和;
    (3)从森林中删除选取的两棵树,并将新树加入森林; (4)重复(2)、(3)步,直到森林中只剩一棵树为止,该树即为所求得的哈夫曼树

    在构造哈夫曼树时首先选择权小的,这样保证权大的离根较近,这种生成算法是一种典型的贪心法

    哈夫曼编码思想

    为了使压缩后的数据文件尽可能短,可采用不定长编码。而为了在对压缩文件进行解码时不产生二义性,确保正确解码应该采用前缀编码的形式(即要求一个字符的编码不能是另一个字符编码的前缀)。而哈夫曼编码是最优前缀编码。

    例如:有一个数据序列ABACCDAA则编码为A(0),B(10),C(110),(D111),压缩后为010011011011100。

    部分实现代码

    //哈夫曼树存储表示 
    typedef struct {
        int  weight;  //节点的权值 
        int parent,lchild,rchild;  //节点的双亲,左孩子,右孩子的下标 
    } HTNode,*HuffmanTree;
     
    //存储数据扫瞄统计结果 
    typedef struct {
        char* data;
        int* num;
        int length;
    } TNode;
    //存储文件读入哈夫曼编码结果 
    typedef struct {
        char *data;
        char** HM;
    } Code;
    
    //存储哈夫曼编码结果
    typedef char** HuffmanCode;
    //选取节点构造哈夫曼树 
    void Select(HuffmanTree &HT,int m,int& s1,int& s2) {
        int k,j,n,min=32767;
        for(k=1; k<=m; k++) {
            if(HT[k].parent==0)
                if(HT[k].weight<=min) {
                    j=k;
                    min=HT[k].weight;
                }
        }
        s1=j;
        HT[j].parent=1;
        min=32767;
        for(k=1; k<=m; k++) {
            if(HT[k].parent==0)
                if(HT[k].weight<=min) {
                    n=k;
                    min=HT[k].weight;
                }
        }
        s2=n;
    }
    //构造哈夫曼树 
    void CreateHuffmanTree (HuffmanTree &HT,TNode T,int length) {
        int m,i,s1,s2;
        //初始化 
        if(length<=1)
            return;
        m=2*length-1;
        HT=new HTNode[m+1];
        for(i=1; i<=m; ++i) {
            HT[i].parent=0;
            HT[i].lchild=0;
            HT[i].rchild=0;
        }
        for(i=1; i<=length; ++i)
            HT[i].weight=T.num[i-1];
        //通过n-1次的选择,删除,合并来创建哈夫曼树 
        for(i=length+1; i<=m; i++) {
            Select(HT,i-1,s1,s2);
            HT[s1].parent=i;
            HT[s2].parent=i;
            HT[i].lchild=s1;
            HT[i].rchild=s2;
            HT[i].weight=HT[s1].weight+HT[s2].weight;
        }
    }
    //从叶子到根逆向求每个字符的哈夫曼编码,存储在编码表HC中 
    void CreatHuffmanCode (HuffmanTree HT,HuffmanCode &HC,int n) {
        int i,f,c,start;
        HC=new char*[n+1];
        char* cd=new char[n];
        cd[n-1]='\0';
        for(i=1; i<=n; i++) {
            start=n-1;
            c=i;
            f=HT[i].parent;
            while(f!=0) {
                --start;
                if(HT[f].lchild==c)
                    cd[start]='0';
                else
                    cd[start]='1';
                c=f;
                f=HT[f].parent;
            }
            HC[i]=new char[n-start];
            strcpy(HC[i],&cd[start]);
        }
        delete cd;
    }

    有兴趣可以下载源码查看https://pan.baidu.com/s/1skAP5lr


    参考 数据结构:C语言版/严蔚敏,李冬梅,吴伟民编

    展开全文
  • 名称:基于哈夫曼编码的文件压缩解压 目的:利用哈夫曼编码压缩存储文件,节省空间 输入:任何格式的文件(压缩)或压缩文件(解压) 输出:压缩文件或解压后的原文件 功能:利用哈夫曼编码...

    一、问题描述

    • 名称:基于哈夫曼编码的文件压缩解压

    • 目的:利用哈夫曼编码压缩存储文件,节省空间

    • 输入:任何格式的文件(压缩)或压缩文件(解压)

    • 输出:压缩文件或解压后的原文件

    • 功能:利用哈夫曼编码压缩解压文件

    • 性能:快速

    二、问题的初步讨论

    为了建立哈夫曼树,首先扫描源文件,统计每类字符出现的频度(出现的次数),然后根据字符频度建立哈夫曼树,接着根据哈夫曼树生成哈夫曼编码。再次扫描文件,每次读取8bits,根据“字符—编码”表,匹配编码,并将编码存入压缩文件,同时存入编码表。解压时,读取编码表,然后读取编码匹配编码表找到对应字符,存入文件,完成解压。

    点击此处下载文档和源码
     

     

     

    展开全文
  • 哈夫曼编码实现文件压缩 二、实验目的 了解文件概念 掌握线性链表插入、删除等算法 掌握Huffman树概念及构造方法 掌握二叉树存储结构及遍历算法 利用Huffman树及Huffman编码,掌握实现文件压缩的...
  • 本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的...
  • 名称:基于哈夫曼编码的文件压缩解压 目的:利用哈夫曼编码压缩存储文件,节省空间 输入:任何格式的文件(压缩)或压缩文件(解压) 输出:压缩文件或解压后的原文件 功能:利用哈夫曼编码压缩解压文件 性能...
  • 文件压缩与解压缩哈夫曼编码

    千次阅读 2017-09-07 15:41:51
    本文采用哈夫曼编码的方式进行文件(文本文件)压缩和解压缩,首先介绍项目的整体思路:哈夫曼编码压缩文件实际就是统计出文件中各个字符出现的频率,然后为每个字符生成对应的编码,然后将每个字符用哈夫曼编码的...
  • 实验目的 了解文件概念 掌握线性链表插入、删除等算法 掌握Huffman树概念及构造方法 掌握二叉树存储结构及遍历算法 利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理 ...

空空如也

空空如也

1 2 3 4 5
收藏数 91
精华内容 36
关键字:

哈夫曼编码的压缩与解压缩