(为什么无论输入什么数,打出来的哈夫曼数都是一样的,而且编码打不出来)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 8
//#define M 2*N-1
//哈夫曼树类型定义
typedef struct
{
unsigned int weight;
unsigned int parent, lchild, rchild;
}HTNode,*HuffmanTree;
typedef char **HuffmanCode;
HuffmanTree HT;
HuffmanCode HC;
char *cd;
//字符、权值、对应编码组成的结构体类型
struct s
{
char data;
int weight;
char code[N];
};
s S[N];
//此处函数定义请自行编写
void Init(s S[N],int *w)
{
int i;
printf("输入%d个字符,及他们的权值:\n",N);
for(i=1;i<=N;i++)
{
printf("请输入第%d个字符:",i);
scanf("%c",&S[i-1].data);
getchar();
printf("请输入该字符的权值:");
scanf("%d",&w[i-1]);
getchar();
}
}
void Select(HuffmanTree HT,int n,int &s1,int &s2)
{
int minn=99999998,maxx=99999999,i=1;
s1=s2=0;
for( i=1; i<=n;i++)
{
if(HT[i].parent==0)
{
if(HT[i].weight<minn)
{
minn=HT[i].weight;s1=i;
}
}
}
int t=HT[s1].weight;
HT[s1].weight=maxx;
minn=99999998;
for( i=1; i<=n; i++)
{
if(HT[i].parent==0)
{
if(HT[i].weight<minn)
{
minn=HT[i].weight;
s2=i;
}
}
}
HT[s1].weight=t;
}
void Huffmancoding(HuffmanTree &HT,HuffmanCode &HC,int n,int *w)
{
int i,c,f,s1=0,s2=0,start,m=2*n-1;
HuffmanTree p;
HT=(HuffmanTree)malloc((m+1) * sizeof(HTNode));
if(n<=1)return;
/* for(i=1;i<=n;i++)
{undefined
HT[i].weight=w[i];
HT[i].parent=HT[i].rchild=HT[i].lchild=0;
}
for(;i<=m;i++)
{undefined
HT[i].weight=HT[i].parent=HT[i].rchild=HT[i].lchild=0;
}*/
for (p=HT+1, i=1; i<=n; ++i, ++p){
p->parent=0;
p->lchild=0;
p->rchild=0;
p->weight=w[i-1];
} /**p={ * w, 0, 0, 0};*/ //用给定的n个
//权值 ,构造n棵只有一个根结点的二叉树
for (;i<=m;i++,++p){
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
for(i=n+1;i<=m;i++);
{
Select(HT,i-1,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((n+1)*sizeof(char *));//分配n个字符编码的头指针向量
cd=(char*)malloc(n*sizeof(char));//分配求编码的工作空间,用cd指向该空间
cd[n-1]='\0';
for (i=1;i<=n;i++)
{
start=n-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((n-start)*sizeof(char));
strcpy(HC[i],&cd[start]);
// strcpy(S[i].code,&HC[i]);
}
/* for( i=1;i<=N;i++)
{
S[i].weight=
S[i].data=
// strcpy(S[i].code,HC[i]);
}
*/
free(cd);
}
int main()
{ //哈夫曼树的建立和编码的生成
//打印输出哈夫曼树数据
//用户输入任意一个由N个字符组成的字符串,输出该字符串对应的哈夫曼编码字符串
//用户输入哈夫曼编码(由01组成),将进行解码,输出对应的字符串
int a[100];
int k,*w,n,m=2*N-1;
w=a;
// HTNode HT[M-1];
// HTCode HC[N+1];
Init(S,w);
Huffmancoding(HT,HC,8,w);
printf("\n哈夫曼树如下所示:\n");
for (int v=1;v<=m;v++){
printf("%d\t",HT[v].weight);
printf("%d\t",HT[v].parent);
printf("%d\t",HT[v].lchild);
printf("%d\t\n",HT[v].rchild);
}
printf("\n%d个字符的字符、权值以及哈夫曼编码如下:\n",N);
for(k=1;k<=n;k++);
{
printf("%-3c%-3d%s\n",S[k].data,S[k].weight,HC[k]);
//puts(S[k].code);
//printf("%c\t",HC[k]);
}
return 0;
}