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

1、題目：哈夫曼編/譯碼器一、 題目要求：寫(xiě)一個(gè)哈夫曼碼的編/譯碼系統(tǒng)，要求能對(duì)要傳輸?shù)膱?bào)文進(jìn)行編碼和解碼。構(gòu)造哈夫曼樹(shù)時(shí),子樹(shù)，權(quán)值大的放右子樹(shù)，編碼時(shí)右子樹(shù)編碼為1,左子樹(shù)編碼為 0.二、 概要設(shè)計(jì)： 數(shù)據(jù)結(jié)構(gòu)：typedef structint bitMAXBIT; int start; HCodeType;typedef structint weight;int pare nt;int lchild;int rchild;char value; HNode;/*結(jié)點(diǎn)結(jié)構(gòu)體 */函數(shù)：void DEMONHuffma nTree (HNode HuffNodeMAXNODE, i nt n)

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

3、,&x); scanf(%c,&HuffNodei.value); eight);for (i=n; i2*n-1; i+)HuffNodei.weight = 0;arent =-1;HuffNodei.lchild =-1;HuffNodei.rchild =-1;HuffNodei.value=i;/* 循環(huán)構(gòu)造 Huffman 樹(shù) */for (i=0; in-1; i+)m1=m2=MAXQZ;eight m1 & HuffNodej.parent=-1)m2=m1;eight; x1=j;else if (HuffNodej.weight m2 &

4、HuffNodej.parent=-1)m2=HuffNodej.weight; x2=j; /* end for */* 設(shè)置找到的兩個(gè)子結(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= x1;HuffNoden+i.rchild = x2;葉子節(jié)點(diǎn)的哈夫曼編碼的保存：for (j=+1; jn; j+)HuffCodei.bitj = j;Huff

5、Codei.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+)= n-1;c = i;p = HuffNodec.parent;while (p != -1) /* 父結(jié)點(diǎn)存在 */if (HuffNodep.lchild = c) = 0; else = 1; /* 求編碼的低一位 *

6、/ c=p;p=HuffNodec.parent; /* 設(shè)置下一循環(huán)條件 */ /* end while */for (j=+1; jn; j+)HuffCodei.bitj = j;HuffCodei.start = ; /* end for */z=getchar();z=getchar(); for(;z!=n;z=getchar()wenk+=z; for(i=0;in;i+)if(z=HuffNodei.value)for (j=HuffCodei.start+1; j n; j+) printf (%d, HuffCodei.bitj);break; else;prin tf(n

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

8、0100）的正整數(shù)，以及 n n 個(gè)字符和 n n 個(gè)權(quán)值（正整數(shù)，值越大 表示該字符出現(xiàn)的概率越大）；輸入串長(zhǎng)小于或等于 100100 的目標(biāo)報(bào)文。六、運(yùn)行結(jié)果：附帶自己的算法完成的結(jié)果圖，可以通過(guò)Prt Sc 和圖片編輯器獲得;-VHp=ll。 曰PONknHU2EOU111600000LVcxl*zl山1XIAI0000LNox-u!pp4t山QONXIAIu!pp4t丄山1XIAIu!pp4tH-mxs u!pp4tHuffNodei.rchild =-1;scanf(%c,&x);scanf(%c,&HuffNodei.value); eight); i+;for (

9、i=n; i2*n-1; i+)HuffNodei.weight = 0;arent =-1;HuffNodei.lchild =-1;HuffNodei.rchild =-1;HuffNodei.value=i;/* 循環(huán)構(gòu)造 Huffman 樹(shù) */for (i=0; in-1; i+)m1=m2=MAXQZ; eight m1 & HuffNodej.parent=-1)m2=m1;eight; x1=j;else if (HuffNodej.weight m2 & HuffNodej.parent=-1)m2=HuffNodej.weight; x2=j; /* end

10、 for */* 設(shè)置找到的兩個(gè)子結(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 = x1;HuffNoden+i.rchild = x2;int main()HNode HuffNodeMAXNODE;/* 定義一個(gè)結(jié)點(diǎn)結(jié)構(gòu)體數(shù)組 */HCodeType HuffCodeMAXLEAF,cd;/* 定義一個(gè)編碼結(jié)構(gòu)體數(shù)組，同時(shí)定義一個(gè)臨時(shí)變量來(lái)存放求解

11、編碼時(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+)= n-1;c = i;p = HuffNodec.parent;while (p != -1) /* 父結(jié)點(diǎn)存在 */if (HuffNodep.lchild = c) = 0;else = 1; /* 求編碼的低一位 */ c=p;p=HuffNodec.parent; /* 設(shè)置下一循環(huán)條件 */ /* end while */* 保存求出的每個(gè)葉結(jié)點(diǎn)的哈夫

12、曼編碼和編碼的起始位 */ for (j=+1;jn; j+)HuffCodei.bitj = j;HuffCodei.start = ; /* end for */z=getchar();z=getchar(); for(;z!=n;z=getchar()wenk+=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(n);return 0;printf(%c,weni);i+;6060上機(jī)實(shí)習(xí)要求：1 1、 認(rèn)真準(zhǔn)備，按時(shí)參加上機(jī)實(shí)習(xí)，不得無(wú)故缺席，抽查不到者扣分；2 2、獨(dú)立完成老師布置的題目，上機(jī)完成程序并調(diào)試正確，課后完成實(shí)驗(yàn)報(bào)告的編寫(xiě)，將上 機(jī)程序和實(shí)驗(yàn)報(bào)告打包后交給輔導(dǎo)老師評(píng)定分?jǐn)?shù)，實(shí)驗(yàn)報(bào)告要求和評(píng)分標(biāo)準(zhǔn)見(jiàn)后面；3 3、 提倡創(chuàng)新，可對(duì)課本上提供的算法進(jìn)行改進(jìn)；4 4、 上機(jī)程序必須在程序中提供足夠的注釋，詳細(xì)為好。5 5、實(shí)驗(yàn)報(bào)告不用寫(xiě)出算法，只要寫(xiě)出對(duì)課程設(shè)計(jì)的見(jiàn)解，如對(duì)某一算法的改進(jìn)思想，算法 設(shè)計(jì)思想，調(diào)試算法過(guò)程中出現(xiàn)的問(wèn)題及改進(jìn)方法，調(diào)試程序的體會(huì)等。只要是自己編程 和調(diào)試就會(huì)寫(xiě)出相應(yīng)的報(bào)告。考核標(biāo)準(zhǔn)1 1、 機(jī)試程序和