#ifndef HAFFMANTREE_H_INCLUDED
#define HAFFMANTREE_H_INCLUDED
/**
* Haffman树的顺序存储
* 哈夫曼编码压缩文件的主要思路:
* 1. 读取某个文本文件, 统计文件中各个字符出现的次数作为权重
* 2. 构建哈夫曼树, 生成每个字符对应的编码, 然后将编码保存到压缩文件中
* 3. 文件解压缩实际就是将压缩文件翻译过来再保存到解压缩文件的过程
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 256
#define HALF_MAX MAX_SIZE / 2
#define ASCII_SIZE 128 // ASCII码的数量0~127个字符
/** 哈夫曼树的结点 */
typedef struct haffNode
{
char data; // 用来存放结点字符的数据域
int weight; // 权重
struct haffNode * leftChild;
struct haffNode * rightChild;
} HaffNode;
/** 以顺序结构存储的树节点 - 编码解码的字符映射表 */
HaffNode node[MAX_SIZE];
/** 用来保存所有左孩子节点的数组*/
HaffNode left[HALF_MAX];
/** 用来保存所有右孩子节点的数组*/
HaffNode right[HALF_MAX];
/** 使用二维数组来存储字符的哈夫曼编码, 其中第一维的下标就是这个字符的ASCII码*/
char code[MAX_SIZE][HALF_MAX];
// char code[][] = {
// "00", "10", "1101", ......
// };
/**
* 构造哈夫曼树
* @param node 结点数组
* @param length 节点数组的长度
*/
void CreateHaffmanTree(HaffNode * node, int length);
/** 冒泡排序, 默认以权值大小降序排列*/
void SortHaffmanNode(HaffNode * node, int length);
/**
* 编码过程(压缩)
* @param node 结点数组
* @param tempCode 编码后的字符数组(keepCode)
* @param index 当前字符数组下标
*/
void Coding(HaffNode * node, char * tempCode, int index);
/** 解码过程 flag - 0/1 标志 */
HaffNode * unzip(HaffNode * node, int flag);
#endif // HAFFMANTREE_H_INCLUDED
#include "HaffmanTree.h"
/**
* 构造哈夫曼树
* @param node 哈夫曼树的(根)节点
* @param length 节点数组的长度
*/
void CreateHaffmanTree(HaffNode * node, int length)
{
if(length <= 1)
{
return ;
}
SortHaffmanNode(node, length);
// 构建一个以node数组最后两个结点组成的父节点
HaffNode parent; // 声明一个父节点
left[length] = node[length - 1]; // 排序后, length-1就是权重最小的结点
right[length] = node[length - 2]; // length-2就是权重次小的结点
parent.weight = left[length].weight + right[length].weight;
parent.leftChild = &left[length];
parent.rightChild = &right[length];
// parent 结点的data不用赋值
// 将倒数第二位替换为parent结点, 数组长度减一, 递归创建哈夫曼树
node[length - 2] = parent;
CreateHaffmanTree(node, length - 1);
}
/**
* 编码过程(压缩)
* @param node 结点数组
* @param tempCode 编码后的字符数组(keepCode)
* @param index 当前字符数组下标
*/
void Coding(HaffNode * node, char * tempCode, int index)
{
if(!node) return ;
// 处理叶节点 - 所有的字符结点都是叶子结点
if(node->leftChild == NULL || node->rightChild == NULL)
{
// 将编码赋值到编码数组中去
tempCode[index] = ' ';
strcpy(code[node->data - 0], tempCode);
return ;
}
// 左分支编码为'0', 右分支编码为'1'
tempCode[index] = '0';
Coding(node->leftChild, tempCode, index + 1);
tempCode[index] = '1';
Coding(node->rightChild, tempCode, index + 1);
}
/** 解码过程 flag - 0/1 标志 */
HaffNode * unzip(HaffNode * node, int flag)
{
if(flag == 0)
{
return node->leftChild;
}
else if(flag == 1)
{
return node->rightChild;
}
return NULL;
}
/** 冒泡排序, 默认以权值大小降序排列*/
void SortHaffmanNode(HaffNode * node, int length)
{
HaffNode tempNode;
for(int i = 0; i < length - 1; ++ i)
{
for(int j = 0; j < length - i - 1; ++ j)
{
if(node[j].weight < node[j + 1].weight)
{
tempNode = node[j];
node[j] = node[j + 1];
node[j + 1] = tempNode;
}
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include "HaffmanTree.h"
int main()
{
unsigned char saveChar = 0; // 保存到二进制文件的无符号字符
unsigned char tempChar;
printf("使用哈夫曼树实现文本文件的压缩: (暂时只支持英文文件)
");
FILE * inputFile = fopen("pride-and-prejudice.txt", "r"); // 待解码文件
FILE * zipedFile = fopen("ziped.txt", "wb"); // 编码压缩后的文件
int fileLength = 0; // 文件中存放的字符个数
// 存放0-127个字符出现的次数 - 权数组
int asciiCount[ASCII_SIZE] = {0};
// 读取待编码的文件, 统计各字符出现的次数
char readChar;
// 逐字符读取文件
while((readChar = fgetc(inputFile)) != EOF)
{
fileLength ++;
// 读取到的字符就作为asciiCount数组的下标
asciiCount[readChar - 0] ++;
}
int num = 0; // 节点数量(计数器)
for(int i = 0; i < ASCII_SIZE; ++ i)
{
if(asciiCount[i] != 0)
{
node[num].data = i;
node[num].weight = asciiCount[i];
num ++;
}
}
// 创建哈夫曼树
CreateHaffmanTree(node, num);
// 进行哈夫曼编码
char tempCode[HALF_MAX];
Coding(node, tempCode, 0);
// 逐位将编码保存到文件zipedFile中
num = 0;
fseek(inputFile, 0L, 0); // 文件指针复位
int zipedLength = 0; // 压缩后的字符数量
// 遍历读取到的这个字符编码("10", "111", "1101" ......)
while((readChar = fgetc(inputFile)) != EOF)
{
for(int i = 0; i < strlen(code[readChar - 0]); ++ i)
{
saveChar |= code[(int)readChar][i] - '0';
num ++;
if(num == 8)
{ // 每8位写入一次文件
fwrite(&saveChar, sizeof(unsigned char), 1, zipedFile);
zipedLength ++;
num = 0;
saveChar = 0;
}
else
{
saveChar <<= 1;
}
}
}
// 如果最后剩余的编码不足8位, 就移动到最左端, 凑够8位
if(num < 8)
{
saveChar = saveChar << (8 - num);
fwrite(&saveChar, sizeof(unsigned char), 1, zipedFile);
zipedLength ++;
saveChar = 0;
}
fclose(inputFile);
fclose(zipedFile);
printf("压缩成功
压缩前字符个数: %d 压缩后字符个数: %d
", fileLength, zipedLength);
printf("压缩比: %.2f%%
", (double)zipedLength / fileLength * 100);
printf("
使用哈夫曼树实现解压缩:
");
zipedFile = fopen("ziped.txt", "rb");
FILE * resultFile = fopen("result.txt", "w");
num = 0; // 计数器清零
HaffNode * currNode = &node[0];
while(fread(&readChar, sizeof(unsigned char), 1, zipedFile))
{
if(fileLength == num) break;
// 遍历readChar中的每个二进制数字
for(int i = 0; i < 8; ++ i)
{
tempChar = readChar & 128; // 取readChar得最高位
tempChar >>= 7;
readChar <<= 1; // 因为最高位已经被取, 所以左移1位
currNode = unzip(currNode, tempChar - 0);
// 判断叶节点
if(currNode->leftChild == NULL || currNode->rightChild == NULL)
{
fprintf(resultFile, "%c", currNode->data);
num ++;
currNode = &node[0];
}
}
}
fclose(zipedFile);
fclose(resultFile);
printf("解压缩完成, 请查看文件: result.txt
");
return 0;
}
本程序只支持ASCII码, 文件均为英文文档