【GDPU】数据结构实验十 哈夫曼编码

本文主要是介绍【GDPU】数据结构实验十 哈夫曼编码，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

【实验内容】

1、假设用于通信的电文仅由8个字母 {a, b, c, d, e, f, g, h} 构成，它们在电文中出现的概率分别为{ 0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10 }，试为这8个字母设计哈夫曼编码。

提示:包含两个过程:（1）构建哈夫曼树，（2）输出编码。

---

我的思路：

（1）建造哈夫曼树的过程直接按照哈夫曼思想模拟即可

（2）输出编码。而 哈夫曼编码函数，我使用了 图论中的 dfs回溯算法 的思想，采用以 递归为 核心的方法遍历整棵树，并将走过的左路径标记为 0，将走过的右路径标记为 1，到了叶子节点收集路径结果，

每一条路径我使用 一维数组 path 记录

全部路径的结果，我使用 二维数组 result 存储

最后打印 result  数组即可

---

简而言之：

用一维数组记录路径 上的 0 和 1，到了叶子节点就成为一条完整的编码

将每一条编码用  二维数组 存起来

---

头文件 Head.h

建造一棵哈夫曼树的相关函数和操作

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#define MAX 40// 创建树节点
typedef struct HtNode {int ww;int parent, Lchild, Rchild;
}HtNode;// 哈夫曼树结构
typedef struct HtTree {int root;HtNode ht[MAX];
}PHtTree;// 构造哈夫曼树
// m 为权值节点数量，w 为权值数组
PHtTree* CreateHuffMan(int m, int* w) {// 创建带有 m 个叶子节点的哈夫曼树PHtTree* pht = (PHtTree*)malloc(sizeof(PHtTree));if (pht == NULL) {perror("malloc fail !");return NULL;}// 初始化for (int i = 0; i < 2 * m - 1; ++i) {pht->ht[i].Lchild = pht->ht[i].Rchild = pht->ht[i].parent = -1;// 将数组前 m 个位置放入 权值数组元素if (i < m)pht->ht[i].ww = w[i];elsepht->ht[i].ww = -1;}// 构建哈夫曼树int i;for (i = 0; i < m - 1; i++) {// 两个m 找最小权值，两个 index 记录这两节点的下标int m1, m2, index1, index2;m1 = m2 = INT_MAX;index1 = index2 = -1;// 每轮都在区间 [0,  m + i] 找两个最小权值节点，且没有父节点(即没有使用过)for (int j = 0; j < m + i; ++j) {if (pht->ht[j].ww < m1 && pht->ht[j].parent == -1) {m2 = m1;index2 = index1;m1 = pht->ht[j].ww;index1 = j;}else if (pht->ht[j].ww < m2 && pht->ht[j].parent == -1) {m2 = pht->ht[j].ww;index2 = j;}}// 找到节点之后，构建父节点，并将父节点放进数组中pht->ht[index1].parent = m + i;pht->ht[index2].parent = m + i;pht->ht[m + i].ww = m1 + m2;pht->ht[m + i].Lchild = index1;pht->ht[m + i].Rchild = index2;}pht->root = m + i; // 更新根节点：m+i 即为 m + (m-2)return pht;
}

哈夫曼编码函数  HuffmanEncode

#include"Head.h"// 哈夫曼编码
// 思路：遍历每一条路，到叶子节点记录结果，左边标记为 0， 右边标记为 1// p  遍历 path ：从下标 1 开始存放编码串，下标 0 存放字符串长度（表示该编码串长度，方便遍历）
// r 遍历 result：代表一一存放结果
int r = 0, p = 1;  
int result[MAX][MAX];  // 收集 path 的每一次结果
int path[MAX];   // 记录每一条路径的编码void HuffmanEncode(HtNode* ht, int root)
{if (root == -1) return; // 空节点返回if (ht[root].Lchild == -1 && ht[root].Rchild == -1) { // 叶子节点 就记录结果path[0] = p - 1;  // p-1 代表此时 path数组中收集的 路径上的（一串 1 和 0）的数量：方便遍历，因为每一串编码不等长，所以需要记录数量memcpy(result + r, path, sizeof(int)*p);  // 将一维数组 path 存放进二维数组 result ：记录每一条路径的最终结果r++;path[0] = 0;  // 将第 0 个位置重新置为 0（表示恢复之前的状态）return;}path[p++] = 0;  // 向左走路径标记为 0HuffmanEncode(ht, ht[root].Lchild); // 递归到左节点p--;  // 从左节点回退回来：p-- 代表将 path[p++] = 0;   这里曾经标记的 0 给"删除"path[p++] = 1;  // 路径标记为 1HuffmanEncode(ht, ht[root].Rchild); // 递归到右节点p--;   // 从右节点回退回来：p-- 代表将 path[p++] = 1;   这里曾经标记的 1 给"删除"}

主函数 Main.c 

int main()
{// 输入 m 和 w 数组int m, w[MAX];scanf("%d", &m);float t = 0;for (int i = 0; i < m; ++i) {scanf("%f", &t);w[i] = t * 100;  // 浮点树先乘上倍数，变成整型，方便计算}// 构建一棵树PHtTree* pht = CreateHuffMan(m, w);HuffmanEncode(pht->ht, pht->root - 1); // 传数组过去就可以了// 打印每一编码printf("\n");for (int i = 0; i < m; ++i) {int x = result[i][0];for (int j = 1; j <= x; ++j) {printf("%d ", result[i][j]);}printf("\n");}return 0;
}

这篇关于【GDPU】数据结构实验十 哈夫曼编码的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---