我按照书上的思路写的哈夫曼树,不知道错在哪儿了,求大神支招
#include<stdlib.h>#include<stdio.h>
#include<string.h>
#define Maxsize 100
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode,*HuffmanTree;
typedef char * *HuffmanCode;
void Select(HuffmanTree HT,int n,int &s1,int &s2) //选出权值最小的的两个结点
{
int i;
s1=s2=0;
for(i=1;i<=n;i++){
if(HT.weight<HT.weight && HT.parent==0&&s2!=0){
if(HT.weight<HT.weight){
s2=s1;
s1=i;
}
else s2=i;
}
if((s1==0||s2==0)&&HT.parent==0){
if(s1==0)
s1=i;
else if(s2==0){
if(HT.weight<HT.weight){
s2=s1;
s1=i;
}
else s2=i;
}
}
}
}
voidHuffmanCoding(HuffmanTree &Ht,HuffmanCode &HC,int *w,int n){
if(n<=1)
return ;
int m=2*n-1;
HuffmanTree HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));
HuffmanTree p;
int i;
for(p=HT,i=1;i<=n;++i,++p,++w){//初始化n个结点
//*p={*w,0,0,0,0};
p->weight=*w;
p->lchild=0;
p->parent=0;
p->rchild=0;
}
for(;i<=m;i++,++p){
// *p={0,0,0,0};
p->weight=0;
p->lchild=0;
p->parent=0;
p->rchild=0;
}
for(i=n+1;i<=m;++i){//// 建哈夫曼树
int s1,s2;
Select(HT,i-1,s1,s2);
HT.parent=i;
HT.parent=i;
HT.weight=HT.weight+HT.weight;
}
HC=(HuffmanCode)malloc((n+1)*sizeof(char*));
char* cd=(char*)malloc(n*sizeof(char));
cd='\0';
for(i=1;i<=n;++i){
int start=n-1;
for(int c=i,int f=HT.parent;f!=0;c=f,f=HT.parent)//逆序编码哈夫曼树
if(HT.lchild==c)////////////
cd[--start]='0';
else
cd[--start]='1';
HC=(char*)malloc((n-start)*sizeof(char));
strcpy(HC,&cd);
}
free(cd);
}
void OutputHuffmanCode(HuffmanTree HT,HuffmanCode HC,int n)
{
int i;
printf("\nnumber---weight---huffman code\n");
for(i=1;i<=n;i++)
printf("%d %d \n",HT.weight,HC);
}
int main(){
HuffmanTree HT;
int n,w;
printf("请输入你要创建的哈夫曼树的节点的个数:\n");
scanf("%d",&n);
HT=(HuffmanTree)malloc(sizeof(HTNode)*n);
char number;
for(int i=0;i<n;i++){
printf("请输入各节点的权值");
scanf("%d",&w);
}
HuffmanCode HC;
HuffmanCoding(HT,HC,w,n);
OutputHuffmanCode(HT,HC,n);
/*for(i=1;i<=n;i++){
printf("%s\n",HC);
}*/
return 0;
}
页:
[1]