C語言哈夫曼編碼、譯碼器

1、#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)/函數(shù)voidselect()調(diào)用intj,

2、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個(gè)字符的權(quán)值(均0),構(gòu)造赫夫曼樹HT,并求出n個(gè)字符的赫夫曼編碼HCintm,i,s1,s2,start;/unsignedc,f;intc,f;HuffmanTreep;char*cd;if(n=1)return;/檢測結(jié)點(diǎn)數(shù)是否可以構(gòu)成樹m=2*n-1;HT=(HuffmanTree)malloc(

3、m+1)*sizeof(HTNode);/0號(hào)單元未用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最小的兩個(gè)結(jié)點(diǎn),其序號(hào)分別為si和s2select(HT,i-1,s1,s2);HTs1.parent=HTs2.parent=i;HTi.lchild=s1;HTi.rchild=s2;HTi.weight=HTs1.weight+HTs2.weight;/從葉子到根逆向求每個(gè)字符的赫夫曼編碼HC

4、=(HuffmanCode)malloc(n+1)*sizeof(char*);/分配n個(gè)字符編碼的頭指針向量(0不用)cd=(char*)malloc(n*sizeof(char);/分配求編碼的工作空間cdn-1=0;/編碼結(jié)束符for(i=1;i=n;i+)/逐個(gè)字符求赫夫曼編碼start=n-1;/編碼結(jié)束符位置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);/為第

5、i個(gè)字符編碼分配空間strcpy(HCi,&cdstart);/從cd復(fù)制編碼(串)到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個(gè)字符(字符型)n注意:必須以回車結(jié)束：endl;charbase2;for(i=0;in;i+)cout第i+1個(gè)字符:endl;gets(base);*(z+i)=*base

6、;for(i=0;i=n-1;i+)coutsetw(6)*(z+i);coutn請依次輸入n個(gè)權(quán)值(n注意:必須以回車結(jié)束)：endl;for(i=0;i=n-1;i+)coutendl第i+1num2;*(w+i)=num2;HuffmanCoding(HT,HC,w,n);/打印編碼cout字符對應(yīng)的編碼為: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,

7、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已將字符與對應(yīng)編碼寫入根目錄下文件htmTree.txt中endlendl；/獲取報(bào)文并寫入文件voidInputCode()/coutvv請輸入你想要編碼的字符vvendl;FILE*tobetran；charstrl00;i

8、f(tobetran=fopen(tobetran.txt,w)=NULL)coutvv不能打開文件vvendl;return;cout請輸入你想要編碼的字符endl;gets(str);fputs(str,tobetran);cout獲取報(bào)文成功endl;fclose(tobetran);/編碼函數(shù)voidEncoding()cout下面對目錄下文件tobetran.txt中的字符進(jìn)行編碼endl;FILE*tobetran,*codefile;if(tobetran=fopen(tobetran.txt,rb)=NULL)cout不能打開文件endl;if(codefile=fopen(c

9、odefile.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字符錯(cuò)誤，無法編碼!endl;break;cout編碼工作完成endl編碼寫入目錄下的codefile.txt中endlendl;fclose(tobetran);fclose(codefile);free(tran)

10、;/譯碼函數(shù)voidDecoding()cout下面對根目錄下文件codefile.txt中的字符進(jìn)行譯碼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;

11、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

12、譯碼完成endl內(nèi)容寫入根目錄下的文件txtfile.txt中endlendl;coutwork2;free(work);free(work2);fclose(txtfile);fclose(codef);/打印赫夫曼樹的函數(shù)voidcoprint(HuffmanTreestart,HuffmanTreeHT)if(start!=HT)FILE*TreePrint;if(TreePrint=fopen(TreePrint.txt,a)=NULL)cout創(chuàng)建文件失敗rchild,HT);coutsetw(5*numb)weightweight);coprint(HT+start-lchild,

13、HT);numb-;fclose(TreePrint);voidTree_printing(HuffmanTreeHT,intw)HuffmanTreep;p=HT+w;cout下面打印赫夫曼樹endl;coprint(p,HT);cout打印工作結(jié)束endl;/主函數(shù)voidmain()charchoice;while(choice!=q)cout赫夫曼編碼解碼系統(tǒng)endl;cout1.要初始化赫夫曼鏈表請輸入endl;cout2.要編碼請輸入eendl;cout3.要譯碼請輸入dendl;cout4.要打印編碼請輸入pendl;cout5.要打印赫夫曼樹請輸入fendl;cout6.要離開

14、請輸入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);運(yùn)行結(jié)果：赫夫曼編碼解碼系統(tǒng)1.要初始化赫夫曼鏈表請輸入丫2要編碼請輸入03要譯碼請輸入d4要打印編碼請輸入p5要打印赫夫曼樹請輸入t6要離開請輸入qi下面初始化赫

15、夫曼鏈表數(shù)請輸入結(jié)點(diǎn)的個(gè)n：8請依次輸入8個(gè)字符（字符型）注意:必須以回車結(jié)束：第1個(gè)字符:a第2個(gè)字符:b第3個(gè)字符:c第4個(gè)字符:d第5個(gè)字符:e第6個(gè)字符:f第7個(gè)字符:g第8個(gè)字符:habcdefgh請依次輸入8個(gè)權(quán)值（注意:必須以回車結(jié)束）：第1個(gè)字符的權(quán)值:5第2個(gè)字符的權(quán)值:29x第3個(gè)字符的權(quán)值:7第4個(gè)字符的權(quán)值:8第5個(gè)字符的權(quán)值:14第6個(gè)字符的權(quán)值:23第7個(gè)字符的權(quán)值:3第8個(gè)字符的權(quán)值:11字符對應(yīng)的編碼為:01101011101111110000111010下面將赫夫曼編碼寫入文件已將字符與對應(yīng)編碼寫入根目錄下文件htmTree.txt中赫夫曼編碼解碼系統(tǒng)1.要初

16、始化赫夫曼鏈表請輸入i2要編碼請輸入03要譯碼請輸入d4要打印編碼請輸入p5要打印赫夫曼樹請輸入t6要離開請輸入qi下面初始化赫夫曼鏈表數(shù)請輸入結(jié)點(diǎn)的個(gè)n：27請依次輸入27個(gè)字符（字符型）注意:必須以回車結(jié)束：第1個(gè)字符:第2個(gè)字符:a第3個(gè)字符:bx第4個(gè)字符:c第5個(gè)字符:d第6個(gè)字符:e第7個(gè)字符:f第8個(gè)字符:g第9個(gè)字符:h第10個(gè)字符:i第11個(gè)字符:j第12個(gè)字符:k第13個(gè)字符:l第14個(gè)字符:m第15個(gè)字符:n第16個(gè)字符:o第17個(gè)字符:p第18個(gè)字符:q第19個(gè)字符:r第20個(gè)字符:s第21個(gè)字符:t第22個(gè)字符:u第23個(gè)字符:v第24個(gè)字符:w第25個(gè)字符:第26個(gè)字符:y第27個(gè)字符:zabcdefgmnopqrstz請依次輸入27個(gè)權(quán)值（注意:必須以回車結(jié)束）第1個(gè)字符的權(quán)值:186第2個(gè)字符的權(quán)值:64第3個(gè)字符的權(quán)值:13第4個(gè)字符的權(quán)值:22第5個(gè)字符的權(quán)值:32第6個(gè)字符的權(quán)值:103第7個(gè)字符的權(quán)值:21第8個(gè)字符的權(quán)值:15第9個(gè)字符的權(quán)值:47第10個(gè)字符的權(quán)值:57第11個(gè)字符的權(quán)值:1第12個(gè)字符的權(quán)值:5第13個(gè)字符的權(quán)值:32第14個(gè)字符的權(quán)值:20第15個(gè)字符的權(quán)值:57第16個(gè)字符的權(quán)值:63第17個(gè)字符的權(quán)值:15第18個(gè)字符的權(quán)值:1第19個(gè)字符的權(quán)值:48第20個(gè)字符的權(quán)值:51第21個(gè)字符的權(quán)值:80第22個(gè)字符