C语言哈夫曼编码、译码器

#include#include#include#include#include/typedefintTElemType;constintUINT_MAX=1000;typedefstructintweight;intparent,lchild,rchild;HTNode,*HuffmanTree;typedefchar*HuffmanCode;/全局变量HuffmanTreeHT;HuffmanCodeHC;int*w,i,j,n;char*z;intflag=0;intnumb=0;/求赫夫曼编码intmin(HuffmanTreet,inti)/函数voidselect()调用intj,flag;intk=UINT_MAX;/取k为不小于可能的值for(j=1;j=i;j+)if(tj.weights2)j=s1;s1=s2;s2=j;/算法6.12voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn)/w存放n个字符的权值(均0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCintm,i,s1,s2,start;/unsignedc,f;intc,f;HuffmanTreep;char*cd;if(n=1)return;/检测结点数是否可以构成树m=2*n-1;HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode);/0号单元未用for(p=HT+1,i=1;iweight=*w;p-parent=0;p-lchild=0;p-rchild=0;for(;iparent=0;for(i=n+1;i=m;+i)/建赫夫曼树/在HT1i-1中选择parent为0且weight最小的两个结点,其序号分别为si和s2select(HT,i-1,s1,s2);HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/从叶子到根逆向求每个字符的赫夫曼编码HC=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n个字符编码的头指针向量(0不用)cd=(char*)malloc(n*sizeof(char);/分配求编码的工作空间cdn-1=0;/编码结束符for(i=1;i=n;i+)/逐个字符求赫夫曼编码start=n-1;/编码结束符位置for(c=i,f=HTi.parent;f!=0;c=f,f=HTf.parent)/从叶子到根逆向求编码if(HTf.lchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n-start)*sizeof(char);/为第i个字符编码分配空间strcpy(HCi,&cdstart);/从cd复制编码(串)到HCfree(cd);/释放工作空间/初始化赫夫曼链表voidInitialization()flag=1;intnum;intnum2;cout下面初始化赫夫曼链表endlnum;n=num;w=(int*)malloc(n*sizeof(int);z=(char*)malloc(n*sizeof(char);coutn请依次输入n个字符(字符型)n注意:必须以回车结束：endl;charbase2;for(i=0;in;i+)cout第i+1个字符:endl;gets(base);*(z+i)=*base;for(i=0;i=n-1;i+)coutsetw(6)*(z+i);coutn请依次输入n个权值(n注意:必须以回车结束)：endl;for(i=0;i=n-1;i+)coutendl第i+1num2;*(w+i)=num2;HuffmanCoding(HT,HC,w,n);/打印编码cout字符对应的编码为:endl;for(i=1;i=n;i+)/coutvv字符vv*(z+i-l)vv的编码；puts(HCi);/将赫夫曼编码写入文件cout下面将赫夫曼编码写入文件endlendl；FILE*htmTree；charr=,0；if(htmTree=fopen(htmTree.txt,w)=NULL)coutcannotopenfileendl；return；fputs(z,htmTree)；for(i=0；in+l；i+)fprintf(htmTree,%6d,*(w+i)；fputs(r,htmTree)；for(i=l；i=n；i+)fputs(HCi,htmTree)；fputs(r,htmTree)；fclose(htmTree)；cout已将字符与对应编码写入根目录下文件htmTree.txt中endlendl；/获取报文并写入文件voidInputCode()/coutvv请输入你想要编码的字符vvendl;FILE*tobetran；charstrl00;if(tobetran=fopen(tobetran.txt,w)=NULL)coutvv不能打开文件vvendl;return;cout请输入你想要编码的字符endl;gets(str);fputs(str,tobetran);cout获取报文成功endl;fclose(tobetran);/编码函数voidEncoding()cout下面对目录下文件tobetran.txt中的字符进行编码endl;FILE*tobetran,*codefile;if(tobetran=fopen(tobetran.txt,rb)=NULL)cout不能打开文件endl;if(codefile=fopen(codefile.txt,wb)=NULL)cout不能打开文件endl;char*tran;i=99;tran=(char*)malloc(100*sizeof(char);while(i=99)if(fgets(tran,100,tobetran)=NULL)cout不能打开文件endl;break;for(i=0;*(tran+i)!=0;i+)for(j=0;jn)cout字符错误，无法编码!endl;break;cout编码工作完成endl编码写入目录下的codefile.txt中endlendl;fclose(tobetran);fclose(codefile);free(tran);/译码函数voidDecoding()cout下面对根目录下文件codefile.txt中的字符进行译码endl;FILE*codef,*txtfile;if(txtfile=fopen(Textfile.txt,w)=NULL)cout不能打开文件endl;/txtfile=fopen(Textfile.txt,w);if(codef=fopen(codefile.txt,r)=NULL)cout不能打开文件endl;/codef=fopen(codefile.txt,r);char*work,*work2,i2;inti4=0,i,i3;unsignedlonglength=10000;work=(char*)malloc(length*sizeof(char);fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char);i3=2*n-1;for(i=0;*(work+i-1)!=0;i+)i2=*(work+i);if(HTi3.lchild=0)*(work2+i4)=*(z+i3-1);i4+;i3=2*n-1;i-;elseif(i2=0)i3=HTi3.lchild;elseif(i2=1)i3=HTi3.rchild;*(work2+i4)=0;fputs(work2,txtfile);cout译码完成endl内容写入根目录下的文件txtfile.txt中endlendl;coutwork2;free(work);free(work2);fclose(txtfile);fclose(codef);/打印赫夫曼树的函数voidcoprint(HuffmanTreestart,HuffmanTreeHT)if(start!=HT)FILE*TreePrint;if(TreePrint=fopen(TreePrint.txt,a)=NULL)cout创建文件失败rchild,HT);coutsetw(5*numb)weightweight);coprint(HT+start-lchild,HT);numb-;fclose(TreePrint);voidTree_printing(HuffmanTreeHT,intw)HuffmanTreep;p=HT+w;cout下面打印赫夫曼树endl;coprint(p,HT);cout打印工作结束endl;/主函数voidmain()charchoice;while(choice!=q)cout赫夫曼编码解码系统endl;cout1.要初始化赫夫曼链表请输入endl;cout2.要编码请输入eendl;cout3.要译码请输入dendl;cout4.要打印编码请输入pendl;cout5.要打印赫夫曼树请输入fendl;cout6.要离开请输入qchoice;switch(choice)casei:Initialization();break;casew:InputCode();break;casee:Encoding();break;cased:Decoding();break;caset:Tree_printing(HT，2*n-1);break;caseq:default:coutinputerrorendl;free(z);free(w);free(HT);运行结果：赫夫曼编码解码系统1.要初始化赫夫曼链表请输入丫2要编码请输入03要译码请输入d4要打印编码请输入p5要打印赫夫曼树请输入t6要离开请输入qi下面初始化赫夫曼链表数请输入结点的个n：8请依次输入8个字符（字符型）注意:必须以回车结束：第1个字符:a第2个字符:b第3个字符:c第4个字符:d第5个字符:e第6个字符:f第7个字符:g第8个字符:habcdefgh请依次输入8个权值（注意:必须以回车结束）：第1个字符的权值:5第2个字符的权值:29第3个字符的权值:7第4个字符的权值:8第5个字符的权值:14第6个字符的权值:23第7个字符的权值:3第8个字符的权值:11字符对应的编码为:01101011101111110000111010下面将赫夫曼编码写入文件已将字符与对应编码写入根目录下文件htmTree.txt中赫夫曼编码解码系统1.要初始化赫夫曼链表请输入i2要编码请输入03要译码请输入d4要打印编码请输入p5要打印赫夫曼树请输入t6要离开请输入qi下面初始化赫夫曼链表数请输入结点的个n：27请依次输入27个字符（字符型）注意:必须以回车结束：第1个字符:第2个字符:a第3个字符:bx第4个字符:c第5个字符:d第6个字符:e第7个字符:f第8个字符:g第9个字符:h第10个字符:i第11个字符:j第12个字符:k第13个字符:l第14个字符:m第15个字符:n第16个字符:o第17个字符:p第18个字符:q第19个字符:r第20个字符:s第21个字符:t第22个字符:u第23个字符:v第24个字符:w第25个字符:第26个字符:y第27个字符:zabcdefgmnopqrstz请依次输入27个权值（注意:必须以回车结束）第1个字符的权值:186第2个字符的权值:64第3个字符的权值:13第4个字符的权值:22第5个字符的权值:32第6个字符的权值:103第7个字符的权值:21第8个字符的权值:15第9个字符的权值:47第10个字符的权值:57第11个字符的权值:1第12个字符的权值:5第13个字符的权值:32第14个字符的权值:20第15个字符的权值:57第16个字符的权值:63第17个字符的权值:15x第18个字符的权值:1第19个字符的权值:48第20个字符的权值:51第21个字符的权值:80第22个字符的权值:23第23个字符的权值:8第24个字符的权值:18第25个字符的权值:1第26个字符的权值:16第27个字符的权值:1字符对应的编码为:11010101001000001010110010111110100101000001101111011100111101101011111111101111000100110111101110100100011111000011111101011110011110111101001111111011111下面将赫夫曼编码写入文件已将字符与对应编码写入根目录下文件htmTree.txt中