哈夫曼編譯碼課程設(shè)計(jì)

1、目錄目錄一、系統(tǒng)開(kāi)發(fā)的背景一、系統(tǒng)開(kāi)發(fā)的背景.1二、系統(tǒng)分析與設(shè)計(jì)二、系統(tǒng)分析與設(shè)計(jì).1（一）（一）系統(tǒng)功能要求系統(tǒng)功能要求.1（二）（二）系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì).2三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn).3（一）（一）初始化哈夫曼樹：初始化哈夫曼樹：I INITNITH HUFFMANUFFMAN(H(HUFFMANUFFMAN H HFMFM) ).3（二）（二）編碼：編碼：E ENCODINGNCODING（H HUFFMANUFFMAN H HFMFM）.8（三）（三）譯碼：譯碼：D DECODINGECODING(H(HUFFMANUFFMAN H HFMFM）.10（四

2、）（四）印代碼文件：印代碼文件：P PRINTRINT(H(HUFFMANUFFMAN H HFMFM) ).12（五）（五）印哈夫曼樹：印哈夫曼樹：T TREEREEP PRINTRINT(H(HUFFMANUFFMAN H HFMFM) ).13四、系統(tǒng)測(cè)試四、系統(tǒng)測(cè)試.14（一）（一）測(cè)試測(cè)試 MAINMAIN( ( ) )函數(shù)函數(shù).14（二）（二）測(cè)試測(cè)試 I INITNITH HUFFMANUFFMAN(H(HUFFMANUFFMAN H HFMFM) )函數(shù)函數(shù).15（三）（三）測(cè)試測(cè)試 E ENCODINGNCODING(H(HUFFMANUFFMAN H HFMFM) ) 函數(shù)

3、函數(shù).15（四）（四）測(cè)試測(cè)試 D DECODINGECODING(H(HUFFMANUFFMAN H HFMFM) ) 函數(shù)函數(shù).15（五）（五）測(cè)試測(cè)試 P PRINTRINT(H(HUFFMANUFFMAN H HFMFM) )函數(shù)函數(shù).15（六）（六）測(cè)試測(cè)試 T TREEREEP PRINTRINT(H(HUFFMANUFFMAN H HFMFM) )函數(shù)函數(shù).16五五、總結(jié)總結(jié).16六、六、附附件（代碼、部分圖表件（代碼、部分圖表）.171哈夫曼編譯碼器哈夫曼編譯碼器一、一、系統(tǒng)開(kāi)發(fā)的系統(tǒng)開(kāi)發(fā)的背景背景利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但

4、是，這要求在發(fā)送端通過(guò)一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來(lái)的數(shù)據(jù)進(jìn)行譯碼（復(fù)原） 。對(duì)于雙工信道（即可以雙向傳輸信息的信道） ，每端都需要一個(gè)完整的編/譯碼系統(tǒng)。因此要為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)，來(lái)實(shí)現(xiàn)電文的編碼、譯碼和打印輸出。二、系統(tǒng)分析與設(shè)計(jì)二、系統(tǒng)分析與設(shè)計(jì)（一）（一） 系統(tǒng)功能要求系統(tǒng)功能要求一個(gè)完整的哈夫曼系統(tǒng)應(yīng)具有以下功能：1) I：初始化（Initialization） 。從終端讀入字符集大小 n，以及 n個(gè)字符和 n 個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件 hfmTree 中。2) E：編碼（Encoding） 。利用以建好的哈夫曼樹（如不在內(nèi)存，

5、則從文件 hfmTree 中讀入） ，對(duì)文件 ToBeTran 中的正文進(jìn)行編碼，然后將結(jié)果存入文件 CodeFile 中。3) D：譯碼（Decoding） 。利用已建好的哈夫曼樹將文件 CodeFile 中的代碼進(jìn)行譯碼，結(jié)果存入文件 TextFile 中。4) P：印代碼文件（Print） 。將文件 CodeFile 以緊湊格式顯示在終端上，每行 50 個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin 中。5) T：印哈夫曼樹（Tree Printing） 。將已在內(nèi)存中的哈夫曼樹以直2觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrin

6、t 中?！緶y(cè)試數(shù)據(jù)測(cè)試數(shù)據(jù)】1) 利用教科書中的數(shù)據(jù)調(diào)試程序。2) 用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE” 。字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161（二）（二） 系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)系統(tǒng)模塊結(jié)構(gòu)設(shè)計(jì)通過(guò)對(duì)系統(tǒng)功能的分析，哈夫曼編譯碼系統(tǒng)功能如圖 1 所示。圖 1 哈夫曼編譯碼器系統(tǒng)功能圖通過(guò)上圖的功能分析，把整個(gè)系統(tǒng)劃分為 6 個(gè)模塊1、初始化哈夫曼樹（Initial

7、ization） ，該模塊主要實(shí)現(xiàn)：從終端讀入哈夫曼編譯碼器初始化哈夫曼樹編碼譯碼印代碼文件印哈夫曼樹退出系統(tǒng)3字符集大小 n，以及 n 個(gè)字符和 n 個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件 hfmTree 中。借助函數(shù) InitHuffman(Huffman Hfm)來(lái)實(shí)現(xiàn)；2、編碼（Encoding） ，該模塊主要實(shí)現(xiàn)：利用以建好的哈夫曼樹（如不在內(nèi)存，則從文件 hfmTree 中讀入） ，對(duì)文件 ToBeTran 中的正文進(jìn)行編碼，然后將結(jié)果存入文件 CodeFile 中。借助函數(shù) void Encoding(Huffman Hfm)來(lái)實(shí)現(xiàn)；3、譯碼（Decoding） ，該模塊主要實(shí)現(xiàn)：

8、利用已建好的哈夫曼樹將文件CodeFile 中的代碼進(jìn)行譯碼，結(jié)果存入文件 TextFile 中。借助函數(shù)void Decoding(Huffman Hfm)來(lái)實(shí)現(xiàn)；4、印代碼文件（Print） ，該模塊主要實(shí)現(xiàn)：將文件 CodeFile 以緊湊格式顯示在終端上，每行 50 個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件 CodePrin 中。借助函數(shù) Print(Huffman Hfm)來(lái)實(shí)現(xiàn)；5、印哈夫曼樹（Tree Printing） ，該模塊主要實(shí)現(xiàn)：將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrint 中。借助函數(shù)Pri

9、nt(Huffman Hfm)來(lái)實(shí)現(xiàn)；三、系統(tǒng)的設(shè)計(jì)三、系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)與實(shí)現(xiàn)（一）（一） 初始化哈夫曼樹：初始化哈夫曼樹：InitHuffman(HuffmanInitHuffman(Huffman Hfm)Hfm)分析：首先建立一個(gè)哈夫曼樹，對(duì)其進(jìn)行初始化后，然后依次輸入字符和權(quán)值的基本信息，存入文件。流程圖如圖 2 所示。4開(kāi)始定義哈夫曼樹結(jié)構(gòu)體調(diào)用select函數(shù)構(gòu)造哈夫曼樹輸入哈夫曼樹結(jié)點(diǎn)i，nreturn HfmHuffman InitHuffman(Huffman Hfm)fp=fopen(hfmTree,rt)Hfm=InputHuffman(Hfm)輸入Hfm.ciHfm.H

10、Ti.weightHfm=HuffmanCoding(Hfm)return Hfm圖 2：InitHuffman(Huffman Hfm)流程圖該模塊的具體代碼如下所示。5#include #include #include #include#include#define Maxsize 1000#define Max 100typedef char *HuffmanCode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼表碼表typedef struct int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedef st

11、ruct HuffmanTree HT; char *c; int length; HuffmanCode HC;Huffman;/全局結(jié)構(gòu)體變量，來(lái)存儲(chǔ)字符與代碼void Select(HuffmanTree HT,int end,int *s1,int *s2)/選擇 HT1.i-1中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為 s1，s2 int i; int min1=Maxsize; int min2; for (i=1;i=end;i+)/遍歷查找權(quán)值最小的結(jié)點(diǎn) S1 if (HTi.parent=0&HTi.weightmin1) *s1=i; min1=HTi.weight;

12、min2=Maxsize; for(i=1;iHTi.weight) *s2=i; min2=HTi.weight; Huffman HuffmanCoding(Huffman Hfm) /存放 n 個(gè)字符的權(quán)值（均0） ，構(gòu)造哈夫曼樹 HT，并求出 n 個(gè)字符的構(gòu)造哈夫曼編碼 HC6 int i,n,m,s1,s2,start; int c,f; char *cd; n=Hfm.length; if(n=1) return Hfm; m=2*n-1; for(i=n+1;i=m;+i) /選擇 HT1.i-1中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2 Select(Hfm.HT,i-1

13、,&s1,&s2); Hfm.HTs1.parent=i;/修改父親位置 Hfm.HTs2.parent=i; Hfm.HTi.lchild=s1;/修改孩子位置 Hfm.HTi.rchild=s2; Hfm.HTi.weight=Hfm.HTs1.weight+Hfm.HTs2.weight;/父親結(jié)點(diǎn)權(quán)值為左右孩子權(quán)值之和 /從葉子結(jié)點(diǎn)到根逆向求每個(gè)字符的哈夫曼編碼 Hfm.HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/分配 n 個(gè)字符編碼的頭指針向量 cd=(char *)malloc(n*sizeof(char);/分配求編碼的

14、工作空間 cdn-1=0;/編碼結(jié)束符 for(i=1;i=n;+i)/逐個(gè)字符求哈夫曼編碼 start=n-1;/編碼結(jié)束符位置 for(c=i,f=Hfm.HTi.parent;f!=0;c=f,f=Hfm.HTf.parent)/從葉子到根逆向求編碼 if(c=Hfm.HTf.lchild) cd-start=0; else cd-start=1; Hfm.HCi=(char *)malloc(n-start)*sizeof(char); strcpy(Hfm.HCi,&cdstart);/從 cd 復(fù)制編碼到 Hfm.HC free(cd);/釋放工作空間 return Hfm

15、;Huffman InputHuffman(Huffman Hfm)/輸入函數(shù)，控制用戶輸入字符和相應(yīng)權(quán)值 int i,n; printf(請(qǐng)輸入字符個(gè)數(shù): ); scanf(%d,&n); if(n=1) 7 printf(只有一個(gè)字符!不需要編碼!n);/若只有一個(gè)數(shù)值則無(wú)需編碼 printf(請(qǐng)輸入字符個(gè)數(shù): ); scanf(%d,&n); Hfm.HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); Hfm.c=(char *)malloc(n+1)*sizeof(char); for(i=1;i=n;i+) printf(請(qǐng)輸入字符

16、: ); scanf(%s,&Hfm.ci); printf(請(qǐng)輸入這個(gè)字符的權(quán)值: ); scanf(%d,&Hfm.HTi.weight); Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; for(;i=2*n-1;+i) Hfm.HTi.weight=0; Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; Hfm.length=n; return Hfm; Huffman InitHuffman(Huffman Hfm)/初始化哈夫曼數(shù)，要求用戶輸入字符和

17、相應(yīng)權(quán)值 int n,i,x; FILE *fp; fp=fopen(hfmTree,rt);/對(duì)文件 hfmTree 以讀文本的形式打開(kāi) if(fp=NULL) Hfm=InputHuffman(Hfm);/調(diào)用 InputHuffman 函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈夫曼數(shù)中 fp=fopen(hfmTree,wt); fprintf(fp,%dn,Hfm.length); for(i=1;i=Hfm.length;i+) fprintf(fp,%c %d ,Hfm.ci,Hfm.HTi.weight); rewind(fp); else 8printf(字符已存在!n); Hfm=I

18、nputHuffman(Hfm);/調(diào)用 InputHuffman 函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈弗曼數(shù)中 fp=fopen(hfmTree,w+); fprintf(fp,%dn,Hfm.length); for(i=1;i=Hfm.length;i+) fprintf(fp,%c %d ,Hfm.ci,Hfm.HTi.weight); rewind(fp); fscanf(fp,%dn,&n); Hfm.c=(char *)malloc(n+1)*sizeof(char); Hfm.HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); for(

19、i=1;i=n;i+) fscanf(fp,%s %d ,&Hfm.ci,&Hfm.HTi.weight);/將已經(jīng)在文件中的字符和其對(duì)應(yīng)的權(quán)重輸入到 Hfm.ci和&Hfm.HTi.weight 中 for(i=1;i=n;i+)/對(duì)每個(gè)節(jié)點(diǎn)初始化 Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; for(;i=2*n-1;+i) Hfm.HTi.weight=0; Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; Hfm.length=n; fclos

20、e(fp); Hfm=HuffmanCoding(Hfm); return Hfm; （二）（二） 編碼：編碼：EncodingEncoding（HuffmanHuffman HfmHfm）分析：利用已建好的 Huffman 樹（如不在內(nèi)存，則從文件 hfmTre中讀入） ，對(duì)文件中的正文進(jìn)行編碼，然后將結(jié)果存入文件 CodeFile 中。流程圖如圖 3 所示。9Encoding(Huffman Hfm)fw=fopen(ToBeTran,r+)=NULL輸入字符串輸出編碼Hfm.HCi輸出編碼文件Hfm.HCi圖 3：Encoding(Huffman Hfm)流程圖該模塊的具體代碼如下所示。

21、void Encoding(Huffman Hfm)/利用已建好的 Huffman 樹（如不在內(nèi)存，則從文件hfmTree 中讀入） ，對(duì)文件 ToBeTran 中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile 中。 int i=0,j=0,n; char chMax; FILE *fp,*fw; n=Hfm.length; if(fw=fopen(ToBeTran,r+)=NULL)/嘗試打開(kāi) ToBeTran printf(請(qǐng)輸入字符串：n ); scanf(%s,ch); printf(n); fp=fopen(CodeFile,wt+); else fscanf(fw,%s,ch)

22、; fclose(fw); while(chj)10 for(i=1;ilchild|p-rchild) if(dj=0) i=p-lchild; p=&Hfm.HTi; else i=p-rchild; p=&Hfm.HTi; j+; printf(%c,Hfm.ci); fprintf(fp,%c,Hfm.ci);12 printf(n); fclose(fp);（四）（四） 印代碼文件：印代碼文件：Print(HuffmanPrint(Huffman Hfm)Hfm)分析：將文件 CodeFile 以緊湊格式顯示在終端上流程圖。如圖 5 所示。void Print(Huf

23、fman Hfm)輸出,Hfm.ciHfm.HTi.weight輸出編碼輸出譯碼圖 5：Printf(Huffman Hfm)流程圖該模塊的具體代碼如下所示。void Print(Huffman Hfm)/將文件 CodeFile 以緊湊格式顯示在終端上，每行 50 個(gè)代碼。 int i,n; int m=1;/計(jì)數(shù)器 char ch; FILE* fprint; n=Hfm.length; printf(輸出字符的代碼:n); for(i=1;i=n;i+)/顯示每一個(gè)字符對(duì)應(yīng)的哈夫曼編碼 printf(n); printf(Char: %ct,Hfm.ci); printf(Weight:

24、 %dt,Hfm.HTi.weight); printf(Code: ); puts(Hfm.HCi);13 fprint=fopen(CodeFile,rb); while ( feof(fprint)=0 ) ch=fgetc(fprint); printf(%c,ch); m+; if (m%50=0)/保證每一行輸出 50 個(gè)字符 printf(n); printf(n); fclose(fprint);（五）（五） 印哈夫曼樹：印哈夫曼樹：TreePrint(HuffmanTreePrint(Huffman Hfm)Hfm)分析：將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯

25、示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrint 中。如圖 6 所示。void TreePrint(Huffman Hfm)輸出,Hfm.ciHfm.HTi.weight輸出編碼輸出譯碼圖 6：TreePrintf(Huffman Hfm)流程圖該模塊的具體代碼如下所示。void TreePrint(Huffman Hfm)/將文件 CodeFile 以緊湊格式顯示在終端上，每行 50 個(gè)代碼。 int i,n; int m=1;/計(jì)數(shù)器 char ch;14 FILE* fprint; n=Hfm.length; printf(輸出字符的代碼:n); for(i=1;i=n

26、;i+)/顯示每一個(gè)字符對(duì)應(yīng)的哈夫曼編碼 printf(n); printf(Char: %ct,Hfm.ci); printf(Weight: %dt,Hfm.HTi.weight); printf(Code: ); puts(Hfm.HCi); fprint=fopen(CodeFile,rb); while ( feof(fprint)=0 ) ch=fgetc(fprint); printf(%c,ch); m+; if (m%50=0)/保證每一行輸出 50 個(gè)字符 printf(n); printf(n); fclose(fprint);四、系統(tǒng)測(cè)試四、系統(tǒng)測(cè)試（一）（一） 測(cè)試測(cè)

27、試 main(main( ) )函數(shù)函數(shù)測(cè)試該函數(shù)使用的測(cè)試方法，測(cè)試的具體步驟，測(cè)試的結(jié)果。15圖 7：void main()函數(shù)測(cè)試結(jié)果圖（二）（二） 測(cè)試測(cè)試 InitHuffman(HuffmanInitHuffman(Huffman Hfm)Hfm)函數(shù)函數(shù)圖 8：InitHuffman(Huffman Hfm)函數(shù)測(cè)試結(jié)果圖（三）（三） 測(cè)試測(cè)試 Encoding(HuffmanEncoding(Huffman Hfm)Hfm) 函數(shù)函數(shù)圖 9：Encoding(Huffman Hfm)函數(shù)測(cè)試結(jié)果圖（四）（四） 測(cè)試測(cè)試 Decoding(HuffmanDecoding(Huff

28、man Hfm)Hfm) 函數(shù)函數(shù)16圖 10：Decoding(Huffman Hfm)函數(shù)測(cè)試結(jié)果圖（五）（五） 測(cè)試測(cè)試 Print(HuffmanPrint(Huffman Hfm)Hfm)函數(shù)函數(shù)圖 11：Print(Huffman Hfm)函數(shù)測(cè)試結(jié)果圖（六）（六） 測(cè)試測(cè)試 TreePrint(HuffmanTreePrint(Huffman Hfm)Hfm)函數(shù)函數(shù)17圖 12：TreePrintf(Huffman Hfm)函數(shù)測(cè)試結(jié)果圖五、總結(jié)五、總結(jié)系統(tǒng)完成了對(duì)所建的哈夫曼樹進(jìn)行初始化、編碼、譯碼、打印輸出功能。但是將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在

29、終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件 TreePrint 中比較困難不能完全實(shí)現(xiàn)。通過(guò)本次數(shù)據(jù)結(jié)構(gòu)的課程設(shè)計(jì)，我學(xué)習(xí)了很多在上課沒(méi)懂的知識(shí)，并對(duì)求哈夫曼樹及哈夫曼編碼/譯碼的算法有了更加深刻的了解，更鞏固了課堂中學(xué)習(xí)有關(guān)于哈夫曼編碼的知識(shí)，真正學(xué)會(huì)一種算法了。當(dāng)求解一個(gè)算法時(shí),不是拿到問(wèn)題就不加思索地做，而是首先要先對(duì)它有個(gè)大概的了解，接著再詳細(xì)地分析每一步怎么做，無(wú)論自己以前是否有處理過(guò)相似的問(wèn)題，只要按照以上的步驟，通過(guò)認(rèn)真分析必定會(huì)做出來(lái)。 這次課程設(shè)計(jì)，我在編輯中犯了不應(yīng)有的錯(cuò)誤，設(shè)計(jì)統(tǒng)計(jì)字符和合并時(shí)忘記應(yīng)該怎樣保存數(shù)據(jù)，對(duì)文件的操作也很生疏，通過(guò)查閱 c 語(yǔ)言課本第十章文件的輸

30、入輸出，我基本掌握了文件的操作，在不斷分析后明確并改正了錯(cuò)誤和疏漏，我的程序更加完善。六、附件（代碼、部分圖表）六、附件（代碼、部分圖表）#include #include #include #include18#include#define Maxsize 1000#define Max 100typedef char *HuffmanCode;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼表碼表typedef struct int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;/動(dòng)態(tài)分配數(shù)組存儲(chǔ)哈夫曼樹typedef struct HuffmanTre

31、e HT; char *c; int length; HuffmanCode HC;Huffman;/全局結(jié)構(gòu)體變量，來(lái)存儲(chǔ)字符與代碼void Select(HuffmanTree HT,int end,int *s1,int *s2)/選擇 HT1.i-1中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為 s1，s2 int i; int min1=Maxsize; int min2; for (i=1;i=end;i+)/遍歷查找權(quán)值最小的結(jié)點(diǎn) S1 if (HTi.parent=0&HTi.weightmin1) *s1=i; min1=HTi.weight; min2=Maxsize; f

32、or(i=1;iHTi.weight) *s2=i; min2=HTi.weight; Huffman HuffmanCoding(Huffman Hfm) /存放 n 個(gè)字符的權(quán)值（均0） ，構(gòu)造哈夫曼樹 HT，并求出 n 個(gè)字符的構(gòu)造哈夫曼編碼 HC int i,n,m,s1,s2,start; int c,f; char *cd;19 n=Hfm.length; if(n=1) return Hfm; m=2*n-1; for(i=n+1;i=m;+i) /選擇 HT1.i-1中無(wú)雙親且權(quán)值最小的兩個(gè)節(jié)點(diǎn)，其序號(hào)為s1，s2 Select(Hfm.HT,i-1,&s1,&

33、s2); Hfm.HTs1.parent=i;/修改父親位置 Hfm.HTs2.parent=i; Hfm.HTi.lchild=s1;/修改孩子位置 Hfm.HTi.rchild=s2; Hfm.HTi.weight=Hfm.HTs1.weight+Hfm.HTs2.weight;/父親結(jié)點(diǎn)權(quán)值為左右孩子權(quán)值之和 /從葉子結(jié)點(diǎn)到根逆向求每個(gè)字符的哈夫曼編碼 Hfm.HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/分配 n 個(gè)字符編碼的頭指針向量 cd=(char *)malloc(n*sizeof(char);/分配求編碼的工作空間 cdn-1=0;/

34、編碼結(jié)束符 for(i=1;i=n;+i)/逐個(gè)字符求哈夫曼編碼 start=n-1;/編碼結(jié)束符位置 for(c=i,f=Hfm.HTi.parent;f!=0;c=f,f=Hfm.HTf.parent)/從葉子到根逆向求編碼 if(c=Hfm.HTf.lchild) cd-start=0; else cd-start=1; Hfm.HCi=(char *)malloc(n-start)*sizeof(char); strcpy(Hfm.HCi,&cdstart);/從 cd 復(fù)制編碼到 Hfm.HC free(cd);/釋放工作空間 return Hfm;Huffman Input

35、Huffman(Huffman Hfm)/輸入函數(shù)，控制用戶輸入字符和相應(yīng)權(quán)值 int i,n; printf(請(qǐng)輸入字符個(gè)數(shù): ); scanf(%d,&n); if(n=1) printf(只有一個(gè)字符!不需要編碼!n);/若只有一個(gè)數(shù)值則無(wú)需編碼 printf(請(qǐng)輸入字符個(gè)數(shù): ); scanf(%d,&n);20 Hfm.HT=(HuffmanTree)malloc(2*n)*sizeof(HTNode); Hfm.c=(char *)malloc(n+1)*sizeof(char); for(i=1;i=n;i+) printf(請(qǐng)輸入字符: ); scanf(%s,

36、&Hfm.ci); printf(請(qǐng)輸入這個(gè)字符的權(quán)值: ); scanf(%d,&Hfm.HTi.weight); Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; for(;i=2*n-1;+i) Hfm.HTi.weight=0; Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; Hfm.length=n; return Hfm; Huffman InitHuffman(Huffman Hfm)/初始化哈夫曼數(shù)，要求用戶輸入字符和相應(yīng)權(quán)值 int n,i,x

37、; FILE *fp; fp=fopen(hfmTree,rt);/對(duì)文件 hfmTree 以讀文本的形式打開(kāi) if(fp=NULL) Hfm=InputHuffman(Hfm);/調(diào)用 InputHuffman 函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈夫曼數(shù)中 fp=fopen(hfmTree,wt); fprintf(fp,%dn,Hfm.length); for(i=1;i=Hfm.length;i+) fprintf(fp,%c %d ,Hfm.ci,Hfm.HTi.weight); rewind(fp); else printf(字符已存在!n); Hfm=InputHuffman(Hfm

38、);/調(diào)用 InputHuffman 函數(shù)，用戶輸入字符和相應(yīng)權(quán)值存入哈弗曼數(shù)中 fp=fopen(hfmTree,w+);21 fprintf(fp,%dn,Hfm.length); for(i=1;i=Hfm.length;i+) fprintf(fp,%c %d ,Hfm.ci,Hfm.HTi.weight); rewind(fp); else fscanf(fp,%dn,&n); for(i=1;i=n;i+) fscanf(fp,%s %d ,&Hfm.ci,&Hfm.HTi.weight);/將已經(jīng)在文件中的字符和其對(duì)應(yīng)的權(quán)重輸入到 Hfm.ci和&

39、Hfm.HTi.weight 中 for(i=1;i=n;i+)/對(duì)每個(gè)節(jié)點(diǎn)初始化 Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; for(;i=2*n-1;+i) Hfm.HTi.weight=0; Hfm.HTi.parent=0; Hfm.HTi.lchild=0; Hfm.HTi.rchild=0; Hfm.length=n; fclose(fp); Hfm=HuffmanCoding(Hfm); return Hfm; void Encoding(Huffman Hfm)/利用已建好的 Huffman 樹（如不在內(nèi)存，則從文

40、件 hfmTree 中讀入） ，對(duì)文件 ToBeTran 中的正文進(jìn)行編碼，然后將結(jié)果存入文件 CodeFile 中。 int i=0,j=0,n; char chMax; FILE *fp,*fw; n=Hfm.length; if(fw=fopen(ToBeTran,r+)=NULL)/嘗試打開(kāi) ToBeTran printf(請(qǐng)輸入字符串：n ); scanf(%s,ch); printf(n);22 fp=fopen(CodeFile,wt+); else fscanf(fw,%s,ch); fclose(fw); while(chj) for(i=1;ilchild|p-rchild) if(dj=0) i=p-lchild; p=&Hfm.HTi; else i=p-rchild; p=&Hfm.HTi; j+; printf(%c,Hfm.ci); fprintf(fp,%c,Hfm.ci); printf(n); fclose(fp);void Print(Huffman Hfm)/將文件 CodeFile 以緊湊格式顯示在終端上，每行 50 個(gè)代碼。 int i,n; int m=1;/計(jì)數(shù)器 char ch; FILE* fprint; n