《数据结构实验三哈夫曼树实验报告（2020年7月整理）.pdf》由会员分享，可在线阅读，更多相关《数据结构实验三哈夫曼树实验报告（2020年7月整理）.pdf（9页珍藏版）》请在金锄头文库上搜索。
1、实验报告 3：哈夫曼编/译码器 1 题目：哈夫曼编/译码器 一、题目要求： 写一个哈夫曼码的编/译码系统，要求能对要传输的报文进行编码和解码。构造哈夫曼树时，权值小的放左 子树，权值大的放右子树，编码时右子树编码为 1，左子树编码为 0. 二、概要设计： 数据结构： typedef struct int bitMAXBIT; int start; HCodeType; /* 编码结构体 */ typedef struct int weight; int parent; int lchild; int rchild; char value; HNode; /* 结点结构体 */ 函数： void
2、 DEMONHuffmanTree (HNode HuffNodeMAXNODE, int n) 作用：构造一个哈夫曼树，并循环构建 int main () 作用：运用已经构建好的哈弗曼树，进行节点的处理，达到成功解码编译 三、详细设计： 哈夫曼树的建立： void DEMONHuffmanTree (HNode HuffNodeMAXNODE, int n) int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼树数组 HuffNode 中的结点 */ while (in) HuffNodei.weight = 0;/权值 HuffNodei.pa
3、rent =-1; HuffNodei.lchild =-1; HuffNodei.rchild =-1; scanf(%c, scanf(%c, /实际值，可根据情况替换为字母 i+; 实验报告 3：哈夫曼编/译码器 2 /* 输入 n 个叶子结点的权值 */ scanf(%c, for(i=0;in;i+) scanf (%d, for (i=n; i2*n-1; i+) HuffNodei.weight = 0;/权值 HuffNodei.parent =-1; HuffNodei.lchild =-1; HuffNodei.rchild =-1; HuffNodei.value=i;
4、/* 循环构造 Huffman 树 */ for (i=0; in-1; i+) m1=m2=MAXQZ; / m1、m2 中存放两个无父结点且结点权值最小的两个结点 x1=x2=0;/找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 for (j=0; jn+i; j+) if (HuffNodej.weight m1 /m1 中是最小 x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight m2 x2=j; /* end for */ /* 设置找到的两个子结点 x1、x2 的父结点信息 */ HuffNode
5、x1.parent = n+i; HuffNodex2.parent = n+i; HuffNoden+i.weight = HuffNodex1.weight + HuffNodex2.weight; HuffNoden+i.lchild = x1; HuffNoden+i.rchild = x2; 叶子节点的哈夫曼编码的保存： 实验报告 3：哈夫曼编/译码器 3 for (j=cd.start+1; jn; j+) HuffCodei.bitj = cd.bitj; HuffCodei.start = cd.start; 主函数展示： int main() HNode HuffNodeMA
6、XNODE; HCodeType HuffCodeMAXLEAF,cd; int i, j, c, p, n,k=0; char wen100; char z; scanf (%d, HuffmanTree (HuffNode, n); for (i=0; i n; i+) cd.start = n-1; c = i; p = HuffNodec.parent; while (p != -1) /* 父结点存在 */ if (HuffNodep.lchild = c) cd.bitcd.start = 0; else cd.bitcd.start = 1; cd.start-; /* 求编码的
7、低一位 */ c=p; p=HuffNodec.parent; /* 设置下一循环条件 */ /* 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) for (j=HuffCodei.start+1; j n; j+) printf (%d, H
8、uffCodei.bitj); break; 实验报告 3：哈夫曼编/译码器 4 else; printf(n); for(i=0;ik;i+) printf(%c,weni); printf(n); return 0; 四、调试分析与心得体会： 虽然哈夫曼树的建立有书上的参考，但是实际写整个代码的时候还是问题重重。首先就是哈弗曼树忘 记了初始的赋值，导致最后出现了问题。这样的错误还是很容易解决，但是之后就出现了 WA 的情况。在 同学的帮助下，最后发现是因为在选取节点的时候，循环出现了问题，虽然看起来编译没有错，但是边缘 情况就会出现数据错误，这个还是很令人警醒，而这种思考的不全面的问题，在
9、 debug 的过程中会耗去大 量的时间，这是要注意的。 五、用户操作说明： 输入表示字符集大小为 n（n = 100）的正整数，以及 n 个字符和 n 个权值（正整数，值 越大表示该字符出现的概率越大）； 输入串长小于或等于 100 的目标报文。 六、运行结果： 附带自己的算法完成的结果图，可以通过 Prt Sc 和图片编辑器获得； 实验报告 3：哈夫曼编/译码器 5 七、附录： #include #include #define MAXBIT 100 #define MAXLEAF 30 #define MAXNODE MAXLEAF*2 -1 #define MAXQZ 10000 /权
10、值 typedef struct int bitMAXBIT; int start; HCodeType; /* 编码结构体 */ typedef struct int weight; int parent; int lchild; 实验报告 3：哈夫曼编/译码器 6 int rchild; char value; HNode; /* 结点结构体 */ /* 构造一颗哈夫曼树 */ void HuffmanTree (HNode HuffNodeMAXNODE, int n) int i = 0, j, m1, m2, x1, x2; char x; /* 初始化存放哈夫曼树数组 HuffNo
11、de 中的结点 */ while (in) HuffNodei.weight = 0;/权值 HuffNodei.parent =-1; HuffNodei.lchild =-1; HuffNodei.rchild =-1; scanf(%c, scanf(%c, /实际值，可根据情况替换为字母 i+; /* 输入 n 个叶子结点的权值 */ scanf(%c, i = 0; while (in) scanf (%d, i+; for (i=n; i2*n-1; i+) HuffNodei.weight = 0;/权值 HuffNodei.parent =-1; HuffNodei.lchil
12、d =-1; HuffNodei.rchild =-1; HuffNodei.value=i; /* 循环构造 Huffman 树 */ for (i=0; in-1; i+) m1=m2=MAXQZ; / m1、m2 中存放两个无父结点且结点权值最小的两个结点 x1=x2=0;/找出所有结点中权值最小、无父结点的两个结点，并合并之为一颗二叉树 for (j=0; jn+i; j+) if (HuffNodej.weight m1 /m1 中是最小 x2=x1; m1=HuffNodej.weight; x1=j; else if (HuffNodej.weight m2 x2=j; /* e
13、nd for */ /* 设置找到的两个子结点 x1、x2 的父结点信息 */ 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; /* 定义一个结点结构体数组 */ HCodeType HuffCodeMAXLEAF,cd; /* 定义一个编码结构体数组， 同时定义一个临 时变量来存放求解编码时的信息 */ int i, j, c, p, n,k=0; char wen100; char z; scanf (%d, HuffmanTree (HuffNode, n); for (i=0; i n; i+) cd.start = n-1; c = i; p = HuffNodec.parent; while (p != -1) /* 父结点存在 */ if (HuffNodep.lchild = c) cd.bitcd.start = 0; else cd.bitcd.star
