哈夫曼编码

2024-07-11 04:28| 来源: 网络整理| 查看: 265

哈夫曼编码的第一步是构造哈夫曼树，第二步是为哈夫曼树的每一条边编码。

构造哈夫曼树的时候，每次取权值最小的两个边合并，边小的放左边，边大的放右边。

哈夫曼树的结点总个数是哈夫曼叶节点个数的2倍减1

代码实现：

#include #include using namespace std; struct Node { int lChild, rChild, parent; string code; int weight; string c; }; //从当前叶节点和已经构造的节点中选出最小的两个数 void Select(Node nd[], int n, int& a, int &b) { //find the minimum double wt = 0; for (int i = 0; i < n; ++i) { if (nd[i].parent != -1) continue; if (wt == 0 && nd[i].parent == -1) { wt = nd[i].weight; a = i; } else if (nd[i].parent == -1 && nd[i].weight < wt) { wt = nd[i].weight; a = i; } } //寻找第二小的数 wt = 0; for (int i = 0; i < n; ++i) { if (nd[i].parent != -1 || i == a) continue; if (wt == 0 && nd[i].parent == -1) { wt = nd[i].weight; b = i; } else if (nd[i].parent == -1 && nd[i].weight < wt) { wt = nd[i].weight; b = i; } } } //构造huffman树 void HuffTree(int w[], string ch[], int N, int M, Node nd[]) { //初始化Node数组 for (int i = 0; i < M; ++i) { //-1代表没有 nd[i].lChild = -1; nd[i].rChild = -1; nd[i].parent = -1; nd[i].code = ""; } for (int i = 0; i < N; ++i) { nd[i].weight = w[i]; nd[i].c = ch[i]; } for (int i = N; i < M; ++i) { int a = 0, b = 0; Select(nd, i, a, b); nd[a].parent = i; nd[b].parent = i; nd[i].lChild = a; nd[i].rChild = b; nd[i].weight = nd[a].weight + nd[b].weight; } } void HuffEnCode(Node nd[], int N) { int i, j, k; for (int i = 0; i < N; ++i) { string s = ""; j = i; //从叶节点一直找到根节点 while (nd[j].parent != -1) { k = nd[j].parent; if (nd[k].lChild == j) { s = s + "0"; } else { s = s + "1"; } j = k; } for (int x = s.size(); x >= 0; --x) nd[i].code += s[x]; cout

【本文地址】

公司简介

联系我们