《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三哈夫曼樹實(shí)驗(yàn)報(bào)告(共11頁(yè)).doc》由會(huì)員分享，可在線閱讀，更多相關(guān)《數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)三哈夫曼樹實(shí)驗(yàn)報(bào)告(共11頁(yè)).doc（11頁(yè)珍藏版）》請(qǐng)?jiān)趨R文網(wǎng)上搜索。

1、精選優(yōu)質(zhì)文檔-傾情為你奉上題目：哈夫曼編/譯碼器 一、 題目要求：寫一個(gè)哈夫曼碼的編/譯碼系統(tǒng)，要求能對(duì)要傳輸?shù)膱?bào)文進(jìn)行編碼和解碼。構(gòu)造哈夫曼樹時(shí)，權(quán)值小的放左子樹，權(quán)值大的放右子樹，編碼時(shí)右子樹編碼為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 DEMONHuffma

2、nTree (HNode HuffNodeMAXNODE, int n)作用：構(gòu)造一個(gè)哈夫曼樹，并循環(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; Huf

3、fNodei.lchild =-1; HuffNodei.rchild =-1;scanf("%c",&x); scanf("%c",&HuffNodei.value); /實(shí)際值，可根據(jù)情況替換為字母 i+; /* 輸入 n 個(gè)葉子結(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)值 H

4、uffNodei.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中存放兩個(gè)無(wú)父結(jié)點(diǎn)且結(jié)點(diǎn)權(quán)值最小的兩個(gè)結(jié)點(diǎn) x1=x2=0;/找出所有結(jié)點(diǎn)中權(quán)值最小、無(wú)父結(jié)點(diǎn)的兩個(gè)結(jié)點(diǎn)，并合并之為一顆二叉樹 for (j=0; j<n+i; j+) if (HuffNodej.weight < m1 && HuffNodej.parent=-1) m2

5、=m1;/m1中是最小 x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight < m2 && 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; HuffNod

6、en+i.lchild = 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 (

7、HuffNode, n); 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+) HuffCo

8、dei.bitj = cd.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+)prin

9、tf("%c",weni);printf("n"); return 0;四、 調(diào)試分析與心得體會(huì)： 雖然哈夫曼樹的建立有書上的參考，但是實(shí)際寫整個(gè)代碼的時(shí)候還是問(wèn)題重重。首先就是哈弗曼樹忘記了初始的賦值，導(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)編譯沒有錯(cuò)，但是邊緣情況就會(huì)出現(xiàn)數(shù)據(jù)錯(cuò)誤，這個(gè)還是很令人警醒，而這種思考的不全面的問(wèn)題，在debug的過(guò)程中會(huì)耗去大量的時(shí)間，這是要注意的。五、 用戶操作說(shuō)明：輸入表示字符集大小為n（n <=

10、 100）的正整數(shù)，以及n個(gè)字符和n個(gè)權(quán)值（正整數(shù)，值越大表示該字符出現(xiàn)的概率越大）；輸入串長(zhǎng)小于或等于100的目標(biāo)報(bào)文。六、 運(yùn)行結(jié)果：附帶自己的算法完成的結(jié)果圖，可以通過(guò)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;

11、/* 編碼結(jié)構(gòu)體 */typedef 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 =-1; HuffNodei.rchild =-1;scanf("%c",&x); scanf("%c",&HuffNodei.value); /實(shí)際值，可根據(jù)情況替換為字母 i+; /* 輸入 n 個(gè)葉子結(jié)點(diǎn)的權(quán)值 */scanf("%c",&x);i = 0; while (i<n)