代码如下:
#include <stdio.h>
#include <limits.h>
#define MAXLEN 100
typedef struct Huffman{
char val;
int parents;
int lchild,rchild;
int weight;
} Huffman;
int n;//the input number
Huffman HuffmanList[MAXLEN];
void BuildHuffman(Huffman HuffmanList[]){
for(int i=0;i<n-1;i++){
int MAXL,MAXR;
int LOCAL_L,LOCAL_R;
MAXL=MAXR=INT_MAX;
LOCAL_L=LOCAL_R=0;
for(int j=0;j<n+i;j++){
if(HuffmanList[j].weight<MAXL && HuffmanList[j].parents==-1){
MAXL=HuffmanList[j].weight;
LOCAL_L=j;
}
}
for(int j=0;j<n+i;j++){
if(HuffmanList[j].weight<MAXR && HuffmanList[j].parents==-1 && j!=LOCAL_L){
MAXR=HuffmanList[j].weight;
LOCAL_R=j;
}
}
HuffmanList[n+i].lchild=LOCAL_L;
HuffmanList[n+i].rchild=LOCAL_R;
HuffmanList[n+i].weight=HuffmanList[LOCAL_L].weight+HuffmanList[LOCAL_R].weight;
HuffmanList[LOCAL_L].parents=n+i;
HuffmanList[LOCAL_R].parents=n+i;
}
}
void CodeHuffman(Huffman HuffmanNode,char n){
if(HuffmanNode.val=='\0'){
printf("%c",n);
CodeHuffman(HuffmanList[HuffmanNode.lchild],'0');
printf("%c",n);
CodeHuffman(HuffmanList[HuffmanNode.rchild],'1');
}else{
printf("%c",n);
printf(" val is %c\n",HuffmanNode.val);
}
return;
}
int main(){
printf("Please input n\n");
scanf("%d",&n);
for(int i=0;i<2*n-1;i++){
HuffmanList[i].val='\0';
HuffmanList[i].parents=-1;
HuffmanList[i].lchild=-1;
HuffmanList[i].rchild=-1;
HuffmanList[i].weight=-1;
}
printf("Please input val:\n");
for(int i=0;i<n;i++){
scanf(" %c",&HuffmanList[i].val);
}
printf("Please input weight:\n");
for(int i=0;i<n;i++){
scanf("%d",&HuffmanList[i].weight);
}
BuildHuffman(HuffmanList);
CodeHuffman(HuffmanList[2*n-2],'\0');
/*
for(int i=0;i<2*n-1;i++){
printf("%c:%d:%d:%d:%d\n",HuffmanList[i].val,HuffmanList[i].lchild,HuffmanList[i].rchild,HuffmanList[i].parents,HuffmanList[i].weight);
}
*/
}
在输入权重同时包括 1,2 时,权值为 2 的项哈夫曼编码会有问题。
比如 输入 权值为 1,2,3,4 时,哈夫曼编码错误。
但是输入权值为 2,3,4,5 时,哈夫曼编码又正确。
求原因.......
1
ech0x OP 求解为什么.......
|