《数据结构》
哈夫曼编码与译码
实验报告
题目： 班级： 学号： 姓名： 完成时间：
哈夫曼编码与译码
xxxx xxxxxxxxxxx
xxx
2012年12月19日
一、 程序总体结构 显示系统时间 showtime() 主程序 main 给用户提供选择方式 chioce1() 显示界面告诉用户程序名称 show() 打开文件进行加密 openfile()
退出程序 输入电文进行加密 input() 统计输入(文件中)字母的出现频率 CrW(data,w,count)【fcount(alldata,data,count)】 将输入(文件中)的电文创建成哈夫曼树 CrtHuffmantree(ht,w,n) 将输入(文件中)的电文进行哈夫曼编码 CrtHuffmanCode(ht,hc,n) 输出每一个字母所对应的哈夫曼编码 Printf(hc,n,data,alldata,count) 对输入(文件中)的文字进行哈夫曼加密 showall(hc,alldata,count,data,n)
下面有几个不同的程序供选着参考：
程序源代码:
#include typedef char * * HuffmanCode; void Select(HuffmanTree &HT,int n,int m) {HuffmanTree p=HT; int tmp; for(int j=n+1;j<=m;j++) {int tag1,tag2,s1,s2; tag1=tag2=32767; for(int x=1;x<=j-1;x++) { if(p[x].parent==0&&p[x].weight { if(p[y].parent==0&&y!=s1&&p[y].weight p[j].weight=p[s1].weight+p[s2].weight; } } void HuffmanCoding(HuffmanTree &HT,int n,char *w1,int*w2) { int m=2*n-1; if(n<=1) return; HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); HuffmanTree p=HT; for(int i=1;i<=n;i++) { p[i].data=w1[i-1]; p[i].weight=w2[i]; p[i].parent=p[i].lchild=p[i].rchild=0; } for(;i<=m;i++) { p[i].weight=p[i].parent=p[i].lchild=p[i].rchild=0; } Select(HT,n,m); ofstream outfile; //生成hfmTree文件 outfile.open(\"hfmTree.txt\for (i=1;i<=m;i++) {outfile< cout<<\"初始化结果已保存在hfmTree文件中\\n\"; } void ToBeTree() //将正文写入文件ToBeTree中 { ofstream outfile; outfile.open(\"ToBeTree.txt\ outfile<<\"THIS PROGRAM IS MYFAVORITE\"; outfile.close(); } void Encoding(HuffmanTree &HT,int n) //编码 { HuffmanCode HC; HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); char *cd; cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\\0'; for(int k=1;k<=n;k++) { int start=n-1; for(int c=k,f=HT[k].parent;f!=0;c=f,f=HT[f].parent) { if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; } HC[k]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[k],&cd[start]); } cout<<\"输出哈夫曼编码:\"< if (h%8==0) cout< infile.open(\"ToBeTree.txt\char s[80]; while(!infile.eof()) {infile.getline(s,sizeof(s));} infile.close(); fstream outfile; outfile.open(\"CodeFile.txt\int count=0; for (h=0;s[h]!='\\0';h++) { for(k=1;k<=n;k++) if (s[h]==HT[k].data) { cout< cout<<\"\\n编码结果已保存在文件CodeFile中.\"; cout< int f=2*n-1; fstream infile; infile.open(\"CodeFile.txt\char s[1000]; while(!infile.eof()) {infile.getline(s,sizeof(s));} infile.close(); int i=0; int j=0; fstream outfile; outfile.open(\"TextFile.txt\while(s[i]!='\\0') { f=2*n-1; while(HT[f].lchild!=0)//以f对应的节点的左孩子的值==0作为结束 {if (s[j]=='0') f=HT[f].lchild; else f=HT[f].rchild; j++; } i=j; cout< cout<<\"\\n译码结果已保存在文件TextFile中.\"; cout< infile.open(\"CodeFile.txt\char s[1000]; while(!infile.eof()) {infile.getline(s,sizeof(s)); for(int i=0;s[i]!='\\0';i++) { cout< void main() { int n; int Array[100]; char cArray[100]; HuffmanTree HT; cout<<\"输入n个字符:\"; cin.getline(cArray,100); n=strlen(cArray); cout<<\"一共\"< char x=menu(); while(1) { switch (x) { case 'I':HuffmanCoding(HT,n,cArray,Array);break; case 'E':Encoding(HT,n);break; case 'D':Decoding(HT,n);break; case 'P':Print();break; case 'Q':tag=0;cout<<\"结束\"< cout<<\"y(继续) or n(退出)\"< { cout<<\"请输入功能字符:\"; char c; cin>>c; x=c; } else exit(1); } } 源程序： #include using namespace std; typedef struct //节点结构 { char data; //记录字符值 long int weight; //记录字符权重 unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; //动态分配数组存储哈夫曼树 typedef char * *HuffmanCode; //动态分配数组存储哈夫曼编码表 void Select(HuffmanTree &HT,int i,int &s1,int &s2) //在HT[1...t]中选择parent不为0且权值最小的两个结点，其序号分别为s1和s2 { s1=0;s2=0; int n1=30000,n2=30000; for(int k=1;k<=i;k++) { if(HT[k].parent==0) { if(HT[k].weight zifu= new char[n+1]; weight=new int[n+1]; for(i=1;i<=n;i++)//将待编码的字符放在zifu数组中 { char ch; ch=fin1.get(); zifu[i]=ch; } for(i=1;i<=n;i++)//将带编码字符对应的权值放在weight数组中 { fin2>>weight[i]; } for( i=1;i<=n;i++) { HT[i].data=zifu[i]; HT[i].weight=weight[i]; } for(i=n+1;i<=m;i++) { HT[i].data='@'; } for(i=1;i<=m;i++) { HT[i].parent=HT[i].lchild=HT[i].rchild=0; } for(i=n+1;i<=m;++i) { int s1,s2; Select(HT,i-1,s1,s2); HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2; HT[i].weight=HT[s1].weight+HT[s2].weight; } HC=(HuffmanCode)malloc((n+1)*sizeof(char*));开辟一个求编码的工作空间 char *cd; cd=(char *)malloc(n*sizeof(char));//开辟空间存放权值 cd[n-1]='\\0'; for(i=1;i<=n;i++) { int start=n-1; int c,f; for( c=i, f=HT[i].parent;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码 { if(HT[f].lchild==c) cd[--start]='0';//若是左孩子编为'0' else cd[--start]='1';//若是右孩子编为'1' } HC[i]=(char *)malloc((n-start)*sizeof(char)); //为第i个编码分配空间 strcpy(HC[i],&cd[start]); } delete []cd; //释放工作空间 } void printHuffmanTree(HuffmanTree HT,int n) //显示有n个叶子结点的哈夫曼树的编码表 { ofstream fout(\"hfmtree.txt\"); //将对应字符的的哈弗曼树存入 cout<<\"NUM\"<<\" \"<<\"data\"<<\" \"<<\"weight\"<<\" \"<<\"parent\"<<\" \"<<\"lchild\"<<\" \"<<\"rchlid\"< while((ch=fin.get())!='*') a.push_back(ch); cout<<\"待编码的字符串为：\"; for(int k=0;k 主要程序代码: //HuffmanCode1.h #ifndef HUFFMAMCODE_H #define HUFFMAMCODE_H #include struct HuffmanNode //定义哈夫曼树各结点 { int weight; int parent; int lchild,rchild; int flag; }; class HuffmanCode1 //哈夫曼编码类 { public: char Info[100]; int Start; char Leaf; }; class HuffmanTree1 //建立哈夫曼树类 { private: HuffmanNode *Node; public: int f; HuffmanCode1 *hf; HuffmanTree1(); ~HuffmanTree1(); void TranslatedCode(); void CodeHuf(HuffmanNode a[],HuffmanCode1 b[],int n); void CreateHfmTree(char Str[],int m[],int n); void TransCode(HuffmanCode1 b[],int n) ; void TranslateArtcle(HuffmanCode1 b[],int n) ; }; #endif //HUFFMAMCODE_HHuffmanCode.cpp #include \"iostream\" #include #include\"HuffmanCode1.h\" #include #define MAXDATA 10000 //最长字符串 #define MAXSIZE 150 //最多子叶数 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////第一部分功能（W）实现的代码$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ HuffmanTree1::HuffmanTree1() { Node=NULL; } //将树结点初始化为空 HuffmanTree1::~HuffmanTree1() { delete[] Node; } //释放结点空间 void HuffmanTree1::CreateHfmTree(char Str[],int m[],int n)//建立哈夫曼树 { int i,j,m1,m2,x1,x2; HuffmanNode *HfmNode=new HuffmanNode[2*n-1]; HuffmanCode1 *HfmCode=new HuffmanCode1[n]; for(i=0;i<2*n-1;i++) { HfmNode[i].weight=0; HfmNode[i].parent=0; HfmNode[i].flag=0; HfmNode[i].lchild=-1; HfmNode[i].rchild=-1; } for(i=0;i void HuffmanTree1::CodeHuf(HuffmanNode a[],HuffmanCode1 b[],int n) //对哈夫曼树进行编码 { HuffmanCode1 Hfd; int c,p; for(int i=0;i char s[1000]; int t=0; char ch; cout<<\"*******************************************************************************\"< int i=0,j,m[100],h,k=0; int n=0; cout<<\"*******************************************************************************\"< //main.cpp //#include\"HuffmanCode1.h\" ////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// ///////////第二部分功能实现的代码$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$$ typedef struct //哈弗曼树节点的结构体 { char info; //关联字符信息 unsigned int weight; //每个节点的权职 unsigned int parent, lchild, rchild; }HTNode,*HuffmanTree; typedef char **HuffmanCode; //存储哈弗曼编码 void Select(HuffmanTree HT, int j,int &s1,int &s2) { //选择双亲节点为0，并且最小的两个子叶节点 int i=1,m; while(HT[i].parent!=0) i++; //找第一个双亲节点为0的子叶结点 for(s2=s1=i;i if(HT[i].parent==0 && HT[i].weight else if(HT[i].parent==0 && HT[i].weight>=HT[s1].weight && HT[i].weight<=HT[s2].weight) s2=i; while(HT[i].parent==0 && s1==s2) { m=i; m++; while(HT[m].parent!=0) m++; s2=m; } } } void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, int *w, int n, char *info) { //哈弗曼编码 int i,m; HuffmanTree p; if(n<1) return; m = 2*n-1; HT = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;++i,++p,++w,++info) { //初始化所有已存在的子叶信息 p->info = *info; p->weight = *w; p->parent = 0; p->lchild = 0; p->rchild = 0; }//for for(; i<=m;++i,++p) { //构造所需要的过度根节点 p->weight = 0; p->parent = 0; p->lchild = 0; p->rchild = 0; }//for for(i=n+1;i<=m;++i) { //建立哈弗曼树 int s1,s2; Select(HT,i-1,s1,s2); HT[s1].parent =i; HT[s2].parent =i; HT[i].lchild = s2; HT[i].rchild = s1; HT[i].weight = HT[s1].weight+HT[s2].weight; }//for //哈弗曼编码 HC = (HuffmanCode)malloc((n+1)*sizeof(char *)); char* cd = (char*)malloc(n*sizeof(char)); cd[n-1] = '\\0'; for(i=1;i<=n;++i) { int f; unsigned int c; int start=n-1; for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) { if(HT[f].lchild==c) cd[--start] = '0'; else cd[--start] = '1'; } HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i], &cd[start]); }//for free(cd); }//HuffmanCoding //Y功能实现 输出并保存字符串的二进制编码 void CheckCoding(HuffmanTree HT, HuffmanCode HC, char *strcheck, int m,int k) { ofstream ofs(\"BCode.txt\"); //查询哈弗曼编码信息 int p; for(int i=0; i cout< //对键盘输入的二进制代码进行译码 void HuffmanTranslateCoding(HuffmanTree HT, int n,char*c) { ofstream ofs(\"TransBData.txt\"); //译码过程 int m=2*n-1; int i,j=0; cout<<\"译码翻译得到的文章已保存在“TransBData.txt”中\"< i=m; while(HT[i].lchild && HT[i].rchild) { if(c[j]=='0') i=HT[i].lchild; else if(c[j]=='1') i=HT[i].rchild; j++; } cout< void HuffmanTranslateCoding2(HuffmanTree HT, int n) { ifstream ifs(\"BCode.txt\"); ofstream ofs(\"TransBData2.txt\"); string c; int m=2*n-1; int i,j=0; getline(ifs,c); cout<<\"译码翻译得到的文章已保存在“TransBData2.txt”中\"< i=m; while(HT[i].lchild && HT[i].rchild) { if(c[j]=='0') i=HT[i].lchild; else if(c[j]=='1') i=HT[i].rchild; j++; } cout< cout<<\" ||************************************************************************||\"< ||\"< //main().cpp int main() { int n=0,i=0,k=0,j,h,*w; FILE *fp; char ch2,str[MAXDATA],choose,name[]=\"BData.txt\"; w=new int[MAXSIZE]; char *info; char *strcheck=str; info=new char[MAXSIZE]; char *ch=new char[MAXSIZE]; HuffmanTree HT=new HTNode[MAXSIZE]; HuffmanCode HC=NULL; HuffmanTree1 HuffmanNode; Menushow(); while(1) { cout< cout<<\"*******************************************************************************\"< HuffmanNode.TranslatedCode(); break; case 'B': case 'b': HuffmanNode.TranslateArtcle(HuffmanNode.hf,HuffmanNode.f); case 'D': case 'd': HuffmanTranslateCoding2( HT,n); break; case 'E': case 'e'://进行译码操作 cout<<\"请您输入您要编译的二进制编码: \"< HuffmanTranslateCoding(HT,n,ch); break; case 'T': case 't'://退出系统 return 0; case 'C': case 'c'://进行编码操作 cout<<\"请输入您要编码的字符串：\"< ch2=getchar();//接收上一次键盘输入的换行符 ch2=getchar(); while(ch2!='#') {fputc(ch2,fp); str[n++]=ch2; putchar(str[n-1]); ch2=getchar(); } putchar(10); fclose(fp); cout< //对输入的字符串进行编码 *strcheck=str[0]; cout<<\"您输入的字符串编码为：\"< 程序清单 .cpp #include FILE * f1=fopen(\"d:\\\\pra1.txt\FILE * f2=fopen(\"d:\\\\pra2.txt\FILE * f3=fopen(\"d:\\\\pra4.huf\ int main(){ init(SN); input(f1); // for(int i=0;forest[i]!=NULL;i++) cout< huffman.hufcode(); 逆向// exchange(); 哈夫曼编huffman.savewithhufcode(f1,f2); 原文件// cout< //初始化字符数据库// //读入初始文件的字符 //输出字符及出现次数类 \"< for(i=0;hufNode[i].sig!=NULL;i++){ cout<<\"字符\"< for(int j=0;j f2=fopen(\"d:\\\\pra2.txt\ huffman.hufdecode(f2,f3); //哈夫曼解码// cout< compress(); //查看压缩情况// cout< cout<<\"*谢谢使用*\"< struct signode{ //signode节点，哈夫曼树节点// char c; //字符// int weight; //权重// bool b; //文章中是否出现// signode * parent; signode * left; signode * right; signode(){ //初始化// c=NULL; b=false; weight=0; parent=left=right=NULL; } }; signode SN[256]; signode * forest[256]; //森林数组保存出现的字符// int count=0; //出现字符计数// float memo1=0,memo2=0; //全局变量记录读入字符数和编码的0 1数// void init(signode * sig){ //SN[]数组初始化，输入常见字符// sig[0].c='a';sig[1].c='b';sig[2].c='c'; sig[3].c='d';sig[4].c='e'; sig[5].c='f';sig[6].c='g';sig[7].c='h';sig[8].c='i';sig[9].c='j'; sig[10].c='k';sig[11].c='l';sig[12].c='m';sig[13].c='n';sig[14].c='o'; sig[15].c='p';sig[16].c='q';sig[17].c='r';sig[18].c='s';sig[19].c='t'; sig[20].c='u';sig[21].c='v';sig[22].c='w';sig[23].c='x';sig[24].c='y'; sig[25].c='z'; sig[26].c='A';sig[27].c='B';sig[28].c='C';sig[29].c='D';sig[30].c='E'; sig[31].c='F';sig[32].c='G';sig[33].c='H';sig[34].c='I';sig[35].c='J'; sig[36].c='K';sig[37].c='L';sig[38].c='M';sig[39].c='N';sig[40].c='O'; sig[41].c='P';sig[42].c='Q';sig[43].c='R';sig[44].c='S';sig[45].c='T'; sig[46].c='U';sig[47].c='V';sig[48].c='W';sig[49].c='X';sig[50].c='Y'; sig[51].c='Z'; sig[52].c='0';sig[53].c='1';sig[54].c='2';sig[55].c='3';sig[56].c='4'; sig[57].c='5';sig[58].c='6';sig[59].c='7';sig[60].c='8';sig[61].c='9'; sig[62].c='+';sig[63].c='-';sig[64].c='*';sig[65].c='/';sig[66].c=','; sig[67].c='.';sig[68].c='\\''; sig[69].c='\"';sig[70].c=':';sig[71].c=';'; sig[72].c='<';sig[73].c='>';sig[74].c='=';sig[75].c='?';sig[76].c=' '; sig[77].c='(';sig[78].c=')';sig[79].c='[';sig[80].c=']';sig[81].c='{'; sig[82].c='}';sig[83].c='!';sig[84].c='@';sig[85].c='#';sig[86].c='$'; sig[87].c='%';sig[88].c='^';sig[89].c='&';sig[90].c='\\\\';sig[91].c=10; } void compress(){ //压缩 情况对比// cout<<\"压缩前:\"< int code[100]; //保存哈夫曼编码// int size; bool b; hufnode(){sig=NULL;size=0;b=true;} }; hufnode hufNode[256]; void exchange(){ //调换首尾交换哈夫曼编码// int temp; for(int i=0;hufNode[i].sig!=NULL;i++){ for(int s=0,b=hufNode[i].size-1;s<=b;s++,b--){ temp=hufNode[i].code[s]; hufNode[i].code[s]=hufNode[i].code[b]; hufNode[i].code[b]=temp } } } class HFM{ //哈夫曼类// private: signode * root; //哈夫曼树根// signode * pt; //编码时做哨兵指针// int alleaf; public: HFM(int all){root=pt=NULL;alleaf=all;}//all是森林中树的个数// ~HFM(){} signode * getroot(){return root;} signode * creat(); //创建哈夫曼树// void hufcode(); //编码// void savewithhufcode(FILE * inf,FILE * outf); //用哈弗曼编码存储文件// void hufdecode(FILE* ipf,FILE* opf); //解码// void inorder(signode * sig); int maxc(); //求取哈夫码曼最大长度// }; signode * HFM::creat(){ signode * pp=NULL; for(int i=0;i for(int i=0;forest[i]!=NULL;i++){ //以下三个for循环选出当前森林中的最小两个节点// if(forest[i]->weight for(i=0;forest[i]!=NULL&&i!=min1;i++){ // if(forest[i]->weight for(i=min1+1;forest[i]!=NULL;i++){ // if(forest[i]->weight pp=new signode(); //新生成节点，权值为两最小节点权值之和// pp->left=forest[min1]; pp->right=forest[min2]; forest[min2]->b=true; //为hufcode函数作准备，与此函数无关// pp->weight=forest[min1]->weight+forest[min2]->weight; forest[min1]->parent=pp; forest[min2]->parent=pp; forest[min1]=pp; //新生成节点加入森林for(i=min2;forest[i]!=NULL;i++)forest[i]=forest[i+1]; //min2后的节点依次前移// count--; } root=pp; return pp; } void HFM::hufcode(){ //哈夫曼编码，保存在hufNode节点的数组当中// inorder(root); for(int i=0;hufNode[i].sig!=NULL;i++){ signode * gud=hufNode[i].sig; while(gud->parent!=NULL){ if(gud->parent->left==gud)hufNode[i].code[hufNode[i].size++]=0; else if(gud->parent->right==gud)hufNode[i].code[hufNode[i].size++]=1; gud=gud->parent; } } } void HFM::savewithhufcode(FILE * inf,FILE * outf){ 用哈弗曼编码存储文件// rewind(inf); 回到文件起始防止文件未关闭导致的错误// char ch=fgetc(inf); while(!feof(inf)){ for(int i=0;hufNode[i].sig->c!=ch;i++); if(hufNode[i].sig->c==ch) { for(int k=0;k else if(hufNode[i].code[k]==1){fputc(49,outf);memo2++;} } } ch=fgetc(inf); } } void HFM::inorder(signode * sig){ if(sig->left==NULL&&sig->right==NULL){ hufNode[count++].sig=sig; return ; } else { inorder(sig->left); inorder(sig->right); } } int HFM::maxc(){ int ma=0; 变量// for(int i=0;i // ////48,49分别是字符 //计数 } return ma; } void HFM::hufdecode(FILE* ipf,FILE* opf){ //解码，由哈夫曼码到字符// signode* pt=root; char ch=fgetc(ipf); while(!feof(ipf)){ //判断有无到文件尾/ if(ch=='0'){ if(pt->left==NULL){ cout< if(pt->right==NULL){ cout< ch=fgetc(ipf); } cout< fputc(pt->c,opf); fclose(ipf); fclose(opf); } void input(FILE * f){ char ch=fgetc(f); while(!feof(f)){ //feof(f1)判断文件是否结束，结束返回值为真// putchar(ch); //向屏幕上输出一个字符// memo1++ for(int i=0;SN[i].c!=NULL;i++){ //查看文件内容修改字符权重// if(SN[i].c==ch){ if(SN[i].b==false){ //如果第一次出现就加入森林,否则什么也不做// SN[i].b=true; forest[count++]=&SN[i]; } SN[i].weight++; //增加权重// } } ch=fgetc(f); } cout< #include unsigned char b; //记录字符 long count; //权重 int parent,lch,rch; //定义双亲，左孩子，右孩子 char bits[256]; //存放哈夫曼编码的数组 } header[512],tmp; //头部一要定设置至少512个,因为结点最多可达256,所有结点数最多可达511 unsigned char 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); } return c; } char *code(unsigned char temp,int leafnum) //寻找对应字符的编码串，并返回 { for(int i=0;i void compress(char *infilename,char *outfilename) { long flength=0; //记录压缩前文件长度 long clength=8; //编码从偏移量8记录，统计压缩后编码长度加8 int leafnum; //定义叶子结点 int pointnum; //定义总结点 unsigned char temp; //定义unsigned char类型，暂存文件中字符的中间变量 /*********************************文件中字符频度************************************/ for(int i=0;i<256;i++) { header[i].count=0; //初始化权重 header[i].b=(unsigned char)i; //初始化字符 } ifstream infile(infilename,ios::in|ios::binary); while(infile.peek()!=EOF) { infile.read((char *)&temp,sizeof(unsigned char)); //读入一个字符 header[temp].count++; //统计对应结点字符权重 flength++; //统计文件长度 } infile.close(); //关闭文件 for(i=0;i<256-1;i++) //对结点进行冒泡排序,权重大的放在上面，编码时效率高 for(int j=0;j<256-1-i;j++) if(header[j].count header[j]=header[j+1]; header[j+1]=tmp; } for(i=0;i<256;i++) if(header[i].count==0) break; leafnum=i; //取得哈夫曼树中叶子结点数 pointnum=2*leafnum-1; //取得哈夫曼树中总结点数目 /**********************************根据频度建树*************************************/ long min; //尽量用long，如果文件过大，这里建树可能不是最优树了 int s1,s2; for(i=leafnum;i for(int j=0;j header[s1].parent=i; //填写第一个叶子结点信息 min=999999999; for(j=0;j header[s2].parent=i; header[i].count=header[s1].count+header[s2].count; //填写父结点信息 header[i].lch=s1; header[i].rch=s2; } /*********************************根据哈夫曼树编码**********************************/ char tmp[256]; //定义临时变量，暂存编码 tmp[255]='\\0'; //添加结束标志 int start; int c; //记录当前叶结点下标 int f; //存储父结点的下标 for(i=0;i for(c=i,f=header[i].parent;f!=0;c=f,f=header[f].parent) //对叶结点进行编码 if(header[f].lch==c) tmp[--start]='0'; else tmp[--start]='1'; strcpy(header[i].bits,&tmp[start]); } /************************************对文件进行编码，写入新文件(核心)*********************************/ 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(i=0;i header[i].count=strlen(header[i].bits); //不再设置其他变量,权值这时已无使用价值,可以用相应结点的权值变量记录长度 outfile.write((char *)&header[i].count,sizeof(unsigned char)); //写入长度的ASCII码 if(header[i].count%8==0) bytelen=header[i].count/8; else { bytelen=header[i].count/8+1; strcat(header[i].bits,\"0000000\"); //在编码后面补0，使其最后凑满8的倍数， //超过无妨，可以用bytelen控制好写入字节的长度 } for(int j=0;j outfile.write((char *)&temp,sizeof(unsigned char)); strcpy(header[i].bits,header[i].bits+8); cout<<\"该文件的哈夫曼的编码为:\"< }//compress void ctoa(unsigned char a,char code[]) /*字符转为二进制形式存入8位数组*/ { int n=9; for(int i=0;i { code[n--]=c%2+'0'; c=c/2; } } int strcmp1(char buf[],struct head head[],int n,unsigned char &c) //将buf字符串与header[i].bits[]中匹配，成功后对应的字符由c带回 { for(int i=0;i c=head[i].b; return 1; } return 0; } void strcpy1(char buf[],char a[],int j) //将字符串a中长度为j的部分复制到buf数组中 { for(int i=0;i long flength; //定义原文件长度，从压缩后文件前四字节获取值 long clength; //获取编码长度后的第一偏移量,从压缩文件第五字节开始获取值 int n; //叶子结点数，从编码尾端开始获取 string str; //读取编码到字符串,好进行统一解码 char code[9]; //将字符转为二进制数组形式暂存 unsigned char temp; //读取字符存放此临时变量 long readlen=0; //记录已经读取的长度(读文件解码时用) long writelen=0; //记录已经写入的字节 long clen; //临时变量，读取字符编码对照表时使用 /************************************读入必要的数据 *****************************************************/ void ctoa(unsigned char a,char code[]); //需要调用的函数的声明 ifstream infile(infilename,ios::binary); if(!infile) { cerr<<\"文件打开失败\"< infile.read((char *)&n,sizeof(int)); //读入叶子结点数 /************************************读入编码对照表，放入header[i].bits[]数组中**************************/ infile.seekg(clength+4); //文件指针定位到字符编码对照表的起始 for(int i=0;i infile.read((char *)&header[i].count,sizeof(unsigned char)); //读入编码长度 clen=(int)header[i].count; int diff=clen%8; if(0==clen%8) //计算需要读取多少个字节 clen=clen/8; else clen=clen/8+1; header[i].bits[0]='\\0'; //初始化，方便后面进行连接 for(int j=0;j strcat(header[i].bits,code); //将转换过来的编码进行连接 } int bitlen=strlen(header[i].bits); if(0!=diff) header[i].bits[bitlen-8+diff]='\\0'; }//for(int i=0;i for(i=0;i tmp=header[j]; header[j]=header[j+1]; header[j+1]=tmp; } } } /************************************将编码读入内容，进行解码工作************************************/ readlen=0; writelen=0; ofstream outfile(outfilename,ios::binary|ios::out); //打开编码后文件 if(!outfile) { cerr<<\"输出文件打开失败\"< infile.seekg(8); /* 读取编码，解压连入缓冲区 */ while(1) { while(readlen<(clength-8)&&strlen(buf)<=256) //读满缓冲区 { infile.read((char *)&temp,sizeof(temp)); ctoa(temp,code); //将字节转为数组 strcat(buf,code); readlen++; }//while while(strlen(buf)>=256) //处理缓冲区，直到少于256位，再读满 它 { for(i=0;i outfile.write((char *)&temp,sizeof(unsigned char)); writelen++; strcpy(buf,buf+i+1); //缓冲区前移 break; } }//for if(writelen>=flength) break; //如果写入达到原文件长度，退出 }//while if(readlen>=(clength-8)/*编码长度*/||writelen>=flength) break; //如果写入或者读入编码完毕，退出 }//退出此循环后，还有未解码完成的buf[] //对buf[]缓冲的善后处理 while(writelen if(strcmp1(buf1,header,n,temp)==1) { outfile.write((char *)&temp,sizeof(unsigned char)); writelen++; strcpy(buf,buf+i+1); break; } }//for } infile.close(); //关闭文件 outfile.close(); }//uncompress() void MainMeun() { cout<<\"******************哈夫曼编码/译码器 ********************\"< string contents; char filename[200]; //cout<<\"sfd\"; cout<<\"该文件的内容为：\"< while(!in.eof()) in>>contents; cout< cout<