哈夫曼编码代码
给定n个权值作为n个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树。由此得到的二进制前缀编码称为哈夫曼编码。
例如权w={5,29,7,8,14,23,3,11},8个结点,构造的哈夫曼树如下图所示:
算法实现如下:
typedef struct {
unsigned int weight;
unsigned int parent;
unsigned int lchild;
unsigned int rchild;
}Node, *HuffmanTree;
typedef char **HuffmanCode;
//在huffmanTree[1...n-1]中选择parent为0,且weight最小的两个结点,分别是s1,s2
void Select(HuffmanTree& huffmanTree, int n,int &s1,int &s2)
{
int min = 1;
for(int i =1;i<=n;i++){
if(huffmanTree[i].parent==0){
min = i;
break;
}
}
for(int i =1;i<=n;i++){
if(huffmanTree[i].parent==0){
if(huffmanTree[i].weight<huffmanTree[min].weight){
min = i;
}
}
}
s1 = min;
for(int i =1;i<=n;i++){
if(huffmanTree[i].parent==0 && i!=s1){
min = i;
break;
}
}
for(int i=1;i<=n;i++){
if(huffmanTree[i].parent==0 && i!=s1){
if(huffmanTree[i].weight<huffmanTree[min].weight){
min = i;
}
}
}
s2 = min;
}
void HuffmanCoding(HuffmanTree &huffmanTree, HuffmanCode &huffmanCode, int *w, int n)
{
if(n <= 1) return;
int m = 2*n-1;//一棵有n个叶子结点的哈夫曼树共有2n-1个结点
int s1,s2;
huffmanTree = (HuffmanTree)malloc((m+1)*sizeof(Node));
HuffmanTree p = huffmanTree+1;
//初始化叶结点
for(int i=1;i<=n;i++,w++,p++){
*p = {*w,0,0,0};
}
//初始化中间结点
for(int i=n+1;i<=m;i++,p++){
*p={0,0,0,0};
}
//构建哈夫曼树
for(int i=n+1;i<=m;i++){
Select(huffmanTree,i-1,s1,s2);
huffmanTree[s1].parent = i;
huffmanTree[s2].parent = i;
huffmanTree[i].lchild = s1;
huffmanTree[i].rchild = s2;
huffmanTree[i].weight = huffmanTree[s1].weight+huffmanTree[s2].weight;
}
//从叶子到根逆向求每个字符的哈夫曼编码
unsigned int c,f;
int start;
huffmanCode = (HuffmanCode)malloc((n+1)*sizeof(char*));
char *cd = (char *)malloc(n*sizeof(char));
cd[n-1]= '\0';
for(int i=1; i<=n; i++){
start = n-1;
for(c=i, f=huffmanTree[i].parent; f!=0; c=f,f=huffmanTree[f].parent){
if(huffmanTree[f].lchild == c){
cd[--start] = '0';
}
else{
cd[--start] = '1';
}
}
huffmanCode[i] = (char *)malloc((n-start)*sizeof(char));
strcpy(huffmanCode[i],&cd[start]);
}
free(cd);
}