《c语言如何实现哈夫曼编码与译码.doc》由会员分享,可在线阅读,更多相关《c语言如何实现哈夫曼编码与译码.doc(6页珍藏版)》请在三一文库上搜索。
1、c语言如何实现哈夫曼编码与译码在电报通讯中,电文是以二进制的0、1序列传送的。字符集中的字符的使用频率是不同的(比如e和t的使用较之q和z要频繁得多),哈夫曼编码可以使得编码的总长最短,从而相同的位长可以传送更多的信息。本程序以下面的字符及使用频率为例:首先建立哈夫曼树:下面是哈夫曼编码的存储结构:程序清单如下:#includestdio.h#define n 5 /叶子数目#define m (2*n-1) /结点总数#define maxval 10000.0#define maxsize 100 /哈夫曼编码的最大位数typedef structchar ch;float weight;
2、int lchild,rchild,parent;hufmtree;typedef structchar bitsn; /位串int start; /编码在位串中的起始位置char ch; /字符codetype;void huffman(hufmtree tree);/建立哈夫曼树void huffmancode(codetype code,hufmtree tree);/根据哈夫曼树求出哈夫曼编码void decode(hufmtree tree);/依次读入电文,根据哈夫曼树译码void main()printf( 哈夫曼编码n);printf(总共有%d个字符n,n);hufmtree
3、 treem;codetype coden;int i,j;/循环变量huffman(tree);/建立哈夫曼树huffmancode(code,tree);/根据哈夫曼树求出哈夫曼编码printf(【输出每个字符的哈夫曼编码】n);for(i=0;in;i+)printf(%c: ,codei.ch);for(j=codei.start;jn;j+)printf(%c ,codei.bitsj);printf(n);printf(【读入电文,并进行译码】n);decode(tree);/依次读入电文,根据哈夫曼树译码void huffman(hufmtree tree)/建立哈夫曼树int
4、i,j,p1,p2;/p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标float small1,small2,f;char c;for(i=0;im;i+) /初始化treei.parent=0;treei.lchild=-1;treei.rchild=-1;treei.weight=0.0;printf(【依次读入前%d个结点的字符及权值(中间用空格隔开)】n,n);for(i=0;in;i+) /读入前n个结点的字符及权值printf(输入第%d个字符为和权值,i+1);scanf(%c %f,c,f);getchar();treei.ch=c;treei.weight=f;f
5、or(i=n;im;i+) /进行n-1次合并,产生n-1个新结点p1=0;p2=0;small1=maxval;small2=maxval; /maxval是float类型的最大值for(j=0;ji;j+) /选出两个权值最小的根结点if(treej.parent=0)if(treej.weightsmall1)small2=small1; /改变最小权、次小权及对应的位置small1=treej.weight;p2=p1;p1=j;elseif(treej.weightsmall2)small2=treej.weight; /改变次小权及位置p2=j;treep1.parent=i;tr
6、eep2.parent=i;treei.lchild=p1; /最小权根结点是新结点的左孩子treei.rchild=p2; /次小权根结点是新结点的右孩子treei.weight=treep1.weight+treep2.weight;/huffmanvoid huffmancode(codetype code,hufmtree tree)/根据哈夫曼树求出哈夫曼编码/codetype code为求出的哈夫曼编码/hufmtree tree为已知的哈夫曼树int i,c,p;codetype cd; /缓冲变量for(i=0;in;i+)cd.start=n;cd.ch=treei.ch;c
7、=i; /从叶结点出发向上回溯p=treei.parent; /treep是treei的双亲while(p!=0)cd.start-;if(treep.lchild=c)cd.bitscd.start=0; /treei是左子树,生成代码0elsecd.bitscd.start=1; /treei是右子树,生成代码1c=p;p=treep.parent;codei=cd; /第i+1个字符的编码存入codei/huffmancodevoid decode(hufmtree tree)/依次读入电文,根据哈夫曼树译码int i,j=0;char bmaxsize;char endflag=2; /电文结束标志取2i=m-1; /从根结点开始往下搜索printf(输入发送的编码(以2为结束标志):);gets(b);printf(译码后的字符为);while(bj!=2)if(bj=0)i=treei.lchild; /走向左孩子elsei=treei.rchild; /走向右孩子if(treei.lchild=-1) /treei是叶结点printf(%c,treei.ch);i=m-1; /回到根结点j+;printf(n);if(treei.lchild!=-1bj!=2) /电文读完,但尚未到叶子结点printf(nERRORn); /输入电文有错/decode
链接地址:https://www.31doc.com/p-3250878.html