[离散作业.docVIP

离 散 实 验 报 告 姓名：毛伟鹏 学号：2012210496 实验题目：哈夫曼编码及其应用 一、题目：哈夫曼编码及其应用 二、摘要 哈夫曼数，也称最优二叉树，是指对于一组带有确定权值的叶结点，构造的具有最小带权路径长度的二叉树。? 设二叉树具有n个带权值的叶结点，那么从根结点到各个叶结点的路径长度与相应结点权值的乘积之和叫做二叉树的带权路径长度WPL，记作：?WPL=kn kkLW1。在给定一组具有确定权值的叶结点，可以构造出不同的带权二叉树。根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。?在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。例如，假设要传送的电文为ABACCDA，电文中只含有A，B，C，D四种字符，若这四种字符采用下表所示的编码，则电文的代码为000010000100100111?000，长度为21。?在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短。如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。并且在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，以避免反译成原文时，编码出现多义性。? 在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。?采用哈夫曼树进行编码，也不会产生上述二义性问题。因为，在哈夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的哈夫曼编码不可能是另一个字符的哈夫曼编码的前缀，从而保证了译码的非二义性。??? 三、实验目的： （1）了解前缀编码的概念，理解数据压缩的基本方法； （2）掌握最优子结构性质的证明方法； （3）掌握贪心法的设计思想并能熟练运用。 四、实验设计： ?1、由给定的n个权值{W1，W2，…，Wn}构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合F＝{T1，T2，…，Tn}；? 2、在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；? 3、在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；? 4、重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。 五、实验方法、步骤（或：程序代码或操作过程） 源程序： #include iostream.h #include iomanip.h #include string.h #include malloc.h #include stdio.h //typedef int TElemType; const int UINT_MAX=1000; char str[50]; typedef struct { int weight,K; int parent,lchild,rchild; }HTNode,* HuffmanTree; typedef char **HuffmanCode; //-----------全局变量----------------------- HuffmanTree HT; HuffmanCode HC; int w[50],i,j,n; char z[50]; int flag=0; int numb=0; // -----------------求哈夫曼编码----------------------- struct cou{ char data; int count; }cou[50]; int min(HuffmanTree t,int i) { // 函数void select()调用 int j,flag; int k=UINT_MAX; // 取k为不小于可能的值,即k为最大的权值1000 for(j=1;j=i;j++) if(t[j].weightkt[j].parent==0) k=t[j].weight,flag=j; t[flag].parent=1; return flag; } //--------------------slect函数---------------------- void select(Huffman