哈夫曼编码解码实验报告及程序.doc

实验1 哈夫曼编码译码的设计一、 实验题目：对输入指令进行哈夫曼编/译码系统的设计二、 实验要求：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。三、 实验内容：1、用C+实现Huffman编码算法程序；2、根据输入的n个带权结点，构造出哈夫曼树，并且把构造结果输出到屏幕3、要求程序输出显示所有的码字以及译码结果；四、 实验原理：根据哈夫曼树的定义，一棵二叉树要使其WPL值最小，必须使权值越大的叶结点越靠近根结点，而权值越小的叶结点越远离根结点。因此，构造哈夫曼树有此种方法：1、由给定的n个权值W1，W2，Wn构造n棵只有一个叶结点的二叉树，从而得到一个二叉树的集合FT1，T2，Tn；2、在F中选取根结点的权值最小和次小的两棵二叉树作为左、右子树构造一棵新的二叉树，这棵新的二叉树根结点的权值为其左、右子树根结点权值之和；3、在集合F中删除作为左、右子树的两棵二叉树，并将新建立的二叉树加入到集合F中；4、重复（2）（3）两步，当F中只剩下一棵二叉树时，这棵二叉树便是所要建立的哈夫曼树。所以，构造哈夫曼树主要由两个步骤组成：一是选择所有结点中权值最小的两个结点，二是将这些结点加入到二叉树中，构建成哈夫曼树。解码则反之。五、 实验步骤： #includestdio.h#define maxbit 10 /*定义哈夫曼编码最大长度*/#define maxvalue 10000 /*定义最大权值常量*/#define maxnodenumber 100/*定义结点最大数目常量*/typedef struct /*定义结点结构*/ int weight; /*权重域值为整型*/ char character; int parent,lchild,rchild;/*3个指针域为整型值，即静态指针*/ htnode; typedef struct /*定义保存一个叶子结点哈曼编码的结构*/ int bitmaxbit; /*哈曼编码域为一维数组*/ int start; /*开始位置域为整型*/ hcodetype; /*定义哈曼编码类型*/void main() /*主函数*/void gethuffmancode(htnode ht,int n); htnode htmaxnodenumber; /*定义链表存储结构区数组*/ int i,j,m1,m2,k1,k2,n,a; printf(Please input n:); /*提示输出叶子结点个数*/ scanf(%d,&n); printf(Please input character and weight:n);/*提示输出各叶子结点的权值*/ for(i=0;i2*n-1;i+) /*数组ht初始化*/ hti.weight=0; /*权重初始化为0*/ hti.character=0; hti.parent=-1; /*3个指针域初始化为-1，即NULL*/ hti.lchild=-1; hti.rchild=-1; for(i=0;in;i+) /*读入n个叶子结点的权重值*/ fflush(stdin); scanf(%c %d,&hti.character,&hti.weight); for(i=0;in-1;i+) / *控制n-1趟生成新结点构造哈夫曼树*/ m1=maxvalue; /*最小权值变量为最大权值*/ m2=maxvalue; /*次小权值变量为最大权值*/ k1=0;k2=0; /*最小和次小权值结点位置为下标0处*/ for(j=0;jn+i;j+) /*在一趟中找出两个最小权值的结点*/ if(htj.parent=-1&htj.weightm1) m2=m1;k2=k1; /*若第j个结点权小于当前最小的m1改为次小的*/ m1=htj.weight;k1=j; /*并记下新的当前最小权值及位置*/ else if(htj.parent=-1&htj.weightm2) m2=htj.weight;k2=j;/*否则若小于当前次小的m2则更新m2及其位置*/ htk1.parent=n+i; /*修改最小权值结点的双亲为刚才生成的新结点*/ htk2.parent=n+i; /*修改次小权值结点的双亲为刚才生成的新结点*/ htn+i.weight=htk1.weight+htk2.weight; /*填新生成结点的权重值*/ htn+i.lchild=k1; /*将新生成结点的左孩子指针指向k1*/ htn+i.rchild=k2; /*新生成结点的右孩子指针指向k2*/ printf(The character and the code is as follows:n); gethuffmancode(ht,n); void gethuffmancode(htnode ht,int n)/*对具有n个叶子结点的哈夫曼树ht，求所有叶子结点的哈夫曼编码并输出*/int i,j,c,p,m,k; char ch100; hcodetype cd100; /*定义存放哈曼编码的数组cd*/ for(i=0;in;i+) /*对n个结点逐一求哈夫曼编码*/ c=i;j=maxbit; /*为求一个结点的哈夫曼编码初始化c和j*/ do j-; /*j指向bit中存放编码位的正确位置*/p=htc.parent; /*p指向c的双亲结点*/if(htp.lchild=c) /*如果c是p的左孩子*/ cdi.bitj=0; /*编码位上赋0*/else cdi.bitj=1; /*否则c是p的右孩子，编码位上赋1*/c=p; /*更新c为p，为求下一个编码位做准备*/ while(p!=-1); /*当未到达根结点继续做do循环*/ cdi.start=+j; /*求完一个叶子结点的哈夫曼编码时，记下编码开始位置*/ for(i=0;in;i+) /*输出n个叶子结点的哈夫曼编码*/ printf( The Character:%c Code:,hti.character); /*显示排版需要*/ for(j=cdi.start;jmaxbit;j+) /*逐位输出一个编码*/ printf(%d,cdi.bitj); printf(n); /*输出完一个哈夫曼编码后换行*/ printf(Please input ch:); scanf(%s,ch); /*输入被译码的字符*/ printf(The decode is:); for(i=0;chi!=0;i+) /*三个循环实现译码*/ for(j=0;jn;j+) if(htj.character=chi) for(k=cdj.start;kmaxbit;k+) /*第三个循环输出译码*/ printf(%d,cdj.bitk); 六、 实验结果：经调试程序正确后，输入n=8个权重值如下：h 6；e 4；l 13；o 24；k 17；i 3；t 9；y 29.再输入被译码的字符串：hellokity七、 结果分析：1、程序用到的抽象数据类型的定义:typedef struct int weight; char character; int parent,lchild,rchild; htnode; 2、主模块的流程以及各子模块的主要功能:主main函数调用了gethuffmancode(htnode ht,int n);函数最终实现编译功能.3、在编程时应注意应注意“”、“”的嵌套，否则不易检查出也易影响实验结果。4、在调试过程中应注意权值的输入的大小，否则会出现码字。 5、在构建哈夫曼树的过程中，想到每两个最小权值结点的父亲结点是需要另外存储的，而最开始虽然按照课件上的内容将哈夫曼树的结点数设置成2*n-1个，却不知道如何使用。最初的想法