C语言哈夫曼编码代码

1、#include<string.h>#include<stdlib.h> #include<stdio.h> int m,s1,s2;typedef structunsigned intweight;unsigned intparent,lchild,rchild;HTNode,*HuffmanTree; / 动态分配数组存储哈夫曼树 typedef char *HuffmanCode;/ 动态分配数组存储哈夫曼编码表void Select(HuffmanTree HT,int n) int i,j;for(i = 1;i <= n;i+)if(!HT

2、i.parent)s1= i;break;for(j = i+1;j <= n;j+)if(!HTj.parent)s2= j;break;for(i = 1;i <= n;i+) if(HTs1.weight>HTi.weight)&&(!HTi.parent)&&(s2!=i)s1=i;for(j = 1;j <= n;j+) if(HTs2.weight>HTj.weight)&&(!HTj.parent)&&(s1!=j)s2=j;*w,0号n)/算法 6.13/w存放n个字符的权值（均0）,

3、构造哈夫曼树/并求出 n 个字符的哈夫曼编码HCinti, j;char*cd;intp;intcdlen;void HuffmanCoding(HuffmanTree &HT, HuffmanCode HC, intintHT，if (n<=1) return;m = 2 * n - 1;HT = (HuffmanTree)malloc(m+1) * sizeof(HTNode); / 单元未用for (i=1; i<=n; i+) / 初始化 HTi.weight=wi-1; HTi.parent=0;HTi.lchild=0;HTi.rchild=0;for (i=n

4、+1; i<=m; i+) / 初始化HTi.weight=0;HTi.parent=0;HTi.lchild=0;HTi.rchild=0;puts("n 哈夫曼树的构造过程如下所示： "); printf("HT 初态 :n结点 weight parent lchild rchild"); for (i=1; i<=m; i+)printf("n%4d%8d%8d%8d%8d",i,HTi.weight,HTi.parent,HTi.lchild, HTi.rchild);printf(" 按任意键，继续 .

5、");getchar();for (i=n+1; i<=m; i+) / 建哈夫曼树/ 在 HT1.i-1 中选择 parent 为 0 且 weight 最小的两个结点，/ 其序号分别为 s1 和 s2。Select(HT, i-1);HTs1.parent = i; HTs2.parent = i;HTi.lchild = s1; HTi.rchild = s2;HTi.weight = HTs1.weight printf("nselect: s1=%d printf(" 结点 weight for (j=1; j<=i; j+)+ HTs2.w

6、eight; s2=%dn", s1, s2); parent lchild rchild");HTj.parent,HTj.lchild,按任意键，继续 .");HTj.rchild);printf("n%4d%8d%8d%8d%8d",j,HTj.weight,printf(" getchar();/ 无栈非递归遍历哈夫曼树，求哈夫曼编码cd = (char *)malloc(n*sizeof(char); / 分配求编码的工作空间 p = m; cdlen = 0;for (i=1; i<=m; +i) / 遍历哈夫曼树时

7、用作结点状态标志 HTi.weight = 0;while (p) if (HTp.weight=0) / 向 左HTp.weight = 1;if (HTp.lchild != 0) p = HTp.lchild; cdc dlen+ ='0' else if (HTp.rchild = 0) / 登记叶子 结点的字符的编码HCp(char *)malloc(cdlen+1)sizeof(char);cdcdle n ='0'strcpy(HCp, cd);/复制编码(串) else if (HTp.weight=1) / 向右HTp.weight = 2;i

8、f (HTp.rchild !=0) p = HTp.rchild;cdcdlen+ ='1' else / HTp.weight=2，退回退到父结点，编码长度减1HTp.weight = 0; p = HTp.pare nt; -cdle n;/Huffma nCodi ngintmai n()HuffmanTreeHT;HuffmanCode *HC;int *w,n,i;puts("输入结点数:");sca nf("%d",&n); getchar();HC = (HuffmanCode *)malloc(n*sizeof(HuffmanCode);w = (i nt*)malloc( n*sizeof(i nt);printf("输入c个结点的权值n",n);for(i = 0;i< n;i+)sca nf("%d",&wi);getchar();Huf