Hi，大家好，我是编程小6，很荣幸遇见你，我把这些年在开发过程中遇到的问题或想法写出来，今天说一说
哈夫曼编码算法步骤_利用哈夫曼编码进行通信可以大大,希望能够帮助你!!!。

哈夫曼树

哈夫曼树, 即带权路径最小的树, 权值最小的结点远离根结点, 权值越大的结点越靠近根结点

图解

图(3)即为哈夫曼树

哈夫曼编码

左孩子路径编码为 0, 右孩子路径编码为 1

图解

即
A 的编码: 0
D 的编码: 10
B 的编码: 110
C 的编码: 111

哈夫曼编码算法的实现

定义一个哈夫曼树

//定义一个哈夫曼树 typedef struct { 
    //定义权值 unsigned int weight; unsigned int parent, lchild, rchild; }HTNode, *HuffmanTree; 

定义存放哈夫曼编码的空间

//存放哈夫曼编码 typedef char** HuffmanCode; 

创建一个哈夫曼树

//创建一个哈夫曼树 void CreateHuffmanTree(HuffmanTree* HT, int* w, int n) { 
    int m = 0; //结点的总数(⊙﹏⊙) HuffmanTree adjust = NULL; //定义一个调整指针, 存放即时指向结点 int i = 0; //即时调整索引 //存放两个最小值 int s1 = 0; int s2 = 0; //判断输入是否合理 if (n <= 1) { 
    return; } m = 2 * n - 1; //动态分配内存空间存放结点 *HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode)); if (!*HT) { 
    exit(-1); } //初始化叶子结点, 第一个结点为空 for (adjust = *HT + 1, i = 1; i <= n; ++adjust, ++i) { 
    adjust->weight = *(w + i - 1); adjust->parent = 0; adjust->lchild = 0; adjust->rchild = 0; } //将最后一个结点的 parent 置为 0 for (; i <= m; ++i, ++adjust) { 
    adjust->parent = 0; } for (i = n + 1; i <= m; ++i) { 
    //在前 i - 1 个结点中找出两个最小值 Select(HT, i - 1, &s1, &s2); //找出双亲结点 (*HT + s1)->parent = (*HT + s2)->parent = i; //找出双亲结点的两个孩子 (*HT + i)->lchild = s1; (*HT + i)->rchild = s2; //计算出双亲结点的权值 (*HT + i)->weight = (*HT + s1)->weight + (*HT + s2)->weight; } } //返回权值最小结点的索引(访问过的结点不再访问) int Min(HuffmanTree HT, int n) { 
    unsigned int f_min = 100; int flag = 0; //用来记录已遍历过的结点 for (int i = 1; i <= n; ++i) { 
    if ((HT + i)->weight < f_min && (HT + i)->parent == 0) { 
    f_min = (HT + i)->weight; flag = i; } } //给选中的结点置 1, 下次不需要再遍历 (HT + flag)->parent = 1; return flag; } //挑选 2 个权值最小的结点 void Select(HuffmanTree* HT, int n, int* s1, int* s2) { 
    int tmp = 0; //临时变量 *s1 = Min(*HT, n); *s2 = Min(*HT, n); //目的是 s1 的权值要不大于 s2 的权值 if ((*HT + *s1)->weight > (*HT + *s2)->weight) { 
    tmp = *s1; *s1 = *s2; *s2 = tmp; } } 

构造哈夫曼编码

void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n) { 
    //动态开辟内存空间存放所有非叶子节点的编码 *HC = (HuffmanCode)malloc((n + 1) * sizeof(char*)); if (!*HC) { 
    exit(-1); } //动态分配内存空间暂时存放某个结点的哈夫曼编码 char* cd = (char*)malloc(n * sizeof(char)); if (!cd) { 
    exit(-1); } //求 n 个非叶子节点的哈夫曼编码 *(cd + n - 1) = '\0'; int start = 0; //用来存放编码起始位置 for (int i = 1; i <= n; ++i) { 
    start = n - 1; for (int c = i, f = (HT + i)->parent; f != 0; c = f, f = (HT + f)->parent) { 
    if ((HT + f)->lchild == c) { 
    *(cd + --start) = '0'; } else { 
    *(cd + --start) = '1'; } } //根据该结点编码字符串的长度在指定位置动态开辟存放编码的空间 *(*HC + i) = (char*)malloc((n - start) * sizeof(char)); //将暂存编码空间中的编码字符串拷贝到地址空间去 strcpy(*(*HC + i), cd + start); } //释放暂存编码字符串的空间 free(cd); } 

遍历叶子结点
从上到下, 从左到右

void Traverse(HuffmanTree HT, int n) { 
    //遍历叶子结点 HuffmanTree p = HT + 2 * n - 1; int i = 0; while ((p - HT > 0) && (p - HT <= 2 * n - 1)) { 
    if (p->lchild == 0 && p->rchild == 0) { 
    break; } if (p->lchild < p->rchild) { 
    i = p->lchild; printf("%u ", (HT + i)->weight); p = HT + p->rchild; } else { 
    i = p->rchild; printf("%u ", (HT + i)->weight); p = HT + p->lchild; } } printf("%u ", p->weight); printf("\n"); } 

遍历哈夫曼编码

//遍历哈夫曼编码 void TraverseCoding(HuffmanCode HC, int n) { 
    for (int i = 1; i <= n; ++i) { 
    printf("哈夫曼编码:"); puts(*(HC + i)); } } 

销毁哈夫曼树

//销毁哈夫曼树 void Destroy(HuffmanTree* HT, HuffmanCode* HC, int n) { 
    for (int i = 1; i <= n; ++i) { 
    free(*(*HC + i)); } free(*HC); free(*HT); *HC = NULL; *HT = NULL; } 

测试

//函数的声明 void CreateHuffmanTree(HuffmanTree* HT, int* w, int n); void HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n); void TraverseTree(HuffmanTree HT, int n); void TraverseCoding(HuffmanCode HC, int n); void Destroy(HuffmanTree* HT, HuffmanCode* HC, int n); int main() { 
    HuffmanTree HT = NULL; HuffmanCode HC = NULL; //存放权值 int* w = 0; int n = 0; //叶子结点个数 printf("请输入叶子结点的个数:"); scanf("%d", &n); //动态分配内存空间存放权值 w = (int*)malloc(n * sizeof(int)); if (!w) { 
    exit(-1); } printf("请输入权值:"); for (int i = 0; i < n; ++i) { 
    scanf("%d", w + i); } CreateHuffmanTree(&HT, w, n); HuffmanCoding(HT, &HC, n); printf("遍历哈夫曼树\n"); TraverseTree(HT, n); printf("遍历哈夫曼编码\n"); TraverseCoding(HC, n); printf("销毁哈夫曼树\n"); Destroy(&HT, &HC, n); if (!HT && !HC) { 
    printf("OK\n"); } system("pause"); return 0; } 

效果图

愿本篇文章能对大家有所帮助, 欢迎大家的评论和建议

今天的分享到此就结束了，感谢您的阅读，如果确实帮到您，您可以动动手指转发给其他人。