哈夫曼树实现图片压缩与解压

# Huffman压缩编码 ## 1. 核心知识 （1） 树的存储结构 （2） 二叉树的三种遍历方法 （3） Huffman树、Huffman编码算法 ## 2. 功能要求 1. 针对一幅BMP格式的图片文件，统计256种不同字节的重复次数，以每种字节重复次数作为权值，构造一颗有256个叶子节点的哈夫曼二叉树。 2. 利用上述哈夫曼树产生的哈夫曼编码对图片文件进行压缩。 3. 压缩后的文件与原图片文件同名，加上后缀.huf（保留原后缀），如pic.bmp 压缩后pic.bmp.huf ## 3.分析与设计 使用Huffman算法实现图片压缩程序，可分为6个步骤。 （1）创建工程 创建HuffmanCompressCPro工程，定义入口函数int main()； （2）读取原文件 读取文件，统计256种字节重复的次数； （3）生成Huffman树 根据上一步统计的结果，构建Huffman树； （4）生成Huffman编码 遍历Huffman树，记录256个叶子节点的路径，生成Huffman编码； （5）压缩编码 使用Huffman编码，对原文件中的字节重新编码，获得压缩后的文件数据； （6）保存文件 将编码过的数据，保存到文件“Pic.bmp.huf”中。 ## 4. 数据结构的设计 1.记录统计256种不同字节的重复次数即权值使用整型数组： > unsigned int weight[256]; 2.二叉树的存储结构。使用结构体存储节点，使用数组存储树的节点，使用静态二叉链表方式存储二叉树。 ```c++ struct HuffNode { unsigned char ch; //字节符 int weight; //字节出现频度 int parent; //父节点 int lchild; //左孩子 int rchild; //右孩子 char bits[256]; // 哈夫曼编码 }; // Huffman树 typedef char** HuffmanCode; ``` 3.Huffman编码存储结构定义一个二维数组: > typedef char** HuffmanCode; 4.压缩文件的算法的数据结构: 为正确解压文件，除了要保存原文件长度外，还要保存原文件中256种字节重复的次数，即权值。定义一个文件头，保存相关的信息： ```c++ struct FILESTRUCT { int sum; int fileid; }; ``` ## 5. 核心算法设计 **（1）构造Huffman树算法 ** ```c++ int CreateHuffmanTree(HuffNode *huf_tree, int n)//构造huffman树 { int i; int s1, s2; for (i = n; i < 2 * n - 1; ++i) { select(huf_tree, i, &s1, &s2); // 选择最小的两个结点 huf_tree[s1].parent = i; //原点双亲为i huf_tree[s2].parent = i; huf_tree[i].lchild = s1; //新结点左子树是最小的s1 huf_tree[i].rchild = s2; //新结点右子树是最小s2 huf_tree[i].weight = huf_tree[s1].weight + huf_tree[s2].weight;////新结点的权值 } return OK; } void select(HuffNode *huf_tree, int n, int *s1, int *s2)//在HT[1~I-1】选择parent为零且为最小的两个数，序号分别为s1,s2 { // 找最小结点 unsigned int i; unsigned long min = LONG_MAX; for (i = 0; i < n; i++) if (huf_tree[i].parent == -1 && huf_tree[i].weight < min) { min = huf_tree[i].weight; *s1 = i;//记录下标 } huf_tree[*s1].parent = 1; // 标记此结点已被选中 // 找次小结点 min = LONG_MAX; for (i = 0; i < n; i++) { if (huf_tree[i].parent == -1 && huf_tree[i].weight < min) { min = huf_tree[i].weight; *s2 = i; } } } ``` **（2）生成Huffman编码算法 ** ```c++ int HuffmanCoding(HuffNode *huf_tree, int n) { int i; int cur, next, index; char code_tmp[256]; // 暂存编码，最多256个叶子，编码长度不超多255 code_tmp[255] = '\0'; for (i = 0; i < n; ++i) { index = 256 - 1; // 编码临时空间初始化 // 从叶子向根求编码 for (cur = i, next = huf_tree[i].parent; next != -1; next = huf_tree[next].parent) { if (huf_tree[next].lchild == cur) code_tmp[--index] = '0'; // 左‘0’ else code_tmp[--index] = '1'; // 右‘1’ cur = next; } strcpy(huf_tree[i].bits, &code_tmp[index]); // 正向保存编码到树结点相应域 index是第一个 } return OK; } ``` **（4）生成压缩文件算法：** ```int compress(HuffNode huf_tree[], int n, long flength, char *ifname, char *ofname) { FILE * inFile = fopen(ifname, "rb");//打开要压缩文件 FILE * outFile = fopen(ofname, "wb");//打开压缩后文件 unsigned char temp = '\0'; //8bit临时的变量 char buffer[256] = "\0"; //缓存流 char tou[20]; //文件后缀名字符数组 int z = 0; int strLen = strlen(ifname);//文件后缀名长度 for (int g = strLen - 1; g>0; g--)//获取文件后缀名（从后面获取） { if (ifname[g] == '.')//获取文件后缀名最后一个“.” { for (int k = g; k< strLen; k++) { z++; tou[z] = ifname[k]; } } } tou[0] = z + '0';//获取文件后缀名长度(转成字符) fwrite((char *)&tou, sizeof(char), z + 1, outFile);//存文件头部 fwrite(&flength, sizeof(long), 1, outFile);//存总长度 fwrite(&n, sizeof(int), 1, outFile);//存字符的种类 for (int i = 0; i < n; i++) {//存每个编号对应的字符,权重 fwrite(&huf_tree[i].ch, sizeof(unsigned char), 1, outFile); fwrite(&huf_tree[i].weight, sizeof(long), 1, outFile); /*for (int f = 0; huf_tree[i].bits[f] == '0' || huf_tree[i].bits[f] == '1'; f++) { fwrite(&huf_tree[i].bits[f], sizeof(char), 1, outFile); }*/ } while (fread(&temp, sizeof(unsigned char), 1, inFile))//文件不为空 { for (int i = 0; i <n; i++)//找对应字符 { if (temp == huf_tree[i].ch) { for (int f = 0; huf_tree[i].bits[f] == '0' || huf_tree[i].bits[f] == '1'; f++)//过滤掉非0非1的编码（数组带来的弊端） { strncat(buffer, &huf_tree[i].bits[f], 1);//给缓存流赋值 } } } while (strlen(buffer) >= 8)//缓存流大于等于8个bits进入循环 { temp = 0; for (int i = 0; i < 8; i++)//每8个bits循环一次 { temp = temp << 1;//左移1 if (buffer[i] == '1')//如果是为1，就按位为1 { temp = temp | 0x01;//在不影响其他位的情况下，最后位置1 } } fwrite(&temp, sizeof(unsigned char), 1, outFile);//写入文件 strcpy(buffer, buffer + 8);//将写入文件的bits删除 } } int m = strlen(buffer);//将剩余不足为8的bits的个数给l if (m) { temp = 0; for (int i = 0; i < m; i++) { temp = temp << 1;//移动1 if (buffer[i] == '1')//如果是为1，就按位为1 { temp = temp | 0x01; } } temp <<= 8 - m;// // 将编码字段从尾部移到字节的高位 fwrite(&temp, sizeof(unsigned char), 1, outFile);//写入最后一个 } fclose(inFile); fclose(outFile); return 1; }//compress ``` **（5）解压算法：** ```c++ int extract(HuffNode huf_tree[], char *ifname, char *ofname) { int i; char huozui; //文件后缀长度 char tou[20]; //文件后缀字符 long flength; //文件总长度 int n; //字符种类 int node_num; //结点总数 unsigned long writen_len = 0; // 控制文件写入长度 FILE *infile, *outfile; unsigned char code_temp; // 暂存8bits编码 unsigned int root; // 保存根节点索引，供匹配编码使用 infile = fopen(ifname, "rb"); // 以二进制方式打开压缩文件 // 判断输入文件是否存在 if (infile == NULL) return -1; //读取文件后缀名长度 fread(&huozui, sizeof(char),1,infile); //字符转数字 int huozui_du = huozui - '0'; //读取文件后缀字符 fread(&tou, sizeof(char), huozui_du, infile); //读取文件后缀字符 fread(&flength, sizeof(long), 1, infile); //读取文件总长度 fread(&n, sizeof(int),