资源描述：
《网络多媒体实验报告》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、网络多媒体上机实验一班级：学号：姓名：教师:题目构造一棵哈夫曼树分析既然是二叉树那么我们首先就定义一个二叉树结构：structtree{chardate;//数据boolmin;//叶子节点intquanzhi;//权值structtree*zuo,*you;〃左右孩子}*tre;其中权值是我们最需要关心的，因为我们就是要通过权值来构造，但权值怎么规定呢？当然是根据实际情况来！其中叶子节点是为了标记是叶子节点，便于后期编码！为了简单说明，第一个例子就直接定义多个哈夫曼树节点，然后通过这些节点來构造出最终的哈夫曼树！treetr[9]={{'a',
2、true,5},{'b',true,2},{'c1,true,9},{'d',true,3},{'etrue,6}};tr是一个哈夫曼数组，其中每个元素都是一个哈夫曼树，我们的任务就是将这些元素“整合”起来，使它们联系起来构成一个哈夫曼树。初始时，数组每个元素都是没有联系的，我们的任务就是把它们通过structtree*zuo,*you;〃左右孩子来连接起來，形象上就是构成一棵二叉树。我们先通过语言叙述的方法来构造一棵哈夫曼二叉树：a权值5b权值2c权值9d权值3e权值6首先，取权值最小的两个节点“整合”出一个新的节点，该节点的权值为最小两个节
3、点权值之和。如下图：A然后，将这个新的节点与剩下元素进行权值比较，依旧取最小的两个权值节点构造新的节点，反复这个过程，直到取完所有元素，本例的哈夫曼树如下图：其中叶子节点（也就是2,3,5,6,9）是有效的数据节点！构造时节点的左右顺序并不影响哈曼树的构造，但会导致出现不同的编码，当然编码只要不出现前缀码就是正确的编码。实现算法通过上面的例子，我们知道构造一个哈夫曼树，需要的节点数数有效数据节点的2*n-l,其中n是有效数据的个数，如上面例子，有效数据个数有5个，但最终构造出的哈夫曼树有2*5-1=9个节点，所以根据这个性质就可写岀一种算法：tr
4、eetr[9]={{*a',true,5},{*btrue,2},{'c*,true,9},{*d',true,3},{'e*,true,6}};5个数据所以需要9个空间，其中9-5M个空间是给那些无效节点使用的（哈夫曼树种非叶子节点）。首先，我们遍历这个数组，找到最小的两个元素。然后，将他们移动到前面，并将权值求和构造出新的节点，新的节点左右子树指向最小的两个元素，将这个新节点插入有效数据后面。最后，从第2+1个元素（前面两个无需遍历了）开始重新遍历。重复上述过程，直到数组填满，填满后的最后一个元素就是最终的哈夫曼树。如第一次遍历后数组诃9]
5、状态就变为：treetr
6、9]={{'d',true,3},{*b',true,2},{'c*,true,9},{'a*,true,5},{'e',true,6},{4,,false,5,tr[0],tr[1]}}最小的两个元素移到了前而，有效数据增加了一个，并且新节点左右子树指向前面两个元素。代码#include"stdafx.h"#includestaticinthfmb=O;structtree{chardate;//数据boolmin;//叶子节点intquanzhi;//权值structtree*zuo,*you;〃左右孩子}*tre;
7、structshfm{chardate;//字符数据charbianm[ll];//哈夫曼编码,最大编码数为11(可根据实际修改！)}hfm[100];//哈夫曼编码对应真实数据表voidgettree(treetr[],intshij,intyoux)//构造哈夫曼树•树集合,shij集合实际数据个数,youx集合有效数据个数{〃模拟动态增长数组，每次构造新的树就插入有效数据后面if(2*youx-l!=shij){printf(惨数不符合！”)；return;}intc=0;while(youx!=shij)//当有效个数二二实际个数时，构造
8、完成！{for(inti=c;i{〃每次循环取两个最小值并将两个最小值放置在当前循环起始两位if(tr[i].quanzhi{treep=tr
9、i];tr[i]=tr[c];tr[c]=p;}if(tr[i].quanzhi{treep=tr[i];tr[i]=tr[c+l];tr[c+l]=p;}}〃以下为通过最小值构造的新树tr[youx].quanzhi=tr[c].quanzhi+tr[c+1].quanzhi;tr[youx].you二&tr[c];//新树右孩子指向当前循环的最小值之一tr[youx].zuo=&tr[c+1];〃新树
10、左孩子指向当前循环的最小值之一youx++;c二c+2;}}voidbianltree(tree*tr,charch
11、])//哈夫曼编码
