1、目錄目錄一、系統開發的背景一、系統開發的背景.1二、系統分析與設計二、系統分析與設計.1（一）（一）系統功能要求系統功能要求.1（二）（二）系統模塊結構設計系統模塊結構設計.2三、系統的設計與實現三、系統的設計與實現.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四、系統測試四、系統測試.14（一）（一）測試測試 MAINMAIN( ( ) )函數函數.14（二）（二）測試測試 I INITNITH HUFFMANUFFMAN(H(HUFFMANUFFMAN H HFMFM) )函數函數.15（三）（三）測試測試 E ENCODINGNCODING(H(HUFFMANUFFMAN H HFMFM) ) 函數

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

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

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

6、t 中。【測試數據測試數據】1) 利用教科書中的數據調試程序。2) 用下表給出的字符集和頻度的實際統計數據建立哈夫曼樹，并實現以下報文的編碼和譯碼：“THIS PROGRAM IS MY FAVORITE” 。字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220字符NOPQRSTUVWXYZ頻度5763151485180238181161（二）（二） 系統模塊結構設計系統模塊結構設計通過對系統功能的分析，哈夫曼編譯碼系統功能如圖 1 所示。圖 1 哈夫曼編譯碼器系統功能圖通過上圖的功能分析，把整個系統劃分為 6 個模塊1、初始化哈夫曼樹（Initial

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

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

9、nt(Huffman Hfm)來實現；三、系統的設計三、系統的設計與實現與實現（一）（一） 初始化哈夫曼樹：初始化哈夫曼樹：InitHuffman(HuffmanInitHuffman(Huffman Hfm)Hfm)分析：首先建立一個哈夫曼樹，對其進行初始化后，然后依次輸入字符和權值的基本信息，存入文件。流程圖如圖 2 所示。4開始定義哈夫曼樹結構體調用select函數構造哈夫曼樹輸入哈夫曼樹結點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;/動態分配數組存儲哈夫曼表碼表typedef struct int weight; int parent,lchild,rchild;HTNode,*HuffmanTree;/動態分配數組存儲哈夫曼樹typedef st

11、ruct HuffmanTree HT; char *c; int length; HuffmanCode HC;Huffman;/全局結構體變量，來存儲字符與代碼void Select(HuffmanTree HT,int end,int *s1,int *s2)/選擇 HT1.i-1中無雙親且權值最小的兩個節點，其序號為 s1，s2 int i; int min1=Maxsize; int min2; for (i=1;i=end;i+)/遍歷查找權值最小的結點 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 個字符的權值（均0） ，構造哈夫曼樹 HT，并求出 n 個字符的構造哈夫曼編碼 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中無雙親且權值最小的兩個節點，其序號為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;/父親結點權值為左右孩子權值之和 /從葉子結點到根逆向求每個字符的哈夫曼編碼 Hfm.HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/分配 n 個字符編碼的頭指針向量 cd=(char *)malloc(n*sizeof(char);/分配求編碼的

14、工作空間 cdn-1=0;/編碼結束符 for(i=1;i=n;+i)/逐個字符求哈夫曼編碼 start=n-1;/編碼結束符位置 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 復制編碼到 Hfm.HC free(cd);/釋放工作空間 return Hfm

15、;Huffman InputHuffman(Huffman Hfm)/輸入函數，控制用戶輸入字符和相應權值 int i,n; printf(請輸入字符個數: ); scanf(%d,&n); if(n=1) 7 printf(只有一個字符!不需要編碼!n);/若只有一個數值則無需編碼 printf(請輸入字符個數: ); 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(請輸入字符

16、: ); scanf(%s,&Hfm.ci); printf(請輸入這個字符的權值: ); 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)/初始化哈夫曼數，要求用戶輸入字符和

17、相應權值 int n,i,x; FILE *fp; fp=fopen(hfmTree,rt);/對文件 hfmTree 以讀文本的形式打開 if(fp=NULL) Hfm=InputHuffman(Hfm);/調用 InputHuffman 函數，用戶輸入字符和相應權值存入哈夫曼數中 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);/調用 InputHuffman 函數，用戶輸入字符和相應權值存入哈弗曼數中 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);/將已經在文件中的字符和其對應的權重輸入到 Hfm.ci和&Hfm.HTi.weight 中 for(i=1;i=n;i+)/對每個節點初始化 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 樹（如不在內存，則從文件 hfmTre中讀入） ，對文件中的正文進行編碼，然后將結果存入文件 CodeFile 中。流程圖如圖 3 所示。9Encoding(Huffman Hfm)fw=fopen(ToBeTran,r+)=NULL輸入字符串輸出編碼Hfm.HCi輸出編碼文件Hfm.HCi圖 3：Encoding(Huffman Hfm)流程圖該模塊的具體代碼如下所示。

21、void Encoding(Huffman Hfm)/利用已建好的 Huffman 樹（如不在內存，則從文件hfmTree 中讀入） ，對文件 ToBeTran 中的正文進行編碼，然后將結果存入文件CodeFile 中。 int i=0,j=0,n; char chMax; FILE *fp,*fw; n=Hfm.length; if(fw=fopen(ToBeTran,r+)=NULL)/嘗試打開 ToBeTran printf(請輸入字符串：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 個代碼。 int i,n; int m=1;/計數器 char ch; FILE* fprint; n=Hfm.length; printf(輸出字符的代碼:n); for(i=1;i=n;i+)/顯示每一個字符對應的哈夫曼編碼 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 個字符 printf(n); printf(n); fclose(fprint);（五）（五） 印哈夫曼樹：印哈夫曼樹：TreePrint(HuffmanTreePrint(Huffman Hfm)Hfm)分析：將已在內存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯

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

26、;i+)/顯示每一個字符對應的哈夫曼編碼 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 個字符 printf(n); printf(n); fclose(fprint);四、系統測試四、系統測試（一）（一） 測試測

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

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

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

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

31、e HT; char *c; int length; HuffmanCode HC;Huffman;/全局結構體變量，來存儲字符與代碼void Select(HuffmanTree HT,int end,int *s1,int *s2)/選擇 HT1.i-1中無雙親且權值最小的兩個節點，其序號為 s1，s2 int i; int min1=Maxsize; int min2; for (i=1;i=end;i+)/遍歷查找權值最小的結點 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 個字符的權值（均0） ，構造哈夫曼樹 HT，并求出 n 個字符的構造哈夫曼編碼 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中無雙親且權值最小的兩個節點，其序號為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;/父親結點權值為左右孩子權值之和 /從葉子結點到根逆向求每個字符的哈夫曼編碼 Hfm.HC=(HuffmanCode)malloc(n+1)*sizeof(char *);/分配 n 個字符編碼的頭指針向量 cd=(char *)malloc(n*sizeof(char);/分配求編碼的工作空間 cdn-1=0;/

34、編碼結束符 for(i=1;i=n;+i)/逐個字符求哈夫曼編碼 start=n-1;/編碼結束符位置 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 復制編碼到 Hfm.HC free(cd);/釋放工作空間 return Hfm;Huffman Input

35、Huffman(Huffman Hfm)/輸入函數，控制用戶輸入字符和相應權值 int i,n; printf(請輸入字符個數: ); scanf(%d,&n); if(n=1) printf(只有一個字符!不需要編碼!n);/若只有一個數值則無需編碼 printf(請輸入字符個數: ); 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(請輸入字符: ); scanf(%s,

36、&Hfm.ci); printf(請輸入這個字符的權值: ); 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)/初始化哈夫曼數，要求用戶輸入字符和相應權值 int n,i,x

37、; FILE *fp; fp=fopen(hfmTree,rt);/對文件 hfmTree 以讀文本的形式打開 if(fp=NULL) Hfm=InputHuffman(Hfm);/調用 InputHuffman 函數，用戶輸入字符和相應權值存入哈夫曼數中 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、);/調用 InputHuffman 函數，用戶輸入字符和相應權值存入哈弗曼數中 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);/將已經在文件中的字符和其對應的權重輸入到 Hfm.ci和&

39、Hfm.HTi.weight 中 for(i=1;i=n;i+)/對每個節點初始化 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 樹（如不在內存，則從文

40、件 hfmTree 中讀入） ，對文件 ToBeTran 中的正文進行編碼，然后將結果存入文件 CodeFile 中。 int i=0,j=0,n; char chMax; FILE *fp,*fw; n=Hfm.length; if(fw=fopen(ToBeTran,r+)=NULL)/嘗試打開 ToBeTran printf(請輸入字符串：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 個代碼。 int i,n; int m=1;/計數器 char ch; FILE* fprint; n