急求用“哈夫曼编码”解决问题

发布网友 发布时间：2022-04-23 04:24

我来回答

共1个回答

热心网友 时间：2022-04-26 13:08

//能成功不过可能不太符合你的要求

#include<stdio.h>
#include<conio.h>
#include<malloc.h>
#include<string.h>

#define ERROR 0;
#define OK 1;

typedef int Status;

typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef char * * HuffmanCode;

Status InitHuffmanTree(HuffmanTree &HT,int n){
int i,tem;
HT=(HTNode *)malloc((2*n-1)*sizeof(HTNode));
if(!HT){
return ERROR;
}

for(i=0;i<n;i++){
scanf("%d",&tem);
HT[i].weight=tem;
HT[i].parent=0;
HT[i].lchild=0;
HT[i].rchild=0;
}

for(;i<2*n-1;i++){
HT[i].parent=-1;
}

return OK;
}

void Select(HuffmanTree &HT,int n,int &fi,int &si){
int i=0,tem;
if(n>=2){
while((HT+i)->parent){
i++;
}
fi=i;

i++;
while((HT+i)->parent){
i++;
}
si=i;

if((HT+fi)->weight>(HT+si)->weight){
tem=fi;
fi=si;
si=tem;
}

for(i++;i<n;i++){
if((HT+i)->parent==0){
if((HT+i)->weight<(HT+fi)->weight){
si=fi;
fi=i;

}
else{
if((HT+i)->weight<(HT+si)->weight){
si=i;
}
}
}//printf("%d %d\n",fi,si);
}
}

}

int HuffmanTreeAllReady(HuffmanTree HT,int m){
int sum=0,i;
for(i=0;i<m;i++){
if((HT+i)->parent==0){
sum++;
}
if(sum>1){
return 0;
}

}
return 1;
}

void CreateHuffmanTree(HuffmanTree &HT,int n){
int s1,s2;
while(!HuffmanTreeAllReady(HT,n)){
Select(HT,n,s1,s2);

HT[n].parent=0;
HT[n].lchild=s1;
HT[n].rchild=s2;
HT[n].weight=HT[s1].weight+HT[s2].weight;
HT[s1].parent=n;
HT[s2].parent=n;
n++;

}

}

void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int n){
char * str;
int len=0,tem,i,j;
unsigned int p;
str=(char *)malloc(n*sizeof(char));

for(i=0;i<n;i++){
p=i;
len=0;
while(tem=HT[p].parent){

if(HT[tem].lchild==p){
str[len]='0';
}
else{
str[len]='1';
}
len++;
p=tem;
}

HC[i]=(char *)malloc((len+1)*sizeof(char));

if(HC[i]){
for(j=0;j<len;j++){
HC[i][j]=str[len-1-j];
}
HC[i][len]='\0';
str[len]='\0';
}
//printf("%d,%d\n",HC[i][0],len);
}
}

int main(){
HuffmanTree HT;
HuffmanCode HC;
int n,i,j,a,b;
HC=(char * *)malloc((n)*sizeof(char *));
scanf("%d",&n);
InitHuffmanTree(HT,n);

/*
for(i=0;i<2*n-1;i++){
printf("%d ",HT[i].parent);
}
printf("\n");
*/
Select(HT,i,a,b);
//printf("a=%d %d, b=%d %d",a,HT[a].weight,b,HT[b].weight);

CreateHuffmanTree(HT,n);

/*
for(i=0;i<2*n-1;i++){
printf("w=%d p=%d l=%d r=%d\n",HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}

printf("\n\n\n");
*/
HuffmanCoding(HT,HC,n);
for(i=0;i<n;i++){
printf("%s\n",HC[i]);
}

return 0;
}