精华内容
下载资源
问答
  • 哈夫曼树编码

    2017-11-02 19:44:00
    哈夫曼树编码 对输入的英文大写字母进行统计概率 然后构建哈夫曼树,输出是按照概率降序排序输出Huffman编码输入 大写字母个数 n 第一个字母 第二个字母 第三个字母 ... 第n个字母 输出字母1 ...

    哈夫曼树编码

     


    对输入的英文大写字母进行统计概率 然后构建哈夫曼树,输出是按照概率降序排序输出Huffman编码
    输入
      大写字母个数 n 第一个字母 第二个字母 第三个字母 ... 第n个字母
     
    输出
     字母1 出现次数 Huffman编码 
     字母2 出现次数 Huffman编码 
     字母3 出现次数 Huffman编码 
     … 
     字母n 出现次数 Huffman编码

    Sample In
    10
    I I U U U I U N U U
     
    Sample Out
    U 6 1
    I 3 01
    N 1 00

    解决此题首先要明白HuffmanTree的构造原理

    首先来看一个简单的例子:
    把某个班同学百分制的成绩转换成5分制,规则如下,
     
    90~100     5
    80~90       4
    70~80       3
    60~70       2
    <60           1
     
    看起来很容易实现
    即 if (score<60)
         grade=1;
         else if(score<70)
         grade=2;
         else if(score<80)
         grade=3;
         else if(score<90)
         grade=4;
         else
         grade=5;
    但是如果这个班的同学大多数都取得了90分以上的好成绩,那么前面4步的判断是很没必要且费时的。
    很明显,这种算法在面对大量数据的时候是比较不合理的。
    那么如何优化算法呢?
    假定我们目前已经知道了这个班成绩的分布律
     

    成绩

    <60

    60~70

    70~80

    80~90

    90~100

    比例

    0.05

    0.15

    0.33

    0.27

    0.20

     
    如果用刚才的办法,则算法的效率是多少呢,用比例乘上判断的次数0.05*1+0.15*2+0.33*3+0.27*4+0.20*4=3.22
    我们稍微修改一下算法,先判断比例最大的,
    即   if(score<80)
        {
            if(score<70)
                if(score<60)
                grade=1;
            else
                grade=2;
            else
                grade=3;
        }
        else if(score<90)
            grade=4;
        else
            grade=5;
          
    改良后的算法效率为0.05*3+0.15*3+0.33*2+0.27*2+0.2*2=2.2
    很明显,改良后的算法效率增加了很多。
    由树的定义可以把刚才的程序抽象成下图所示的"树":
     
     
    那么如何构造一个效率更好或者最好的搜索树呢,这就是哈夫曼树要解决的问题。
    构造HuffmanTree思想:把权值(频率)从小到大排序,把权值最小的两颗二叉树合并
    比如现有权值为1,2,3,4,5的节点(已经排好序)。
    1.选择最小的两个,即1和2,合并,权值之和为3,
    2.从刚才合并好的3和剩下的3,4,5里选择两个最小的,即3和3,合并,权值之和为6
    3.从6,4,5里选择两个最小的,即4和5,合并,权值之和为9
    4.将6和9合并,权值之和为15
    下图为形成的哈夫曼树:
     
    对于上面的问题,我们的思路之一应该是这样
    1.统计相同字符出现的次数并记录之
    2.根据统计好的结果构造哈夫曼树
    3.获得哈夫曼编码
    4.按题目要求格式打印
    那么写出代码就是轻而易举的事情了:
    #include <iostream>
    #include <cstring>
    #include <cstdio>
    using namespace std;
    
    
    template<class T>
    struct StaFrequency
    {
        T data;
        int times;
        StaFrequency();
        StaFrequency(T data,int times) {this->data=data;this->times=times;}
    };
    template<class T>
    struct TriNode
    {
        T data;
        int parent,left,right;
    };
    template<class T>
    class HuffmanTree
    {
    private:
        int leafNum;
        TriNode<int> *huftree;
        char **hufcodes;
        void createHuffmanTree(T weight[],int n);
        void getHuffmanCode();
    public:
        HuffmanTree(T weight[],int n);
        ~HuffmanTree() {delete []huftree;delete []hufcodes;};
        void print(int i);
    };
    const int Max_Weight=9999;
    template <class T>
    HuffmanTree<T>::HuffmanTree(T weight[],int n)
    {
        createHuffmanTree(weight,n);
        getHuffmanCode();
    }
    //构造哈夫曼树
    template <class T>
    void HuffmanTree<T>::createHuffmanTree(T weight[],int n)
    {
        leafNum=n;
        huftree=new TriNode<int>[2*n-1];
        int i;
        for(i=0;i<n;i++)
        {
            huftree[i].data=weight[i];
            huftree[i].parent=huftree[i].left=huftree[i].right=-1;
        }
        for(i=0;i<n-1;i++)
        {
            int min1,min2,x1,x2;
            min1=min2=Max_Weight;
            x1=x2=-1;
            for(int j=0;j<n+i;j++)
            {
                if(huftree[j].data<min1&&huftree[j].parent==-1)
                {
                    min2=min1;
                    x2=x1;
                    min1=huftree[j].data;
                    x1=j;
                }
                else if(huftree[j].data<min2&&huftree[j].parent==-1)
                {
                    min2=huftree[j].data;
                    x2=j;
                }
            }
            huftree[x1].parent=n+i;
            huftree[x2].parent=n+i;
            huftree[n+i].data=huftree[x1].data+huftree[x2].data;
            huftree[n+i].parent=-1;
            huftree[n+i].left=x1;
            huftree[n+i].right=x2;
        }
    }
    //获得哈夫曼编码
    template <class T>
    void HuffmanTree<T>::getHuffmanCode()
    {
        int n=leafNum;
        hufcodes=new char *[n];
        for(int i=0;i<n;i++)
        {
            char * code=new char[n];
            code[n-1]='\0';
            int start=n-1;
            int child=i;
            int parent=huftree[child].parent;
            while(parent!=-1)
            {
                start--;
                if(huftree[parent].left==child)
                    code[start]='0';
                else
                    code[start]='1';
                child=parent;
                parent=huftree[child].parent;
            }
            hufcodes[i]=code+start;
        }
    }
    //打印哈夫曼编码
    template <class T>
    void HuffmanTree<T>::print(int i)
    {
        cout<<hufcodes[i]<<endl;
    }
    int main()
    {
        int m;
        cin>>m;
        char weight[m];
        for(int i=0;i<m;i++)
            cin>>weight[i];
    int i=0,n=0,sum=0,num=0,x=0;
    int s[m];
    char w[m];
    bool flag;
    for(i=0;i<m;i++)
    {
       flag=true;
       sum=0;
       for(int j=i-1;j>=0;j--)//检测是否有已经算过的字母
       {
          if(weight[j]==weight[i])
          {
          flag=false;
          break;
      }
    }
    for(n=i;n<m&&flag;n++)//若上一步没有,则算相同的个数
    {
    if(weight[i]==weight[n])
    {
    sum++;
    }
    }
    if(flag) //存储相同字符及个数
       {
      s[num++]=sum;
      w[x++]=weight[i];
    }
    }
        //就写个最简单的冒泡排序吧
        for(int k=0;k<num;k++)
        {
            for(int j=0; j<num-1-k; j++)
            {
                if(s[j]<s[j+1])
                {
                    swap(s[j],s[j+1]);
                    swap(w[j],w[j+1]);
                }
    
    
            }
        }
        HuffmanTree<int> htree(s,num);
        for(int i=0;i<num;i++)
        {
            cout<<w[i]<<" "<<s[i]<<" ";
            htree.print(i);
        }
        return 0;
    }

     

    posted @ 2017-11-02 19:44 Nikki_o3o 阅读(...) 评论(...) 编辑 收藏
    展开全文
  • Java哈夫曼编码实验--哈夫曼树的建立,编码与解码建树,造树,编码,解码一、哈夫曼树编码介绍1、哈夫曼树:(1)定义:假设有n个权值{w1, w2, ..., wn},试构造一棵含有n个叶子结点的二叉树,每个叶子节点带权威wi,...

    Java哈夫曼编码实验--哈夫曼树的建立,编码与解码

    建树,造树,编码,解码

    一、哈夫曼树编码介绍

    1、哈夫曼树:

    (1)定义:假设有n个权值{w1, w2, ..., wn},试构造一棵含有n个叶子结点的二叉树,每个叶子节点带权威wi,则其中带权路径长度WPL最小的二叉树叫做最优二叉树或者哈夫曼树。

    (2)特点:哈夫曼树中没有度为1的结点,故由n0 = n2+1以及m= n0+n1+n2,n1=0可推出m=2*n0-1,即一棵有n个叶子节点的哈夫曼树共有2n-1个节点。

    2、哈夫曼编码步骤:

    (1)计算字符出现的次数:

    假设我们现在有一段文档需要进行编码,我们现在需要对于每一个字符出现的次数进行统计,然后分别计算出其在这篇文档的权重,也就是频率,我们用下面的一段文字进行举例;

    在如下的文档中包括的字符有8个字母和2个空格,所以我们现在需要去统计这10个字符的个数,统计后的数据如下:

    (2)对字符出现的次数作为一个权重,从小到大进行排序;

    排序结果:0.1,0.1,0.1,0.1,0.1,0.1,0.2,0.2

    (3)依照排序结果从小到大根据以下规则进行造树:

    a、最小的前两个数进行权重的相加,形成他们两个作为左子树和右子树的父结点,如果是左结点就标记为0,如果是右结点就标记为1

    b、然后将父结点作为一个新的结点进入排序结果,之后进行重新排序(ps:假如出现添加后的父结点的权重和之前排序中的结点的权重相等的情况,两者的位置具体是对于建树没有影响的,但是在编程实现的过程中,程序需要将两者的位置进行确定)

    c、重复上述过程,直到得到的父结点的权重为1。

    d、具体流程如下:

    i like you //文档

    字符

    频率

    i

    0.2

    l

    0.1

    k

    0.1

    e

    0.1

    y

    0.1

    o

    0.1

    u

    0.1

    空格

    0.2

    205f3d46d688d6550409bb75181a8998.png

    从根向下一次读取0或者1,进行编码,编码结果如下表

    字符

    编码

    i

    111

    l

    010

    k

    011

    e

    000

    y

    001

    o

    100

    u

    101

    空格

    110

    二、编程实现过程

    1、首先我准备了一段英文文档,包括26个字母和一个空格字符

    for many young people they dont have the habit to save money because they think they are young and should enjoy the life quickly so there is no need to save money but saving part of the income can better help us to deal with emergent situations though it is hard to store income index zero we still can figure out some ways

    2、然后先进行文件的读取和进行字符出现的次数统计

    //读取文档中的英文文档

    String[] a = new String[800];

    try (FileReader reader = new FileReader("英文文档");

    BufferedReader br = new BufferedReader(reader)

    ) {

    int b =0;

    for (int i =0;i<800;i++){

    a[b]=br.readLine();

    b++;

    }

    } catch (IOException e) {

    e.printStackTrace();

    }

    String[] b = a[0].split("");

    // System.out.println(Arrays.toString(b));

    //开始构造哈夫曼树

    Objects Za= new Objects("a",an);

    Objects Zb = new Objects("b",bn);

    Objects Zc = new Objects("c",cn);

    Objects Zd = new Objects("d",dn);

    Objects Ze = new Objects("e",en);

    Objects Zf = new Objects("f",fn);

    Objects Zg = new Objects("g",gn);

    Objects Zh = new Objects("h",hn);

    Objects Zi = new Objects("i",in);

    Objects Zj = new Objects("j",jn);

    Objects Zk = new Objects("k",kn);

    Objects Zl = new Objects("l",ln);

    Objects Zm = new Objects("m",mn);

    Objects Zn = new Objects("n",nn);

    Objects Zo = new Objects("o",on);

    Objects Zp = new Objects("p",pn);

    Objects Zq = new Objects("q",qn);

    Objects Zr = new Objects("r",rn);

    Objects Zs = new Objects("s",sn);

    Objects Zt = new Objects("t",tn);

    Objects Zu = new Objects("u",un);

    Objects Zv = new Objects("v",vn);

    Objects Zw = new Objects("w",wn);

    Objects Zx = new Objects("x",xn);

    Objects Zy = new Objects("y",yn);

    Objects Zz = new Objects("z",zn);

    Objects Zkongge = new Objects(" ",zkongge);

    System.out.println("各个字符的概率统计为:");

    Objects[] temp = new Objects[]{Za,Zb,Zc,Zd,Ze,Zf,Zg,Zh,Zi,Zj,Zk,Zl,Zm,Zn,Zo,Zp,Zq,Zr,Zs,Zt,Zu,Zv,Zw,Zx,Zy,Zz,Zkongge};

    for (int i =0;i

    System.out.println(temp[i].getName()+"的概率为"+temp[i].getWeight()/323);

    }

    3、因为我用了一个Objects保存了一个元素的名字,权重,编码,还有他的左孩子,右孩子。

    package 哈夫曼树编码实验;

    public class Objects implements Comparable {

    private String name;

    private double weight;

    private String date;

    private Objects left;

    private Objects right;

    public Objects(String Name , double Weight){

    name=Name;

    weight=Weight;

    date="";

    }

    public String getName() {

    return name;

    }

    public double getWeight() {

    return weight;

    }

    public Objects getLeft() {

    return left;

    }

    public Objects getRight() {

    return right;

    }

    public void setLeft(Objects left) {

    this.left = left;

    }

    public void setRight(Objects right) {

    this.right = right;

    }

    public void setName(String name) {

    this.name = name;

    }

    public void setWeight(double weight) {

    this.weight = weight;

    }

    @Override

    public String toString() {

    return "Objects{" + "name='" + name + '\'' + ", weight=" + weight + ", 编码为='" + date + '\'' + '}'+"\n";

    }

    @Override

    public int compareTo(Objects o) {

    if (weight>=o.weight){

    return 1;

    }

    else {

    return -1; //规定发现权重相等向后放;

    }

    }

    public void setDate(String date) {

    this.date = date;

    }

    public String getDate() {

    return date;

    }

    }

    4、进行哈夫曼树的建立

    List tempp = new ArrayList();

    for (int i =0;i

    tempp.add(temp[i]);

    }

    Collections.sort(tempp); //将我们的Objects类中的每一个字符放进链表进行排序

    while (tempp.size() > 1) { //直到我们链表只剩下一个元素,也就是我们的根结点的时候跳出循环

    Collections.sort(tempp); //排序

    Objects left = (Objects) tempp.get(0); //得到第一个元素,作为左孩子

    left.setDate( "0"); //初始化左孩子的编码为0

    Objects right = (Objects) tempp.get(1); //得到第二个元素,作为右孩子

    right.setDate( "1"); //初始化有孩子的编码为1

    Objects parent = new Objects(left.getName()+right.getName(), left.getWeight() + right.getWeight()); //构造父结点

    parent.setLeft(left); //设置左结点

    parent.setRight(right); //设置右结点

    tempp.remove(left); //删除左结点

    tempp.remove(right); //删除右结点

    tempp.add(parent); //将父结点添加进入链表

    }

    5、开始进行编码

    //开始进行哈夫曼编码

    Objects root = (Objects) tempp.get(0); //我们通过一个root保存为根结点

    System.out.println( ); //我们利用先序遍历,遍历到每一个结点,因为这样可以保证都从根结点开始遍历

    List list = new ArrayList();

    Queue queue = new ArrayDeque();

    queue.offer(root);

    while (!queue.isEmpty()){

    list.add(queue.peek());

    Objects temp1 = (Objects) queue.poll();

    if(temp1.getLeft() != null)

    {

    queue.offer(temp1.getLeft());

    temp1.getLeft().setDate(temp1.getDate()+"0"); //判断假如为左结点,就基于结点本身的编码加上0

    }

    if(temp1.getLeft() != null)

    {

    queue.offer(temp1.getRight());

    temp1.getRight().setDate(temp1.getDate()+"1"); //判断假如为右结点,就基于结点本身的编码加上1

    }

    }

    6、开始对于文档进行加密并且保存进文档

    //进行加密

    String result = ""; //定义了一个字符串,用来保存加密后的文档

    for (int i =0 ;i

    for (int j=0;j

    if (b[i].equals(temp[j].getName())){

    result+=temp[j].getDate(); //因为现在我们之前保存Objects的数组中的每一个字符已经有各自的编码,所以我们用我们之前保存文档的数组b进行对于,假如找到相对应的,就将编码赋给result,进行累加,重复过程

    break;

    }

    }

    }

    System.out.println("加密后");

    System.out.println(result);

    File file = new File("加密后文档");

    FileWriter fileWritter = null;

    try {

    fileWritter = new FileWriter(file.getName(),true);

    } catch (IOException e) {

    e.printStackTrace();

    }

    try {

    fileWritter.write(result);

    } catch (IOException e) {

    e.printStackTrace();

    }

    try {

    fileWritter.close();

    } catch (IOException e) {

    e.printStackTrace();

    }

    7、进行解密

    //解密,读取需要解密的文档

    try (FileReader reader = new FileReader("加密后文档");

    BufferedReader br = new BufferedReader(reader)

    ) {

    int e =0;

    for (int i =0;i<800;i++){

    a[e]=br.readLine();

    e++;

    }

    } catch (IOException e) {

    e.printStackTrace();

    }

    String duqu=a[0];

    String jiemi=""; //保存解密后的文档

    String temp2=""; // 作为一个临时的字符串,一个一个进行获取密文,当进行匹配成功了以后,变为空,如下

    for (int i =0;i

    temp2+=duqu.charAt(i);

    for (int j = 0;j

    if (temp2.equals(temp[j].getDate())){ //进行获取,然后获取成功以后将其赋给jiemi,然后清空temp2;

    jiemi+=temp[j].getName();

    temp2="";

    }

    }

    }

    System.out.println("解密后");

    System.out.println(jiemi);

    //将解密后的文本写入文件

    File file1 = new File("解密后文档");

    FileWriter fileWritter1 = null;

    try {

    fileWritter1 = new FileWriter(file1.getName(),true);

    } catch (IOException e) {

    e.printStackTrace();

    }

    try {

    fileWritter1.write(jiemi);

    } catch (IOException e) {

    e.printStackTrace();

    }

    try {

    fileWritter1.close();

    } catch (IOException e) {

    e.printStackTrace();

    }

    8、成功完成加密解密,结果如下:

    028303562d66e93df89b8a7cddc2db68.png

    参考资料

    展开全文
  • 哈夫曼树
  • 哈夫曼树及哈夫曼树编码

    千次阅读 2015-09-09 15:50:57
    本文转自哈夫曼树及哈夫曼树编码 在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN) 树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用...

    本文转自哈夫曼树及哈夫曼树编码

    在一般的数据结构的书中,树的那章后面,著者一般都会介绍一下哈夫曼(HUFFMAN)

    树和哈夫曼编码。哈夫曼编码是哈夫曼树的一个应用。哈夫曼编码应用广泛,如

    JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树。哈夫曼树又称最优二叉树,

    是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点

    的权值乘上其到根结点的 路径长度(若根结点为0层,叶结点到根结点的路径长度

    为叶结点的层数)。树的带权路径长度记为WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)

    ,N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径

    长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。

    哈夫曼编码步骤:

    一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。(为方便在计算机上实现算 法,一般还要求以Ti的权值Wi的升序排列。)
    二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
    三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
    四、重复二和三两步,直到集合F中只有一棵二叉树为止。

    简易的理解就是,假如我有A,B,C,D,E五个字符,出现的频率(即权值)分别为5,4,3,2,1,那么我们第一步先取两个最小权值作为左右子树构造一个新树,即取1,2构成新树,其结点为1+2=3,如图:

    12

    虚线为新生成的结点,第二步再把新生成的权值为3的结点放到剩下的集合中,所以集合变成{5,4,3,3},再根据第二步,取最小的两个权值构成新树,如图:

    13

    再依次建立哈夫曼树,如下图:

    14

    其中各个权值替换对应的字符即为下图:

    15

    所以各字符对应的编码为:A->11,B->10,C->00,D->011,E->010

    霍夫曼编码是一种无前缀编码。解码时不会混淆。其主要应用在数据压缩,加密解密等场合。

     

    C语言代码实现:

    /*-------------------------------------------------------------------------
     * Name:   哈夫曼编码源代码。
     * Date:   2011.04.16
     * Author: Jeffrey Hill+Jezze(解码部分)
     * 在 Win-TC 下测试通过
     * 实现过程:着先通过 HuffmanTree() 函数构造哈夫曼树,然后在主函数 main()中
     *           自底向上开始(也就是从数组序号为零的结点开始)向上层层判断,若在
     *           父结点左侧,则置码为 0,若在右侧,则置码为 1。最后输出生成的编码。
     *------------------------------------------------------------------------*/
    #include <stdio.h>
    #include<stdlib.h>
     
    #define MAXBIT      100
    #define MAXVALUE  10000
    #define MAXLEAF     30
    #define MAXNODE    MAXLEAF*2 -1
     
    typedef struct 
    {
        int bit[MAXBIT];
        int start;
    } HCodeType;        /* 编码结构体 */
    typedef struct
    {
        int weight;
        int parent;
        int lchild;
        int rchild;
        int value;
    } HNodeType;        /* 结点结构体 */
     
    /* 构造一颗哈夫曼树 */
    void HuffmanTree (HNodeType HuffNode[MAXNODE],  int n)
    { 
        /* i、j: 循环变量,m1、m2:构造哈夫曼树不同过程中两个最小权值结点的权值,
            x1、x2:构造哈夫曼树不同过程中两个最小权值结点在数组中的序号。*/
        int i, j, m1, m2, x1, x2;
        /* 初始化存放哈夫曼树数组 HuffNode[] 中的结点 */
        for (i=0; i<2*n-1; i++)
        {
            HuffNode[i].weight = 0;//权值 
            HuffNode[i].parent =-1;
            HuffNode[i].lchild =-1;
            HuffNode[i].rchild =-1;
            HuffNode[i].value=i; //实际值,可根据情况替换为字母  
        } /* end for */
     
        /* 输入 n 个叶子结点的权值 */
        for (i=0; i<n; i++)
        {
            printf ("Please input weight of leaf node %d: \n", i);
            scanf ("%d", &HuffNode[i].weight);
        } /* end for */
     
        /* 循环构造 Huffman 树 */
        for (i=0; i<n-1; i++)
        {
            m1=m2=MAXVALUE;     /* m1、m2中存放两个无父结点且结点权值最小的两个结点 */
            x1=x2=0;
            /* 找出所有结点中权值最小、无父结点的两个结点,并合并之为一颗二叉树 */
            for (j=0; j<n+i; j++)
            {
                if (HuffNode[j].weight < m1 && HuffNode[j].parent==-1)
                {
                    m2=m1; 
                    x2=x1; 
                    m1=HuffNode[j].weight;
                    x1=j;
                }
                else if (HuffNode[j].weight < m2 && HuffNode[j].parent==-1)
                {
                    m2=HuffNode[j].weight;
                    x2=j;
                }
            } /* end for */
                /* 设置找到的两个子结点 x1、x2 的父结点信息 */
            HuffNode[x1].parent  = n+i;
            HuffNode[x2].parent  = n+i;
            HuffNode[n+i].weight = HuffNode[x1].weight + HuffNode[x2].weight;
            HuffNode[n+i].lchild = x1;
            HuffNode[n+i].rchild = x2;
     
            printf ("x1.weight and x2.weight in round %d: %d, %d\n", i+1, HuffNode[x1].weight, HuffNode[x2].weight);  /* 用于测试 */
            printf ("\n");
        } /* end for */
      /*  for(i=0;i<n+2;i++)
        {
            printf(" Parents:%d,lchild:%d,rchild:%d,value:%d,weight:%d\n",HuffNode[i].parent,HuffNode[i].lchild,HuffNode[i].rchild,HuffNode[i].value,HuffNode[i].weight);
                      }*///测试 
    } /* end HuffmanTree */
     
    //解码 
    void decodeing(char string[],HNodeType Buf[],int Num)
    {
      int i,tmp=0,code[1024];
      int m=2*Num-1;
      char *nump;
      char num[1024];
      for(i=0;i<strlen(string);i++)
      {
       if(string[i]=='0')
      num[i]=0;        
      else
      num[i]=1;                    
      } 
      i=0;
      nump=&num[0];
      
     while(nump<(&num[strlen(string)]))
     {tmp=m-1;
      while((Buf[tmp].lchild!=-1)&&(Buf[tmp].rchild!=-1))
      {
      
       if(*nump==0)
       {
         tmp=Buf[tmp].lchild ;          
       } 
       else tmp=Buf[tmp].rchild;
       nump++;
            
      } 
      
      printf("%d",Buf[tmp].value);                                  
     }
     
      
    }
     
     
    int main(void)
    {
        
        HNodeType HuffNode[MAXNODE];            /* 定义一个结点结构体数组 */
        HCodeType HuffCode[MAXLEAF],  cd;       /* 定义一个编码结构体数组, 同时定义一个临时变量来存放求解编码时的信息 */
        int i, j, c, p, n;
        char pp[100];
        printf ("Please input n:\n");
        scanf ("%d", &n);
        HuffmanTree (HuffNode, n);
       
        
        for (i=0; i < n; i++)
        {
            cd.start = n-1;
            c = i;
            p = HuffNode[c].parent;
            while (p != -1)   /* 父结点存在 */
            {
                if (HuffNode[p].lchild == c)
                    cd.bit[cd.start] = 0;
                else
                    cd.bit[cd.start] = 1;
                cd.start--;        /* 求编码的低一位 */
                c=p;                    
                p=HuffNode[c].parent;    /* 设置下一循环条件 */
            } /* end while */
            
            /* 保存求出的每个叶结点的哈夫曼编码和编码的起始位 */
            for (j=cd.start+1; j<n; j++)
            { HuffCode[i].bit[j] = cd.bit[j];}
            HuffCode[i].start = cd.start;
        } /* end for */
        
        /* 输出已保存好的所有存在编码的哈夫曼编码 */
        for (i=0; i<n; i++)
        {
            printf ("%d 's Huffman code is: ", i);
            for (j=HuffCode[i].start+1; j < n; j++)
            {
                printf ("%d", HuffCode[i].bit[j]);
            }
            printf(" start:%d",HuffCode[i].start);
           
            printf ("\n");
            
        }
    /*    for(i=0;i<n;i++){
        for(j=0;j<n;j++)
            {
                 printf ("%d", HuffCode[i].bit[j]);           
            }
            printf("\n");
            }*/
        printf("Decoding?Please Enter code:\n");
        scanf("%s",&pp);
    decodeing(pp,HuffNode,n);
        getch();
        return 0;
    }

    展开全文
  • 哈夫曼树和哈夫曼树编码一、名词介绍二、哈夫曼树的基本概念三、构建哈夫曼树四、哈弗曼树中结点结构五、哈弗曼树中的查找算法六、构建哈弗曼树的代码实现七、哈夫曼编码八、完整代码(可运行)九、总结 一、名词...

    一、名词介绍

    (1)路径:在一棵树中,一个结点到另一个结点之间的通路,称为路径。图 1 中,从根结点到结点 a 之间的通路就是一条路径。

    (2)路径长度:在一条路径中,每经过一个结点,路径长度都要加 1 。例如在一棵树中,规定根结点所在层数为1层,那么从根结点到第 i 层结点的路径长度为 i - 1 。图 1 中从根结点到结点 c 的路径长度为 3。

    (3)结点的权:给每一个结点赋予一个新的数值,被称为这个结点的权。例如,图 1 中结点 a 的权为 7,结点 b 的权为 5。

    (4)结点的带权路径长度:指的是从根结点到该结点之间的路径长度与该结点的权的乘积。例如,图 1 中结点 b 的带权路径长度为 2 * 5 = 10 。

    树的带权路径长度为树中所有叶子结点的带权路径长度之和。通常记作 “WPL” 。例如图 1 中所示的这颗树的带权路径长度为:

    WPL = 7 * 1 + 5 * 2 + 2 * 3 + 4 * 3

    在这里插入图片描述

    二、哈夫曼树的基本概念

    当用 n 个结点(都做叶子结点且都有各自的权值)试图构建一棵树时,如果构建的这棵树的带权路径长度最小,称这棵树为“最优二叉树”,有时也叫“赫夫曼树”或者“哈夫曼树”

    在构建哈弗曼树时,要使树的带权路径长度最小,只需要遵循一个原则,那就是:权重越大的结点离树根越近。在图 1 中,因为结点 a 的权值最大,所以理应直接作为根结点的孩子结点。

    三、构建哈夫曼树

    对于给定的有各自权值的 n 个结点,构建哈夫曼树有一个行之有效的办法:
    (1)在 n 个权值中选出两个最小的权值,对应的两个结点组成一个新的二叉树,且新二叉树的根结点的权值为左右孩子权值的和;
    (2)在原有的 n 个权值中删除那两个最小的权值,同时将新的权值加入到 n–2 个权值的行列中,以此类推;
    (3)重复 1 和 2 ,直到所以的结点构建成了一棵二叉树为止,这棵树就是哈夫曼树。
    在这里插入图片描述
    上图中,(A)给定了四个结点a,b,c,d,权值分别为7,5,2,4;第一步如(B)所示,找出现有权值中最小的两个,2 和 4 ,相应的结点 c 和 d 构建一个新的二叉树,树根的权值为 2 + 4 = 6,同时将原有权值中的 2 和 4 删掉,将新的权值 6 加入;进入(C),重复之前的步骤。直到(D)中,所有的结点构建成了一个全新的二叉树,这就是哈夫曼树。

    四、哈弗曼树中结点结构

    构建哈夫曼树时,首先需要确定树中结点的构成。由于哈夫曼树的构建是从叶子结点开始,不断地构建新的父结点,直至树根,所以结点中应包含指向父结点的指针。但是在使用哈夫曼树时是从树根开始,根据需求遍历树中的结点,因此每个结点需要有指向其左孩子和右孩子的指针。

    所以,哈夫曼树中结点构成用代码表示为:

    //哈夫曼树结点结构
    typedef struct 
    {
      int weight;  //结点权重
      int parent, left, right;  //父结点、左孩子、右孩子在数组中的位置下标
    }HTNode, *HuffmanTree;

    五、哈弗曼树中的查找算法

    构建哈夫曼树时,需要每次根据各个结点的权重值,筛选出其中值最小的两个结点,然后构建二叉树。

    查找权重值最小的两个结点的思想是:从树组起始位置开始,首先找到两个无父结点的结点(说明还未使用其构建成树),然后和后续无父结点的结点依次做比较,有两种情况需要考虑:

    (1)如果比两个结点中较小的那个还小,就保留这个结点,删除原来较大的结点;
    (2)如果介于两个结点权重值之间,替换原来较大的结点;

    代码实现:

    //HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
    void Select(HuffmanTree HT, int end, int *s1, int *s2)
    {
      int min1, min2;
      //遍历数组初始下标为 1
      int i = 1;
      //找到还没构建树的结点
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      min1 = HT[i].weight;
      *s1 = i;
      i++;
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      //对找到的两个结点比较大小,min2为大的,min1为小的
      if(HT[i].weight < min1)
      {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
      }
      else
      {
        min2 = HT[i].weight;
        *s2 = i;
      }
      //两个结点和后续的所有未构建成树的结点做比较
      for(int j=i+1; j <= end; j++)
      {
        //如果有父结点,直接跳过,进行下一个
        if(HT[j].parent != 0)
        {
          continue;
        }
        //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if(HT[j].weight < min1)
        {
          min2 = min1;
          min1 = HT[j].weight;
          *s2 = *s1;
          *s1 = j;
        }
        //如果介于两者之间,min2赋值为新的结点的位置下标
        else if(HT[j].weight >= min1 && HT[j].weight < min2)
        {
          min2 = HT[j].weight;
          *s2 = j;
        }
      }
    }

    注意:s1和s2传入的是实参的地址,所以函数运行完成后,实参中存放的自然就是哈夫曼树中权重值最小的两个结点在数组中的位置。

    六、构建哈弗曼树的代码实现

    //HT为地址传递的存储哈夫曼树的数组,w为存储结点权重值的数组,n为结点个数
    void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
    {
      if(n <= 1) 
        return;   // 如果只有一个编码就相当于0
      int m = 2*n-1;   // 哈夫曼树总节点数,n就是叶子结点
      *HT = (HuffmanTree) malloc((m+1) * sizeof(HTNode));   // 0号位置不用
      HuffmanTree p = *HT;
      // 初始化哈夫曼树中的所有结点
      for(int i = 1; i <= n; i++)
      {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
      //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
      for(int i = n+1; i <= m; i++)
      {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
      //构建哈夫曼树
      for(int i = n+1; i <= m; i++)
      {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
      }
    }

    七、哈夫曼编码

    哈夫曼编码就是在哈夫曼树的基础上构建的,这种编码方式最大的优点就是用最少的字符包含最多的信息内容

    根据发送信息的内容,通过统计文本中相同字符的个数作为每个字符的权值,建立哈夫曼树。对于树中的每一个子树,统一规定其左孩子标记为 0 ,右孩子标记为 1 。这样,用到哪个字符时,从哈夫曼树的根结点开始,依次写出经过结点的标记,最终得到的就是该结点的哈夫曼编码。

    文本中字符出现的次数越多,在哈夫曼树中的体现就是越接近树根,编码的长度越短

    在这里插入图片描述
    如上图所示,字符 a 用到的次数最多,其次是字符 b 。字符 a 在哈夫曼编码是 0 ,字符 b 编码为 10 ,字符 c 的编码为 110 ,字符 d 的编码为 111 。

    使用程序求哈夫曼编码有两种方法:

    1)从叶子结点一直找到根结点,逆向记录途中经过的标记。
    例如,图 3中字符 c 的哈夫曼编码从结点 c 开始一直找到根结点,结果为:0 1 1 ,所以字符 c 的哈夫曼编码为:1 1 0(逆序输出)。
    
    (2)从根结点出发,一直到叶子结点,记录途中经过的标记。
    例如,求图 中字符 c 的哈夫曼编码,就从根结点开始,依次为:1 1 0

    采用方法(1)的实现代码为:

    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
      cd[n-1] = '\0';//字符串结束符
      for(int i=1; i<=n; i++)
      {
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while(j != 0)
        {
          // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
          if(HT[j].left == c)
            cd[--start] = '0';
          else
            cd[--start] = '1';
          //以父结点为孩子结点,继续朝树根的方向遍历
          c = j;
          j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i], &cd[start]);
      }
      //使用malloc申请的cd动态数组需要手动释放
      free(cd);
    }

    采用方法(2)的实现代码为:

    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      int m = 2*n-1;
      int p = m;
      int cdlen = 0;
      char *cd = (char *)malloc(n*sizeof(char));
      //将各个结点的权重用于记录访问结点的次数,首先初始化为0
      for (int i=1; i<=m; i++) 
      {
        HT[i].weight = 0;
      }
      //一开始 p 初始化为 m,也就是从树根开始。一直到p为0
      while (p) 
      {
        //如果当前结点一次没有访问,进入这个if语句
        if (HT[p].weight == 0) 
        {
          HT[p].weight = 1;  //重置访问次数为1
          //如果有左孩子,则访问左孩子,并且存储走过的标记为0
          if (HT[p].left != 0) 
          {
            p = HT[p].left;
          }
          else if(HT[p].right == 0) // 当前结点没有左孩子,也没有右孩子,说明为叶子结点,直接记录哈夫曼编码
          {
            (*HC)[p] = (char*)malloc((cdlen+1)*sizeof(char));
            cd[cdlen] = '\0';
            strcpy((*HC)[p], cd);
          }
        }
        else if(HT[p].weight == 1) // 如果weiget为1,说明访问过一次,即使是左孩子返回的
        {
          HT[p].weight = 2;  //设置访问次数为2
          //如果有右孩子,遍历右孩子,记录标记值 1
          if (HT[p].right != 0) 
          {
            p = HT[p].right;
            cd[cdlen++] = '1';
          }
        }
        else //如果访问次数为2,说明左孩子都遍历完了,返回父结点
        {
          HT[p].weight = 0;
          p = HT[p].parent;
          --cdlen;
        }
      }
    }

    八、完整代码(可运行)

    #include<stdlib.h>
    #include<stdio.h>
    #include<string.h>
    
    //哈夫曼树结点结构
    typedef struct 
    {
      int weight;//结点权重
      int parent, left, right;//父结点、左孩子、右孩子在数组中的位置下标
    }HTNode, *HuffmanTree;
    //动态二维数组,存储哈夫曼编码
    typedef char **HuffmanCode;
    //HT数组中存放的哈夫曼树,end表示HT数组中存放结点的最终位置,s1和s2传递的是HT数组中权重值最小的两个结点在数组中的位置
    void Select(HuffmanTree HT, int end, int *s1, int *s2)
    {
      int min1, min2;
      //遍历数组初始下标为 1
      int i = 1;
      //找到还没构建树的结点
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      min1 = HT[i].weight;
      *s1 = i;
      i++;
      while(HT[i].parent != 0 && i <= end)
      {
        i++;
      }
      //对找到的两个结点比较大小,min2为大的,min1为小的
      if(HT[i].weight < min1)
      {
        min2 = min1;
        *s2 = *s1;
        min1 = HT[i].weight;
        *s1 = i;
      }
      else
      {
        min2 = HT[i].weight;
        *s2 = i;
      }
      //两个结点和后续的所有未构建成树的结点做比较
      for(int j=i+1; j <= end; j++)
      {
        //如果有父结点,直接跳过,进行下一个
        if(HT[j].parent != 0)
        {
          continue;
        }
        //如果比最小的还小,将min2=min1,min1赋值新的结点的下标
        if(HT[j].weight < min1)
        {
          min2 = min1;
          min1 = HT[j].weight;
          *s2 = *s1;
          *s1 = j;
        }
        else if(HT[j].weight >= min1 && HT[j].weight < min2)   // 如果介于两者之间,min2赋值为新的结点的位置下标
        {
          min2 = HT[j].weight;
          *s2 = j;
        }
      }
    }
    
    //HT为地址传递的存储哈夫曼树的数组,w为存储结点权重值的数组,n为结点个数
    void CreateHuffmanTree(HuffmanTree *HT, int *w, int n)
    {
      if(n<=1) 
        return;     // 如果只有一个编码就相当于0
      int m = 2*n-1;   // 哈夫曼树总节点数,n就是叶子结点
      *HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode)); // 0号位置不用
      HuffmanTree p = *HT;
      // 初始化哈夫曼树中的所有结点
      for(int i = 1; i <= n; i++)
      {
        (p+i)->weight = *(w+i-1);
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
    
      //从树组的下标 n+1 开始初始化哈夫曼树中除叶子结点外的结点
      for(int i = n+1; i <= m; i++)
      {
        (p+i)->weight = 0;
        (p+i)->parent = 0;
        (p+i)->left = 0;
        (p+i)->right = 0;
      }
    
      //构建哈夫曼树
      for(int i = n+1; i <= m; i++)
      {
        int s1, s2;
        Select(*HT, i-1, &s1, &s2);
        (*HT)[s1].parent = (*HT)[s2].parent = i;
        (*HT)[i].left = s1;
        (*HT)[i].right = s2;
        (*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
      }
    }
    
    //HT为哈夫曼树,HC为存储结点哈夫曼编码的二维动态数组,n为结点的个数
    void HuffmanCoding(HuffmanTree HT, HuffmanCode *HC, int n)
    {
      *HC = (HuffmanCode) malloc((n+1) * sizeof(char *));
      char *cd = (char *)malloc(n*sizeof(char)); //存放结点哈夫曼编码的字符串数组
      cd[n-1] = '\0';//字符串结束符
      for(int i=1; i<=n; i++)
      {
        //从叶子结点出发,得到的哈夫曼编码是逆序的,需要在字符串数组中逆序存放
        int start = n-1;
        //当前结点在数组中的位置
        int c = i;
        //当前结点的父结点在数组中的位置
        int j = HT[i].parent;
        // 一直寻找到根结点
        while(j != 0)
        {
          // 如果该结点是父结点的左孩子则对应路径编码为0,否则为右孩子编码为1
          if(HT[j].left == c)
            cd[--start] = '0';
          else
            cd[--start] = '1';
          //以父结点为孩子结点,继续朝树根的方向遍历
          c = j;
          j = HT[j].parent;
        }
        //跳出循环后,cd数组中从下标 start 开始,存放的就是该结点的哈夫曼编码
        (*HC)[i] = (char *)malloc((n-start)*sizeof(char));
        strcpy((*HC)[i], &cd[start]);
      }
      //使用malloc申请的cd动态数组需要手动释放
      free(cd);
    }
    
    //打印哈夫曼编码的函数
    void PrintHuffmanCode(HuffmanCode htable, int *w, int n)
    {
      printf("Huffman code : \n");
      for(int i = 1; i <= n; i++)
        printf("%d code = %s\n",w[i-1], htable[i]);
    }
    
    int main(void)
    {
      int w[5] = {2, 8, 7, 6, 5};
      int n = 5;
      HuffmanTree htree;
      HuffmanCode htable;
      CreateHuffmanTree(&htree, w, n);
      HuffmanCoding(htree, &htable, n);
      PrintHuffmanCode(htable, w, n);
    
      return 0;
    }

    运行结果:

    Huffman code :
    2 code = 100
    8 code = 11
    7 code = 01
    6 code = 00
    5 code = 101

    九、总结

    程序运行效果图如下:
    在这里插入图片描述
    本节的程序中对权重值分别为 2,8,7,6,5 的结点构建的哈夫曼树如上图(A)所示。图 中(B)是另一个哈夫曼树,两棵树的带权路径长度相同。

    程序运行效果图之所以是(A)而不是(B),原因是在构建哈夫曼树时,结点 2 和结点 5 构建的新的结点 7 存储在动态树组的最后面,所以,在程序继续选择两个权值最小的结点时,直接选择了的叶子结点 6 和 7 。

    展开全文
  • 哈夫曼树的构建及哈夫曼树编码

    万次阅读 2018-09-09 14:56:29
    哈夫曼树的构建: 注意:(1).首先把一组数3 5 6 8 9 12 15从小到大排列 (2).选取里面最小2个,顶点出为2个数的和 (3).新产生的顶点在与原先的...(4)....哈夫曼树编码: 注意:(1).上图的a b c d e f假如...
  • 本篇文章主要介绍了C++哈夫曼树编码和译码的实现,详细的讲诉了哈夫曼树编码的原理,有需要的同学可以了解一下。
  • 主要为大家详细介绍了C++实现哈夫曼树编码解码,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 哈夫曼树编码压缩

    2015-11-04 23:49:21
    利用哈夫曼树编码的无损压缩与解压软件,c++语言版本,操作简单,将文件拖至窗口即可,显示压缩比,程序设计课程会用到
  • 数据结构课程 实验报告 实验名称 哈弗曼编码和译码 专业班级 电子信息科学与技术0904 姓 名 秦杰 学 号 1404090506 指导教师 胡志坤 2011年 11月 实验四哈夫曼编码和译码 实验目的和要求 掌握哈夫曼树的基本概念及其...
  • 哈夫曼树编码-C语言

    千次阅读 多人点赞 2019-11-10 17:02:45
    哈夫曼树编码 1.实验目的 了解二叉树的定义,理解二叉树的基本性质和存储结构,掌握哈夫曼树的构造,实现哈夫曼编码与译码算法。 2.实验内容 从键盘输入一串电文字符与权值,输出对应的哈夫曼编码;从键盘输入一...
  • 哈夫曼树和哈夫曼树编码

    千次阅读 2014-05-28 14:50:01
    哈夫曼编码哈夫曼树的一个应用。哈夫曼编码应用广泛,如 JPEG中就应用了哈夫曼编码。 首先介绍什么是哈夫曼树哈夫曼树又称最优二叉树, 是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中...
  • 哈夫曼树编码C语言实现

    万次阅读 多人点赞 2017-05-06 01:46:20
    实现哈夫曼树编码的算法可分为两大部分: (1)构造哈夫曼树; (2)在哈夫曼树上求叶结点的编码; 哈夫曼树构造算法: (1)由给定的n个权值构造n棵只有一个叶结点的二叉树,从而得到一个二叉树的集合F={T1,T2...
  • 哈夫曼树编码转换

    千次阅读 2015-12-31 19:10:49
    哈夫曼树编码转换
  • 主要介绍了Python完成哈夫曼树编码过程及原理详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
  • 图解哈夫曼树:https://blog.csdn.net/lee18254290736/article/details/77618201构建哈夫曼及哈夫曼编码实现:https://blog.csdn.net/wtfmonking/article/details/17150499#
  • 根据创建好的哈夫曼树创建一张哈夫曼编码表  3.输入一串哈夫曼序列,输出原始字符  三.设计思想:  1.首先要构造一棵哈夫曼树哈夫曼树的结点结构包括权值,双亲,左右孩子;假如由n个字符来构造一棵哈夫曼...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,002
精华内容 1,600
关键字:

哈夫曼树编码