huffman树及其编码
程序代码:
#include <stdio.h> #include <malloc.h> #include <string.h> typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode, *HuffmanTree; typedef char **HuffmanCode; //从ht[1,n]中找出没有父节点,权值最小的s1,s2 void select(HuffmanTree ht,int n,int *s1,int *s2){ int i; *s1 = *s2 = 0; for(i=1; i<=n; i++){ if(ht[i].parent==0){ if(*s1==0) *s1 = i; else if(*s2==0){ if(ht[*s1].weight>ht[i].weight){ *s2 = *s1; *s1 = i;} else *s2 = i; }else{ //s1,s2都有值 if(ht[i].weight<=ht[*s1].weight){ *s2 = *s1; *s1 = i; }else if(ht[i].weight>ht[*s1].weight&&ht[i].weight<ht[*s2].weight) *s2 = i; } } }//end for } /* 根据huffman树进行编码,从叶子节点开始 */ void codingFromLeaf(HuffmanTree tr,HuffmanCode *co,int n){ char *cd; int i,start; unsigned int c,f; *co = (HuffmanCode)malloc((n+1)*sizeof(char *)); cd = (char *)malloc(n*sizeof(char)); //临时空间,用来拼接编码 cd[n-1] = '\0'; for(i=1; i<=n; i++){ //求n个编码 start = n - 1; for(c=i,f=tr[i].parent; f!=0; c=f,f=tr[f].parent) if(tr[f].lchild==c) cd[--start] = '0'; else cd[--start] = '1'; (*co)[i] = (char *)malloc((n-start)*sizeof(char)); strcpy((*co)[i],&cd[start]); } free(cd); } /* 根据huffman树进行编码,从根节点开始 */ void codingFromRoot(HuffmanTree tr,HuffmanCode *co,int n){ int p,cdlen,i,m; char *cd; m = 2*n-1; p = m; cd = (char *)malloc((n-1)*sizeof(char)); cdlen = 0; *co = (HuffmanCode)malloc((n+1)*sizeof(char *)); for(i=0; i<=m; i++) tr[i].weight = 0; while(p){ if(tr[p].weight==0){ //向左 tr[p].weight = 1; if(tr[p].lchild!=0){ p = tr[p].lchild; cd[cdlen++] = '0'; }else if(tr[p].rchild==0){ (*co)[p] = (char *)malloc((cdlen+1)*sizeof(char)); cd[cdlen] = '\0'; strcpy((*co)[p],cd); } }else if(tr[p].weight==1){ //向右 tr[p].weight = 2; if(tr[p].rchild!=0){ p = tr[p].rchild; cd[cdlen++] = '1'; } }else{ //tr[p].weight==2 tr[p].weight = 0; p = tr[p].parent; cdlen--; } }//end while } /* w存放n个字符的权值,构造huffman树ht,并求出n个字符的huffman编码存放在hc */ void huffmanCoding(HuffmanTree *ht, HuffmanCode *hc, int *w, int n){ int m; //节点数 int i,s1,s2; HuffmanTree p; if(n<=1) return; m = 2*n-1; *ht = (HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(i=1,p=*ht+1; i<=n; i++,p++,w++){//初始化n个叶子节点 (*p).weight = *w; (*p).lchild = (*p).rchild = (*p).parent = 0; } for(; i<=m; i++,p++)//初始化其余n-1个节点 (*p).weight = (*p).lchild = (*p).rchild = (*p).parent = 0; for(i=n+1; i<=m; i++){ //建立huffman树 select(*ht,i-1,&s1,&s2); (*ht)[s1].parent = (*ht)[s2].parent = i; (*ht)[i].lchild = s1; (*ht)[i].rchild = s2; (*ht)[i].weight = (*ht)[s1].weight + (*ht)[s2].weight; } codingFromLeaf(*ht,hc,n); //codingFromRoot(*ht,hc,n); } void main(){ int weight[4]= {7,5,2,4},n,i; HuffmanTree tree; HuffmanCode code; n = 4; huffmanCoding(&tree,&code,weight,n); for(i=1; i<=n; i++) printf("%s\n",*(code+i)); }
严蔚敏版《数据结构》huffman树一节的C程序。已测。
[ 本帖最后由 三月的雪 于 2011-5-17 18:08 编辑 ]