|
#2
栀子与你2020-06-04 18:12
|
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
typedef struct//树结点定义
{
int weight;
int parent;
int lchild;
int rchild;
}HTNode,*HuffmanTree;
//哈弗曼编码，char型二级指针
typedef char **HuffmanCode;
static char N[100];//用于保存正文
typedef struct//封装最小权结点和次小权结点
{
int s1;
int s2;
}MinCode;
int d[100],count1=0,count2=0,sum=0;//统计编码长度
double avg=0;//平均编码长度
//构造哈夫曼树HT，编码存放在HC中,w为权值,n为结点个数
HuffmanCode HuffmanCoding(HuffmanTree HT,HuffmanCode HC,int *w,int n)
{
int i,s1=0,s2=0;
HuffmanTree p;
char *cd;
int f,c,start,m;
MinCode min;
m=2*n-1;//哈弗曼编码需要开辟的结点大小为2n-1
HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//开辟哈夫曼树结点空间 m+1 。为了对应关系，我们第0个空间不用。
//初始化n个叶子结点,w[0] = 0,main函数已赋值
for(p=HT,i=0;i<=n;i++,p++,w++)
{
p->weight=*w;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
//将n-1个非叶子结点的初始化
for(;i<=m;i++,p++)
{
p->weight=0;
p->parent=0;
p->lchild=0;
p->rchild=0;
}
//构造哈夫曼树
for(i=n+1;i<=m;i++)
{
min=Select(HT,i-1);//找出最小和次小的两个结点
s1=min.s1 ; //最小结点下标
s2=min.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;//赋权和
}
//打印哈弗曼树
printf("哈夫曼树如下:\n");
printf("Number\tweight\tparent\tlchild\trchild\n");
for(i=1;i<=m;i++)
{
printf("%d\t%d\t%d\t%d\t%d\t\n",i,HT[i].weight,HT[i].parent,HT[i].lchild,HT[i].rchild);
}
//从叶子结点到根节点求每个字符的哈弗曼编码
HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
cd=(char *)malloc(n*sizeof(char *));//为哈弗曼编码动态分配空间
cd[n-1]='\0';//如：3个结点编码最长为2。cd[3-1] = '\0';
for(i=1;i<=n;i++)//求叶子结点的哈弗曼编码
{
start=n-1;//从最下面的节点开始，start为开始节点···
//从最下面的1号节点开始往顶部编码(逆序存放)，然后编码2号节点，3号......
for(c=i,f=HT[i].parent; f!=0; c=f,f=HT[f].parent)
{
if(HT[f].lchild==c)
{
cd[--start]='0'; //定义左子树为0，右子树为1
count1++;
}
else
{
cd[--start]='1';
count2++;
}
}
HC[i]=(char *)malloc((n-start)*sizeof(char *));//为第i个字符分配编码空间
strcpy(HC[i],&cd[start]); //将当前求出结点的哈弗曼编码复制到HC
}
free(cd);
return HC;
}
MinCode Select(HuffmanTree HT,int n)
{
int min,secmin;
int temp = 0;
int i,s1,s2,tempi = 0;
MinCode code;
s1=1;
s2=1;
min = 10000;//足够大
for(i=1;i<=n;i++) //找出权值weight最小的结点，下标保存在s1中
{
if(HT[i].weight<min && HT[i].parent==0)
{
min=HT[i].weight;
s1=i;
}
}
secmin = 10000;//足够大
for(i=1;i<=n;i++) //找出权值weight次小的结点，下标保存在s2中
{
if((HT[i].weight<secmin) && (i!=s1) && HT[i].parent==0)
{
secmin=HT[i].weight;
s2=i;
}
}
code.s1=s1; //放进封装中
code.s2=s2;
return code;
}
void main()
{
HuffmanTree HT=NULL;
HuffmanCode HC=NULL;
int *w=NULL;
int i,n;
char tran[100];
int len=strlen(N);
printf("输入节点:");
gets(N);
fflush(stdin);
n = strlen(N);
w=(int *)malloc((n+1)*sizeof(int *));//开辟n+1个长度的int指针空间
w[0]=0;
printf("输入节点的权值:\n");
//输入结点权值
for(i=1;i<=n;i++)
{
printf("w[%d]=",i);
scanf("%d",&w[i]);
}
fflush(stdin);
//构造哈夫曼树HT，编码存放在HC中,w为权值,n为结点个数
HC=HuffmanCoding(HT,HC,w,n);
//输出哈弗曼编码
printf("哈夫曼编码为:\n");
printf("Number\tWeight\tCode\n");
for(i=1;i<=n;i++)
{
printf("%c\t%d\t%s\n",N[i-1],w[i],HC[i]);
d[i]=strlen(HC[i]);
}
fflush(stdin);
sum=count1+count2;
//printf("节点长度为：%d",len);
//printf("\n编码总长度为：%d",sum);
for(i=1;i<=n;i++)
{
avg+=d[i]*w[i]*0.01;
}
printf("\n平均编码长度为：%f",avg);
return;
}
