《数据结构哈夫曼树编码及译码的实现实验报告》由会员分享，可在线阅读，更多相关《数据结构哈夫曼树编码及译码的实现实验报告（13页珍藏版）》请在金锄头文库上搜索。
1、实验：哈夫曼树编码及译码的实现一实验题目给定字符集的HUFFMANN编码与解码,这里的字符集及其字符频数 自己定义，要求输出个字符集的哈夫曼编码及给定的字符串的哈夫曼 码及译码结果。二实验原理首先规定构建哈夫曼树,然后进行哈夫曼树的编码,接着设计 函数进行字符串的编码过程,最后进行哈夫曼编码的译码。首先定义一个结构体,这个结构体定义时尽可能的大,用来存 放左右的变量,再定义一个地址空间,用于存放数组,数组中每个元 素为之前定义的结构体。输入n个字符及其权值。构建哈夫曼树：在上述存储结构上实现的哈夫曼算法可大致描 述为：1. 首先将地址空间初始化，将ht 0n-l中所有的结点里的指 针都设置为空
2、,并且将权值设置为 0.2. 输入:读入n个叶子的权值存于向量的前n个分量中。它们是 初始森林中 n 个孤立的根结点上的权值。3. 合并:对森林中的树共进行n-1次合并，所产生的新结点依次 放入向量 ht 的第 i 个分量中。每次合并分两步： 在当前森林ht 0iT的所有结点中，选取权最小和次小的 两个根结点si和s2作为合并对象，这里0Wsl, s2Wi-l。 将根为ht si和ht s2的两棵树作为左右子树合并为一棵 新的树，新树的根是新结点ht i。具体操作：将 ht si和 ht s2的 parent 置为 i， 将 hti的 lchild 和rchild分别置为si和s2 .新结点h
3、t i的权值置为ht si和ht s2 的权值之和。4. 哈夫曼的编码：约定左子为0右子为i,则可以从根结点到叶子结点的路径上的字符组成的字符串作为该叶子结点的编码。 当用户输入字母时。就在已经找好编码的编码结构体中去查找 该字母。查到该字母就打印所存的哈夫曼编码。接着就是完成用户输 入 0 、1 代码时把代码转成字母的功能。这是从树的头结点向下查找， 如果当前用户输入的 0、1 串中是 0 则就走向该结点的左子。如果是 1 这就走向该结点的右结点，重复上面步骤。直到发现该结点属于输 入了字母的结构体则打印该结构体的字母。重复上面步骤。直到找完 用户输入 0、1 串为止。则就完成了程序所有的译
4、码过程。三源程序代码#include #include #include #include#include 文件#include #define MAX 200typedef struct数组char data;int weight;int parent;int lchild;int rchild;/调用数组头文件/用get ch ()要调用的头/宏定义/定义哈夫曼编码的结构/定义权值/定义左子树/定义右子树huffmannode;typedef structchar bits50;int start;huffmancode ;void main()huffmannode ht100;huff
5、mancode cd100;char string100;/定义保存哈夫曼结构体char hcd100;int i,j,x,y,s1,s2,m1,m2,n,c,f,k;printf(请输入字符个数n=);scanf(%d,&n);for(i=0;in;i+)/定义储存权值的空间/定义数组存储空间/输入字符的个数getchar();/获得输入的字符printf (请输入第%d字符变量和权值大小:，i+1);scanf(%c%d，&hti.data，&hti.weight);/输入字符函数和权值for(i=0;i2*n-1;i+)hti.parent=hti.lchild=hti.rchild=0
6、; / 初始化 父结点，左右子结点for (i=n;i2*n-1;i+)s1=s2=0;/初始化变量m1=m2=MAX;for (j=0;ji;j+) if (htj.weightm1 &htj.parent=0) / 寻找无 父结点的最小值m2=m1;s2=s1;m1=htj.weight;s1=j; / 寻找当前 最小值else if(htj.weightm2 &htj.parent=0 ) /寻找无父结点的次小值m2=htj.weight;s2=j;hts1.parent=i;hts2.parent=i;hti.weight=m1+m2;为 i 的权值hti.lchild=s1;hti.
7、rchild=s2;for(i=0;in;i+)/寻找次小值/s1 的父结点为 i/ 最小值的权值相加/i的左子为si/i 的右子为 s2cdi.start=n;cdi.bitscdi.start=0;for(c=i,f=hti.parent;f!=0;c=f,f=htf.parent)if(htf.lchild=c) cdi.bits-cdi.start=0;else cdi.bits-cdi.start=i;printf (n输出哈夫曼译码:n);for (i=0;in;i+)printf(%c:,hti.data);/输出字符for(j=cdi.start;j=n;j+)printf(%
8、c,cdi.bitsj); / 输出字符的 01代码printf(n);printf (n请输入字符串信息:n);scanf(%s,string);/输入字符串for(i=0;stringi!=0;i+)for(c=0;c=n;c+)if(stringi=htc.data) /寻找与输入字符相匹配的字母for(j=cdc.start;j=n;j+)printf(%c,cdc.bitsj); / 输出字母代码break;prin tf(请输入哈夫曼译码:n);scanf(%s,hcd);/输入 0、1 代码f=2*n-2;for(i=0;hcdi!=0;i+)if(hcdi=0)子f=htf.l
9、child;else if(hcdi=1)f=htf.rchild;子if(fn)/判断输入为 0，寻找左/判断输入为 1，寻找右printf(%c,htf.data); /输出字符串f=2*n-2;printf(n);口冈63339847981 132323321k a b c e f ff h i J :c./1; .lzl.l/lj-.1/1.弋 大大大大大大大大蟲 +B亠M+H+R+-H+R+M+R+Mr 打 nununnunnunnunu rK- 0汞汞汞汞汞汞汞汞汞丢 =1量量量量量量量量量a 躺变变变变变变变变蟲 初宀rHMMMHMHm 兴入入入入入入入入入入字 0 123456
10、7891鹼岀哈夫曼译码: 卜=0100b：011L：110F：000KfEl： 101i：001Lj：1110肛 0101getch();四运行结果（截图）信息:晴输入字符串F八计算机类件业、练习、教程算法与数据结构-c语言描述、数据结构作业哈夫曼树M）.五实验体会通过编程，我进一步学习了哈弗曼编码的特点、存储方法和基本原理，提高 了自己运用C语言正确编程及调试的能力，运用数据结构解决简单的实际问题的 能力，为后续数据结构课程的学习打下基础。在此次实验中遇到了很多语句赋值的错误，还有 for 语句使用的不熟 练，以及自己的粗心而造成的标点符号使用错误，宏语句的定义等等，主 要的解决方案是，看一些关于 C 语言编程的书籍，请教其他同学，使得编 译成功自己的程序。这次的设计可以看作是一次理论与实践相结合的桥梁，通过这次的设计，我 学习到了许多的知识，也认识到了自己目前的不足，那就是缺乏相应的知识与经 验，所以在运用和操作方面体现了不足。我还明白了在编写程序的时候，应该尽 量使界面简洁大方，布局统一。变量类型的定义，一定要够用就好，这样程序就 可以尽可能的减少对系统资源的占用。在设计时也免不了存在着一些不足，所以 在今后的学习中我会努力取得更大的进步。
