// 压缩函数
int compress(char ifname, char ofname)
{
unsigned int i, j;
unsigned int char_kinds; // 字符种类
unsigned char char_temp; // 暂存8bits字符
unsigned long file_len = 0;
FILE *infile, *outfile;
TmpNode node_temp;
unsigned int node_num;
HufTree huf_tree;
char code_buf[256] = "\0"; // 待存编码缓冲区
unsigned int code_len;
/
* 动态分配256个结点，暂存字符频度，
** 统计并拷贝到树结点后立即释放
*/
TmpNode *tmp_nodes =(TmpNode *)malloc(256*sizeof(TmpNode));
// 初始化暂存结点 for(i = 0; i < 256; ++i) { tmp_nodes[i].weight = 0; tmp_nodes[i].uch = (unsigned char)i; // 数组的256个下标与256种字符对应 } // 遍历文件，获取字符频度 infile = fopen(ifname, "rb"); // 判断输入文件是否存在 if (infile == NULL) return -1; fread((char *)&char_temp, sizeof(unsigned char), 1, infile); // 读入一个字符 while(!feof(infile)) { ++tmp_nodes[char_temp].weight; // 统计下标对应字符的权重，利用数组的随机访问快速统计字符频度 ++file_len; fread((char *)&char_temp, sizeof(unsigned char), 1, infile); // 读入一个字符 } fclose(infile); // 排序，将频度为零的放最后，剔除 for(i = 0; i < 256-1; ++i) for(j = i+1; j < 256; ++j) if(tmp_nodes[i].weight < tmp_nodes[j].weight) { node_temp = tmp_nodes[i]; tmp_nodes[i] = tmp_nodes[j]; tmp_nodes[j] = node_temp; } // 统计实际的字符种类（出现次数不为0） for(i = 0; i < 256; ++i) if(tmp_nodes[i].weight == 0) break; char_kinds = i; if (char_kinds == 1) { outfile = fopen(ofname, "wb"); // 打开压缩后将生成的文件 fwrite((char *)&char_kinds, sizeof(unsigned int), 1, outfile); // 写入字符种类 fwrite((char *)&tmp_nodes[0].uch, sizeof(unsigned char), 1, outfile); // 写入唯一的字符 fwrite((char *)&tmp_nodes[0].weight, sizeof(unsigned long), 1, outfile); // 写入字符频度，也就是文件长度 free(tmp_nodes); fclose(outfile); } else { node_num = 2 * char_kinds - 1; // 根据字符种类数，计算建立哈夫曼树所需结点数 huf_tree = (HufNode *)malloc(node_num*sizeof(HufNode)); // 动态建立哈夫曼树所需结点 // 初始化前char_kinds个结点 for(i = 0; i < char_kinds; ++i) { // 将暂存结点的字符和频度拷贝到树结点 huf_tree[i].uch = tmp_nodes[i].uch; huf_tree[i].weight = tmp_nodes[i].weight; huf_tree[i].parent = 0; } free(tmp_nodes); // 释放字符频度统计的暂存区 // 初始化后node_num-char_kins个结点 for(; i < node_num; ++i) huf_tree[i].parent = 0; CreateTree(huf_tree, char_kinds, node_num); // 创建哈夫曼树 HufCode(huf_tree, char_kinds); // 生成哈夫曼编码 // 写入字符和相应权重，供解压时重建哈夫曼树 outfile = fopen(ofname, "wb"); // 打开压缩后将生成的文件 fwrite((char *)&char_kinds, sizeof(unsigned int), 1, outfile); // 写入字符种类 for(i = 0; i < char_kinds; ++i) { fwrite((char *)&huf_tree[i].uch, sizeof(unsigned char), 1, outfile); // 写入字符（已排序，读出后顺序不变） fwrite((char *)&huf_tree[i].weight, sizeof(unsigned long), 1, outfile); // 写入字符对应权重 } // 紧接着字符和权重信息后面写入文件长度和字符编码 fwrite((char *)&file_len, sizeof(unsigned long), 1, outfile); // 写入文件长度 infile = fopen(ifname, "rb"); // 以二进制形式打开待压缩的文件 fread((char *)&char_temp, sizeof(unsigned char), 1, infile); // 每次读取8bits while(!feof(infile)) { // 匹配字符对应编码 for(i = 0; i < char_kinds; ++i) if(char_temp == huf_tree[i].uch) strcat(code_buf, huf_tree[i].code); // 以8位（一个字节长度）为处理单元 while(strlen(code_buf) >= 8) { char_temp = '\0'; // 清空字符暂存空间，改为暂存字符对应编码 for(i = 0; i < 8; ++i) { char_temp <<= 1; // 左移一位，为下一个bit腾出位置 if(code_buf[i] == '1') char_temp |= 1; // 当编码为"1"，通过或操作符将其添加到字节的最低位 } fwrite((char *)&char_temp, sizeof(unsigned char), 1, outfile); // 将字节对应编码存入文件 strcpy(code_buf, code_buf+8); // 编码缓存去除已处理的前八位 } fread((char *)&char_temp, sizeof(unsigned char), 1, infile); // 每次读取8bits } // 处理最后不足8bits编码 code_len = strlen(code_buf); if(code_len > 0) { char_temp = '\0'; for(i = 0; i < code_len; ++i) { char_temp <<= 1; if(code_buf[i] == '1') char_temp |= 1; } char_temp <<= 8-code_len; // 将编码字段从尾部移到字节的高位 fwrite((char *)&char_temp, sizeof(unsigned char), 1, outfile); // 存入最后一个字节 } // 关闭文件 fclose(infile); fclose(outfile); // 释放内存 for(i = 0; i < char_kinds; ++i) free(huf_tree[i].code); free(huf_tree); }
}//compress
代码如上
不懂的就是压缩后码表的部分
希望各位懂得帮帮忙
huffman树以及码表如
