1、數據結構課程設計設計說明書（題目）哈夫曼編譯器起止日期：2011年6 月20 日至2011年6月27 日學 生 姓 名班級學號成績指導教師（簽字）計算機與通信學院2011年6月23日一、課題任務與說明1 .編輯一個哈夫曼編譯器系統程序2問題描述設某編碼系統共有n個字符，使用頻率分別為Wl,W2,Wn，設 計一個不等長編碼方案，使得該編碼系統的空間效率最好。3. 所具有的功能：（1）為一字符文本編碼功能：將一字符文本復制到指定的文本中，并保存到指定路徑，讓程序自動為它編碼。（2）為部分字符編碼功能：輸入部分字符與對應的字符頻率， 讓程序為之編碼（需注意輸入格式） 。（3）保存輸出到文本功能：將編

2、碼結果輸出到文本。（4）輸出保存文本信息功能：將功能 3 保存的文本信息輸出到 屏幕上，用于查看結果是否正確。4. 設計要求（1）設計數據結構；（2）設計編碼算法；（3）分析時間復雜度和空間復雜度。（4）字符和頻度如下：字符 空格 A B C D E F G H I J K L M N O P Q R S T U VW X Y Z頻度 186 64 13 22 32 103 21 15 47 57 1 2 32 20 57 63 151 48 51 80 23 8 18 1 165. 設計內容與步驟（1）選擇合適的數據結構（2）結點結構的設計（3）算法設計與分析（4）程序設計、實現、調試（5）

3、課程設計說明書6. 設計工作計劃與進度安排（1）設計工作 4 學時（2）實現與調試 16 學時（3）課程設計說明書 4 學時二、算法設計Huffman 編碼是一種可變長編碼方式，是由美國數學家 David Huffman 創立的，是二叉樹的一種特殊轉化形式。編碼的原理是：將 使用次數多的代碼轉換成長度較短的代碼， 而使用次數少的可以使用 較長的編碼，并且保持編碼的唯一可解性。 Huffman 算法的最根本的 原則是：累計的 （ 字符的統計數字 *字符的編碼長度 ） 為最小，也就是 權值（字符的統計數字 *字符的編碼長度 ） 的和最小。三、程序的功能設計為實現系統功能，本程序主要分為五個模塊。它

4、們分別為：1. 初始化功能模塊此功能模塊的功能為從鍵盤接收字符集大小n,以及n各字符和n個權值。2. 建立哈弗曼樹的功能模塊此模塊功能為使用1中或從一文本中得到的數據按照教材 的構造哈夫曼樹的算法構造哈夫曼樹。3. 建立哈夫曼編碼與譯碼的功能模塊此模塊功能為讀入相關的字符信息進行哈夫曼編碼，并將譯 碼結果輸出，在必要時也可保存到文件中。其中各個函數的功能分別如下：notesave函數用于保存輸出的結果； hfmtree函數用于建立結點哈夫曼樹并輸出最終結果； read note函數用于讀取目標文本字符信息；4. 流程圖：四、函數編碼及調試由于本人能力有限難免不會在編碼與調試過程中遇到這樣或 那

5、樣的問題，但通過長時間的改正，查詢資料與詢問，終于能將 出現一些致命錯誤得以修正。例如：在輸入編碼結果信息時由于 少了一個很不明顯的Getchar ()的接收Enter的函數，后面的 就全亂了使程序出現了不能達到意料之中的效果。還有先是運行 完一個函數后就跳出了整個運行程序不能再繼續，后來通過查閱 書籍，明白再主函數中加一個 For語句就可以避免這一問題。第 三個問題就是由于調用完一個函數后顯示的信息還是留在運行界 面，但它們的確有沒什么用且占用界面，不美觀，后來通過詢問 同學得知，在每個要調用的函數后加一個 system（"cls"） 語句就 可達到清除上屏信息的功能。五

6、、總結 該程序主要用于哈夫曼編碼，并在必要時保存數據。做法主 要是用一個主函數MAIN用它達到顯示歡迎界面，提示選擇操作 與調用其它函數功能（用到 Switch 函數），這樣使得程序簡單， 易讀，運行效果也好。但由于能力有限，該程序在時間與空間復 雜度上有待作改正。參考文獻：（1）劉振鵬、張小莉等編著；數據結構（第二版） . 中國鐵道出版社。（2） 石強、羅文浩等編著；數據結果習題解答與實驗指導（第二版）. 中國鐵道出版 社。（3）劉克成 主編；C語言程序設計中國鐵道出版社。附全部代碼 （ 正常運行 VC+6.0）：#in clude<stdio.h>#in clude<c

7、oni o.h>#include<string.h>#include<stdlib.h>#define MAXLEAF 27#define MAXNODE MAXLEAF*2-1#define MAXBIT 25#define MAXVALUE 2000n"#define H "tttypedef structint parent;int weight;int lchild;int rchild;hfm_n;typedef structint bitMAXBIT;int start;hfm_c;void notesave(int n,char

8、a,hfm_c hfm_code)FILE *fp;int i=0,j;char c;if(fp=fopen("d:notesave.txt","w")=NULL) printf("n Cannot open file!n"); getchar();exit(1);for(i=0;i<n;i+)fputc(ai,fp);fputs("->",fp);for(j=hfm_codei.start+1;j<n;j+)c=char(48+hfm_codei.bitj);fputc(c,fp);fputs(

9、" ",fp);if(i+1)%3=0) fputs("n",fp); fclose(fp);printf("n 保存成功 !n");hfm_n *hfmtree(int n,char a,int s)hfm_n hfm_nodeMAXNODE;hfm_c hfm_codeMAXLEAF,cd;int i,j,m1,m2,x1,x2,c,p;char ch1;for(i=0;i<2*n-1;i+)hfm_nodei.weight=0;hfm_nodei.parent=-1;hfm_nodei.lchild=-1;hfm_node

10、i.rchild=-1;for(i=0;i<n;i+)hfm_nodei.weight=si;for(i=0;i<n-1;i+)m1=m2=MAXVALUE;x1=x2=0;for(j=0;j<n+i;j+)if(hfm_nodej.parent=-1&&hfm_nodej.weight<m1)m2=m1;x2=x1;m1=hfm_nodej.weight;x1=j;elseif(hfm_nodej.parent=-1&&hfm_nodej.weight<m2)m2=hfm_nodej.weight;x2=j;hfm_nodex1.

11、parent=hfm_nodex2.parent=n+i;hfm_noden+i.weight=hfm_nodex1.weight+hfm_nodex2.weight;hfm_noden+i.lchild=x1;hfm_noden+i.rchild=x2;for(i=0;i<n;i+)cd.start=n-1;c=i;p=hfm_nodec.parent;while(p!=-1)if(hfm_nodep.lchild=c) cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=hfm_nodec.parent; for(j=cd.st

12、art+1;j<n;j+) hfm_codei.bitj=cd.bitj; hfm_codei.start=cd.start;printf("nn 所有編碼 :n "); for(i=0;i<n;i+)printf("%c",ai);printf("<=>");for(i=0,c=0;i<n;i+)for(j=hfm_codei.start+1;j<n;j+)printf("%d",hfm_codei.bitj);c+; if(c=48|(c-48)%78=0) printf(&

13、quot;n ");printf("nn 各字符對應的編碼 :n"); for(i=0;i<n;i+)printf(" ");printf("%c->",ai);for(j=hfm_codei.start+1;j<n;j+) printf("%d",hfm_codei.bitj);printf(" ");if(i+1)%5=0) printf("n");printf("nn 是否將結果保存到 -> 路徑 D: notesave (y

14、/n)?"); ch1=getchar();getchar();if(ch1='y'|ch1='Y')notesave(n,a,hfm_code);return NULL;int readnote()FILE *fp;int i,j,b26,s26,k;char a26,ch,ch1='n'memset(b,0,sizeof(b);if(fp=fopen("d:note.txt","r")=NULL)printf("n Cannot open the file of note!"

15、;);printf("n Please creat a new text!n");ch1='y'if(ch1='y')此功能你要做的只是將要編碼的字符文本復制到下面文本并將它printf("n 命名為 note 并 n保存到 ->D:.n 需注意的是一定要是字符文本且文本保存路徑是 D 盤下 .n ");system("notepad");printf("n 保存好文本后，請按任意鍵繼續 ");getchar();if(fp=fopen("d:note.txt&quo

16、t;,"r")=NULL)printf("n Open files fail!");getchar();exit(1);while(ch=fgetc(fp)!=EOF)if(sizeof(ch)!=1) break;k=int(ch); if(k>=65&&k<=90)bk-65+;if(k>=97&&k<=122)bk-97+;fclose(fp);printf("n 文本中各字符的頻率為 :n");for(i=0,j=0;i<26;i+)if(bi!=0)ch=char

17、(i+65); aj=ch;sj=bi;printf(" %c->%d ",aj,sj); j+; if(j%6=0) printf("n");hfmtree(j,a,s);return 1;void main()int i,h,n=0,b26;char a26,c30,ch,ch1;for(;)printf("nnntt <<-1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1->>n");printf("tt一一 一一一一一* *n");printf(&

18、quot;tt =>>*歡迎使用本哈夫曼編碼系統 !*<<=n");printf("tt*=n");printf("tt = |功能選項 !_ _ _ _|=n");printf("tt/ =n");printf("tt = |printf("tt = | 1.| =n");為一字符文本編碼 . | =n");printf("tt = | =n");printf("tt = | 2.輸入部分字符與相應頻率為之編碼 .| =n&quo

19、t;);printf("tt = |printf("tt = | 3.| =n");退出程序 . | =n");printf("tt = | =n");printf("tt = | 4. 打開保存的文本 . | =n");printf("tt = | =n");printf("tt = =n");printf(H);printf("ntt 請選擇某功能選項 (14):");scanf("%d",&h);getchar();swi

20、tch(h)case 1: system("cls");printf("n 功能 1: 為一字符文本編碼!n" );read no te();break;case 2: system("cls");printf("n功能 2: 輸入部分字符與相應頻率為之編碼!n");printf("n =>輸入格式應為 : 字符 +空格 n => 例如 :a b cn => 對應的字符頻率格式也應如此 .n");doprintf("n 請輸入葉子結點個數 :");if(scanf("%d",&n)!=1|sizeof(n)!=4)ch='s'printf("n Input worry!n Please input again.n");else ch='n'getchar();while(ch='s');doprintf("n => 請輸入相應個字符 :"