#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define OK 1
#define ERROR 0
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,* HuffmanTree; //动态分配数组存储哈夫曼树
typedef char * *HuffmanCode;//动态分配数组存储哈夫曼编码表
void SelectMin(HuffmanTree HT,int nNode,int &s1,int &s2){
int i,j;
for(i=1;i<=nNode;i++)
if(!HT[i].parent){
s1=i;
break;
}
for(j=i+1;j<=nNode;j++)
if(!HT[j].parent){
s2=j;
break;
}
for(i=1;i<=nNode;i++)
if((HT[i].weight<HT[s1].weight)&&(!HT[i].parent)&&s2!=i)
s1=i;
for(i=1;j<=nNode;j++)
if((HT[j].weight<HT[s2].weight)&&(!HT[j].parent)&&s1!=j)
s2=j;
if(HT[s1].weight>HT[s2].weight){
int temp=s1;
s1=s2;
s2=temp;
}
}
void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int nNode){
int i,s1,s2,start,c,f;
char *cd;
if(nNode<=1)
return;
int m=2*nNode-1;
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
for(i=1;i<=nNode;i++)
{
HT[i].parent=0;
HT[i].weight=w[i-1];
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=nNode+1;i<=m;i++)
{
HT[i].parent=0;
HT[i].weight=0;
HT[i].lchild=0;
HT[i].rchild=0;
}
for(i=nNode+1;i<=m;i++){//建立哈夫曼树
SelectMin(HT,nNode,s1,s2);
HT[s1].parent=i;
HT[s2].parent=i;
HT[i].lchild=s1;
HT[i].rchild=s2;
HT[i].weight=HT[s1].weight+HT[s2].weight;
}
//- - - -从叶子到根逆向求每个字符的哈夫曼编码- - - -//
HC=(HuffmanCode)malloc((nNode+1)*sizeof(char *));
cd=(char *)malloc(nNode*sizeof(char));
cd[nNode-1]='0';
for(i=1;i<=nNode;i++){
start=nNode-1;
for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent)
if(HT[f].lchild==c)
cd[--start]='0';
else
cd[--start]='1';
HC[i]=(char *)malloc((nNode-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
}
free(cd);
}//HuffmanCoding
int main(){
HuffmanTree HT;
HuffmanCode HC;
int i,nNode,*w;
char Code[20]={0};
printf("请输入结点个数:");
scanf("%d",&nNode);
HC=(HuffmanCode)malloc(nNode*sizeof(HuffmanCode));
w=(int *)malloc(nNode*sizeof(int));
printf("请输入各结点的权值\n");
for(i=0;i<nNode;i++)
scanf("%d",&w[i]);
HuffmanCoding(HT,HC,w,nNode);
printf("各点的哈夫曼编码为:\n");
for(i=0;i<=nNode;i++){
printf("%3d:%s\n",i,HC[i]);
}
return OK;
}
目前暂无任何回答
- 0 回答
- 1 关注
- 1222 浏览
添加回答
举报
0/150
提交
取消