大數(shù)據(jù)的結(jié)構(gòu)試驗三哈夫曼樹試驗報告材料

1、實用標(biāo)準(zhǔn)文案精彩文檔題目：哈夫曼編/譯碼器一、題目要求：寫一個哈夫曼碼的編/譯碼系統(tǒng)，要求能對要傳輸?shù)膱笪倪M(jìn)行編碼和解碼。構(gòu)造哈夫曼樹時，權(quán)值小的放左子樹，權(quán)值大的放右子樹，編碼時右子樹編碼為1，左子樹編碼為0.二、概要設(shè)計：數(shù)據(jù)結(jié)構(gòu)：typedef structint bitMAXBIT;int start; HCodeType;/*編碼結(jié)構(gòu)體*/typedef struct實用標(biāo)準(zhǔn)文案精彩文檔int weight;int pare nt;int Ichild;int rchild;char value; HNode;/*結(jié)點(diǎn)結(jié)構(gòu)體*/函數(shù)：void DEMONHuffma nTree (H

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

3、標(biāo)準(zhǔn)文案精彩文檔HuffNodei.rchild =-1;sea nf(%c, &x);scan f(%c,&HuffNodei.value); /實際值，可根據(jù)情況替換為字母i+；/*輸入n個葉子結(jié)點(diǎn)的權(quán)值*/scan f(%c, &x);for(i=0;i n;i+)scanf (%d, &Hu ffNodei.weight);for (i=n; i2*n-1; i+)HuffNodei.weight = 0;/權(quán)值HuffNodei.pare nt =-1;HuffNodei.lchild =-1;HuffNodei.rchild =-1;HuffNode

4、i.value=i;實用標(biāo)準(zhǔn)文案精彩文檔/*循環(huán)構(gòu)造Huffman樹*/for (i=0; in _1; i+)/ ml、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 (HuffNode j.weight ml & HuffNodej.pare nt=-1)m2=m1;/m1中是最小x2=x1;m1= HuffNodej.weight;x1=j;else if (HuffNode j.weight m2 & HuffNodej.pare nt=-1)m

5、2=HuffNodej.weight;x2=j; /* end for */*設(shè)置找到的兩個子結(jié)點(diǎn)x1、x2的父結(jié)點(diǎn)信息*/m仁m2=MAXQ Z;實用標(biāo)準(zhǔn)文案精彩文檔HuffNodex1.pare nt= n+i;HuffNodex2.pare nt= n+i;HuffNode n+i.weight = HuffNodex1.weight + HuffNodex2.weight;HuffNode n+i.lchild = x1;HuffNode n+i.rchild = x2;葉子節(jié)點(diǎn)的哈夫曼編碼的保存:for (j=cd.start+1; j n; j+)HuffCodei.bit j =

6、 cd.bitj;HuffCodei.start = cd.start;主函數(shù)展示:int mai n()HNode HuffNodeMAXNODE;HCodeType HuffCodeMAXLEAF,cd;int i, j, c, p, n,k=0;char wen 100;實用標(biāo)準(zhǔn)文案精彩文檔char z;scanf (%d, &n);Huffma nTree (HuffNode, n);for (i=0; i n; i+)cd.start = n-1;c = i;p = HuffNodec.pare nt;while (p != -1)/*父結(jié)點(diǎn)存在*/if (HuffNodep

7、.lchild = c)cd.bitcd.start = 0;elsecd.bitcd.start = 1;cd.start-;/*求編碼的低一位*/c=p;p=HuffNodec.pare nt;/*設(shè)置下一循環(huán)條件*/ /* end while */ for (j=cd.start+1; j n; j+)HuffCodei.bit j = cd.bitj;實用標(biāo)準(zhǔn)文案精彩文檔HuffCodei.start = cd.start; /* end for */z=getchar();z=getchar();for(;z!=n;z=getchar()wen k+=z;for(i=0;i n ;i

8、+)if(z=HuffNodei.value)for (j=HuffCodei.start+1; j n; j+) printf (%d, HuffCodei.bit break;else;prin tf(n);for(i=0;ik;i+)prin tf(%c,we n i);j);實用標(biāo)準(zhǔn)文案精彩文檔prin tf(n);return 0;四、調(diào)試分析與心得體會：雖然哈夫曼樹的建立有書上的參考，但是實際寫整個代碼的時候還是問題重重。首先就是哈弗曼樹忘記了初始的賦值，導(dǎo)致最后出現(xiàn)了問題。這樣的錯誤還是很容易解決，但是之后就出現(xiàn)了WA的情況。在同學(xué)的幫助下，最后發(fā)現(xiàn)是因為在選取節(jié)點(diǎn)的時候，循環(huán)出

9、現(xiàn)了問題，雖然看起來編譯沒有錯，但是邊緣情況就會出現(xiàn)數(shù)據(jù)錯誤，這個還是很令人警醒，而這種思考的不全面的問題，在debug的過程中會耗去大量的時間，這是要注意的。五、用戶操作說明：輸入表示字符集大小為 n n (n n = fl u it 3阿iR !：實用標(biāo)準(zhǔn)文案30精彩文檔七、附錄：#in elude #in clude#define MAXBIT#define MAXLEAF100實用標(biāo)準(zhǔn)文案30精彩文檔#defi ne MAXNODEMAXLEAF*2 -1實用標(biāo)準(zhǔn)文案精彩文檔#define MAXQZ10000 /權(quán)值typedef structint bitMAXBIT;int st

10、art; HCodeType;/*編碼結(jié)構(gòu)體*/typedef structint weight;int pare nt;int lchild;int rchild;char value; HNode;/*結(jié)點(diǎn)結(jié)構(gòu)體*/*構(gòu)造一顆哈夫曼樹*/void Huffma nTree (HNode HuffNodeMAXNODE, i nt n)int i = 0, j, m1, m2, x1, x2;實用標(biāo)準(zhǔn)文案精彩文檔char x;/*初始化存放哈夫曼樹數(shù)組HuffNode中的結(jié)點(diǎn)*/while (i n)HuffNodei.weight = 0;/權(quán)值HuffNodei.pare nt =-1;

11、HuffNodei.lchild =-1;HuffNodei.rchild =-1;scan f(%c, &x);sca nf(%c,&HuffNodei.value); /實際值，可根據(jù)情況替換為字母i+;/*輸入n個葉子結(jié)點(diǎn)的權(quán)值*/scan f(%c, &x);i = 0;while (i n)sca nf (%d, &Hu ffNodei.weight);i+;for (i=n; i2*n-1; i+)實用標(biāo)準(zhǔn)文案精彩文檔HuffNodei.weight = 0;/權(quán)值HuffNodei.pare nt =-1;HuffNodei.lchild =-1;

12、HuffNodei.rchild =-1;HuffNodei.value=i;/*循環(huán)構(gòu)造Huffman樹*/for (i=0; in-1; i+)m仁m2=MAXQZ;/ m1、m2中存放兩個無父結(jié)點(diǎn)且結(jié)點(diǎn)權(quán)值最小的兩個結(jié)點(diǎn)x仁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.pare nt=-1)m2=m1;/m1中是最小x2=x1;m仁Hu ffNodej.weight;實用標(biāo)準(zhǔn)文案精彩文檔int mai n()x1=j；else if (Hu

13、ffNodej.weight m2 & HuffNodej.pare nt=-1)m2=HuffNodej.weight;x2=j; /* end for */*設(shè)置找到的兩個子結(jié)點(diǎn)x1、x2的父結(jié)點(diǎn)信息*/HuffNodex1.pare nt= n+i;HuffNodex2.pare nt= n+i;HuffNode n+i.weight = HuffNodex1.weight + HuffNodex2.weight;HuffNode n+i.lchild = x1;HuffNode n+i.rchild = x2;實用標(biāo)準(zhǔn)文案精彩文檔HNode HuffNodeMAXNODE;/*

14、定義一個結(jié)點(diǎn)結(jié)構(gòu)體數(shù)組HCodeType HuffCodeMAXLEAF,cd;/*定義一個編碼結(jié)構(gòu)體數(shù)組,臨時變量來存放求解編碼時的信息*/int i, j, c, p, n,k=0;char wen 100;char乙scanf (%d, &n);Huffma nTree (HuffNode, n);for (i=0; i n; i+)cd.start = n-1;c = i;p = HuffNodec.pare nt;while (p != -1)/*父結(jié)點(diǎn)存在*/if (HuffNodep.lchild = c)cd.bitcd.start = 0;elsecd.bitcd.s

15、tart = 1;cd.start-;/*求編碼的低一位*/c=p;*/同時定義一個實用標(biāo)準(zhǔn)文案精彩文檔p=HuffNodec.pare nt;/*設(shè)置下一循環(huán)條件*/ /* end while */*保存求出的每個葉結(jié)點(diǎn)的哈夫曼編碼和編碼的起始位*/for (j=cd.start+1; j n; j+)HuffCodei.bitj = cd.bitj;HuffCodei.start = cd.start; /* end for */z=getchar();z=getchar();for(;z!=n;z=getchar()wen k+=z;for(i=0;i n;i+)if(z=HuffNod

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