哈夫曼編譯碼器教學(xué)規(guī)劃報(bào)告(完全版)

1、XXX 學(xué)院 本科數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)總結(jié)報(bào)告設(shè)計(jì)題目 ： 實(shí)驗(yàn)一、哈夫曼編 / 譯碼器學(xué)生姓名 ：XXX系別：XXX專業(yè)：XXX班級(jí)：XXX學(xué)號(hào)：XXX指導(dǎo)教師 ：XXXXXX2012年6月21日XXX學(xué)院課程設(shè)計(jì)任務(wù)書題目、赫夫曼編譯碼器專業(yè)、班級(jí)XXX 學(xué)號(hào) XXX 姓名 XXX主要內(nèi)容、基本要求、主要參考資料等:1. 主要內(nèi)容利用哈夫曼編碼進(jìn)行信息通信可大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼；在接收端將傳 來的數(shù)據(jù)進(jìn)行譯碼(復(fù)原)。對(duì)于雙工信道(既可以雙向傳輸信息的信道)，每端 都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫

2、一個(gè)哈夫曼的編/譯碼 系統(tǒng)。2. 基本要求系統(tǒng)應(yīng)具有以下功能:(1)C:編碼(Coding )。對(duì)文件tobetrans中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中，將以此建好的哈夫曼樹存入文件HuffmanTree 中(2)D :解碼(Decoding )。利用已建好的哈夫曼樹將文件 codefile中的代碼進(jìn)行譯碼，結(jié)果存入textfile中。（3） P:打印代碼文件（Print ）。將文件codefile以緊湊格式顯示在終端上,每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件code print中。（4）T：打印哈夫曼樹（Tree Printing ）。將已在內(nèi)存中的哈夫曼樹

3、以直觀的方 式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件treeprint 中。3. 參考資料：數(shù)據(jù)結(jié)構(gòu)（C語言版）嚴(yán)蔚敏、吳偉民編著;數(shù)據(jù)結(jié)構(gòu)標(biāo)準(zhǔn)教程胡超、閆寶玉編著完成期限:2012年6月21日指導(dǎo)教師簽名：課程負(fù)責(zé)人簽名:2012年 6月21日、設(shè)計(jì)題目（任選其一）實(shí)驗(yàn)一、哈夫曼編/譯碼器實(shí)驗(yàn)?zāi)康?鞏固和加深對(duì)數(shù)據(jù)結(jié)構(gòu)的理解，提高綜合運(yùn)用本課程所學(xué)知識(shí)的能力;2深化對(duì)算法課程中基本概念、理論和方法的理解;3鞏固構(gòu)造赫夫曼樹的算法;4設(shè)計(jì)試驗(yàn)用程序?qū)嶒?yàn)赫夫曼樹的構(gòu)造。三、運(yùn)行環(huán)境（軟、硬件環(huán)境）Windows xp sp3 ，Visual C+ 6.0 英文版四、算

4、法設(shè)計(jì)的思想(1 )初始化赫夫曼樹，輸入文件tobetra ns.txt中各字符及其權(quán)值，并保存于 hfmtree.txt 文件中(2)編碼(Coding )。對(duì)文件tobetrans中的正文進(jìn)行編碼，然后將結(jié)果存入 文件codefile中(3)D :解碼(Decoding )。利用已建好的哈夫曼樹將文件 codefile中的代碼進(jìn)行譯碼，結(jié)果存入textfile中。(4)P:打印代碼文件(Print )。將文件codefile 以緊湊格式顯示在終端上,code print 中。每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件(5)T：打印哈夫曼樹(Tree Printing )。將已在內(nèi)存

5、中的哈夫曼樹以直觀的方treeprint 中。式顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件五、流程圖赫夫曼編/譯碼器打印編碼六、算法設(shè)計(jì)分析1.赫夫曼樹節(jié)點(diǎn)的數(shù)據(jù)類型定義為:typ edef struct/赫夫曼樹的結(jié)構(gòu)體/權(quán)值char ch;int weight;int paren t,lchild,rchild; HTNode,*HuffmanTree;2. void HuffmanCoding(HuffmanTree&char *,int *,int);建立赫夫曼樹的算法，此函數(shù)塊調(diào)用了 Select()函數(shù)。void select(HuffmanTree HT,int j

6、,int *x,i nt *y);從已建好的赫夫曼樹中選擇 pare nt為0， weight最小的兩個(gè)結(jié)點(diǎn)。3 .利用已建好的哈夫曼樹從文件hfmtree.txt中讀入，對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile.txt中。4. cod ing編碼功能：對(duì)輸入字符進(jìn)行編碼5. Decod ing譯碼功能：利用已建好的哈夫曼樹將文件codefile.txt中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile.txt 中。6. PrintO打印功能函數(shù)：輸出哈夫曼樹以及對(duì)應(yīng)的編碼。七、源代碼/#i nclude <stdio.h>#i nclude <stdlib.h

7、>#i nclude <stri ng.h>/定義赫夫曼樹結(jié)點(diǎn)的結(jié)構(gòu)體typ edef structvoid Prin t_code();/打印譯碼好的代碼char ch;/增加一個(gè)域，存放該節(jié)點(diǎn)的字符int weight;int paren t,lchild,rchild;/指向赫夫曼編碼的指針HTNode,*Huffma nTree;typ edef char *Huffma nCode;void tip s();/打印操作選擇界面/建立赫夫曼/從已建好的赫夫曼void Huffma nCodi ng(Huffma nTree &,char *,i nt *,i

8、nt);樹的算法void select(Huffma nTree HT,i nt j,i nt *x,i nt *y);樹中選擇pare nt為0，weight最小的兩個(gè)結(jié)點(diǎn) void In it();void Codi ng();/編碼void Decod in g();/譯碼void Print_tree(); / 打印哈夫曼樹/譯碼int Read_tree(Huffma nTree &); /從文件中讀入赫夫曼樹void fin d(Huffma nTree &HT,char *code,char *text,i nt i,i nt m);時(shí)根據(jù)01字符串尋找相應(yīng)葉子節(jié)

9、點(diǎn)的遞歸算法/將內(nèi)void Co nvert_tree(u nsig ned char T100100,i nt s,i nt *i,i nt j);存中的赫夫曼樹轉(zhuǎn)換成凹凸表形式的赫夫曼樹Huffma nTree HT;/全局變量int n=0;/全局變量，存放赫夫曼樹葉子結(jié)點(diǎn)的數(shù)目int main() char select;while(1)tip s();sca nf("%c",&select);switch(select) /選擇操作，根據(jù)不同的序號(hào)選擇不同的操作case '1':I nit();break;case 2:Codi ng();

10、break;case 3:Decodi ng();break;case '4': Prin t_code();break;case '5':Prin t_tree();break;case 'O':exit(1);default :prin tf("I nput error!' n");getchar();return 0;void tips()/操作選擇界面pnntf("n");printf("-請(qǐng)選擇操作pnntf("n");printf("pnntf(&

11、quot;1初始化赫夫曼樹n");pnntf("2編碼n");pnntf("3譯碼n");pnntf("4打印代碼文件-n");pnntf("5打印赫夫曼樹n");pnntf("0退出n");pnntf("n");-n");n");/初始化函數(shù)，輸入n個(gè)字符及其對(duì)應(yīng)的權(quán)值，根據(jù)權(quán)值建立哈夫曼樹，并將其存于文件hfmtree中void In it()FILE *fp;char character52;/存放n個(gè)字符printf（"n輸入字

12、符個(gè)數(shù)n:"）;sca nf("%d",&n);/輸入字符集大小printf（"輸入%d個(gè)字符及其對(duì)應(yīng)的權(quán)值：n",n）;for (i=0;i vn ;i+)char b=getchar();sca nf("%c"，&characteri);sca nf("%d",&wi);/輸入n個(gè)字符和對(duì)應(yīng)的權(quán)值Huffma nCodi ng(HT,character,w, n);/建立赫夫曼樹if(fp=fo pen ("hfmtree.txt","w"

13、;)=NULL)printfC'Open file hfmtree.txt error!n");for (i=1;i<=2* n-1;i+)if(fwrite(&H Ti,sizeof(HTNode),1,fp)!=1)/將建立的赫夫曼樹存入文件 hfmtree.txt 中prin tf("File write error!n");prin tf（"n赫夫曼樹建立成功，并已存于文件hfmtree.txt 中 n");fclose(fp);/建立赫夫曼樹的算法 void Huffma nCodi ng(Huffma nTre

14、e &HT,char *character,i nt *w,i nt n)Huffma nTree p;if(nv=1) return;m=2* n-1;HT=(Huffma nTree)malloc(m+1)*sizeof(HTNode);for(p=HT+1,i=1;iv=n;+i,+p,+character,+w) p->ch=*character; p->weight=*w; p->paren t=0; p->lchild=0; p->rchild =0; for(;i<=m;+i,+p) p->ch=0;p->weight=0;

15、p->parent=0;p->lchild=0;p-> rchild=0; for(i=n+1;i<=m;+i)select(HT,i-1, &x,&y);HTx. paren t=i;HTy. paren t=i;HTi.lchild=x;HTi.rchild=y;HTi.weight=HTx.weight+HTy.weight;/從HT1到HTj中選擇pare nt為0 , weight最小的兩個(gè)結(jié)點(diǎn)，用 x和y返回其序號(hào)void select(Huffma nTree HT,i nt j,i nt *x,i nt *y) int i;/查找weig

16、ht最小的結(jié)點(diǎn) for (i=1;i<=j;i+)if (HTi. pare nt=0)*x=i;break; for (;i<=j;i+)if (HTi. paren t=0)&&(HTi.weightvHT*x.weight)*x=i;HT*x. paren t=1;/查找weight次小的結(jié)點(diǎn) for (i=1;i<=j;i+)if (HTi. pare nt=0)*y=i;break; for (;iv=j;i+)if (HTi. paren t=0)&&( i!=*x )&&(HTi.weightvHT*y.weigh

17、t)*y=i；II對(duì)文件tobetrans中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中 void Codi ng()FILE *fp,*fw;int i,f,c,start;char *cd;Huffma nCode HC;if(n=0)n=Read_tree(HT);II 從文件hfmtree.txt中讀入赫夫曼樹，返回葉子結(jié)點(diǎn)數(shù)II求赫夫曼樹中各葉子節(jié)點(diǎn)的字符對(duì)應(yīng)的的編碼，并存于HC指向的空間中HC=(Huffma nCode)malloc( n+1)*sizeof(char*);cd=(char *)malloc( n*sizeof(char);cdn-1='0'

18、;for(i=1;iv=n ;+i)start=n-1;for(c=i,f=HTi. pare nt;f!=0;c=f,f=HTf. parent)if(HTf.lchild=c)cd-start='0'else cd-start='1'HCi=(char *)malloc( n-start)*sizeof(char);strc py(HCi, &cdstart);free(cd);if(fp=fo pen ("tobetra ns.txt","rb")=NULL)printf("Open file to

19、betra ns.txt error!n");if(fw=fo pen ("codefile.txt","wb+")=NULL)prin tf("O pen file codefile.txt error!n");char temp;fsca nf(fp,"%c", &tem p);/從文件讀入第一個(gè)字符while(!feof(fp)for(i=1;iv=n ;i+)if(HTi.ch=te mp) break;/在赫夫曼樹中查找字符所在的位置for(i nt r=O;HCir!='O&#

20、39;r+)/將字符對(duì)應(yīng)的編碼存入文件fputc(HCir,fw);fsca nf(fp,"%c", &tem p);/從文件讀入下一個(gè)字符fclose(fw);fclose(fp);printf("n 已將文件 hfmtree.txt成功編碼，并已存入codefile.txt 中！ nn");/將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中 void Decod in g()FILE *fp,*fw;int m,i;char *code,*text,* p;if(n=0)n=Read_tree(HT);/ 從文件hfmt

21、ree.txt中讀入赫夫曼樹，返回葉子結(jié)點(diǎn)數(shù)if(fp=fo pen ("codefile.txt","rb")=NULL)prin tf("O pen file codefile.txt error!n");if(fw=fo pen ("textfile.txt","wb+")=NULL)prin tf("O pen file textfile.txt error!n");code=(char *)malloc(sizeof(char);fsca nf(fp,"%

22、c",code);/從文件讀入一個(gè)字符for(i=1;!feof(fp);i+)code=(char *)realloc(code,(i+1)*sizeof(char);/增加空間fsca nf(fp,"%c",&codei);/從文件讀入下一個(gè)字符codei-1='0'/ codefile.txt文件中的字符已全部讀入，存放在 code數(shù)組中text=(char *)malloc(100*sizeof(char);p=text;m=2* n-1;/從根節(jié)點(diǎn)的左子樹去找/從根節(jié)點(diǎn)的右子樹去找if(*code='0')fin

23、d(HT,code,text,HTm.lchild,m);elsefin d(HT,code,text,HTm.rchild,m);for(i=0; pi!='O'i+)/把譯碼好的字符存入文件textfile.txt中fputc( pi,fw);fclose(fp);fclose(fw);printf("n 已將 codefile.txt 文件成功譯碼，兵已存入 textfile.txt 文件！ nn");/將文件codefi1e以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件code print中。void Prin t_cod

24、e()FILE *fp,*fw;char temp;int i;if(fp=fo pen( "codefile.txt","rb")=NULL)prin tf("O pen file codefile.txt error!n");if(fw=fo pen ("code prin t.txt","wb+")=NULL)printfC'Open file code prin t.txt error!n");printf("n 文件 codefile 顯示如下:n"

25、;);fsca nf(fp,"%c", &tem p);/從文件讀入一個(gè)字符for (i=1;!feof(fp);i+)prin tf("%c",tem p);if(i%50=0) prin tf("n");fputc(temp,fw);/ 將該字符存入文件 codeprint.txt中fsca nf(fp,"%c", &tem p);/從文件讀入一個(gè)字符printf（"nn已將此字符形式的編碼寫入文件codeprint.txt中！ nn"）;fclose(fp);fclose(

26、fw);/將已在內(nèi)存中的哈夫曼樹顯示在屏幕上，并將此字符形式的哈夫曼樹寫入文件 tree print 中。void Prin t_tree()un sig ned char T100100;int i,j,m=0;FILE *fp;if(n=0)n=Read_tree(HT); /從文件hfmtree.txt中讀入赫夫曼樹，返回葉子結(jié)占數(shù)/將內(nèi)存中的赫夫曼樹轉(zhuǎn)換成凹凸表形式丿、人Co nvert_tree(T,0,&m,2* n-1);的樹，存于數(shù)組T中if(fp=fo pen ("tree prin t.txt","wb+")=NULL)pnn

27、tf("Open file tree prin t.txt error!n");prin tf("n打印已建好的赫夫曼樹：n");for(i=1;i<=2* n-1;i+)for (j=0;Tij!=0;j+)if(Tij=' ') printf(" ");fputc(Tij,fp);elseprin tf("%d",Tij);fpri ntf(fp,"%dn",Tij);prin tf("n");fclose(fp);printf（"n已將該

28、字符形式的哈夫曼樹寫入文件treeprint.txt 中！ nn"）;II從文件hfmtree.txt中讀入赫夫曼樹，返回葉子節(jié)點(diǎn)數(shù)int Read_tree(Huffma nTree &HT)FILE *fp;int i,n;HT=(Huffma nTree)malloc(sizeof(HTNode);if(fp=fo pen ("hfmtree.txt","廣)=NULL)printfC'Open file hfmtree.txt error!n");/增加空間for (i=1;!feof(fp);i+)/讀入一個(gè)節(jié)點(diǎn)信息H

29、T=(Huffma nTree)realloc(HT,(i+1)*sizeof(HTNode);fread(&H Ti,sizeof(HTNode),1,fp);fclose(fp);n=(i-1)/2;return n;/譯碼時(shí)根據(jù)01字符串尋找相應(yīng)葉子節(jié)點(diǎn)的遞歸算法void fin d(Huffma nTree &HT,char *code,char *text, int i,i nt m)if(*code!='0')/若譯碼未結(jié)束code+;if(HTi.lchild=O&&H Ti.rchild=O)/若找到葉子節(jié)點(diǎn)*text=HTi.c

30、h; /將葉子節(jié)點(diǎn)的字符存入text中text+;if(*code='0')fin d(HT,code,text,HTm.lchild,m);/從根節(jié)點(diǎn)的左子樹找elsefin d(HT,code,text,HTm.rchild,m);/從根節(jié)點(diǎn)的右子樹找else /如果不是葉子節(jié)點(diǎn)/從該節(jié)點(diǎn)的左子樹去找/從該節(jié)點(diǎn)的右子樹去找if(*code='0')fin d(HT,code,text,HTi.lchild,m);elsefin d(HT,code,text,HTi.rchild,m);else*text='0' /譯碼結(jié)束/將文件中的赫夫曼樹

31、轉(zhuǎn)換成凹凸表形式的赫夫曼樹打印出來 void Con vert_tree(u nsig ned char T100100,i nt s,i nt *i,i nt j) int k,l;l=+(*i);for(k=0;k<s;k+)Tlk=''Tlk=HTj.weight;if(HTj.lchild)Con vert_tree(T,s+1,i,HTj.lchild);if(HTj.rchild)Co nvert_tree(T,s+1,i,HT|j.rchild);Tl+k='O'/八、運(yùn)行結(jié)果分析截圖說明:1、運(yùn)行后界面如圖（1）:中 U *Cz VJDCU

32、MC-dI J lU-Lll Sett XIl£.s. 口 we'呈MjlDcl3U£a._ CXE，圖（1）選擇要選擇的操作序號(hào)可以運(yùn)行各個(gè)步驟;2、初始化赫夫曼樹:輸入tobetrans.txt中各元素及其出現(xiàn)頻率，如圖（2）圖（2）3、編碼及譯碼，如圖（3）圖（3）4、打印編碼文件，如圖（4）圖（4）5、打印赫夫曼樹，如圖（5）叮二卩三譴好RJ勰夫5S啊- 1Be,le4己將該宇雅劃式釣皓夫曼榔三入文井t«E:申如t.t祇中I丄釗化閒去曼啊-H編碼.J詳閔.4疔和代彳-丈斗* 圖（5）6、各步驟所存的文件內(nèi)容如圖（6）圖（6）九、收獲及體會(huì)課程設(shè)計(jì)是

33、讓我們充分利用我們專業(yè)課程所學(xué)知識(shí)的機(jī)會(huì)， 也是我們邁向社 會(huì)，從事工作前一個(gè)必不少的過程。 通過這次課程設(shè)計(jì)，我深深體會(huì)到將知識(shí)運(yùn) 用到實(shí)踐中的重要作用。我這兩天的課程設(shè)計(jì)，是讓我學(xué)會(huì)腳踏實(shí)地邁開這一步, 也是為明天能穩(wěn)健地在社會(huì)大潮中奔跑打下堅(jiān)實(shí)的基礎(chǔ)。我的課程設(shè)計(jì)題目是赫夫曼編譯碼器。 最初做這個(gè)程序的時(shí)候，讓我覺得完成這次程序設(shè)計(jì)真的是太難了，然后我查閱了課本，并去圖書館借了資料，在寫 這個(gè)程序的時(shí)候也參考了網(wǎng)上的設(shè)計(jì)流程， 寫完剛運(yùn)行時(shí)出現(xiàn)了很多問題。 尤其 是編碼錯(cuò)誤，導(dǎo)致內(nèi)存無法 read，通過同組人員的交流請(qǐng)教，逐漸明白過來,然后經(jīng)過不知道多少次修改才順利運(yùn)行。本次試驗(yàn)也讓我明

34、白了理論與實(shí)際相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫大型程序的能力，培養(yǎng)了基本的、良好的程序設(shè)計(jì)技能以及合作能力。通過對(duì)各個(gè)步驟各個(gè)流程的控制，逐漸讓我產(chǎn)生了興趣，在實(shí)際編寫過程中，和同學(xué)們相互討論讓我學(xué)到的不僅僅是一些解決問題的方法，更是解決問題的思想。課程設(shè)計(jì)本身也是一種相互學(xué)習(xí)的過 程,/#in elude <stdio.h>#in elude <stdlib.h>/為exit()提供原型#in elude <stri ng.h>/哈夫曼樹結(jié)點(diǎn)的結(jié)構(gòu)typedef struct char ch;/該字符域用于存放節(jié)點(diǎn)的關(guān)鍵字int weight;i

35、nt paren t, lchild, rchild;HTNode , *HuffmanTree ;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedef char * HuffmanCode/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表void Menu();/顯示菜單void HuffmanCoding(HuffmanTree &HT, char *character, int * w, int n);/建立哈夫曼樹void select( HuffmanTree HT, int j, int *x, int *y);/從已建好的赫夫曼樹中選擇pare nt為0，weight最小的兩個(gè)結(jié)點(diǎn) void Init(

36、);voidCodi ng();/編碼voidDecod in g();/譯碼voidP ri nt_code();/打印譯碼好的代碼voidP ri nt_tree();/打印哈夫曼樹int Read_tree( HuffmanTree &); /從文件中讀入赫夫曼樹void find( HuffmanTree &HT, char *code, char *text, int i, int m);/ 譯碼時(shí)根據(jù) 01 字符串尋找 相應(yīng)葉子節(jié)點(diǎn)的遞歸算法void Convert_tree( unsigned char T100100, int s, int *i, int j)

37、;/ 將內(nèi)存中的赫夫曼樹轉(zhuǎn)換成 凹凸表形式的赫夫曼樹HuffmanTree HT; / 全局變量intn = 0;/全局變量，存放赫夫曼樹葉子結(jié)點(diǎn)的數(shù)目intmai n()char select;while (1)Men u();scanf( "%c" , &select);switch (select) /選擇操作，根據(jù)不同的序號(hào)選擇不同的操作case'1' :lnit();break ;case2 :Coding();break ;case3 :Decoding();break ;case'4':Print_code();brea

38、k ;case'5':Print_tree();break ;case'O':exit(1);default :printf( "Input error!n");getchar();return 0;voidMenu()/操作選擇界面printf("n")；printf("-請(qǐng)選擇操作-n")printf("n")Jprintf("n"printf("1初始化赫夫曼樹-n");printf("2編碼n");printf(&q

39、uot;3譯碼-n");printf("4打印代碼文件-n");printf("5打印赫夫曼樹n");printf("0退岀-n");printf("n")I)；/初始化函數(shù)，輸入n個(gè)字符及其對(duì)應(yīng)的權(quán)值，根據(jù)權(quán)值建立哈夫曼樹,并將其存于文件hfmtreevoid Init()FILE *fp;int i, n, w52;/數(shù)組存放字符的權(quán)值char character52;/存放n個(gè)字符printf( "n輸入字符個(gè)數(shù) n:");scanf( "%d" , &

40、;n);/輸入字符集大小printf（"輸入%d個(gè)字符及其對(duì)應(yīng)的權(quán)值：n" , n）;for(i = 0; ivn; i+)char b = getchar();scanf( "%c" , &character);scanf( "%d" , &wi);/輸入n個(gè)字符和對(duì)應(yīng)的權(quán)值Huffma nCod in g(HT, character, w, n);/建立赫夫曼樹if (fp = fopen( "hfmtree.txt" , "w")=NULL)printf( "Op

41、en file hfmtree.txt error!n");for (i = 1; i <= 2 * n - 1; i+)if (fwrite(&HTi,sizeof (HTNode ), 1, fp) != 1)/ 將建立的赫夫曼樹存入文件hfmtree.txt 中printf( "File write error!n" );printf（ "n赫夫曼樹建立成功，并已存于文件 hfmtree.txt中n");fclose(f p);/構(gòu)造哈夫曼樹的算法void HuffmanCoding(HuffmanTree &HT,

42、 char *character,int * w, int n)/w存放n個(gè)字符的權(quán)值（均0 ）,構(gòu)造哈夫曼樹HTint m, i, x, y;Huffma nTree 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, +character, +w)p->ch = Character; p->weight = *w; p->p are nt = 0; p->

43、lchild = 0; p-> rchild = 0;for(;i <= m; +i, +p) p->ch = 0; p->weight = 0; p->parent = 0; p->lchild = 0;p->rchild = 0; for (i = n + 1; i <= m; +i)select(HT, i - 1, &x, &y);HTx. parent = i; HTy. pare nt = i;HTi.lchild = x; HTi.rchild = y;HTi.weight = HTx.weight + HTy.we

44、ight;/從HT1到HT j中選擇pare nt為0 , weight最小的兩個(gè)結(jié)點(diǎn)，用x和y返回其序號(hào)void select( HuffmanTreeHT, int j, int *x, int *y)int i;/查找weight最小的結(jié)點(diǎn)for (i = 1; i <= j; i+)if (HTi. pare nt = 0)*x = i; break ;for (; i <= j; i+)if (HTi. pare nt = 0) && ( HTi.weightv HT*x.weight)HT*x. pare nt = 1;/查找weight次小的結(jié)點(diǎn)for

45、 (i = 1; i <= j; i+)if (HTi. pare nt = 0)*y = i; break ;for (; i <= j; i+)if (HTi. pare nt = 0) && (i != * x) && ( HTi.weightv HT*y.weight)y = i;/對(duì)文件tobetrans中的正文進(jìn)行編碼，然后將結(jié)果存入文件codefile中 void Coding()FILE *fp, *fw;int i, f, c, start;char *cd;Huffma nCode HC;if (n = 0)n = Read_tr

46、ee(HT); /從文件hfmtree.txt中讀入赫夫曼樹,返回葉子結(jié)點(diǎn)數(shù)/求赫夫曼樹中各葉子節(jié)點(diǎn)的字符對(duì)應(yīng)的的編碼，并存于HC指向的空間中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 .p are nt)if (HTf.lchild =

47、 c)cd-start ='O'else cd-start ='1'HCi = ( char *)malloc(n - start) * sizeof (char);strc py(HCi, & cdstart);free(cd);if (fp = fopen("tobetrans.txt", "rb" ) = NULL )prints "Open file tobetrans.txt error!'n")；if (fw = fopen( "codefile.txt"

48、 , "wb+")=NULL)printf( "Open file codefile.txt error!'n");char temp;fscanffp, "%c" , &temp);/從文件讀入第一個(gè)字符while (!feof(fp)for(i = 1; i <= n; i+)if (HTi.ch = temp)break ;/在赫夫曼樹中查找字符所在的位置for(int r = 0; HCir !='0'葉+)/將字符對(duì)應(yīng)的編碼存入文件fputc(HCir, fw);fscanffp, &q

49、uot;%c" , &temp);/從文件讀入下一個(gè)字符fclose(fw);fclose(f p);printf( "n 已將文件 hfmtree.txt成功編碼，并已存入codefile.txt中！ nn");/將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中void Decod in g()FILE *fp, *fw;int m, i;char *code, *text, * p;if (n = 0)n = Read_tree(HT); /從文件hfmtree.txt中讀入赫夫曼樹,返回葉子結(jié)點(diǎn)數(shù)if (fp = fopen(

50、"codefile.txt" , "rb" ) = NULL);printf( "Open file codefile.txt error!'n"if (fw = fopen( "textfile.txt" , "wb+" ) = NULL)；printf( "Open file textfile.txt erroH'n"code = ( char *)malloc( sizeof (char);fscanf(fp, "%c" , code

51、);/從文件讀入一個(gè)字符for (i = 1; !feof(fp); i+)code = ( char *)realloc(code, (i + 1) * sizeof (char);/ 增加空間fscanf(fp, "%c" , &codei);/從文件讀入下一個(gè)字符codei - 1 ='0'/ codefile.txt文件中的字符已全部讀入，存放在code數(shù)組中text = ( char*)malloc(100 * sizeof (char);p = text;m = 2 * n - 1;if (*code ='0')elsef

52、in d(HT, code, text, HTm.lchild, m);/從根節(jié)點(diǎn)的左子樹去找fin d(HT, code, text, HTm.rchild, m);/從根節(jié)點(diǎn)的右子樹去找for (i = 0; pi !='0' ; i+)/ 把譯碼好的字符存入文件textfile.txt 中fputc( pi, fw);fclose(f p);fclose(fw);printf( "n 已將 codefile.txt文件成功譯碼，兵已存入textfile.txt 文件！ nn");/將文件codefi1e以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件 code print 中。void Print_codeOFILE *fp, *fw;char temp;int i;if (fp = fopen( "codefile.txt" , "rb" ) = NULL)printf( "Open file codefile.txt error!'n"）；if (fw = fopen("codeprint.txt", "wb+" ) = NULL)prints "Open file codepri