基于Huffman编码的C语言解压缩文件程序
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
//极大值用于生成Huffman树
#define MAXSIZE 100000000
//用于生成相应叶子节点Huffman编码的二维字符数组
typedef char* HCode;
//Huffman树节点
typedef struct node
{
int weight;
int data;
int parent,lchild,rchild;
}Node;
//count 叶子节点数的计算 sum_bit 记录被压缩文件编码后的编码总长度
int sum_bit,count;
//Huffman叶子节点，最多不过256个（以字节为单位）
Node huffmanNode[260];
//解压缩的时候记录每次读取到编码（0....1..）
int num[8];
//对应词频信息表的信息，用ASCII值表示
int code[260];
//二维字符数组
HCode *HC;
//统计词频时用于查找是否已经记录过,记录过的话返回下标，没有则返回0
int isInNode(int value)
{
int i = 1;
for(;i<=count;i++)
{
if(huffmanNode[i].data == value)
{
return i;
}
}
return 0;
}
//获取文件词频，记录在Node huffmanNode[260]的节点数组当中
void calWeight(char *file)
{
count = 0;
FILE *f;
int a;
//以二进制方式打开文件，为了读取到换行符
f = fopen(file,"rb");
if(f == NULL)
{
printf("文件不存在！打开失败！");
return ;
}
while(!feof(f))
{
a = fgetc(f);
if(a==EOF) break;
if(!isInNode(a)) //count从1开始计数
{
count++;
huffmanNode[count].weight = 1;
huffmanNode[count].data = a;
}
else
{
int i = isInNode(a);
huffmanNode[i].weight++;
}
}
fclose(f);
}
/*得到待压缩文件的总字节数，权值为几就代表着有多少个字节*/
int getSumBytes()
{
int i=1;
int result = 0;
for(;i<=count;i++)
{
result +=huffmanNode[i].weight;
}
return result;
}
//获取压缩后文件的总bit数
int getSumBits()
{
int i = 1;
int result = 0;
for(;i<=count;i++)
{
result+=huffmanNode[i].weight * strlen(HC[i]);
}
return result;
}
//建立huffman树 根据huffman树的特性,具有n个节点的huffman树的具有2n-1个节点
//n值由全局变量count值来确定，该函数主要用来初始化Huffman树的所有节点信息
void createHufmanTree(Node * huffmanTree)
{
int m = 2*count - 1;
int m1,m2,x1,x2,i,j;
//初始化结点信息，从1--count这count个节点信息为叶子节点的信息
for(i=1;i<=count;i++)
{
huffmanTree[i].data = huffmanNode[i].data;
huffmanTree[i].lchild = -1;
huffmanTree[i].rchild = -1;
huffmanTree[i].parent = -1;
huffmanTree[i].weight = huffmanNode[i].weight;
}
//从count---2*count-1这些节点首先初始化为空
for(;i<=m;i++)
{
huffmanTree[i].data = 0; huffmanTree[i].weight = 0;
huffmanTree[i].lchild = -1; huffmanTree[i].rchild = -1;
huffmanTree[i].parent = -1;
}
//构造huffman树，按照huffman树构建原理
for(i=count+1;i<=m;i++)
{
/*m2,m1分别存储倒数第二小的权值和倒数第一小的权值
x2,x1分别存储倒数第二小的下标和倒数第一小的下标*/
m1 = m2 = MAXSIZE;
x1 = x2 = 0;
for(j=1;j<i;j++)
{
if(huffmanTree[j].parent == -1&&huffmanTree[j].weight <m1)
{
m2 = m1; x2 = x1;
m1 = huffmanTree[j].weight; x1 = j;
}
else if(huffmanTree[j].parent == -1&&huffmanTree[j].weight<m2)
{
m2 = huffmanTree[j].weight;
x2 = j;
}