这是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）放在下一个问题中
目前暂无任何回答
- 0 回答
- 0 关注
- 2184 浏览
添加回答
举报
0/150
提交
取消