1、實(shí)驗(yàn)報(bào)告1、實(shí)驗(yàn)?zāi)康模?1)理解哈夫曼樹(shù)的含義和性質(zhì)。(2)掌握哈夫曼樹(shù)的存儲(chǔ)結(jié)構(gòu)以及描述方法。(3)掌握哈夫曼樹(shù)的生成方法。(4)掌握哈夫曼編碼的一般方法，并理解其在數(shù)據(jù)通訊中的應(yīng)用。2、實(shí)驗(yàn)內(nèi)容：哈夫曼樹(shù)與哈弗曼編碼、譯碼a.問(wèn)題描述：哈夫曼問(wèn)題的提出可以參考教材P.145.利用哈弗曼編碼進(jìn)行通信可以大大提高通信利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼。b.算法提示：參見(jiàn)教材P.147-148算法6.12、6.13的描述。3、實(shí)驗(yàn)要求：建立哈夫曼樹(shù)，實(shí)現(xiàn)編碼，譯碼。.初始化（Initialization）。

2、從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹(shù)，并將它存于文件hfmTree中。.編碼（Encoding）。利用已建好的哈夫曼樹(shù)（如不在內(nèi)存，則從文件hfmTree中讀入），對(duì)文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。.譯碼（Decoding )。利用已建好的哈夫曼樹(shù)將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。.輸出代碼文件（Print）。將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件CodePrint中。.輸出哈夫曼樹(shù)（TreePrinting）。將已在內(nèi)存中的哈夫曼

3、樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件TreePrint中。測(cè)試數(shù)據(jù)：設(shè)權(quán)值 c= (a, b, c, d , e, f, g, h)w=（5，29，7，8，14，23，3，11），n=8。 按照字符0或1確定找左孩子或右孩子，則權(quán)值對(duì)應(yīng)的編碼為： 5：0001，29：11，7：1110，8：1111 14：110，23：01，3：0000，11：001。四實(shí)驗(yàn)代碼#include #include #include #include #include typedef struct int weight,K; int parent,lchild,rch

4、ild;HTNode,* HuffmanTree;typedef char *HuffmanCode;char str50;int wa50; HuffmanTree HT; HuffmanCode HC; int w50,i,j,n=8; char z50; int flag=0; int numb=0;/ -求哈夫曼編碼- struct cou char data; int count;cou50;void select(HuffmanTree HT,int j,int *s1,int *s2)int i;/找weight最小的結(jié)點(diǎn)for (i=1;i=j;i+) if (HTi.pare

5、nt=0) *s1=i;break;for (;i=j;i+) if (HTi.parent=0)&(HTi.weightHT*s1.weight) *s1=i; HT*s1.parent=1;/找weight次小的結(jié)點(diǎn)for (i=1;i=j;i+) if (HTi.parent=0) *s2=i;break;for (;i=j;i+) if (HTi.parent=0)&(i!=*s1)&(HTi.weightHT*s2.weight) *s2=i; / -算法6.12-void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,in

6、t n) int m,i,s1,s2,start; int c,f; HuffmanTree p; char *cd; if(n=1) return;/檢測(cè)結(jié)點(diǎn)數(shù)是否可以構(gòu)成樹(shù) m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT+1,i=1;iweight=wai-1; p-parent=0; p-lchild=0; p-rchild=0; for(;iparent=0; for(i=n+1;i=m;+i) / 建哈夫曼樹(shù) select(HT,i-1,&s1,&s2); HTs1.parent=HTs2.parent=i;

7、 HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; HC=(HuffmanCode)malloc(n+1)*sizeof(char*); 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; else cd-start=1; HCi=(char*)malloc(n-start)*size

8、of(char); strcpy(HCi,&cdstart); free(cd); /-獲取報(bào)文并寫(xiě)入文件-int InputCode() FILE *tobetran;int i=0; if(tobetran=fopen(tobetran.txt,w)=NULL) printf(不能打開(kāi)文件n); return 0; printf(請(qǐng)輸入你想要編碼的字符n);scanf(%s,&str); fputs(str,tobetran); printf(請(qǐng)輸入你相應(yīng)編碼的權(quán)值n);for(i=0;istrlen(str);i+)scanf(%d,&wai); while(wai!=0) fprint

9、f(tobetran,%d,wai+); printf(獲取報(bào)文成功n); fclose(tobetran); return strlen(str);/-初始化哈夫曼鏈表-void Initialization() int a,k,flag,len; a=0; len=InputCode(); for(i=0;ik) if(stri=strk) a+; flag=0; k+; if(flag=0) break; if(flag) for(j=i+1;jlen;j+) if(stri=strj) +coui-a.count; n=len-a; for(i=0;in;i+) printf(%c,c

10、oui.data); printf( ); printf(%dn,coui.count); for(i=0;i=n;i+) *(z+i)=coui.data; *(w+i)=coui.count; HuffmanCoding(HT,HC,w,8);/-打印編碼- printf(字符對(duì)應(yīng)的編碼為n:); for(i=1;i=n;i+) puts(HCi); /-將哈夫曼編碼寫(xiě)入文件-printf(下面將哈夫曼編碼寫(xiě)入文件n); FILE *htmTree; char r= ,0; if(htmTree=fopen(htmTree.txt,w)=NULL) printf(can not open

11、filen); return; fputs(z,htmTree); for(i=0;in+1;i+) fprintf(htmTree,%6d,*(w+i); fputs(r,htmTree); for(i=1;i=n;i+) fputs(HCi,htmTree); fputs(r,htmTree); fclose(htmTree); printf(已將字符與對(duì)應(yīng)編碼寫(xiě)入根目錄下文件htmTree.txt中n);/-編碼函數(shù)-void Encoding() printf(下面對(duì)目錄下文件tobetran.txt中的字符進(jìn)行編碼n); FILE *tobetran,*codefile; if(to

12、betran=fopen(tobetran.txt,rb)=NULL) printf(不能打開(kāi)文件n); if(codefile=fopen(codefile.txt,wb)=NULL) printf(不能打開(kāi)文件n); char *tran; i=99; tran=(char*)malloc(100*sizeof(char); while(i=99) if(fgets(tran,100,tobetran)=NULL) printf(不能打開(kāi)文件n); break; for(i=0;*(tran+i)!=0;i+) for(j=0;jn) printf(字符錯(cuò)誤，無(wú)法編碼!n); break;

13、 printf(編碼工作完成,編碼寫(xiě)入目錄下的codefile.txt中n); fclose(tobetran); fclose(codefile); free(tran);/-譯碼函數(shù)-void Decoding() printf(下面對(duì)根目錄下文件codefile.txt中的字符進(jìn)行譯碼n); FILE *codef,*txtfile; if(txtfile=fopen(txtfile.txt,w)=NULL) printf(不能打開(kāi)文件n); if (codef=fopen(codefile.txt,r)=NULL) printf(不能打開(kāi)文件n); char *work,*work2,

14、i2; int i4=0,i,i3; unsigned long length=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-; else if(i2=0) i3=HTi3.lchild; else

15、if(i2=1) i3=HTi3.rchild; *(work2+i4)=0; fputs(work2,txtfile); printf(譯碼完成n); printf(內(nèi)容寫(xiě)入根目錄下的文件txtfile.txt中n); free(work); free(work2); fclose(txtfile); fclose(codef);/-打印編碼的函數(shù)-void Code_printing() printf(下面打印根目錄下文件CodePrin.txt中編碼字符); FILE * CodePrin,* codefile; if(CodePrin=fopen(CodePrin.txt,w)=NUL

16、L) printf(不能打開(kāi)文件n); return; if(codefile=fopen(codefile.txt,r)=NULL) printf(不能打開(kāi)文件n); return; char *work3; work3=(char*)malloc(51*sizeof(char); do if(fgets(work3,51,codefile)=NULL) printf(不能讀取文件n); break; fputs(work3,CodePrin); puts(work3); while(strlen(work3)=50); free(work3); printf(打印工作結(jié)束n); fclos

17、e(CodePrin); fclose(codefile);/-打印譯碼函數(shù)-void Code_printing1() Printf(下面打印根目錄下文件txtfile.txt中譯碼字符); FILE * CodePrin1,* txtfile; if(CodePrin1=fopen(CodePrin1.txt,w)=NULL) printf(不能打開(kāi)文件n); return; if(txtfile=fopen(txtfile.txt,r)=NULL) printf(不能打開(kāi)文件n); return; char *work5; work5=(char*)malloc(51*sizeof(ch

18、ar); do if(fgets(work5,51,txtfile)=NULL) printf(不能讀取文件n); break; fputs(work5,CodePrin1); puts(work5); while(strlen(work5)=50); free(work5); printf(打印工作結(jié)束n); fclose(CodePrin1); fclose(txtfile);/-打印哈夫曼樹(shù)的函數(shù)-void coprint(HuffmanTree start,HuffmanTree HT) if(start!=HT) FILE * TreePrint; if(TreePrint=fope

19、n(TreePrint.txt,a)=NULL) printf(創(chuàng)建文件失敗n); return; numb+; coprint(HT+start-rchild,HT); printf(%d,setw(5*numb); printf(%d,start-weight); fprintf(TreePrint,%dn,start-weight); coprint(HT+start-lchild,HT); numb-; fclose(TreePrint); void Tree_printing(HuffmanTree HT,int w) HuffmanTree p; p=HT+w; printf(下面打印哈夫曼樹(shù)n); coprint(p,HT); printf(打印工作結(jié)束n);/-主函數(shù)-void main() char choice;printf(*n); printf(歡迎使用哈夫曼編碼解碼系統(tǒng)n); printf(*n); printf(1)要初始化哈夫曼鏈表請(qǐng)輸入in); printf(2)編碼請(qǐng)輸