[计算机]08级实验.doc

实验报告一. 实验目的1.掌握哈夫曼树的基本概念及所用的存储结构2.掌握哈夫曼树的建立算法3.掌握哈夫曼树的应用二. 实验内容1.给定权值5，29，7，8，14，23，3，11，建立哈夫曼树，输出哈夫曼编码2.对上述给定的哈夫曼树及得到的哈夫曼编码，试输入一串二进制编码，输出它的哈夫曼译码三.实验与算法分析将建立哈夫曼树、实现哈夫曼编码、哈夫曼译码都定义成子函数的形式，然后再在主函数中调用它们。建立哈夫曼树时，将哈夫曼树的结构定义为一个结构型的一维数组，每个元数含有四项：权值、双亲、左孩子、右孩子。给定的权值可以从键盘输入，要输出所建立的哈夫曼树，只要输出表示哈夫曼树的一维数组中的全部元素即可。要实现哈夫曼编码，只要在所建立的哈夫曼树上进行二进制编码：往左走，编码为0，往右走编码为1，然后将从根节点到树叶中的所有0，1排列起来，则得到该树叶的哈夫曼编码。哈夫曼编码可以用一个结构型的一维数组保存，每个元素包含：编码、编码的开始位置、编码所对应的字符三项。哈夫曼译码，就是将输入的编码还原成对应的字符。该实验中哈夫曼树采用双亲孩子表示法存储，并增加权值域，构造哈夫曼树的叶子结点（树的权）n个，合并次数为n-1次，则森林中总共有2n-1颗树（包含合并后删除的）。抽象的算法描述为：建立哈夫曼树（n个结点的权值分别是：w1,w2,w3,w4,Wn） 把w1,w2,w3,w4,Wn看成是有n颗树的森林（每颗树仅有一个结点） 在森林中选出两个根节点的权值最小的树合并，作为一颗新树的左右子树，并且新树的根节点权值为其左右子树根节点权值之和 从森林中删除选取的两颗树，并将新树加入森林 重复步，直到森林中只剩一棵树为止，该树及为我们所求得的哈夫曼树实现哈夫曼编码 第一个树叶为a 其他的树叶为b,c,d,进行哈夫曼译码四.可执行程序及注释代码：#include#includeconst int n=8; /maxn表示叶子数目const int m=2*n-1;/m为森林中树的棵树struct tree /哈夫曼树种的一个结点float weight;/权值int parent;/双亲int lch,rch;/左孩子、右孩子;struct codetype/哈夫曼编码int bitsn+1;/编码的存放位置int start;/编码的开始存放位置char ch;/所对应的字符;tree hftreem+1;codetype coden+1;void creathuffmantree()/建立哈夫曼树int i,j,p1,p2;float s1,s2;for(i=1;i=m;i+)hftreei.parent=0;hftreei.lch=0;hftreei.rch=0;hftreei.weight=0;cout请输入n个权值endl;for(i=1;ihftreei.weight;/输入权值for(i=n+1;i=m;i+)/进行次合并p1=p2=0;/p1、p2分别指向两个权最小的值的位置s1=s2=32767;/s1、s2代表两个最小权值for(j=1;j=i-1;j+)/该权值还没有被选中if(hftreej.parent=0)if(hftreej.weights1)s2=s1;s1=hftreej.weight;p2=p1;p1=j;elseif(hftreej.weights2)s2=hftreej.weight;p2=j;hftreep1.parent=i;hftreep2.parent=i;hftreei.lch=p1;hftreei.rch=p2;hftreei.weight=hftreep1.weight+hftreep2.weight;void huffcode() /哈夫曼编码codetype cd;int c,p;for(int i=1;i=n;i+)cd.start=n+1;cd.ch=96+i; /第一个树叶对应字母a，其余依此类推c=i;p=hftreei.parent;while(p!=0)cd.start-;if(hftreep.lch=c)cd.bitscd.start=0;else cd.bitscd.start=1;c=p;p=hftreep.parent;codei=cd;for(i=1;i=n;i+)cout字符codei.ch的权值为：hftreei.weightsetw(5)编码是：;for(int j=codei.start;j=n;j+)coutcodei.bitsj ; coutendl;void trancode() /哈夫曼译码int i=m;char b;coutb;while(b=0)|(b=1)if(b=0)i=hftreei.lch;else i=hftreei.rch;if(hftreei.lch=0)coutb;void main()creathuffmantree(); /建立哈夫曼树huffcode(); /实现哈夫曼编码trancode(); /进行哈夫曼译码运行结果五.试验小结算法的时间复杂度分析：哈夫曼树的建立：O(n2)；哈夫曼编码：O(n)；哈夫曼译码：O(1)。所用结构特色的深入分析：二叉树,每个结点最多有两个孩子的有序树,而哈夫曼树是一种特殊的二叉树及最优二叉树.哈夫曼树在数据编码中的应用是数据的最小冗余编码问题，它是数据压缩学的基础。哈夫曼树是一种最优二叉树，它的编码是一种最优编码。哈夫曼译码是将哈夫曼编码采用通信的形式发送出去，对方接受到编码后，将编码还原成字符的过程，在通信中得到广泛的应用。而在程序设计中，对多分支的判别（各个分子的频率不同），利用哈夫曼树，可以提高程序的执行效率。树的存储结构和前面所讲线性表的链式存储结构有异曲同工之处，每个结点结构都有存放自身结点信息的量，又有存放与之相关的结点信