哈夫曼編譯碼器課程設(shè)計(jì)報(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)教師：XXX XXX 2012年 6 月 21日xxx學(xué)院課 程 設(shè) 計(jì) 任 務(wù) 書(shū)題目 一、赫夫曼編譯碼器 專業(yè)、班級(jí) xxx 學(xué)號(hào) xxx 姓名 xxx 主要內(nèi)容、基本要求、主要參考資料等：1. 主要內(nèi)容利用哈夫曼編碼進(jìn)行信息通信可大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼；在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對(duì)于雙工信道（既可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編

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

3、內(nèi)存中的哈夫曼樹(shù)以直觀的方式（樹(shù)或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹(shù)寫(xiě)入文件treeprint中。3. 參考資料：數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版） 嚴(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)造赫夫曼樹(shù)的算法；4 設(shè)計(jì)試驗(yàn)用程序?qū)嶒?yàn)赫夫曼樹(shù)的構(gòu)造。 三、運(yùn)行環(huán)境（軟、硬件環(huán)境）Windows x

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

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

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

7、include <string.h>/定義赫夫曼樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)體typedef struct char ch; /增加一個(gè)域，存放該節(jié)點(diǎn)的字符int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;typedef char *HuffmanCode; /指向赫夫曼編碼的指針void tips(); /打印操作選擇界面void HuffmanCoding(HuffmanTree &,char *,int *,int); /建立赫夫曼樹(shù)的算法void select(HuffmanTree HT,int j,int *x,i

8、nt *y); /從已建好的赫夫曼樹(shù)中選擇parent為0，weight最小的兩個(gè)結(jié)點(diǎn)void Init(); void Coding(); /編碼void Decoding(); /譯碼void Print_code(); /打印譯碼好的代碼void Print_tree(); /打印哈夫曼樹(shù)int Read_tree(HuffmanTree &); /從文件中讀入赫夫曼樹(shù)void find(HuffmanTree &HT,char *code,char *text,int i,int m); /譯碼時(shí)根據(jù)01字符串尋找相應(yīng)葉子節(jié)點(diǎn)的遞歸算法void Convert_tree

9、(unsigned char T100100,int s,int *i,int j); /將內(nèi)存中的赫夫曼樹(shù)轉(zhuǎn)換成凹凸表形式的赫夫曼樹(shù)HuffmanTree HT; /全局變量int n=0; /全局變量，存放赫夫曼樹(shù)葉子結(jié)點(diǎn)的數(shù)目int main()char select;while(1) tips(); scanf("%c",&select); switch(select) /選擇操作，根據(jù)不同的序號(hào)選擇不同的操作 case '1':Init();break; case '2':Coding();break; case '

10、3':Decoding();break; case '4':Print_code();break; case '5':Print_tree();break; case '0':exit(1); default :printf("Input error!n"); getchar();return 0;void tips() /操作選擇界面printf(" -n");printf(" - 請(qǐng)選擇操作 -n");printf(" -n");printf("

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

12、; /數(shù)組存放字符的權(quán)值char character52; /存放n個(gè)字符printf("n輸入字符個(gè)數(shù) n:");scanf("%d",&n); /輸入字符集大小printf("輸入%d個(gè)字符及其對(duì)應(yīng)的權(quán)值:n",n);for (i=0;i<n;i+) char b=getchar(); scanf("%c",&characteri); scanf("%d",&wi); /輸入n個(gè)字符和對(duì)應(yīng)的權(quán)值 HuffmanCoding(HT,character,w,n);

13、/建立赫夫曼樹(shù)if(fp=fopen("hfmtree.txt","w")=NULL) printf("Open file hfmtree.txt error!n");for (i=1;i<=2*n-1;i+) if(fwrite(&HTi,sizeof(HTNode),1,fp)!=1) /將建立的赫夫曼樹(shù)存入文件hfmtree.txt中 printf("File write error!n");printf("n赫夫曼樹(shù)建立成功，并已存于文件hfmtree.txt中n");fc

14、lose(fp);/建立赫夫曼樹(shù)的算法void HuffmanCoding(HuffmanTree &HT,char *character,int *w,int n)int m,i,x,y;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,+character,+w)p->ch=*character;p->weight=*w;p->parent=0;p->lchild=0;p->rc

15、hild=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.parent=i; HTi.lchild=x;HTi.rchild=y; HTi.weight=HTx.weight+HTy.weight;/從HT1到HTj中選擇parent為0，weight最小的兩個(gè)結(jié)點(diǎn)，用x和y返回其序號(hào)void select(Huffman

16、Tree HT,int j,int *x,int *y)int i;/查找weight最小的結(jié)點(diǎn)for (i=1;i<=j;i+) if (HTi.parent=0) *x=i;break;for (;i<=j;i+) if (HTi.parent=0)&&(HTi.weight<HT*x.weight) *x=i; HT*x.parent=1;/查找weight次小的結(jié)點(diǎn)for (i=1;i<=j;i+) if (HTi.parent=0) *y=i;break;for (;i<=j;i+) if (HTi.parent=0)&&

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

18、loc(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)*sizeof(char); strcpy(HCi,&cdstart);free(cd);if(fp=fopen("tobetrans.txt","rb&qu

19、ot;)=NULL) printf("Open file tobetrans.txt error!n");if(fw=fopen("codefile.txt","wb+")=NULL) printf("Open file codefile.txt error!n");char temp;fscanf(fp,"%c",&temp); /從文件讀入第一個(gè)字符while(!feof(fp) for(i=1;i<=n;i+) if(HTi.ch=temp) break; /在赫夫曼樹(shù)中查找

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

21、n=0) n=Read_tree(HT);/從文件hfmtree.txt中讀入赫夫曼樹(shù),返回葉子結(jié)點(diǎn)數(shù)if(fp=fopen("codefile.txt","rb")=NULL) printf("Open file codefile.txt error!n"); if(fw=fopen("textfile.txt","wb+")=NULL) printf("Open file textfile.txt error!n");code=(char *)malloc(sizeof(

22、char);fscanf(fp,"%c",code); /從文件讀入一個(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'

23、;) find(HT,code,text,HTm.lchild,m); /從根節(jié)點(diǎn)的左子樹(shù)去找else find(HT,code,text,HTm.rchild,m); /從根節(jié)點(diǎn)的右子樹(shù)去找 for(i=0;pi!='0'i+) /把譯碼好的字符存入文件textfile.txt中 fputc(pi,fw);fclose(fp);fclose(fw);printf("n已將codefile.txt文件成功譯碼，兵已存入textfile.txt文件！nn");/將文件codefi1e以緊湊格式顯示在終端上,每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫(xiě)入文件co

24、deprint中。void Print_code()FILE *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) printf("Open file codeprint.txt error!n");printf("n文件codef

25、i1e顯示如下:n");fscanf(fp,"%c",&temp); /從文件讀入一個(gè)字符for (i=1;!feof(fp);i+) printf("%c",temp); if(i%50=0) printf("n"); fputc(temp,fw); /將該字符存入文件codeprint.txt中 fscanf(fp,"%c",&temp); /從文件讀入一個(gè)字符printf("nn已將此字符形式的編碼寫(xiě)入文件codeprint.txt中！nn");fclose(fp

26、);fclose(fw);/將已在內(nèi)存中的哈夫曼樹(shù)顯示在屏幕上，并將此字符形式的哈夫曼樹(shù)寫(xiě)入文件treeprint中。void Print_tree()unsigned char T100100;int i,j,m=0;FILE *fp;if(n=0) n=Read_tree(HT); /從文件hfmtree.txt中讀入赫夫曼樹(shù),返回葉子結(jié)點(diǎn)數(shù)Convert_tree(T,0,&m,2*n-1); /將內(nèi)存中的赫夫曼樹(shù)轉(zhuǎn)換成凹凸表形式的樹(shù)，存于數(shù)組T中if(fp=fopen("treeprint.txt","wb+")=NULL) printf

27、("Open file treeprint.txt error!n"); printf("n打印已建好的赫夫曼樹(shù)：n");for(i=1;i<=2*n-1;i+) for (j=0;Tij!=0;j+) if(Tij=' ') printf(" ");fputc(Tij,fp); else printf("%d",Tij);fprintf(fp,"%dn",Tij); printf("n");fclose(fp);printf("n已將該字符形

28、式的哈夫曼樹(shù)寫(xiě)入文件treeprint.txt中！nn");/從文件hfmtree.txt中讀入赫夫曼樹(shù)，返回葉子節(jié)點(diǎn)數(shù)int Read_tree(HuffmanTree &HT) FILE *fp;int i,n;HT=(HuffmanTree)malloc(sizeof(HTNode); if(fp=fopen("hfmtree.txt","r")=NULL) printf("Open file hfmtree.txt error!n");for (i=1;!feof(fp);i+) HT=(HuffmanTre

29、e)realloc(HT,(i+1)*sizeof(HTNode); /增加空間 fread(&HTi,sizeof(HTNode),1,fp); /讀入一個(gè)節(jié)點(diǎn)信息fclose(fp);n=(i-1)/2;return n;/譯碼時(shí)根據(jù)01字符串尋找相應(yīng)葉子節(jié)點(diǎn)的遞歸算法void find(HuffmanTree &HT,char *code,char *text,int i,int m)if(*code!='0') /若譯碼未結(jié)束 code+; if(HTi.lchild=0&&HTi.rchild=0) /若找到葉子節(jié)點(diǎn) *text=HTi

30、.ch; /將葉子節(jié)點(diǎn)的字符存入text中 text+; if(*code='0') find(HT,code,text,HTm.lchild,m); /從根節(jié)點(diǎn)的左子樹(shù)找 else find(HT,code,text,HTm.rchild,m); /從根節(jié)點(diǎn)的右子樹(shù)找 else /如果不是葉子節(jié)點(diǎn) if(*code='0') find(HT,code,text,HTi.lchild,m); /從該節(jié)點(diǎn)的左子樹(shù)去找 else find(HT,code,text,HTi.rchild,m); /從該節(jié)點(diǎn)的右子樹(shù)去找else *text='0' /譯

31、碼結(jié)束/將文件中的赫夫曼樹(shù)轉(zhuǎn)換成凹凸表形式的赫夫曼樹(shù)打印出來(lái)void Convert_tree(unsigned char T100100,int s,int *i,int j)int k,l;l=+(*i);for(k=0;k<s;k+) Tlk=' 'Tlk=HTj.weight;if(HTj.lchild) Convert_tree(T,s+1,i,HTj.lchild);if(HTj.rchild) Convert_tree(T,s+1,i,HTj.rchild); Tl+k='0'/八、運(yùn)行結(jié)果分析截圖說(shuō)明：1、運(yùn)行后界面如圖（1）：圖（1）選擇

32、要選擇的操作序號(hào)可以運(yùn)行各個(gè)步驟；2、初始化赫夫曼樹(shù)：輸入tobetrans.txt中各元素及其出現(xiàn)頻率，如圖（2）圖（2）3、編碼及譯碼，如圖（3）圖（3）4、打印編碼文件，如圖（4）圖（4）5、打印赫夫曼樹(shù)，如圖（5）圖（5）6、各步驟所存的文件內(nèi)容如圖（6）圖（6）九、收獲及體會(huì)課程設(shè)計(jì)是讓我們充分利用我們專業(yè)課程所學(xué)知識(shí)的機(jī)會(huì)，也是我們邁向社會(huì)，從事工作前一個(gè)必不少的過(guò)程。通過(guò)這次課程設(shè)計(jì)，我深深體會(huì)到將知識(shí)運(yùn)用到實(shí)踐中的重要作用。我這兩天的課程設(shè)計(jì)，是讓我學(xué)會(huì)腳踏實(shí)地邁開(kāi)這一步，也是為明天能穩(wěn)健地在社會(huì)大潮中奔跑打下堅(jiān)實(shí)的基礎(chǔ)。我的課程設(shè)計(jì)題目是赫夫曼編譯碼器。最初做這個(gè)程序的時(shí)候，

33、讓我覺(jué)得完成這次程序設(shè)計(jì)真的是太難了，然后我查閱了課本，并去圖書(shū)館借了資料，在寫(xiě)這個(gè)程序的時(shí)候也參考了網(wǎng)上的設(shè)計(jì)流程，寫(xiě)完剛運(yùn)行時(shí)出現(xiàn)了很多問(wèn)題。尤其是編碼錯(cuò)誤，導(dǎo)致內(nèi)存無(wú)法read，通過(guò)同組人員的交流請(qǐng)教，逐漸明白過(guò)來(lái)，然后經(jīng)過(guò)不知道多少次修改才順利運(yùn)行。本次試驗(yàn)也讓我明白了理論與實(shí)際相結(jié)合的重要性，并提高了自己組織數(shù)據(jù)及編寫(xiě)大型程序的能力，培養(yǎng)了基本的、良好的程序設(shè)計(jì)技能以及合作能力。 通過(guò)對(duì)各個(gè)步驟各個(gè)流程的控制，逐漸讓我產(chǎn)生了興趣，在實(shí)際編寫(xiě)過(guò)程中，和同學(xué)們相互討論讓我學(xué)到的不僅僅是一些解決問(wèn)題的方法，更是解決問(wèn)題的思想。課程設(shè)計(jì)本身也是一種相互學(xué)習(xí)的過(guò)程,/ #include <

34、;stdio.h>#include <stdlib.h> /為exit()提供原型#include <string.h>/哈夫曼樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)typedef struct char ch; /該字符域用于存放節(jié)點(diǎn)的關(guān)鍵字int weight;int parent, lchild, rchild;HTNode, *HuffmanTree; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹(shù)typedef char *HuffmanCode; /動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼編碼表void Menu(); /顯示菜單void HuffmanCoding(HuffmanTree &HT, cha

35、r *character, int * w, int n); /建立哈夫曼樹(shù)void select(HuffmanTree HT, int j, int *x, int *y); /從已建好的赫夫曼樹(shù)中選擇parent為0，weight最小的兩個(gè)結(jié)點(diǎn)void Init();void Coding(); /編碼void Decoding(); /譯碼void Print_code(); /打印譯碼好的代碼void Print_tree(); /打印哈夫曼樹(shù)int Read_tree(HuffmanTree &); /從文件中讀入赫夫曼樹(shù)void find(HuffmanTree &

36、;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); /將內(nèi)存中的赫夫曼樹(shù)轉(zhuǎn)換成凹凸表形式的赫夫曼樹(shù)HuffmanTree HT; /全局變量int n = 0; /全局變量，存放赫夫曼樹(shù)葉子結(jié)點(diǎn)的數(shù)目int main()char select;while (1)Menu();scanf("%c", &select);switch (select) /選擇操作

37、，根據(jù)不同的序號(hào)選擇不同的操作case '1':Init();break;case '2':Coding();break;case '3':Decoding();break;case '4':Print_code();break;case '5':Print_tree();break;case '0':exit(1);default:printf("Input error!n");getchar();return 0;void Menu() /操作選擇界面printf("

38、; -n");printf(" - 請(qǐng)選擇操作 -n");printf(" -n");printf(" n");printf(" -1初始化赫夫曼樹(shù) -n");printf(" -2編碼 -n");printf(" -3譯碼 -n");printf(" -4打印代碼文件 -n");printf(" -5打印赫夫曼樹(shù) -n");printf(" -0退出 -n");printf(" -n"

39、);/初始化函數(shù)，輸入n個(gè)字符及其對(duì)應(yīng)的權(quán)值，根據(jù)權(quán)值建立哈夫曼樹(shù)，并將其存于文件hfmtree中void Init()FILE *fp;int i, n, w52; /數(shù)組存放字符的權(quán)值char character52; /存放n個(gè)字符printf("n輸入字符個(gè)數(shù) n:");scanf("%d", &n); /輸入字符集大小printf("輸入%d個(gè)字符及其對(duì)應(yīng)的權(quán)值:n", n);for (i = 0; i<n; i+)char b = getchar();scanf("%c", &ch

40、aracteri);scanf("%d", &wi); /輸入n個(gè)字符和對(duì)應(yīng)的權(quán)值HuffmanCoding(HT, character, w, n); /建立赫夫曼樹(shù)if (fp = fopen("hfmtree.txt", "w") = NULL)printf("Open file hfmtree.txt error!n");for (i = 1; i <= 2 * n - 1; i+)if (fwrite(&HTi, sizeof(HTNode), 1, fp) != 1) /將建立的赫

41、夫曼樹(shù)存入文件hfmtree.txt中printf("File write error!n");printf("n赫夫曼樹(shù)建立成功，并已存于文件hfmtree.txt中n");fclose(fp);/構(gòu)造哈夫曼樹(shù)的算法void HuffmanCoding(HuffmanTree &HT, char *character, int * w, int n) /w存放n個(gè)字符的權(quán)值（均>0），構(gòu)造哈夫曼樹(shù)HTint m, i, x, y;HuffmanTree p;if (n <= 1) return;m = 2 * n - 1;HT =

42、(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->parent = 0; p->lchild = 0; p->rchild = 0;for (; i <= m; +i, +p) p->ch = 0; p->weight = 0; p->parent = 0; p->lchild = 0; p->rc

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

44、 <= j; i+)if (HTi.parent = 0)*x = i; break;for (; i <= j; i+)if (HTi.parent = 0) && (HTi.weight<HT*x.weight)*x = i;HT*x.parent = 1;/查找weight次小的結(jié)點(diǎn)for (i = 1; i <= j; i+)if (HTi.parent = 0)*y = i; break;for (; i <= j; i+)if (HTi.parent = 0) && (i != *x) && (HTi.w

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

46、* 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) * sizeof(char);strcpy(HCi, &cdstart);free(cd);if (fp = fopen(&

47、quot;tobetrans.txt", "rb") = NULL)printf("Open file tobetrans.txt error!n");if (fw = fopen("codefile.txt", "wb+") = NULL)printf("Open file codefile.txt error!n");char temp;fscanf(fp, "%c", &temp); /從文件讀入第一個(gè)字符while (!feof(fp)for (i

48、= 1; i <= n; i+)if (HTi.ch = temp) break; /在赫夫曼樹(shù)中查找字符所在的位置for (int r = 0; HCir != '0' r+) /將字符對(duì)應(yīng)的編碼存入文件fputc(HCir, fw);fscanf(fp, "%c", &temp); /從文件讀入下一個(gè)字符fclose(fw);fclose(fp);printf("n已將文件hfmtree.txt成功編碼,并已存入codefile.txt中！nn");/將文件codefile中的代碼進(jìn)行譯碼，結(jié)果存入文件textfile中

49、void Decoding()FILE *fp, *fw;int m, i;char *code, *text, *p;if (n = 0)n = Read_tree(HT);/從文件hfmtree.txt中讀入赫夫曼樹(shù),返回葉子結(jié)點(diǎn)數(shù)if (fp = fopen("codefile.txt", "rb") = NULL)printf("Open file codefile.txt error!n");if (fw = fopen("textfile.txt", "wb+") = NULL)pr

50、intf("Open file textfile.txt error!n");code = (char *)malloc(sizeof(char);fscanf(fp, "%c", code); /從文件讀入一個(gè)字符for (i = 1; !feof(fp); i+)code = (char *)realloc(code, (i + 1) * sizeof(char); /增加空間fscanf(fp, "%c", &codei); /從文件讀入下一個(gè)字符 codei - 1 = '0'/ codefile.tx

51、t文件中的字符已全部讀入，存放在code數(shù)組中text = (char *)malloc(100 * sizeof(char);p = text;m = 2 * n - 1;if (*code = '0')find(HT, code, text, HTm.lchild, m); /從根節(jié)點(diǎn)的左子樹(shù)去找elsefind(HT, code, text, HTm.rchild, m); /從根節(jié)點(diǎn)的右子樹(shù)去找for (i = 0; pi != '0' i+) /把譯碼好的字符存入文件textfile.txt中fputc(pi, fw);fclose(fp);fclose(fw);printf("n已將codefile.txt文件成功譯碼，兵已存入textfile.txt文件！nn");/將文件codefi1e以緊湊格式顯示在終端上,每行50個(gè)代碼。同時(shí)將此字符形式的編