赫夫曼編譯碼器說明書

1、目目 錄錄摘摘 要要 .1 1前前 言言 .2 2正正 文文 .3 31.采用類C語言定義相關(guān)的數(shù)據(jù)類型.32.各模塊的偽碼算法 .33.函數(shù)的調(diào)用關(guān)系圖 .34.調(diào)試分析 .35.測試結(jié)果 .36.源程序（帶注釋） .3總總 結(jié)結(jié) .4 4參考文獻參考文獻 .5 5致致 謝謝 .6 6附件附件 部分源程序代碼部分源程序代碼 .7 71摘摘 要要本課程設(shè)計主要研究如何解決本課程設(shè)計主要研究如何解決對于給定的葉子數(shù)目及其權(quán)值構(gòu)造對于給定的葉子數(shù)目及其權(quán)值構(gòu)造最優(yōu)二叉樹的方法最優(yōu)二叉樹的方法。通過對問題的分析，采用哈夫曼算法的設(shè)計思想。通過對問題的分析，采用哈夫曼算法的設(shè)計思想。根據(jù)給定的權(quán)值構(gòu)成

2、二叉樹森林，在森林中任意選取兩棵根結(jié)點權(quán)值根據(jù)給定的權(quán)值構(gòu)成二叉樹森林，在森林中任意選取兩棵根結(jié)點權(quán)值最小的樹，將這兩棵樹合并為新的樹，為保證新樹仍為二叉樹，需要最小的樹，將這兩棵樹合并為新的樹，為保證新樹仍為二叉樹，需要增加一個新的結(jié)點作為根增加一個新的結(jié)點作為根將這兩個孩子的權(quán)值之和作為新樹根的權(quán)值。將這兩個孩子的權(quán)值之和作為新樹根的權(quán)值。對新的森林重復(fù)上述步驟直到森林中只剩一棵樹為止。此樹即為哈夫?qū)π碌纳种貜?fù)上述步驟直到森林中只剩一棵樹為止。此樹即為哈夫曼樹曼樹。2前前 言言字符以某種編碼形式存儲在計算機中，目前世界上應(yīng)用最廣泛的兩個字符是ASCII 碼（美國信息交換標(biāo)準碼）和 EBC

3、DIC 碼（擴充的二進制的十進制信息碼） 。當(dāng)采納這兩個字符集時字符在計算機內(nèi)是以固定長度的比特串表示的。但事實上，在具體應(yīng)用中字符集中字符的使用頻率常常差別很大，為了提高存儲和傳輸?shù)男剩刹捎貌坏乳L的編碼方式。若要設(shè)計不等長編碼，則要求對字符集中任一字符的編碼都不是另一個字符編碼的前綴，稱這種編碼符合前綴特性，也稱前綴編碼，前綴編碼可以一個字符一個字符地進行譯碼，不需要在字符之間添加分隔符。利用哈夫曼編碼可以解決上述問題。3正正 文文1.1. 采用類采用類 c c 語言定義相關(guān)的數(shù)據(jù)類型語言定義相關(guān)的數(shù)據(jù)類型用 C 語言實現(xiàn) :typedef struct HaffmanTreeNode

4、char ch, code15; /ch 代表當(dāng)前字符，code 代表這個字符的編碼 int weight; /當(dāng)前統(tǒng)計的字符的個數(shù) int parent, lchild, rchild; HTNode, *HaTree; typedef struct HTNode arrMAX_NODE; int total; HTree; Max_Node 代表數(shù)的最大結(jié)點數(shù) Max_Weight 代表權(quán)值的最大值typedef struct /結(jié)點類型int weight; /根節(jié)點的權(quán)值int flag; /標(biāo)志位,為 0 即沒有雙親,反之則是int parent; /雙親結(jié)點 char ch; /要

5、編碼的字符,即哈夫曼樹葉子int lchild; /根節(jié)點的左孩子4int rchild; /根節(jié)點的右孩子HafNode;typedef struct /哈夫曼編碼int bitMAX_NODE; /二進制編碼位,用于存放哈夫曼樹編碼int start; /編碼的值在數(shù)組存放的起始位置int weight; /要編碼的字符出現(xiàn)的頻率,即權(quán)值char ch; /要編碼的字符Code;typedef struct /編碼操作類型char bitMAX_NODE; /將字符的編碼結(jié)果存入 bit 數(shù)組中char ch; /要編碼的字符int weight; /字符出現(xiàn)的頻率Coding;typed

6、ef struct /輸入字符信息 HafNode arrMAX_NODE; /數(shù)組結(jié)點信息 int total; /統(tǒng)計輸入字符的種類個數(shù) HTree;52.2. 各模塊的偽碼算法各模塊的偽碼算法算法描述 : int statistic_char(char *text, HTree *t) /* 統(tǒng)計字符出現(xiàn)的頻率 */ int text_len = strlen(text); t-total = 0; for (i=0; itext_len; i+) for (j=0;jtotal ; j+) if (t-arrj.ch = texti) .統(tǒng)計已經(jīng)出現(xiàn)的字符的個數(shù) if (j=t-tot

7、al) .記錄新出現(xiàn)的字符 return t-total; /打印出字符和它們的出現(xiàn)的次數(shù) int create_htree(HTree *t) /* 建立一棵赫夫曼樹,并對數(shù)據(jù)初始化 */ for (i=0; itotal total_node) /初始森林根節(jié)點數(shù)小于合并后新樹的所有結(jié)點數(shù)6 min1 = min2 = Max_Weight; for (i=0; itotal; i+) .找到當(dāng)前權(quán)值最小的兩個結(jié)點,并把它們建立成一棵新樹,其中樹根的權(quán)值為這兩個的權(quán)值的和 t-total +; return 0; void coding(HTree *t, int head_i, char

8、 *code) /* 對哈夫曼樹進行編碼 */ if ( head_i = -1) /判斷是否為空，為空返回 return;.從樹的根節(jié)點出發(fā)，查找左子樹輸出 0，查找右子樹輸出 1，直到找到該樹的葉子結(jié)點，按每個葉子結(jié)點在數(shù)組中的下標(biāo)依次輸出 void print_htree_ldr(HTree *t, int head_i, int deep, int* path) /* 中序打印樹 */ .判斷是否為空樹，是的話返回；不是的話，按照先輸出左孩子，然后輸出雙親，再輸出右孩子的方法依次打印各個字符和它的權(quán)值； void code_string(char *text, HTree *t) /*

9、 對字符進行編碼 */ 變量初始化： 7 for (條件判斷) 依次輸出每個字符的編碼 3.3. 函數(shù)的調(diào)用關(guān)系圖函數(shù)的調(diào)用關(guān)系圖4.4. 調(diào)試分析調(diào)試分析a、調(diào)試中遇到的問題及對問題的解決方法調(diào)試過程中遇到的問題及解決： 我在該程序中遇到的最大問題是如何以文件形式存儲赫夫曼樹，以及如何從文件讀取赫夫曼樹，讀與存都要涉及到字符串轉(zhuǎn)換成整數(shù)或整數(shù)轉(zhuǎn)換成字符串的問題，最后終于成功了，可是很耗時，不知道是不是我的方法太不好了。b、算法的時間復(fù)雜度和空間復(fù)雜度算法的時空分析 在此程序中，存儲字符串都用了指針，先動態(tài)申請空間，然后再存，這樣就有效的利用了空間，不過為了實現(xiàn)任意長字符串的輸入，最后轉(zhuǎn)存到字

10、符指針里，這樣就浪費了一些空間。 而對于哈夫曼樹算法本身，由于這里只是一個靜態(tài)的，所以當(dāng)進行網(wǎng)絡(luò)傳輸時，可能會顯得效率比較低。 85.5. 測試結(jié)果測試結(jié)果910116.6. 源程序（帶注釋）源程序（帶注釋）#include #include #include #define MAX_NODE 100 /代表哈夫曼樹最大的結(jié)點數(shù)#define MAX_VALUE 10000 /代表權(quán)值的最大值typedef struct /結(jié)點類型int weight; /根節(jié)點的權(quán)值int flag; /標(biāo)志位,為 0 即沒有雙親,反之則是int parent; /雙親結(jié)點 char ch; /要編碼的字符

11、,即哈夫曼樹葉子int lchild; /根節(jié)點的左孩子int rchild; /根節(jié)點的右孩子HafNode;12typedef struct /哈夫曼編碼int bitMAX_NODE; /二進制編碼位,用于存放哈夫曼樹編碼int start; /編碼的值在數(shù)組存放的起始位置int weight; /要編碼的字符出現(xiàn)的頻率,即權(quán)值char ch; /要編碼的字符Code;typedef struct /編碼操作類型char bitMAX_NODE; /將字符的編碼結(jié)果存入 bit 數(shù)組中char ch; /要編碼的字符int weight; /字符出現(xiàn)的頻率Coding;typedef s

12、truct /輸入字符信息 HafNode arrMAX_NODE; /數(shù)組結(jié)點信息 int total; /統(tǒng)計輸入字符的種類個數(shù) HTree; void statistic_char(char text, HTree *t) /* 統(tǒng)計字符出現(xiàn)的頻率 */ FILE *fp,*fp1; char ch,ch120;printf(請輸入一批字符數(shù)據(jù): nA:鍵盤輸入 B:文件輸入n);scanf(%c,&ch);if(ch=A)scanf( %s,text);if(ch=B)13printf(請輸入文件名: n);scanf( %s,ch1); if(fp=fopen(ch1,r)=

13、NULL) puts(cant open file!); exit(0); fscanf(fp,%s,text); fclose(fp); fp1=fopen(zifu_quanzhi.txt,w+);int text_len = strlen(text); t=(HTree *)malloc(sizeof(HTree); t-total = 0; int i,j; for (i=0; itext_len; i+) for (j=0;jtotal; j+) if (t-arrj.ch = texti) /要統(tǒng)計字符在之前已出現(xiàn) t-arrj.weight+; break; if (j=t-to

14、tal) /記錄新出現(xiàn)的字符 t-total+; t-arrj.ch=texti; t-arrj.weight=1; printf(共有%d 個數(shù)據(jù)項!n,t-total); fprintf(fp1,%dn,t-total);14printf(字符t 出現(xiàn)次數(shù)n); for(j=0;jtotal;j+) /打印出字符和它們的出現(xiàn)的次數(shù)printf(%ct %dn,t-arrj.ch,t-arrj.weight);fprintf(fp1,%c%d ,t-arrj.ch,t-arrj.weight);free(t); fclose(fp1); void Haffman(int weight,cha

15、r ch,int n,HafNode haffTree) /* 生成哈夫曼樹的函數(shù) */int i,j,m1,m2,x1,x2;for (i=0;i2*n-1;i+) /對所有結(jié)點初始化if(in) /對 n 個葉子結(jié)點賦值haffTreei.weight=weighti;haffTreei.ch=chi;else /對 n-1 個新結(jié)點權(quán)值清 0haffTreei.weight=0;haffTreei.parent=-1;haffTreei.flag=0;haffTreei.lchild=-1;haffTreei.rchild=-1;for (i=0;in-1;i+) /找到當(dāng)前權(quán)值最小的兩

16、個結(jié)點,并把它們建立成一棵新樹,其中樹根的權(quán)值為這兩個的權(quán)值的和15m1=m2=MAX_VALUE;x1=x2=0;for (j=0;jn+i;j+) /每次比較中 m1 等于符合比較條件的所有結(jié)點中最小的權(quán)值,相應(yīng)的 m2 為次小 if (haffTreej.weightm1&haffTreej.flag=0) /注意:已有根節(jié)點的葉子在第 2 次以后的比較中實際不需比較m2=m1; /m2 取相比較權(quán)值的較大值x2=x1; /x2 取較大結(jié)點的下標(biāo)m1=haffTreej.weight; /m1 取相比較結(jié)點的較小權(quán)值x1=j; /x1 取該結(jié)點所在下標(biāo)值else if(haffT

17、reej.weightm2 & haffTreej.flag=0)m2=haffTreej.weight;x2=j;haffTreex1.parent= n + i; /x1,x2 指向新節(jié)點,其值等于在haffTree 數(shù)組中的下標(biāo)haffTreex2.parent = n + i;haffTreex1.flag = 1; /標(biāo)志位置 1haffTreex2.flag = 1;haffTreen+i.weight = haffTreex1.weight + haffTreex2.weight;haffTreen+i.lchild = x1;haffTreen+i.rchild = x

18、2;16FILE *fp; fp=fopen(haffman_tree.txt,w+);printf(本次輸入初始森林根節(jié)點數(shù):%dn,n); /輸出葉子結(jié)點的個數(shù)fprintf(fp,%dn,n); /并寫入文件for (i=0;in;i+) /寫入文件的所有葉子結(jié)點的信息fprintf(fp,%c %d %d %dn,haffTreei.ch,haffTreei.parent,haffTreei.lchild,haffTreei.rchild); for (i=n;i2*n-1;i+) /寫入文件的新結(jié)點的信息fprintf(fp,%d %d %dn,haffTreei.parent,ha

19、ffTreei.lchild,haffTreei.rchild); fclose(fp);void HaffmanCode (HafNode haffTree,int n,Code haffCode) /* 生成哈夫曼編碼的函數(shù) */Code *cd=( Code *) malloc (sizeof (Code);int i,j,child,parent;for (i=0; istart=n-1; cd-weight=haffTreei.weight;cd-ch=haffTreei.ch;child=i; parent=haffTreechild.parent;while (parent !=

20、-1) /從葉子結(jié)點開始一直找到一棵樹的根結(jié)點if (haffTreeparent.lchild=child)cd-bitcd-start=0;17elsecd-bitcd-start=1;cd-start-;child =parent;parent=haffTreechild.parent;for (j=cd-start+1; jbitj; haffCodei.start =cd-start+1; haffCodei.weight=cd-weight; haffCodei.ch=cd-ch;free(cd);void Init(int weight,char ch) /* 初始化操作,生成哈

21、夫曼樹及哈夫曼編碼 */FILE *fp; int i,j,n; char ch1=0;printf(n 現(xiàn)在進行初始化操作,相關(guān)數(shù)據(jù)從文件 zifu_quanzhi.txt 導(dǎo)入.n,ch1);if(fp=fopen(zifu_quanzhi.txt,r)=NULL) puts(cant open file!); exit(0) ;fscanf(fp,%dn,&n);HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1);Code *myHaffCode =(Code *)malloc (sizeof (Code)

22、*n);18for (i=0;iarrj.ch,t-arrj.weightfclose(fp);Haffman(weight,ch,n,myHaffTree); /CALL Haffman;HaffmanCode(myHaffTree,n,myHaffCode); /CALL HaffmanCode;fp=fopen(leaves.txt,w+);printf(初始化后哈夫曼編碼信息: n 字符t 權(quán)值t 二進制編碼 n);for (i=0;in;i+) printf(%ct %dt,myHaffCodei.ch,myHaffCodei.weight);fprintf(fp,%c %d ,my

23、HaffCodei.ch,myHaffCodei.weight); for ( j=myHaffCodei.start; jn; j+) /從屏幕輸出哈夫曼編碼并寫入到文件中printf(%d,myHaffCodei.bitj);fprintf(fp,%d,myHaffCodei.bitj); fprintf(fp,n);printf(n); fclose(fp); free(myHaffTree); free(myHaffCode);printf(初始化成功!n); printf(要清屏嗎?(Y/N)n);scanf( %c,&ch1);if(ch1=Y)system(cls);vo

24、id Caozuo_C() /* 哈夫曼編碼過程的函數(shù)，用于將文件編碼 */19FILE *fp,*fp1,*fp2;char zf500;if(fp=fopen(leaves.txt,r)=NULL) puts(cant open file!); exit(0) ; Coding ch100;char c;int i=0;while (feof(fp)=0) fscanf(fp,%c %d %sn,&chi.ch,&chi.weight,chi.bit); /對應(yīng) 150 和 161 行 myHaffCode輸入的信息 i+; fclose(fp);printf(現(xiàn)在進行編碼

25、操作.n 請選擇:nA.鍵盤輸入 B.文件輸入n);scanf( %c,&c);if (c=A) printf(請輸入字符串:n);scanf( %s,zf);char ch120,ch220; int j;if (c=B)printf(請輸入正文的文件名:n); /對應(yīng)輸入的文件名為20haffman.txtscanf( %s,ch1);if(fp1=fopen(ch1,r)=NULL) puts(cant open file!); exit(0) ;printf(請輸入保存結(jié)果的文件名:n);scanf( %s,ch2);fp2=fopen(ch2,w+);if (c=A) pri

26、ntf(二進制編碼為: );int len,k;len=strlen(zf);for (k=0;klen;k+)for (j=0;ji;j+)if (chj.ch=zfk)fprintf(fp2,%s,chj.bit);printf(%s,chj.bit);printf(n);if (c=B)printf(二進制編碼為: );while(feof(fp1)=0) fscanf(fp1,%c,&c);for (j=0;ji;j+) /對文件中的每一個字符進21行編碼if (chj.ch=c)fprintf(fp2,%s,chj.bit);printf(%s,chj.bit);fprint

27、f(fp2,n); printf(n);fclose(fp1);fclose(fp2);printf(編碼過程完成!同時已將結(jié)果存入%s 中.nn,ch2);void Caozuo_D() /* 譯碼操作 */FILE *fp,*fp1,*fp2; if(fp=fopen(haffman_tree.txt,r)=NULL) puts(cant open file!); exit(0) ; int i,n;fscanf(fp,%dn,&n);HafNode *myHaffTree=(HafNode *)malloc(sizeof (HafNode)*(2*n+1);for (i=0;in

28、;i+) fscanf(fp,%c %d %d %dn,&myHaffTreei.ch,&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild); for (i=n;i2*n-1;i+) fscanf(fp,%d %d 22%dn,&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild); fclose(fp);printf(請輸入譯碼文件的文件名:n); /對應(yīng)輸入的文件名為ch2.txt(函數(shù) Caozuo_

29、C 中的)char ch,ch120,ch220;scanf( %s,ch1);printf(請輸入結(jié)果文件的文件名:n);scanf( %s,ch2);if(fp1=fopen(ch1,r)=NULL) puts(cant open file!); exit(0) ; fp2=fopen(ch2,w+);i=2*n-2; /該值對應(yīng)最后一個新的結(jié)點(即該樹的根結(jié)點)在數(shù)組中的下標(biāo)printf(譯碼結(jié)果是: );while (!feof(fp1) fscanf(fp1,%c,&ch);if (ch=0) /若編碼為 0,則找此結(jié)點的左孩子;i=myHaffTreei.lchild;if

30、 (ch=1) /若編碼為 1,則找此結(jié)點的右孩子;i=myHaffTreei.rchild; if (in) /表示找到了樹的葉子結(jié)點,即對應(yīng)譯碼后的字符printf(%c,myHaffTreei.ch); fprintf(fp2,%c,myHaffTreei.ch);i=2*n-2; /繼續(xù)讀下一個編碼,再從根結(jié)點順序查找葉子結(jié)點23printf(n);fprintf(fp2,n);fclose(fp1);fclose(fp2);printf(譯碼過程完成!已將結(jié)果存入%s 中.n,ch2); free(myHaffTree);void Caozuo_P() /* 打印代碼文件的操作 */

31、FILE *fp1,*fp2;printf(請輸入文件名:n);char ch120,ch220;scanf( %s,ch1);printf(請輸入結(jié)果保存的文件名:n);scanf( %s,ch2);if(fp1=fopen(ch1,r)=NULL) puts(cant open file!); exit(0) ; fp2=fopen(ch2,w+);int count=0;char ch;printf(打印結(jié)果:n);while (!feof(fp1) ch=fgetc(fp1);printf(%c,ch);24fprintf(fp2,%c,ch);count+;if (count=50)

32、 /每打印 50 個字符進行換行printf(n);fprintf(fp2,n); count=0;printf(n);fprintf(fp2,n); fclose(fp1); fclose(fp2); printf(打印代碼過程完成!已將結(jié)果存入%s 中.nn,ch2);void PrintTree_ldr(HafNode *huf,Coding *cod,int n,int p,FILE *fp) /* 中序打印哈夫曼樹(具體過程) huf 表示獲取結(jié)點信息, cod 表示獲取葉子結(jié)點權(quán)值,n 表示結(jié)點數(shù)目,p 表示空出一定的空格用于打印左右分支, fp 表示文件指針,用來將打印出的哈夫曼

33、樹存入文件中 */int i;if (n=-1) /判斷是否為空樹,是的話返回return; PrintTree_ldr(huf,cod,hufn.lchild,p-1,fp); /打印左子樹 for (i=0;i=0&hufn.rchild=-1) /如果此結(jié)點為葉子結(jié)點,則將此結(jié)點輸出；printf(-%d,codn.weight); /打印字符權(quán)值printf(%cn,hufn.ch); /打印各個字符 fprintf(fp,-%d,codn.weight);fprintf(fp,%cn,hufn.ch);else /如果此結(jié)點為非葉子結(jié)點(即雙親),則輸出;if(p=6) pr

34、intf(根)n);fprintf(fp,(根)n); else printf(n); fprintf(fp,n); PrintTree_ldr(huf,cod,hufn.rchild,p-1,fp); /打印右子樹void Caozuo_T() /* 打印哈夫曼樹的操作 */FILE *fp,*fp1,*fp2; if(fp=fopen(haffman_tree.txt,r)=NULL) puts(cant open file!); exit(0) ; int i,n;26fscanf(fp,%dn,&n);HafNode *myHaffTree=(HafNode *)malloc(

35、sizeof (HafNode)*(2*n+1);for (i=0;in;i+)fscanf(fp,%c %d %d %dn,&myHaffTreei.ch,&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild);for (i=n;i2*n-1;i+)fscanf(fp,%d %d %dn,&myHaffTreei.parent,&myHaffTreei.lchild,&myHaffTreei.rchild);fclose(fp); if(fp1=fopen(zifu_qu

36、anzhi.txt,r)=NULL) puts(cant open file!); exit(0) ; fscanf(fp1,%*cn);Coding *myHaffCode =(Coding *)malloc (sizeof (Coding)*n);for(i=0;in;i+)fscanf(fp1,%*c%d ,&myHaffCodei.weight);fclose(fp1);printf(請輸入保存結(jié)果的文件名:n);char ch120;scanf( %s,ch1);fp2=fopen(ch1,w+); PrintTree_ldr(myHaffTree,myHaffCode,2*

37、n-2,6,fp2); /CALL PrintTree fclose(fp2); printf(打印哈夫曼樹過程完成!同時已將結(jié)果存入%s 中.nn,ch1);free(myHaffTree); free(myHaffCode);27void print()printf(*n);printf(* 歡迎使用哈夫曼編譯碼器 *n);printf(* *n);printf(* 溫馨提醒:1.在使用本軟件前先看下隨附的說明書,請按照說明書的規(guī)范要求 *n); printf(* 操作,否則可能會產(chǎn)生難以意料的結(jié)果! *n);printf(* 2.對于與程序相關(guān)的文件只能在本路徑下使用,請妥善保管. *n

38、);printf(*n);int main() int weight100; /存儲字符權(quán)值數(shù)組char ch100,cha; /數(shù)組 ch用于存放字符名print(); /打印說明書char s500; HTree *t=NULL; /數(shù)組 s用于存放要編碼的一批數(shù)據(jù),HTree *t 用于獲取字符和權(quán)值信息 statistic_char(s,t); /統(tǒng)計字符出現(xiàn)的頻率Init(weight,ch); /對字符數(shù)據(jù)進行初始化操作,生成哈夫曼樹及哈夫曼編碼while (1) 28printf(*n);printf(* _ 我們?yōu)槟峁┑南嚓P(guān)服務(wù) _ *n); printf(* C.編碼D.譯

39、碼T.印哈夫曼樹P.印代碼文件E.退出 *n); printf(*n);printf(請選擇: ); scanf( %c,&cha);if (cha=E) break; switch (cha)case C:Caozuo_C();break;/執(zhí)行編碼操作case D:Caozuo_D();break;/執(zhí)行譯碼操作case T:Caozuo_T();break;/打印哈夫曼樹case P:Caozuo_P();break;/打印代碼文件printf(要清屏嗎?(Y/N)n); scanf( %c,&cha); if(cha=Y) system(cls);return 0;29總總 結(jié)結(jié)這次的課程設(shè)計讓我感受頗多，剛開始選題的時候，我就覺得我們的這一個課題應(yīng)該是一個還不錯的題目，因為上課的時候我聽懂了哈夫曼數(shù)以及編碼的問題，也就是說我應(yīng)該可以做好，而且像這樣的問題在網(wǎng)絡(luò)上可以找到很多相