哈夫曼编码的c实现数据结构与算法TianJinCheng'sBlog-

目录

设计思想

设计流程 

实现代码

实验结果

实验结果与理论结果验证

参考文献

设计思想

由数据结构学习的哈夫曼树的编程思想，可以先构造哈夫曼树，在构造哈夫曼编码。

哈夫曼编码(Huffman Coding)，又称霍夫曼编码，是一种编码方式，可变字长编码(VLC)的一种。Huffman于1952年提出一种编码方法，该方法完全依据字符出现概率来构造异字头的平均长度最短的码字，有时称之为最佳编码，一般就叫做Huffman编码（有时也称为霍夫曼编码）。哈夫曼编码，主要目的是根据使用频率来最大化节省字符（编码）的存储空间。

设计流程 

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

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

• 再依次建立哈夫曼树，如下图：

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

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

实现代码

 /*********************************************************************************  *      Copyright:  (C) 2020 shx  *                  All rights reserved.  *  *       Filename:  tmp.c  *    Description:  This file  *  *        Version:  1.0.0(04/20/2020)  *         Author:  tianjincheng <473892093@qq.com>  *      ChangeLog:  1, Release initial version on "04/20/2020 10:08:09 AM"  *  ********************************************************************************/  #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #define H_MAXBIT 100 #define H_MAXVALUE 1000 #define H_MAXLEAF 30  //叶子节点数目 #define H_MAXNODE (((H_MAXLEAF)*2)-1)  //节点数目  typedef struct  //定义编码结构体 {     int bit[H_MAXBIT];     int start; }HCodeType;  typedef struct //定义节点结构体 {     int weight;     int parent;     int lchild;     int rchild; }HNodeType;  //构造哈夫曼树 void HuffmanTree(HNodeType HuffNode[H_MAXNODE], int n) {     int i, j, m1, m2, x1, x2;     for (i = 0; i < 2*n-1; ++i)     {         HuffNode[i].weight = 0;         HuffNode[i].parent = -1;         HuffNode[i].lchild = -1;         HuffNode[i].rchild = -1;     }      for (i = 0; i < n; i++)     {         char *buf[5] = {"A","B","C","D","E"};         /*输入每个节点的权值*/         printf("输入[%s]节点的权值: n", buf[i]);         scanf("%d", &HuffNode[i].weight);     }     /*构造哈夫曼树*/     for (i = 0; i < n - 1; i++)     {         m1 = m2 = H_MAXVALUE;         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;             }         }         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;     }  }  int main() {     char* buf[5] = { "A","B","C","D","E" };      HNodeType HufNode[H_MAXNODE];     HCodeType HufCode[H_MAXLEAF], cd;      int i, j, c, p, n;     printf("输入需要编码的节点数目:n");     scanf("%d", &n);     if (n < 0 || n> 6)     {         printf("输入参数不合法，请输入0<x<6n");         return 0;      }     HuffmanTree(HufNode, n);      for (i = 0; i < n; i++)     {         cd.start = n - 1;         c = i;         p = HufNode[c].parent;         while (p != -1)         {             if (HufNode[p].lchild == c)             {                 cd.bit[cd.start] = 0;             }             else             {                 cd.bit[cd.start] = 1;             }             cd.start--;             c = p;             p = HufNode[c].parent;         }          for (j = cd.start + 1; j < n; j++)         {             HufCode[i].bit[j] = cd.bit[j];             HufCode[i].start = cd.start;         }     }      for (i = 0; i < n; i++)     {         printf("[%s]节点的哈夫曼编码为: ", buf[i]);         for (j = HufCode[i].start + 1; j < n; j++)         {             printf("%2d", HufCode[i].bit[j]);         }         printf("n");     }     getchar();     system("pause");     return 0; }  

实验结果

实验结果与理论结果验证

• 实验结果：A(0): 1 1 , B(2): 1 0 C(2): 0 0 D(3):0 1 1 E(5): 0 1 0
• 理论结果：A(0): 1 1 , B(2): 1 0 C(2): 0 0 D(3):0 1 1 E(5): 0 1 0

参考文献

• 百度：《哈夫曼编码测的基本实现》
• 陈运《信息论与编码》第三版