这是Huffman.cpp文件
// Huffman.cpp: implementation of the Huffman class.
//
//////////////////////////////////////////////////////////////////////
#include "Huffman.h"
#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
#include <iomanip>
//#include <climits>
using namespace std;
//////////////////////////////////////////////////////////////////////
// Construction/Destruction
//////////////////////////////////////////////////////////////////////
//(1)
//从文件(text.txt)读入原文
void Huffman::ReadTextFromFile(const char *infilename)
{
flength = 0;
unsigned char temp; //定义unsigned char类型，暂存文件中字符的中间变量
for (int i=0; i<256; i++)
{
treeNode[i].weight = 0;
treeNode[i].ch=(unsigned char)i;
}
ifstream infile(infilename,ios::in|ios::binary);
while(infile.peek()!=EOF) //peek()方法预读取下一个字符（不管是何符号）
{
infile.read((char *)&temp,sizeof(unsigned char)); //读入一个字符
/*
由代码来看，infile 是一个记录式文件的输入流，以二进制打开。
这条语句的作用就是以二进制形式从文件读入一个 unsigned char 的信息。
(char*)&temp这是获取 unsigned char 的首地址，sizeof(unsigned char) 是获取 unsigned char 的大小，
read 函数将从文件中读入相应大小的数据放入该地址
*/
treeNode[temp].weight++; //统计对应结点字符权重
flength++; //统计文件长度
}
infile.close(); //关闭文件
// for (int a=0; a<256; a++)
// cout << treeNode[a].weight << endl;
}
/*
int Huffman::compare(const void *a,const void *b)
{
struct node *p1 = (struct node *)a;
struct node *p2 = (struct node *)b;
return p1->weight < p1->weight;
}
*/
void Huffman::sortNode()
{
for(int i=0;i<256-1;i++) //对结点进行冒泡排序,权重大的放在上面，编码时效率高
for(int j=0;j<256-1-i;j++)
if(treeNode[j].weight<treeNode[j+1].weight)
{
tempNode=treeNode[j];
treeNode[j]=treeNode[j+1];
treeNode[j+1]=tempNode;
}
}
void Huffman::display()
{
leafnum = 0;
sortNode();
for(int i=0;i<256;i++)
{
if(treeNode[i].weight == 0)
break;
}
leafnum = i; //取得哈夫曼树中叶子结点数
pointnum = 2*leafnum - 1; //取得哈夫曼树中总结点数目
// cout << leafnum << endl;
// for (int a=0; a<256; a++)
// cout << treeNode[a].weight << endl;
// cout << pointnum << endl;
}
void Huffman::MakeCharMap()
{
cout << "构造Huffman树中...";
/*********************************根据哈夫曼树编码**********************************/
display();
long min;
int s1,s2;
for(int i=leafnum;i<pointnum;i++)
{
min = treeNode[0].weight;
for(int j=0; j<i ;j++) //挑权重最小的一个
if(treeNode[j].parent == -1 && treeNode[j].weight<=min)
{
min=treeNode[j].weight;
s1=j;
}
treeNode[s1].parent = i; //填写第一个叶子结点信息
min = treeNode[0].weight;
for(j=0; j<i; j++) //挑权重最小的第二个
if(treeNode[j].parent == -1 && treeNode[j].weight<=min)
{
min=treeNode[j].weight;
s2=j;
}
treeNode[s2].parent=i;
treeNode[i].weight=treeNode[s1].weight + treeNode[s2].weight; //填写父结点信息
treeNode[i].lchild=s1;
treeNode[i].rchild=s2;
}
//从叶子到根节点逆向求每个字符的哈弗曼编码
char tmp[256]; //定义临时变量，暂存编码
tmp[255]='\0'; //添加结束标志
int start;
int c; //记录当前叶结点下标
int f; //存储父结点的下标
for(int k=0; k<leafnum; k++)
{
start=255; //另开始等于数组最后位
for(c=k,f=treeNode[k].parent;f!=0;c=f,f=treeNode[f].parent) //对叶结点进行编码
{
if(treeNode[f].lchild == c)
tmp[--start]='0';
else
tmp[--start]='1';
}
strcpy(treeNode[k].bits,&tmp[start]);
}
}
/************************************对文件进行编码，写入新文件(核心)*********************************/
void Huffman::compressText(const char *infilename,const char *outfilename)
{
long clength=8; //编码从偏移量8记录，统计压缩后编码长度加8
unsigned char temp; //定义unsigned char类型，暂存文件中字符的中间变量
ifstream infile;
ofstream outstream;
infile.open(infilename,ios::in|ios::binary); //打开待压缩的文件
infile.clear(); //把文件清零
infile.seekg(0); //把文件指针置为开头处
ofstream outfile(outfilename,ios::out|ios::binary); //打开压缩后将生成的文件
outfile.write((char *)&flength,sizeof(long)); //写入原文件长度
char buf[513]="\0"; //初始化编码缓冲区
outfile.seekp(8); //指针定向偏移量8
while(infile.peek()!=EOF)
{
infile.read((char *)&temp,sizeof(unsigned char)); //读入字符
// strcat(buf,code(temp,leafnum)); //检索出字符对应编码，连到buf[]中
while(strlen(buf) >= 8) //当buf中字符长度大于8时，一直处理写入，直至小于8
{
temp=ctoa(buf); //上面临时变量已经完成使命，可以赋新值了
outfile.write((char *)&temp,sizeof(unsigned char)); //转成二进制写入
clength++; //统计代码结尾偏移加1,用于找到叶子结点位置
strcpy(buf,buf+8); //字符串前移八位
} //当此循环结束时，表示buf[]中已经小于8了，没到文件末尾，读下一个，继续，否则退出
} //while 此层循环退出时，表示已到末尾,再判断buf中是否写完，没写完，连满至少8个字符，再写一个字节，就够了
if(strlen(buf)>0)
{
strcat(buf,"0000000");
temp=ctoa(buf); //前八位转成二进制形式
outfile.write((char *)&temp,sizeof(unsigned char));
clength++; //统计代码结尾偏移加1,用于找到叶子结点位置
}
outfile.seekp(4);
outfile.write((char *)&clength,sizeof(long)); //写入文件中将记录叶子结点位置
infile.close();
long bytelen; //记录编码以二进制存储时需要占多少个字节
outfile.clear();
outfile.seekp(clength); //将文件指针移到编码后面的第一位置，在此处记录叶子结点数
outfile.write((char *)&leafnum,sizeof(long)); //写入叶子结点数
for(int i=0; i<leafnum; i++)
{
outfile.write((char *)&treeNode[i].ch,sizeof(unsigned char)); //写入字符
treeNode[i].weight = strlen(treeNode[i].bits); //不再设置其他变量,权值这时已无使用价值,可以用相应结点的权值变量记录长度
outfile.write((char *)&treeNode[i].weight,sizeof(unsigned char)); //写入长度的ASCII码
if(treeNode[i].weight%8==0)
bytelen = treeNode[i].weight/8;
else
{
bytelen = treeNode[i].weight/8+1;
strcat(treeNode[i].bits,"0000000"); //在编码后面补0，使其最后凑满8的倍数，
//超过无妨，可以用bytelen控制好写入字节的长度
}
for(int j=0;j<bytelen;j++)
{
temp=ctoa(treeNode[i].bits);
outfile.write((char *)&temp,sizeof(unsigned char));
strcpy(treeNode[i].bits,treeNode[i].bits+8);
}
} //此循环结束后就完成了编码对照表的写入
}
char * Huffman::code(unsigned char temp,int leafnum/*叶子节点*/) //寻找对应字符的编码串，并返回
{
for(int i=0;i<leafnum;i++)
{
if(temp == treeNode[i].ch)
return treeNode[i].bits;
}
return NULL;
}
unsigned char Huffman::ctoa(char a[]) /*将数组的前八位转成二进制形式比特位*/
{
unsigned char c=0;
for(int i=0;i<8;i++)
{
if(a[i]!=0)
c = c+(int)(a[i]-'0')*pow(2,8-1-i); //这里的pow(x,y)是求x的y次方
}
return c;
}
void Huffman::ctoa(unsigned char a,char code[]) /*字符转为二进制形式存入8位数组*/
{
int n=9;
for(int i=0;i<n;i++) code[i]='0'; //整个字符串初始化
code[n-1]='\0'; //添加结束标志
n=n-2;
int c=(int)a;
while(c>0)
{
code[n--]=c%2+'0';
c=c/2;
}
}
int Huffman::strcmp1(char buf[],huffmanNode head[],int n,unsigned char &c) //将buf字符串与treeNode[i].bits[]中匹配，成功后对应的字符由c带回
{
for(int i=0;i<n;i++)
if(strcmp(buf,head[i].bits)==0)
{
c=head[i].ch;
return 1;
}
return 0;
}
void Huffman::strcpy1(char buf[],char a[],int j) //将字符串a中长度为j的部分复制到buf数组中
{
for(int i=0;i<j;i++)
buf[i]=a[i];
buf[i]='\0';
}
void Huffman::decompressText(char *infilename,char *outfilename)
{
long flength; //定义原文件长度，从压缩后文件前四字节获取值
long clength; //获取编码长度后的第一偏移量,从压缩文件第五字节开始获取值
int n; //叶子结点数，从编码尾端开始获取
string str; //读取编码到字符串,好进行统一解码
char code[9]; //将字符转为二进制数组形式暂存
unsigned char temp; //读取字符存放此临时变量
long readlen=0; //记录已经读取的长度(读文件解码时用)
long writelen=0; //记录已经写入的字节
long clen; //临时变量，读取字符编码对照表时使用
因为不能上传这么多代码，我把部分（Huffman.cpp）的文件和头文件（Huffman.h）和main（demo.cpp）放在下一个问题中
相关分类