二、实验内容
1.根据给出的字符以及这些字符的使用频率构建哈夫曼树。
2.根据哈夫曼树对字符进行哈夫曼编码，并保存这些编码。
三、实验原理、方法和手段
试构造出问题模型，并编程实现这一问题的求解。根据实验内容编程，上机调试、得出正确的运行程序；编译运行程序，观察运行情况和输出结果。
六、实验步骤
1. 建立哈夫曼树的存储结构和哈夫曼编码的存储结构。
2. 建立哈夫曼树的函数；
3. 哈夫曼编码的函数；
4．哈夫曼编码的解码函数
5. 设计测试用例进行测试。
七、实验报告
记录数据结构与算法设计的过程及实验步骤、上机过程中遇到的困难及解决办法、遗留的问题、托福考位意见和建议等。格式见实验报告模板。测试数据及测试结果请在上交的资料中写明。
#include #include
#define N 50#define M 2*N-1 const int
INF=1e9+7;typedef struct//哈夫曼树的存储结构
{
char data[6];
double weight;
int parent;
int lchild;
int rchild;
} HTNode;typedef struct//存放哈夫曼码存储结构
{
char cd[N];
int start;
} HCode;void CreateHT(HTNode ht[],int n0) //建立哈夫曼树的函数{
int i,k,lnode,rnode;
double min1,min2;
for (i=0;i<2*n0-1;i++)
ht[i].parent=ht[i].lchild=ht[i].rchild=-1;
for (i=n0;i<=2*n0-2;i++)
{
min1=min2=INF;//min1存最小的权值,min2存次小权值
lnode=rnode=-1;
for (k=0;kif (ht[k].parent==-1)
{
if(ht[k].weight{
min2=min1;//保证
min1<=min2
rnode=lnode;
min1=ht[k].weight;
lnode=k;
}
else if(ht[k].weight{
min2=ht[k].weight;
rnode=k;
}
}
ht[i].weight=ht[lnode].weight+ht[rnode].weight;
ht[i].lchild=lnode;
ht[i].rchild=rnode;
ht[lnode].parent=i;
ht[rnode].parent=i;
}
}
void CreateHCode(HTNode ht[],HCode hcd[],int n0) //构造哈夫曼树编码{
int i,f,c;
HCode hc;
for (i=0;i{
hc.start=n0;c=i;
f=ht[i].parent;
while (f!=-1)
{
if (ht[f].lchild==c)
hc.cd[hc.start--]='0';
else
hc.cd[hc.start--]='1';
c=f;
f=ht[f].parent;
}
hc.start++;
hcd[i]=hc;
}
}
void DispHCode(HTNode ht[],HCode hcd[],int n0) { int i,k,temp=0;
double sum=0;
int j;
printf(" 输出");
for(i=0;i<8;i++)
printf("%s",ht[i].data);
printf("的哈夫曼编码:\n");
for (i=0;i{
printf(" %s:\t\t",ht[i].data);
for (k=hcd[i].start;k<=n0;k++)
printf("%c",hcd[i].cd[k]);
printf("\n");
}
}
void Decode(HTNode ht[],char code[]) //解码{
printf("\n\n 对“%s”解码：\n",code);
int p=ht[0].parent;
int m;//根
while(p!=-1)//找到根
{
m=p;
p=ht[m].parent;
}
int t;
int a1=0,a2=0;
for(int i=0;i{
a1=a2;
t=m;
while(ht[t].lchild!=-1&&ht[t].rchild!=-1&&i{
if(code[i]== '0')
t=ht[t].lchild;
else if(code[i]== '1')
t=ht[t].rchild;
