计算Huffman平均编码长度 题目：输入： 第一行为一个整数，表示输入数据中有n种字符 第2~n+1行为n个整数，表示每个字符出现的次数 输出：Huffman编码的平均长度（保留两位小数） 代码： #include <iostream> #include <cstring> #include<iomanip> using namespace std; struct HuffmanNode { int weight; // 权重，出现的次数或者频率 char ch; // 存储符号 string code; // 存储该符号对应的编码 int leftChild, rightChild, parent; // 左、右孩子，父结点 }; class HuffmanCode { public: HuffmanCode(string str); // 构造函数 ~HuffmanCode(); // 析构函数 void getMin(int& first, int& second, int parent); // 选取两个较小的素 void Merge(int first, int second, int parent); // 合并 void Encode(); // 编码:利用哈夫曼编码原理对数据进行加密 private: HuffmanNode* HuffmanTree; // 数组 int leafSize; // 统计不同字符的个数 double average;//记录编码平均长度 }; // 构造函数 HuffmanCode::HuffmanCode(string str) { int len = (int)str.size(); // 字符串的长度 int arr[256], i; // 存储字符串各个字符的个数 HuffmanTree = new HuffmanNode[256]; // 动态分配空间 // 1.初始化HuffmanTree数组 for (i = 0; i < (2 * len – 1); i++) { // 叶子结点为len,则树最多有2*len-1个结点 HuffmanTree[i].leftChild = HuffmanTree[i].rightChild = HuffmanTree[i].parent = -1; HuffmanTree[i].code = “”; } // 2.统计输入的字符串的各个字符出现的个数 memset(arr, 0, sizeof(arr)); // 清零 for (i = 0; i < len; i++) // 统计次数 arr[str[i]]++; // str[i] -> 转成对应的ASCII码，如’0′->48 leafSize = 0; // 出现不同字符的个数 for (i = 0; i < 256; i++) { if (arr[i] != 0) { // 有出现的字符 // cout << “字符:” << (char)i << “次数为：” << arr[i] << endl; HuffmanTree[leafSize].ch = (char)i; // 将数字转成对应的字符 HuffmanTree[leafSize].weight = arr[i]; // 权重 leafSize++; } } // 3.选取两个较小值合并 int first, second; // 两个较小的结点 for (i = leafSize; i < (2 * leafSize – 1); i++) { // 做leafSize-1趟 getMin(first, second, i); // 选取两个较小的素 Merge(first, second, i); // 合并 } } // 析构函数 HuffmanCode::~HuffmanCode() { delete[]HuffmanTree; } // 选取权值两个较小的素 void HuffmanCode::getMin(int& first, int& second, int parent) { double weight = 0; int i; // 找权重最小素 for (i = 0; i < parent; i++) { if (HuffmanTree[i].parent != -1) // 已选过，直接跳过 continue; if (weight == 0) { // 第一次找到没选过的结点 weight = HuffmanTree[i].weight; first = i; } else if (HuffmanTree[i].weight < weight) { // 权值更小 weight = HuffmanTree[i].weight; first = i; } } // 找权重次小素 weight = 0; for (i = 0; i < parent; i++) { if (HuffmanTree[i].parent != -1 || i == first) // 已选过，直接跳过 continue; if (weight == 0) { // 第一次找到没选过的结点 weight = HuffmanTree[i].weight; second = i; } else if (HuffmanTree[i].weight < weight) { // 权值更小 weight = HuffmanTree[i].weight; second = i; } } } // 合并 void HuffmanCode::Merge(int first, int second, int parent) { HuffmanTree[first].parent = HuffmanTree[second].parent = parent; // 父结点 HuffmanTree[parent].leftChild = first; // 左孩子 HuffmanTree[parent].rightChild = second; // 右孩子 HuffmanTree[parent].weight = HuffmanTree[first].weight + HuffmanTree[second].weight; // 权值 } // 编码,同时计算平均编码长度 void HuffmanCode::Encode() { string code; // 存储符号的不定长二进制编码 int i, j, k, parent; int sum = 0;//总的权重 for (i = 0; i < leafSize; i++) { // 从叶子结点出发 j = i; code = “”; // 初始化为空 while (HuffmanTree[j].parent != -1) { // 往上找到根结点 parent = HuffmanTree[j].parent; // 父结点 if (j == HuffmanTree[parent].leftChild) // 如果是左孩子，则记为0 code += “0”; else // 右孩子，记为1 code += “1”; j = parent; // 上移到父结点 } // 编码要倒过来：因为是从叶子往上走到根，而编码是要从根走到叶子结点 for (k = (int)code.size() – 1; k >= 0; k–) { HuffmanTree[i].code += code[k]; // 保存编码 } sum += HuffmanTree[i].weight; string str = string(HuffmanTree[i].code); average += str.length() * HuffmanTree[i].weight; } cout<< setiosflags(ios::fixed) <<setprecision(2)<< average/sum << endl; } int main() { int n=0;//几种字符 cin >> n; int* p = new int[n]; string str; char m = ‘a’; for (int i = 0; i < n; i++) { cin >> p[i];//输入权重 for (int j = 0; j < p[i]; j++) { str +=m ; } m++; } HuffmanCode st(str); // 对象 st.Encode(); // 编码，输出平均编码长度 return 0; delete[]p; }
2024最新激活全家桶教程，稳定运行到2099年，请移步至置顶文章：https://sigusoft.com/99576.html
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。 文章由激活谷谷主-小谷整理,转载请注明出处：https://sigusoft.com/89013.html
