C语言―哈夫曼树编码器和译码器

1、#include #include stdlib.h #define MAXBIT 10#define MAXVALUE 10000#define MAXLEAF 100#define MAXNODE MAXLEAF*2-1 /定义哈夫曼树编码类型typedef struct char bitMAXBIT; /存放叶子结点字符编码过后的二进制编码 int start; /存放叶子结点二进制编码在bit数组里的起始数组位置int length; /存放二进制编码的位数HFMCode; /定义哈夫曼树结点类型typedef struct char data; /编码字符int weight; /哈

2、夫曼树结点的权值int parent; /哈夫曼树结点的父结点int lchild; /哈夫曼树结点的左孩子int rchild; /哈夫曼树结点的右孩子HFMNode; /构造哈夫曼树void createHFMTree(HFMNode hfmnodeMAXNODE,int n) int i,j,m1,m2,x1,x2; for(i=0;i2*n-1;i+) hfmnodei.weight=0; hfmnodei.parent=-1; hfmnodei.lchild=-1; hfmnodei.rchild=-1; for(i=0;in;i+) getchar();printf(请输入第%d片

3、叶子的字符：,i+1); scanf(%c,&hfmnodei.data);printf(请输入第%d片叶子的权重：,i+1); scanf(%d,&hfmnodei.weight); for(i=0;in-1;i+) m1=m2=MAXVALUE; /m1和m2分别用来存储叶子结点权值的最小值和次小值x1=x2=0; /x1和x2分别用来存储m1和m2的位置for(j=0;jn+i;j+) if(hfmnodej.weightm1&hfmnodej.parent=-1) m2=m1;x2=x1;m1=hfmnodej.weight;x1=j; else if(hfmnodej.weightm

4、2&hfmnodej.parent=-1) m2=hfmnodej.weight;x2=j; hfmnodex1.parent=n+i; hfmnodex2.parent=n+i; hfmnoden+i.weight=hfmnodex1.weight+hfmnodex2.weight;/父结点的权重是左孩子和右孩子的权重之和 hfmnoden+i.lchild=x1; hfmnoden+i.rchild=x2; /显示叶子的编码字符和编码字符对应的二进制编码void showCode(HFMCode hfmcodeMAXNODE,HFMNode hfmnodeMAXNODE,int n)int

5、 i,j,k,c,p; HFMCode cd;for(i=0;in;i+) hfmcodei.length=0;hfmcodei.start=0;k=hfmcodei.start;cd.start=n-1;c=i; p=hfmnodec.parent; while(p!=-1) if(hfmnodep.lchild=c) cd.bitcd.start=0; else cd.bitcd.start=1; cd.start-; c=p; p=hfmnodec.parent; for(j=cd.start+1;jn;j+) hfmcodei.bitk=cd.bitj; k+;hfmcodei.len

6、gth+; /length计算存放的二进制编码的位数 for(i=0;in;i+) /输出每个叶子节点的哈夫曼编码 printf(第%d片叶子的编码是:,i+1); printf(%ct,hfmnodei.data);for(j=hfmcodei.start;jhfmcodei.length;j+)printf(%d,hfmcodei.bitj); printf(n); /输入字符串，得到二进制编码void compileCode(char str,int n,HFMCode hfmcodeMAXLEAF,HFMNode hfmnodeMAXNODE)int i,j,k;for(i=0;str

7、i!=0;i+)for(j=0;jn;j+)if(stri=hfmnodej.data)for(k=hfmcodej.start;khfmcodej.length;k+)printf(%d,hfmcodej.bitk);printf(nn);/输入二进制编码得到字符串void decompileCode(char num,int n,HFMCode hfmcodeMAXLEAF,HFMNode hfmnodeMAXNODE)int i,j;j=2*n-2; /哈夫曼树根结点的位置for(i=0;numi!=0;i+)if(numi=0)j=hfmnodej.lchild;else if(num

8、i=1)j=hfmnodej.rchild;if(jn) /j大于等于n表示的都是除叶子结点以外的哈夫曼树结点 printf(%c,hfmnodej.data);j=2*n-2;printf(n);/主函数void main() HFMNode hfmnodeMAXNODE; HFMCode hfmcodeMAXLEAF; char str100; /存放输入的需要编译的的字符串char num100; /存放输入的需要编译的二进制字符串int n; /输入的叶子结点数/哈夫曼编码器printf(-哈弗曼编码器-n);printf(请输入叶子结点数:); scanf(%d,&n);createHFMTree(hfmnode,n);showCode(hfmcode,hfmnode,n);/哈夫曼译码器printf(-哈夫曼译码器-n);printf(