实验三哈夫曼编码译码器-Read

《实验三哈夫曼编码译码器-Read》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、/1问题实验三哈夫曼编码译码器利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道）每端都需要一个完整的编/译码系统。试为这样的信息收发站写一哈夫曼编/译码系统。基本要求：（1）初始化;从终端输入字符集的大小n，以及n个字符和n个权值建立哈夫曼树。（2）输出哈夫曼树，及各字符对应的编码。（3）编码：利用建好的哈夫曼树，对输入的待发送电文

2、进行编码。同时输入原文及编码串。（4）译码：利用建好的哈夫曼树，对输入的已接收电文进行译码。同时输入编码串及原文。2解题思路:（1）对输入的一段欲编码的字符串进行统计各个字符出现的次数，并它们转化为权值{w1,w2,……，wN}构成n棵二叉树的集合F={T1,T2,……，Tn}把它们保存到结构体数组HT[n]中,其中{Ti是按它们的ASCⅡ码值先后排序。其中每棵二叉树Ti中只有一个带权为Wi的根结点的权值为其左、右子树上根结点的权值之和。（2）在HT[1..i]中选取两棵根结点的权值最小且没有被

3、选过的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为左、右子树上根结点的权值之和。（3）哈夫曼树已经建立后，从叶子到根逆向求每一个字符的哈夫曼编码。3.结构体定义typedefstruct{floatweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;4.代码#include"stdio.h"#include"stdlib.h"#include"string.h

4、"#include"conio.h"#defineMAXSIZE60/************************************定义赫夫曼树结构体*******************************************/typedefstruct{floatweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;/*********************

5、***************************定义堆结构体**********************************************************/typedefstruct{floatkey;/关键字项intotherinfo;/其他数据项（此题目中用不到）}RedType;typedefstruct{RedTyper[MAXSIZE+1];/r[0]闲置用作哨兵intlength;/顺序表长度}SqList;/***********************

6、***************************全局变量*************************************************************/HuffmanTreeHT;/赫夫曼树HuffmanCodeHC;/码值FILE*fp,*fp1,*fp2;inta[30]={0};floatb[30];float*w;/权/****************************************测试解码（可以输入一个不正确的二进制码串）*******

7、*******************************/voidtestdecode(){charstr[200];/存放自己输入的码子intp,p1,i;/解码的线索charch;printf("请根据以上各个字符的编码输入一串二进制码字(200个以内):");gets(str);printf("以上码子解码后为:");p=59;/最初令p为树根整数，p由根顺着树枝一直到树叶i=0;ch=str[i++];while(ch!=''){for(;ch!=''&&(HT

8、[p].lchild!=0

9、HT[p].rchild!=0);){if(ch=='0'){p=HT[p].lchild;}elseif(ch=='1'){p=HT[p].rchild;}else{printf("你输入了'0','1'之外的字符，无法正确译码，请检查!");return;/直接结束}ch=str[i++];/下一个码字不断的取下一个}if(p<=30)/小于等于30的时候才正确，有可能最后一位p还没有在1-30范围内的时候就没有二进制码了，也就是说二进制码最后不完整。sw