哈夫曼編譯碼---數(shù)據(jù)結(jié)構(gòu)C語言版課程設(shè)計(jì)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告設(shè)計(jì)題目 哈 夫 曼 (Huffman) 編/譯 碼 器 學(xué)院名稱 信 息 工 程 學(xué) 院 專 業(yè) 班 級 12 計(jì) 本 2 姓 名 張 翠 翠 學(xué) 號 _ 題目：哈夫曼(Huffman)編/譯碼器一、問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率，縮短信息傳輸時(shí)間，降低傳輸成本。但是，這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對待傳數(shù)據(jù)預(yù)先編碼，在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）。對于雙工信道（即可以雙向傳輸信息的信道），每端都需要一個(gè)完整的編/譯碼系統(tǒng)。試為這樣的信息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)。 二、設(shè)計(jì)目標(biāo)幫助學(xué)生熟練掌握樹的應(yīng)用和基本操作，重點(diǎn)掌握二叉樹的存儲(chǔ)，

2、這里以哈夫曼樹為設(shè)計(jì)目標(biāo)進(jìn)一步提高學(xué)生的設(shè)計(jì)能力及對樹的理解。三、任務(wù)要求一個(gè)完整的系統(tǒng)應(yīng)具有以下功能： 1) I：初始化（Initialization）。從終端讀入字符集大小n，以及n個(gè)字符和n個(gè)權(quán)值，建立哈夫曼樹，并將它存于文件hfmTree中。 2) E：編碼（Encoding）。利用以建好的哈夫曼樹（如不在內(nèi)存，則從文件hfmTree中讀入），對文件ToBeTran中的正文進(jìn)行編碼，然后將結(jié)果存入文件CodeFile中。 3) D：譯碼（Decoding）。利用已建好的哈夫曼樹將文件CodeFile中的代碼進(jìn)行譯碼，結(jié)果存入文件TextFile中。 4) P：印代碼文件（Print）。

3、將文件CodeFile以緊湊格式顯示在終端上，每行50個(gè)代碼。同時(shí)將此字符形式的編碼文件寫入文件CodePrin中。 5) T：印哈夫曼樹（Tree Printing）。將已在內(nèi)存中的哈夫曼樹以直觀的方式（樹或凹入表形式）顯示在終端上，同時(shí)將此字符形式的哈夫曼樹寫入文件TreePrint中。 四、需求分析利用哈夫曼樹(Huffman)編/譯碼（一）、初始化哈夫曼樹（二）、建立哈夫曼樹（三）、對哈夫曼樹進(jìn)行編碼（四）、輸出對應(yīng)字符的編碼（五）、譯碼過程五、概要設(shè)計(jì)哈夫曼樹的存儲(chǔ)結(jié)構(gòu)描述typedef structunsigned int weight;unsigned int parent, l

4、child, rchild;HTNode, *HuffmanTree; 哈弗曼樹的算法void CreateHT(HTNode ht,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點(diǎn)數(shù)n int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結(jié)點(diǎn)的相關(guān)域置初值-1 for (i=n;i2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩

5、個(gè)結(jié)點(diǎn)位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (htk.weightmin1) /若權(quán)值小于最小的左節(jié)點(diǎn)的權(quán)值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.weight=htlnode.weight+htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為

6、兩個(gè)最小節(jié)點(diǎn)權(quán)值之和 hti.lchild=lnode;hti.rchild=rnode; /父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)哈弗曼編碼void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;in;i+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點(diǎn) hc.cdhc.start-=0; else /處理右孩子結(jié)點(diǎn) hc.cdhc.start-=1; c=f;f=h

7、tf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,k; printf( 輸出哈夫曼編碼:n); for (i=0;in;i+) /輸出data中的所有數(shù)據(jù)，即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCo

8、de hcd,int n) /編碼函數(shù)char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要進(jìn)行編碼的字符串存入string數(shù)組中printf(n輸出編碼結(jié)果:n);for (i=0;stringi!=#;i+) /#為終止標(biāo)志for (j=0;jn;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號，相同的就輸出這個(gè)字符的編碼for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)哈弗曼譯碼void deHCode(HTNode ht,H

9、Code hcd,int n) /譯碼函數(shù)char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要進(jìn)行譯碼的字符串存入code數(shù)組中while(code0!=#)for (i=0;in;i+)m=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.start,j=0;k=n;k+,j+) /j為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)if(codej=hcdi.cdk) /當(dāng)有相同編碼時(shí)m值加1m+;if(m=j) /當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符串個(gè)數(shù)相等時(shí)則輸出這個(gè)的data數(shù)據(jù)printf(%c,hti.data);for(x=0;codex-

10、1!=#;x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;主函數(shù)void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結(jié)構(gòu)體 HCode hcdN; /建立結(jié)構(gòu)體 for (i=0;in;

11、i+) /把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數(shù)，當(dāng)flag為0時(shí)跳出循環(huán)顯示部分源程序： printf(n); printf( *); printf(n * 1-顯示編碼 *); printf(n * 2-進(jìn)行編碼 *); printf(n * 3-進(jìn)行譯碼 *); printf(n * 4-退出 *n); printf( * *); printf(n); printf( 請輸入選擇的編號:); scanf(%c,&orz); switch(orz) case a: case A: system(

12、cls); /清屏函數(shù) CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case b: case B: system(cls); printf(請輸入要進(jìn)行編碼的字符串(以#結(jié)束):n); editHCode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case c: case C: system(cls); DispHCode(ht,hcd,n); prin

13、tf(請輸入編碼(以#結(jié)束):n); deHCode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case d: case D: flag=0; break; default: system(cls); 六、詳細(xì)設(shè)計(jì)字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220由上表畫出哈夫曼樹：由哈夫曼樹得出各字符的編碼：字符編碼字符編碼空格10D0001A010E1111BF11001C0000G01110關(guān)系調(diào)用：該程序的流程圖：開始結(jié)點(diǎn)數(shù)是否大于1將data和權(quán)值賦給ht輸出根結(jié)點(diǎn)和

14、權(quán)值調(diào)用selectmin函數(shù)計(jì)算根結(jié)點(diǎn)函數(shù)父結(jié)點(diǎn)為兩子結(jié)點(diǎn)之和輸出兩子結(jié)點(diǎn)和已構(gòu)造的結(jié)點(diǎn) 點(diǎn)是否為根結(jié)點(diǎn)？左子是否為空？此時(shí)編碼為0i=2*ni+編碼為1結(jié)束否否否右子是否為空是是否否是是是七、測試分析白盒：查看代碼完整性白盒測試也稱結(jié)構(gòu)測試或邏輯驅(qū)動(dòng)測試，它是按照程序內(nèi)部的結(jié)構(gòu)測試程序，通過測試來檢測產(chǎn)品內(nèi)部動(dòng)作是否按照設(shè)計(jì)規(guī)格說明書的規(guī)定正常進(jìn)行，檢驗(yàn)程序中的每條通路是否都能按預(yù)定要求正確工作。 這一方法是把測試對象看作一個(gè)打開的盒子，測試人員依據(jù)程序內(nèi)部邏輯結(jié)構(gòu)相關(guān)信息，設(shè)計(jì)或選擇測試用例，對程序所有邏輯路徑進(jìn)行測試，通過在不同點(diǎn)檢查程序的狀態(tài)，確定實(shí)際的狀態(tài)是否與預(yù)期的狀態(tài)一致。 黑

15、盒：測試是否可以正確的創(chuàng)建，刪除，插入，打印，查找等操作黑盒測試也稱功能測試，它是通過測試來檢測每個(gè)功能是否都能正常使用。在測試中，把程序看作一個(gè)不能打開的黑盒子，在完全不考慮程序內(nèi)部結(jié)構(gòu)和內(nèi)部特性的情況下，在程序接口進(jìn)行測試，它只檢查程序功能是否按照需求規(guī)格說明書的規(guī)定正常使用，程序是否能適當(dāng)?shù)亟邮蛰斎霐?shù)據(jù)而產(chǎn)生正確的輸出信息。黑盒測試著眼于程序外部結(jié)構(gòu)，不考慮內(nèi)部邏輯結(jié)構(gòu)，主要針對軟件界面和軟件功能進(jìn)行測試。八、使用說明1) 輸入n個(gè)字符的權(quán)值2) 輸入對應(yīng)的字符3) 得出各字符的編碼九、測試數(shù)據(jù)用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹，并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：“THIS P

16、ROGRAM IS MY FAVORITE”。字符 空格 A B C D E F G H I J K L M 頻度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符 N O P Q R S T U V W X Y Z 頻度 57 63 15 1 48 51 80 23 8 18 1 16 1注：學(xué)生在測試數(shù)據(jù)時(shí)，需要寫出測試用例和截圖十、該程序的源代碼#include #include /要用system函數(shù)要調(diào)用的頭文件#include /用getch()要調(diào)用的頭文件#include #define N 50 /義用N表示50葉節(jié)點(diǎn)數(shù)#define

17、M 2*N-1 /用M表示節(jié)點(diǎn)總數(shù) 當(dāng)葉節(jié)點(diǎn)數(shù)位n時(shí)總節(jié)點(diǎn)數(shù)為2n-1#define MAXSIZE 100typedef struct char data; /結(jié)點(diǎn)值 int weight; /權(quán)值 int parent; /雙親結(jié)點(diǎn) int lchild; /左孩子結(jié)點(diǎn) int rchild; /右孩子結(jié)點(diǎn)HTNode; typedef struct char cdN; /存放哈夫曼碼 int start; /從start開始讀cd中的哈夫曼碼HCode;void CreateHT(HTNode ht,int n) /調(diào)用輸入的數(shù)組ht,和節(jié)點(diǎn)數(shù)n int i,k,lnode,rnode;

18、 int min1,min2; for (i=0;i2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有結(jié)點(diǎn)的相關(guān)域置初值-1 for (i=n;i2*n-1;i+) /構(gòu)造哈夫曼樹 min1=min2=32767; /int的范圍是-3276832767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 for (k=0;k=i-1;k+) if (htk.parent=-1) /只在尚未構(gòu)造二叉樹的結(jié)點(diǎn)中查找 if (htk.weightmin1) /若權(quán)值小于最小的左節(jié)點(diǎn)的權(quán)值 min2=min1;rnod

19、e=lnode; min1=htk.weight;lnode=k; else if (htk.weightmin2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)是i hti.weight=htlnode.weight+htrnode.weight; /兩個(gè)最小節(jié)點(diǎn)的父節(jié)點(diǎn)權(quán)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和 hti.lchild=lnode;hti.rchild=rnode; /父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c

20、; HCode hc; for (i=0;in;i+) /根據(jù)哈夫曼樹求哈夫曼編碼 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到樹根結(jié)點(diǎn)結(jié)束循環(huán) if (htf.lchild=c) /處理左孩子結(jié)點(diǎn) hc.cdhc.start-=0; else /處理右孩子結(jié)點(diǎn) hc.cdhc.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /輸出哈夫曼編碼的列表 int i,

21、k; printf( 輸出哈夫曼編碼:n); for (i=0;in;i+) /輸出data中的所有數(shù)據(jù)，即A-Z printf( %c:t,hti.data); for (k=hcdi.start;k=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf(%c,hcdi.cdk); printf(n); void editHCode(HTNode ht,HCode hcd,int n) /編碼函數(shù)char stringMAXSIZE; int i,j,k;scanf(%s,string); /把要進(jìn)行編碼的字符串存入string數(shù)組中printf(n輸出編碼結(jié)果:n);for (i=0;

22、stringi!=#;i+) /#為終止標(biāo)志for (j=0;jn;j+)if(stringi=htj.data) /循環(huán)查找與輸入字符相同的編號，相同的就輸出這個(gè)字符的編碼for (k=hcdj.start;k=n;k+) printf(%c,hcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)void deHCode(HTNode ht,HCode hcd,int n) /譯碼函數(shù)char codeMAXSIZE;int i,j,l,k,m,x;scanf(%s,code); /把要進(jìn)行譯碼的字符串存入code數(shù)組中while(code0!=#)for (i=0;in;i+)m

23、=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.start,j=0;k=n;k+,j+) /j為記錄所存儲(chǔ)這個(gè)字符的編碼個(gè)數(shù)if(codej=hcdi.cdk) /當(dāng)有相同編碼時(shí)m值加1m+;if(m=j) /當(dāng)輸入的字符串與所存儲(chǔ)的編碼字符串個(gè)數(shù)相等時(shí)則輸出這個(gè)的data數(shù)據(jù)printf(%c,hti.data);for(x=0;codex-1!=#;x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str=A,B,C,D,E,F,G,H,I,J,K,

24、L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; /初始化 int fnum=186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16; /初始化 HTNode htM; /建立結(jié)構(gòu)體 HCode hcdN; /建立結(jié)構(gòu)體 for (i=0;in;i+) /把初始化的數(shù)據(jù)存入ht結(jié)構(gòu)體中 hti.data=stri; hti.weight=fnumi; while (flag) /菜單函數(shù)，當(dāng)flag為0時(shí)跳出循環(huán) printf(n); printf( *); printf(n * A-顯示

25、編碼 *); printf(n * B-進(jìn)行編碼 *); printf(n * C-進(jìn)行譯碼 *); printf(n * D-退出 *n); printf( *); printf(n); printf( 請輸入選擇的編號:); scanf(%c,&orz); switch(orz) case a: case A: system(cls); /清屏函數(shù) CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case b: case B: system(cls); printf(請輸入要進(jìn)行編碼的字符串(以#結(jié)束):n); editHCode(ht,hcd,n); printf(n按任意鍵返回.); getch(); system(cls); break; case c: case C: syste