#include <stdio.h>
#include<conio.h>
#include<string.h>
#define N 10 /*待编码字符的个数,即树中叶结点的最大个数*/
#define M 2*N-1 /*树中总的结点数目*/
typedef struct{
unsigned int weight;
unsigned int parent,lchild,rchild;
}HTNode; /*树中结点的结构*/
typedef struct {
char data; /*待编码的字符*/
int weight; /*字符的权值 */
char code[N]; /*字符的编码 */
} HTCode;
void Init(HTCode hc[],int *n){
/*初始化,读入待编码字符的个数n,从键盘输入n个字符和n个权值*/
int i;
printf("\n输入待编码字符的个数n:n=");
scanf("%d",&(*n));
printf("\n依次输入 %d个字符\n",*n);
for (i=1;i<=*n;i++)
{ hc[i].data=getch();
printf("%c",hc[i].data);}
printf("\n依次输入 %d 个字符的权值,以空格隔开\n",*n);
for (i=1;i<=*n;i++) scanf("%d",&(hc[i].weight));
}
void Select(HTNode ht[],int k,int *s1,int *s2){
/*ht[1…k]中选择parent为0,并且weight最小的两个结点
其序号由指针变量s1,s2指向*/
int i;
for (i=1;i<=k && ht[i].parent!=0 ;i++);
*s1=i;
for (i=1;i<=k;i++)
if (ht[i].parent==0 && ht[i].weight<ht[*s1].weight) *s1=i;
for (i=1; i<=k ; i++)
if (ht[i].parent==0 && i!=*s1) break;
*s2=i;
for (i=1;i<=k;i++)
if ( ht[i].parent==0 && i!=*s1 && ht[i].weight<ht[*s2].weight) *s2=i;
}
void HuffmanCoding(HTNode ht[],HTCode hc[],int n){
/*构造Huffman树ht,并求出n个字符的编码*/
char cd[N];
int i,j,m,c,f,s1,s2,start;
m=2*n-1;
for (i=1;i<=m;i++){
if (i<=n) ht[i].weight=hc[i].weight;
else ht[i].weight=0;
ht[i].parent=ht[i].lchild=ht[i].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;
}
cd[n-1]='\0';
for (i=1;i<=n;i++) {
start=n-1;
for (c=i,f=ht[i].parent;f;c=f,f=ht[f].parent)
if (ht[f].lchild==c) cd[--start]='0';
else cd[--start]='1';
strcpy(hc[i].code,&cd[start]);
}
}
void main(){
int i,m,n,w[N+1];
HTNode ht[M+1];
HTCode hc[N+1];
Init(hc,&n); /*初始化*/
HuffmanCoding(ht,hc,n);/*构造Huffman树,并形成字符的编码*/
/*输出字符的编码*/
for (i=1;i<=n;i++)printf("\n%c --- %s",hc[i].data,hc[i].code);
}
本站仅提供存储服务,所有内容均由用户发布,如发现有害或侵权内容,请
点击举报。