數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三哈夫曼樹實(shí)驗(yàn)報(bào)告

1、 題目：哈夫曼編/譯碼器一、 題目要求：寫一個哈夫曼碼的編/譯碼系統(tǒng)，要求能對要傳輸?shù)膱?bào)文進(jìn)行編碼和解碼。構(gòu)造哈夫曼樹時，權(quán)值小的放左子樹，權(quán)值大的放右子樹，編碼時右子樹編碼為1，左子樹編碼為0.二、 概要設(shè)計(jì)：數(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é)點(diǎn)結(jié)構(gòu)體 */函數(shù)： void DEMONHuffmanTree (HNode

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

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

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

5、2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight < m2 && HuffNodej.parent=-1) m2=HuffNodej.weight; x2=j; /* end for */ /* 設(shè)置找到的兩個子結(jié)點(diǎn) x1、x2 的父結(jié)點(diǎn)信息 */ HuffNodex1.parent = n+i; HuffNodex2.parent = n+i; HuffNoden+i.weight = HuffNodex1.weight + HuffNodex2.weight; HuffNoden+i.lchild =

6、 x1; HuffNoden+i.rchild = x2; 葉子節(jié)點(diǎn)的哈夫曼編碼的保存：for (j=cd.start+1; j<n; j+) HuffCodei.bitj = cd.bitj; HuffCodei.start = 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);

7、 for (i=0; i < n; i+) cd.start = n-1; c = i; p = HuffNodec.parent; while (p != -1) /* 父結(jié)點(diǎn)存在 */ if (HuffNodep.lchild = c) cd.bitcd.start = 0; else cd.bitcd.start = 1; cd.start-; /* 求編碼的低一位 */ c=p; p=HuffNodec.parent; /* 設(shè)置下一循環(huán)條件 */ /* end while */ for (j=cd.start+1; j<n; j+) HuffCodei.bitj = cd

8、.bitj; HuffCodei.start = cd.start; /* end for */ z=getchar(); z=getchar(); for(;z!='n'z=getchar()wenk+=z;for(i=0;i<n;i+)if(z=HuffNodei.value) for (j=HuffCodei.start+1; j < n; j+)printf ("%d", HuffCodei.bitj);break;else;printf("n");for(i=0;i<k;i+)printf("%c&q

9、uot;,weni);printf("n"); return 0;四、 調(diào)試分析與心得體會： 雖然哈夫曼樹的建立有書上的參考，但是實(shí)際寫整個代碼的時候還是問題重重。首先就是哈弗曼樹忘記了初始的賦值，導(dǎo)致最后出現(xiàn)了問題。這樣的錯誤還是很容易解決，但是之后就出現(xiàn)了WA的情況。在同學(xué)的幫助下，最后發(fā)現(xiàn)是因?yàn)樵谶x取節(jié)點(diǎn)的時候，循環(huán)出現(xiàn)了問題，雖然看起來編譯沒有錯，但是邊緣情況就會出現(xiàn)數(shù)據(jù)錯誤，這個還是很令人警醒，而這種思考的不全面的問題，在debug的過程中會耗去大量的時間，這是要注意的。五、 用戶操作說明：輸入表示字符集大小為n（n <= 100）的正整

10、數(shù)，以與n個字符和n個權(quán)值（正整數(shù)，值越大表示該字符出現(xiàn)的概率越大）；輸入串長小于或等于100的目標(biāo)報(bào)文。六、 運(yùn)行結(jié)果：附帶自己的算法完成的結(jié)果圖，可以通過Prt Sc和圖片編輯器獲得；七、 附錄：#include <stdio.h>#include<stdlib.h>#define MAXBIT 100#define MAXLEAF 30#define MAXNODE MAXLEAF*2 -1#define MAXQZ 10000 /權(quán)值typedef struct int bitMAXBIT; int start; HCodeType; /* 編碼結(jié)構(gòu)體 */ty

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

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

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

14、1中是最小 x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight < m2 && HuffNodej.parent=-1) m2=HuffNodej.weight; x2=j; /* end for */ /* 設(shè)置找到的兩個子結(jié)點(diǎn) x1、x2 的父結(jié)點(diǎn)信息 */ HuffNodex1.parent = n+i; HuffNodex2.parent = n+i; HuffNoden+i.weight = HuffNodex1.weight + HuffNodex2.weight; HuffNoden+i.l

15、child = x1; HuffNoden+i.rchild = x2; int main() HNode HuffNodeMAXNODE; /* 定義一個結(jié)點(diǎn)結(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-

16、1; c = i; p = HuffNodec.parent; while (p != -1) /* 父結(jié)點(diǎn)存在 */ if (HuffNodep.lchild = c) cd.bitcd.start = 0; else cd.bitcd.start = 1; cd.start-; /* 求編碼的低一位 */ c=p; p=HuffNodec.parent; /* 設(shè)置下一循環(huán)條件 */ /* end while */ /* 保存求出的每個葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位 */ for (j=cd.start+1; j<n; j+) HuffCodei.bitj = cd.bitj; H

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