《实验三 哈夫曼编码》由会员分享，可在线阅读，更多相关《实验三 哈夫曼编码（6页珍藏版）》请在金锄头文库上搜索。
1、第 1 页共 6 页华北水利水电大学数据结构 实验报告20132014 学年学年第第 二二 学期学期2013 级级计算机科学与技术计算机科学与技术（专升本）（专升本） 专业专业班级：学号：姓名：实验三树的应用一、 实验题目：树的应用树的应用哈夫曼编码哈夫曼编码二、 实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈 夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。 从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，求 出各字符的哈夫曼编码。要求： 1 输出存放哈夫曼树的数组 HT 的初态和
2、终态； 2 输出每个字符的哈夫曼编码； 3 输入由上述若干字符组成的字符串，对电文进行编码并输出； 4 （选作）输入电文的哈夫曼编码，进行译码并输出。三、程序源代码：#include #include #include #define N 80typedefstruct unsigned intweight; unsigned intparent,lchild,rchild; HTNode,*HuffmanTree;/*动态分配数组存储赫夫曼树 */ typedef char* *HuffmanCode;/* 动态分配数组存储赫夫曼编码表 */void Select(HuffmanTree /
3、* 从 i 个节点中选出 parent 为 0 且 weight 最小的两个结点，其序号分别为 s1 和 s2 */ void reverse(char a,int /*把原字符串逆置*/ void Huffmancoding(HuffmanTree if (nweight=*w; p-parent=0; p-lchild=0; p-rchild=0; for (i=n+1;iweight=0; p-parent=0; p-lchild=0; p-rchild=0; printf(“初态:n“); printf(“nodetweighttparenttlchildtrchildn“); p=H
4、T+1; for(i=1;iweight,p-parent,p-lchild,p-rchild); printf(“n“);int s1,s2,t;/*s1 和 s2 分别为最小和次小节点*/ for (i=n+1;iweight,p-parent,p-lchild,p-rchild); printf(“n“);/*从叶子到根逆向求每个字符的赫夫曼编码*/ int start,k;第 3 页共 6 页unsigned int c,f; char *cd; cd=NULL; HC=(HuffmanCode)malloc(n+1)*sizeof(char *); /*分配 n 个字符编码的头指针向
5、量 ,0 号单元未用*/ cd=(char *)malloc(n*sizeof(char); /*分配求编码的临时工作空间*/ for (i=1; iweight=0; p-parent=0; p-lchild=0; p-rchild=0;， 这 两个问题检查了多次才发现，本实验遇到的最大的问题也就是这两个，经过多次反复检查才修改出来。 还有一个就是对各个叶子节点编码时，本实验采用了从叶子节点到根节点逆序编码并存入 cd 所指向 的存储单元中，即第 1 个节点的编码存入 cd0，第 2 个节点的编码存入 cd1等依次类推，最后再调用 逆置字符串函数修改一下 cd 中编码的顺序，调用逆置函数修改之后即为从根节点到叶子节点的正序编码， 本人认为这样做不仅容易理解，而且这样做的结果对哈夫曼树的编码是“不等长编码” ，节省了内存空间。 其它问题都是些小的问题，经过多次反复检查修改即可。 本实验除课本和课件外无任何参考，本人独立完成，建议无。
