數(shù)據(jù)結(jié)構(gòu)實驗三哈夫曼樹實驗報告

1、.題目：哈夫曼編/譯碼器 一、 題目要求：寫一個哈夫曼碼的編/譯碼系統(tǒng)，要求能對要傳輸?shù)膱笪倪M(jìn)行編碼和解碼。構(gòu)造哈夫曼樹時，權(quán)值小的放左子樹，權(quán)值大的放右子樹，編碼時右子樹編碼為1，左子樹編碼為0.二、 概要設(shè)計：數(shù)據(jù)結(jié)構(gòu)：typedef struct int bitMAXBIT; int start; HCodeType; /* 編碼結(jié)構(gòu)體 */typedef struct int weight; int parent; int lchild; int rchild; char value; HNode; /* 結(jié)點結(jié)構(gòu)體 */函數(shù)： void DEMONHuffmanTree (HNode

2、 HuffNodeMAXNODE, int n)作用：構(gòu)造一個哈夫曼樹，并循環(huán)構(gòu)建int main ()作用：運用已經(jīng)構(gòu)建好的哈弗曼樹，進(jìn)行節(jié)點的處理，達(dá)到成功解碼編譯三、 詳細(xì)設(shè)計：哈夫曼樹的建立：void DEMONHuffmanTree (HNode HuffNodeMAXNODE, int n) int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼樹數(shù)組 HuffNode 中的結(jié)點 */ while (in) HuffNodei.weight = 0;/權(quán)值 HuffNodei.parent =-1; HuffNodei.lchild =-

3、1; HuffNodei.rchild =-1;scanf(%c,&x); scanf(%c,&HuffNodei.value); /實際值，可根據(jù)情況替換為字母 i+; /* 輸入 n 個葉子結(jié)點的權(quán)值 */scanf(%c,&x);for(i=0;in;i+) scanf (%d, &HuffNodei.weight); for (i=n; i2*n-1; i+) HuffNodei.weight = 0;/權(quán)值 HuffNodei.parent =-1; HuffNodei.lchild =-1; HuffNodei.rchild =-1; HuffNodei.value=i; /* 循

4、環(huán)構(gòu)造 Huffman 樹 */ for (i=0; in-1; i+) m1=m2=MAXQZ; / m1、m2中存放兩個無父結(jié)點且結(jié)點權(quán)值最小的兩個結(jié)點 x1=x2=0;/找出所有結(jié)點中權(quán)值最小、無父結(jié)點的兩個結(jié)點，并合并之為一顆二叉樹 for (j=0; jn+i; j+) if (HuffNodej.weight m1 & HuffNodej.parent=-1) m2=m1;/m1中是最小 x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight m2 & HuffNodej.parent=-1) m2=HuffNodej

5、.weight; x2=j; /* end for */ /* 設(shè)置找到的兩個子結(jié)點 x1、x2 的父結(jié)點信息 */ HuffNodex1.parent = n+i; HuffNodex2.parent = n+i; HuffNoden+i.weight = HuffNodex1.weight + HuffNodex2.weight; HuffNoden+i.lchild = x1; HuffNoden+i.rchild = x2; 葉子節(jié)點的哈夫曼編碼的保存：for (j=cd.start+1; jn; j+) HuffCodei.bitj = cd.bitj; HuffCodei.star

6、t = cd.start;主函數(shù)展示：int main() HNode HuffNodeMAXNODE; HCodeType HuffCodeMAXLEAF,cd; int i, j, c, p, n,k=0; char wen100; char z; scanf (%d, &n); HuffmanTree (HuffNode, n); for (i=0; i n; i+) cd.start = n-1; c = i; p = HuffNodec.parent; while (p != -1) /* 父結(jié)點存在 */ if (HuffNodep.lchild = c) cd.bitcd.sta

7、rt = 0; else cd.bitcd.start = 1; cd.start-; /* 求編碼的低一位 */ c=p; p=HuffNodec.parent; /* 設(shè)置下一循環(huán)條件 */ /* end while */ for (j=cd.start+1; jn; j+) HuffCodei.bitj = cd.bitj; HuffCodei.start = cd.start; /* end for */ z=getchar(); z=getchar(); for(;z!=n;z=getchar()wenk+=z;for(i=0;in;i+)if(z=HuffNodei.value)

8、for (j=HuffCodei.start+1; j n; j+)printf (%d, HuffCodei.bitj);break;else;printf(n);for(i=0;ik;i+)printf(%c,weni);printf(n); return 0;四、 調(diào)試分析與心得體會： 雖然哈夫曼樹的建立有書上的參考，但是實際寫整個代碼的時候還是問題重重。首先就是哈弗曼樹忘記了初始的賦值，導(dǎo)致最后出現(xiàn)了問題。這樣的錯誤還是很容易解決，但是之后就出現(xiàn)了WA的情況。在同學(xué)的幫助下，最后發(fā)現(xiàn)是因為在選取節(jié)點的時候，循環(huán)出現(xiàn)了問題，雖然看起來編譯沒有錯，但是邊緣情況就會出現(xiàn)數(shù)據(jù)錯誤，這個還是很令

9、人警醒，而這種思考的不全面的問題，在debug的過程中會耗去大量的時間，這是要注意的。五、 用戶操作說明：輸入表示字符集大小為n（n=100）的正整數(shù)，以及n個字符和n個權(quán)值（正整數(shù)，值越大表示該字符出現(xiàn)的概率越大）；輸入串長小于或等于100的目標(biāo)報文。六、 運行結(jié)果：附帶自己的算法完成的結(jié)果圖，可以通過Prt Sc和圖片編輯器獲得；七、 附錄：#include #include#define MAXBIT 100#define MAXLEAF 30#define MAXNODE MAXLEAF*2 -1#define MAXQZ 10000 /權(quán)值typedef struct int bit

10、MAXBIT; int start; HCodeType; /* 編碼結(jié)構(gòu)體 */typedef struct int weight; int parent; int lchild; int rchild; char value; HNode; /* 結(jié)點結(jié)構(gòu)體 */* 構(gòu)造一顆哈夫曼樹 */void HuffmanTree (HNode HuffNodeMAXNODE, int n) int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼樹數(shù)組 HuffNode 中的結(jié)點 */ while (in) HuffNodei.weight = 0;/權(quán)值

11、 HuffNodei.parent =-1; HuffNodei.lchild =-1; HuffNodei.rchild =-1;scanf(%c,&x); scanf(%c,&HuffNodei.value); /實際值，可根據(jù)情況替換為字母 i+; /* 輸入 n 個葉子結(jié)點的權(quán)值 */scanf(%c,&x);i = 0; while (in) scanf (%d, &HuffNodei.weight); i+; for (i=n; i2*n-1; i+) HuffNodei.weight = 0;/權(quán)值 HuffNodei.parent =-1; HuffNodei.lchild =

12、-1; HuffNodei.rchild =-1; HuffNodei.value=i; /* 循環(huán)構(gòu)造 Huffman 樹 */ for (i=0; in-1; i+) m1=m2=MAXQZ; / m1、m2中存放兩個無父結(jié)點且結(jié)點權(quán)值最小的兩個結(jié)點 x1=x2=0;/找出所有結(jié)點中權(quán)值最小、無父結(jié)點的兩個結(jié)點，并合并之為一顆二叉樹 for (j=0; jn+i; j+) if (HuffNodej.weight m1 & HuffNodej.parent=-1) m2=m1;/m1中是最小 x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNo

13、dej.weight m2 & HuffNodej.parent=-1) m2=HuffNodej.weight; x2=j; /* end for */ /* 設(shè)置找到的兩個子結(jié)點 x1、x2 的父結(jié)點信息 */ HuffNodex1.parent = n+i; HuffNodex2.parent = n+i; HuffNoden+i.weight = HuffNodex1.weight + HuffNodex2.weight; HuffNoden+i.lchild = x1; HuffNoden+i.rchild = x2; int main() HNode HuffNodeMAXNODE

14、; /* 定義一個結(jié)點結(jié)構(gòu)體數(shù)組 */ HCodeType HuffCodeMAXLEAF,cd; /* 定義一個編碼結(jié)構(gòu)體數(shù)組， 同時定義一個臨時變量來存放求解編碼時的信息 */ int i, j, c, p, n,k=0; char wen100; char z; scanf (%d, &n); HuffmanTree (HuffNode, n); for (i=0; i n; i+) cd.start = n-1; c = i; p = HuffNodec.parent; while (p != -1) /* 父結(jié)點存在 */ if (HuffNodep.lchild = c) cd.b

15、itcd.start = 0; else cd.bitcd.start = 1; cd.start-; /* 求編碼的低一位 */ c=p; p=HuffNodec.parent; /* 設(shè)置下一循環(huán)條件 */ /* end while */ /* 保存求出的每個葉結(jié)點的哈夫曼編碼和編碼的起始位 */ for (j=cd.start+1; jn; j+) HuffCodei.bitj = cd.bitj; HuffCodei.start = cd.start; /* end for */ z=getchar(); z=getchar(); for(;z!=n;z=getchar()wenk+=

16、z;for(i=0;in;i+)if(z=HuffNodei.value) for (j=HuffCodei.start+1; j n; j+)printf (%d, HuffCodei.bitj);break;else;printf(n);i = 0;while (ik)printf(%c,weni);i+;printf(n); return 0;上機(jī)實習(xí)要求：1、 認(rèn)真準(zhǔn)備，按時參加上機(jī)實習(xí)，不得無故缺席，抽查不到者扣分；2、 獨立完成老師布置的題目，上機(jī)完成程序并調(diào)試正確，課后完成實驗報告的編寫，將上機(jī)程序和實驗報告打包后交給輔導(dǎo)老師評定分?jǐn)?shù)，實驗報告要求和評分標(biāo)準(zhǔn)見后面；3、 提倡創(chuàng)新，可對課本上提供的算法進(jìn)行改進(jìn)；4、 上機(jī)程序必須在程序中提供足夠的注釋，詳細(xì)為好。5、 實驗報告不用寫出算法，只要寫出對課程設(shè)計的見解，如對某一算法的改進(jìn)