C++ Huffman 编码解码器实现 - 压缩文件大小
// 头文件
#include
using namespace std;
const int N = 256; // 字符集大小
// 哈夫曼树结点的定义 typedef struct { char data; // 字符 int weight; // 权重 int parent; // 父亲结点下标 int lchild; // 左孩子结点下标 int rchild; // 右孩子结点下标 } HTNode, *HuffmanTree;
// 哈夫曼编码表的定义 typedef struct { char data; // 字符 string code; // 编码 } HCNode, *HuffmanCode;
// 用于比较两个结点的权重 bool cmp(HTNode a, HTNode b) { return a.weight < b.weight; }
// 统计字符出现的频率 void frequencyRecord(HuffmanTree& HT) { ifstream file('binaryfile.txt'); // 打开二进制编码文件 HT = new HTNode[2 * N - 1]; // 动态分配哈夫曼树结点的存储空间 for (int i = 0; i < N; ++i) { HT[i].data = i; // ASCII码值即为下标 HT[i].weight = 0; // 初始化权重为0 HT[i].parent = -1; // 初始化父亲结点下标为-1 HT[i].lchild = -1; // 初始化左孩子结点下标为-1 HT[i].rchild = -1; // 初始化右孩子结点下标为-1 } char _data; cin.unsetf(ios::skipws); // 取消忽略空格的设置 while (!file.eof()) { // 读取文件直至文件结束 if (file.get(_data)) { // 读取一个字符 ++HT[_data].weight; // 对应字符的权重加1 } } file.close(); // 关闭文件 sort(HT, HT + N, cmp); // 根据权重从小到大排序 }
// 构建哈夫曼树 void HuffmanTreeBuilding(HuffmanTree& HT) { int m = 2 * N - 1; // 哈夫曼树的结点数 int i, j; for (i = N; i < m; ++i) { HT[i].weight = 0; // 初始化权重为0 HT[i].parent = -1; // 初始化父亲结点下标为-1 HT[i].lchild = -1; // 初始化左孩子结点下标为-1 HT[i].rchild = -1; // 初始化右孩子结点下标为-1 } for (i = 0; i < N - 1; ++i) { // 构建哈夫曼树 int min1 = -1, min2 = -1; // 记录权重最小的两个结点的下标 for (j = 0; j <= i; ++j) { // 在前i个结点中找到权重最小的两个结点 if (HT[j].parent == -1) { // 如果该结点没有父亲结点 if (min1 == -1 || HT[j].weight < HT[min1].weight) { // 如果min1未被赋值或者当前结点的权重小于min1的权重 min2 = min1; // min2记录上一次的min1 min1 = j; // min1记录当前结点 } else if (min2 == -1 || HT[j].weight < HT[min2].weight) { // 如果min2未被赋值或者当前结点的权重小于min2的权重 min2 = j; // min2记录当前结点 } } } HT[min1].parent = i + N; // 最小权重的结点作为新结点的左孩子 HT[min2].parent = i + N; // 次小权重的结点作为新结点的右孩子 HT[i + N].weight = HT[min1].weight + HT[min2].weight; // 新结点的权重为左右孩子结点的权重之和 HT[i + N].lchild = min1; // 左孩子结点为权重最小的结点 HT[i + N].rchild = min2; // 右孩子结点为次小权重的结点 } }
// 从叶子结点开始逆向求每个字符的哈夫曼编码 void HuffmanCoding(HuffmanTree& HT, HuffmanCode& HC) { HC = new HCNode[N]; // 动态分配哈夫曼编码表结点的存储空间 char* cd = new char[N]; // 动态分配求解哈夫曼编码的临时存储空间 cd[N - 1] = '\0'; // 结束符 for (int i = 0; i < N; ++i) { // 求解每个字符的哈夫曼编码 int start = N - 1; // 从结束符开始向前求解 int c = i; // 当前字符的下标 int f = HT[i].parent; // 当前结点的父亲结点下标 while (f != -1) { if (HT[f].lchild == c) { // 如果当前结点是父亲结点的左孩子 cd[--start] = '0'; // 编码为0 } else { // 如果当前结点是父亲结点的右孩子 cd[--start] = '1'; // 编码为1 } c = f; // 当前结点变为父亲结点 f = HT[f].parent; // 父亲结点上移一层 } HC[i].data = HT[i].data; // 记录当前字符 HC[i].code = &cd[start]; // 保存当前字符的哈夫曼编码 } delete[] cd; // 释放临时存储空间 }
// 将源文件进行哈夫曼编码，写入编码文件
void zip(HuffmanTree& HT, HuffmanCode& HC, vector
// 将哈夫曼编码文件进行解码，写入解码文件
void unzip(HuffmanTree& HT, HuffmanCode& HC, vector
// 将源文件以一个字节进行二进制编码，写入二进制编码文件 void binaryCode() { ofstream binaryFile('binaryfile.txt'); // 打开二进制编码文件 ifstream originFile('poem.txt'); // 打开源文件 originFile.seekg(0); // 将读取指针指向文件开头 if (!originFile) { // 如果打开源文件失败 cout << 'Can't find the file!' << endl; // 输出错误信息 } else { char _data; cin.unsetf(ios::skipws); // 取消忽略空格的设置 while (!originFile.eof()) { // 读取文件直至文件结束 if (originFile.get(_data)) { // 读取一个字符 bitset<8> data(_data); // 将字符转换为8位二进制数 binaryFile << data; // 将二进制数写入二进制编码文件 } } originFile.close(); // 关闭源文件 } }
// 主函数
int main() {
system('color 02'); // 设置控制台字体颜色
cout << '' << endl;
cout << '哈夫曼编码解码器' << endl;
cout << '' << endl;
Sleep(1000); // 延时1秒
HuffmanTree HT; // 哈夫曼树
HuffmanCode HC; // 哈夫曼编码表
vector
原文地址: https://www.cveoy.top/t/topic/orfl 著作权归作者所有。请勿转载和采集!