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

1、不必問別人你能做什么，除了你自己，沒有人知道。也不必問別人你到底該做什么，除了行動(dòng)，沒有任何解答。 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告 設(shè)計(jì)題目 哈 夫 曼 (Huffman) 編/譯 碼 器 學(xué)院名稱 信 息 工 程 學(xué) 院 專 業(yè) 班 級(jí) 12 計(jì) 本 2 姓 名 張 翠 翠 學(xué) 號(hào) 1212210217 _ 題目：哈夫曼(Huffman)編/譯碼器一、問題描述利用哈夫曼編碼進(jìn)行通信可以大大提高信道利用率縮短信息傳輸時(shí)間降低傳輸成本但是這要求在發(fā)送端通過一個(gè)編碼系統(tǒng)對(duì)待傳數(shù)據(jù)預(yù)先編碼在接收端將傳來的數(shù)據(jù)進(jìn)行譯碼（復(fù)原）對(duì)于雙工信道（即可以雙向傳輸信息的信道）每端都需要一個(gè)完整的編/譯碼系統(tǒng)試為這樣的信

2、息收發(fā)站寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng) 二、設(shè)計(jì)目標(biāo)幫助學(xué)生熟練掌握樹的應(yīng)用和基本操作重點(diǎn)掌握二叉樹的存儲(chǔ)這里以哈夫曼樹為設(shè)計(jì)目標(biāo)進(jìn)一步提高學(xué)生的設(shè)計(jì)能力及對(duì)樹的理解三、任務(wù)要求一個(gè)完整的系統(tǒng)應(yīng)具有以下功能： 1) I：初始化（Initialization）從終端讀入字符集大小n以及n個(gè)字符和n個(gè)權(quán)值建立哈夫曼樹并將它存于文件hfmTree中 2) E：編碼（Encoding）利用以建好的哈夫曼樹（如不在內(nèi)存則從文件hfmTree中讀入）對(duì)文件ToBeTran中的正文進(jìn)行編碼然后將結(jié)果存入文件CodeFile中 3) D：譯碼（Decoding）利用已建好的哈夫曼樹將文件CodeFile中的代碼

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

4、t weight;unsigned int parent lchild rchild;HTNode *HuffmanTree; 哈弗曼樹的算法void CreateHT(HTNode htint n) /調(diào)用輸入的數(shù)組ht和節(jié)點(diǎn)數(shù)n int iklnodernode; int min1min2; 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的范圍是-32768-32767 lnode=rnode=-

5、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;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

6、.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 htHCode hcdint n) int ifc; 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.cdh

7、c.start-=1; c=f;f=htf.parent; hc.start+; /start指向哈夫曼編碼hc.cd中最開始字符 hcdi=hc; void DispHCode(HTNode htHCode hcdint n) /輸出哈夫曼編碼的列表 int ik; printf( 輸出哈夫曼編碼:n); for (i=0;in;i+) /輸出data中的所有數(shù)據(jù)即A-Z printf( %c:thti.data); for (k=hcdi.start;k=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf(%chcdi.cdk); printf(n); void editHCode(

8、HTNode htHCode hcdint n) /編碼函數(shù)char stringMAXSIZE; int ijk;scanf(%sstring); /把要進(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)查找與輸入字符相同的編號(hào)相同的就輸出這個(gè)字符的編碼for (k=hcdj.start;k=n;k+) printf(%chcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)哈弗曼譯碼void deHCode(HTNod

9、e htHCode hcdint n) /譯碼函數(shù)char codeMAXSIZE;int ijlkmx;scanf(%scode); /把要進(jìn)行譯碼的字符串存入code數(shù)組中while(code0!=#)for (i=0;in;i+)m=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.startj=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(%chti.data);for(x=0;codex-1!=#;

10、x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;主函數(shù)void main() int n=26i; char orzbackflag=1; char str=ABCDEFGHIJKLMNOPQRSTUVWXYZ; /初始化 int fnum=1866413223210321154757123220576315148518023818116; /初始化 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; whil

11、e (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( 請(qǐng)輸入選擇的編號(hào):); scanf(%c&orz); switch(orz) case a: case A: system(cls); /清屏函數(shù) CreateHT(htn); CreateHCode(hthcdn); DispHCode(ht

12、hcdn); printf(n按任意鍵返回.); getch(); system(cls); break; case b: case B: system(cls); printf(請(qǐng)輸入要進(jìn)行編碼的字符串(以#結(jié)束):n); editHCode(hthcdn); printf(n按任意鍵返回.); getch(); system(cls); break; case c: case C: system(cls); DispHCode(hthcdn); printf(請(qǐng)輸入編碼(以#結(jié)束):n); deHCode(hthcdn); printf(n按任意鍵返回.); getch(); system

13、(cls); break; case d: case D: flag=0; break; default: system(cls); 六、詳細(xì)設(shè)計(jì)字符空格ABCDEFGHIJKLM頻度1866413223210321154757153220由上表畫出哈夫曼樹：由哈夫曼樹得出各字符的編碼： 字符編碼 字符編碼 空格10 D0001A010 E1111B011111F11001C 0000G01110關(guān)系調(diào)用：該程序的流程圖：七、測試分析白盒： 查看代碼完整性白盒測試也稱結(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)程序中的每

14、條通路是否都能按預(yù)定要求正確工作 這一方法是把測試對(duì)象看作一個(gè)打開的盒子測試人員依據(jù)程序內(nèi)部邏輯結(jié)構(gòu)相關(guān)信息設(shè)計(jì)或選擇測試用例對(duì)程序所有邏輯路徑進(jìn)行測試通過在不同點(diǎn)檢查程序的狀態(tài)確定實(shí)際的狀態(tài)是否與預(yù)期的狀態(tài)一致 黑盒：測試是否可以正確的創(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)主要針對(duì)軟件界面和軟件功能進(jìn)行

15、測試八、使用說明1) 輸入n個(gè)字符的權(quán)值2) 輸入對(duì)應(yīng)的字符3) 得出各字符的編碼九、測試數(shù)據(jù)用下表給出的字符集和頻度的實(shí)際統(tǒng)計(jì)數(shù)據(jù)建立哈夫曼樹并實(shí)現(xiàn)以下報(bào)文的編碼和譯碼：THIS PROGRAM 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 #incl

16、ude /要用system函數(shù)要調(diào)用的頭文件#include /用getch()要調(diào)用的頭文件#include #define N 50 /義用N表示50葉節(jié)點(diǎn)數(shù)#define 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; /從s

17、tart開始讀cd中的哈夫曼碼HCode;void CreateHT(HTNode htint n) /調(diào)用輸入的數(shù)組ht和節(jié)點(diǎn)數(shù)n int iklnodernode; int min1min2; 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的范圍是-32768-32767 lnode=rnode=-1; /lnode和rnode記錄最小權(quán)值的兩個(gè)結(jié)點(diǎn)位置 for (k=0;k=i-1;k+) if

18、 (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)值為兩個(gè)最小節(jié)點(diǎn)權(quán)值之和 hti.lchild=lnode

19、;hti.rchild=rnode; /父節(jié)點(diǎn)的左節(jié)點(diǎn)和右節(jié)點(diǎn)void CreateHCode(HTNode htHCode hcdint n) int ifc; 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指向哈夫曼編碼h

20、c.cd中最開始字符 hcdi=hc; void DispHCode(HTNode htHCode hcdint n) /輸出哈夫曼編碼的列表 int ik; printf( 輸出哈夫曼編碼:n); for (i=0;in;i+) /輸出data中的所有數(shù)據(jù)即A-Z printf( %c:thti.data); for (k=hcdi.start;k=n;k+) /輸出所有data中數(shù)據(jù)的編碼 printf(%chcdi.cdk); printf(n); void editHCode(HTNode htHCode hcdint n) /編碼函數(shù)char stringMAXSIZE; int i

21、jk;scanf(%sstring); /把要進(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)查找與輸入字符相同的編號(hào)相同的就輸出這個(gè)字符的編碼for (k=hcdj.start;k=n;k+) printf(%chcdj.cdk);break; /輸出完成后跳出當(dāng)前for循環(huán)void deHCode(HTNode htHCode hcdint n) /譯碼函數(shù)char codeMAXSIZE;int ijlkmx;scanf(%

22、scode); /把要進(jìn)行譯碼的字符串存入code數(shù)組中while(code0!=#)for (i=0;in;i+)m=0; /m為想同編碼個(gè)數(shù)的計(jì)數(shù)器 for (k=hcdi.startj=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(%chti.data);for(x=0;codex-1!=#;x+) /把已經(jīng)使用過的code數(shù)組里的字符串刪除codex=codex+j;void main() int n=26i

23、; char orzbackflag=1; char str=ABCDEFGHIJKLMNOPQRSTUVWXYZ; /初始化 int fnum=1866413223210321154757123220576315148518023818116; /初始化 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-

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