p=creatstree(n);//调用建立哈夫曼树函数赋返回值给p
getstree(p,n); //调用编码函数读入建立的哈夫曼树p进行编码
return 0;
}
测试数据：
输入字符串“this*program*is*my*favourite”，完成这28个字符的编码和译码。
实验结果
1、演示程序运行结果。
2、说明调试过程中出现的现象
学生实验评价依据：
优：实验认真、刻苦，有钻研精神，不无故缺席。
良：能认真对待实验，不无故缺席。
中：基本能认真对待实验，不无故缺席。
hcnodetype cd[maxnodenumber]; //定义存储哈夫曼编码的数组
for(i=0;i<n;i++) //循环控制对每一个节点进行编码
{
c=i; //为编码各节点初始化c和j
j=maxbit;
do
{
j--; //j指向bit中存放编码为的正确位置
p=ht[c].parent; //p指向c的双亲节点
#define maxbit 10 //定义哈弗曼编码最大长度
typedef struct{ //定义新数据类型即节点结构
int weight; //权重域
int parent,lchild,rchild; //指针域
}htnode; //节点类型标识符//
typedef htnode * huffmanstree; //定义哈弗曼数类型
差：对待实验不够认真，有少量迟到、早退或无故缺席现象。
不及格：对待实验马虎、敷衍，经常迟到、早退或无故缺席。
#include <stdio.h>
#include <malloc.h>
#define maxvalue 10000 //定义最大权值常量
#define maxnodenumber 100 //定义节点最大数
if(ht[j].parent==-1&&ht[j].weight<m2)
{
m2=ht[j].weight;k2=j;
}
ht[k1].parent=n+i; //修改最小权值节点的双亲为刚生成的新节点
ht[k2].parent=n+i; //修改次小权值节点的双亲为刚生成的新节点
ht[n+i].weight=ht[k1].weight+ht[k2].weight; //将新生成的权重值填入新的根节点
for(i=0;i<n;i++) //权重赋初值，由用户输入
{
scanf("%d",&ht[i].weight);
}
for(i=0;i<n-1;i++) //生成新节点构造哈夫曼树
{
m1=maxvalue; //预置最小权值变量为最大权值
m2=maxvalue; //预置次小权值变量为最大权值
k1=0; //预置最小权值节点位置为下标为0处
}
}
int main() //主函数
{
int n;
printf("请输入节点数:"); //用户输入节点数
scanf("%d",&n);
htnode * p; // huffmanstree p //定义哈夫曼树类型p
p=(htnode * )malloc(sizeof(htnode *));//p=(huffmanstree)malloc(sizeof(huffmanstree))//分配内存空间
实验6：哈夫曼树及哈夫曼编码的算法实现
实验所需
学时数
2学时
实验目的
1)掌握哈夫曼树的基本概念及其存储结构；
2)掌握哈夫曼树的建立算法；
3)掌握哈夫曼树的应用（哈夫曼编码和译码）。
实验内容
对输入的一串电文字符实现哈夫曼编码，再对哈夫曼编码生成的代码串进行译码，输出电文字符串。
实验所需
器材
计算机及VC++ 6.0软件
cd[i].start=j; //编码完成,记下编码开始位置
}
for(i=0;i<n;i++) //循环打印各节点哈夫曼编码
{
for(j=cd[i].start;j<maxbit;j++)//循环逐一输出
printf("%d",cd[i].bit[j]);
printf("\n"); //每输出一编码后换行
if(ht[p].lchild==c) //如果c是p的左孩子
cd[i].bit[j]=0; //编码为赋值0
else //否则即c是p的右孩子
cd[i].bit[j]=1; //编码赋值1
c=p;//更新当前指针，为下一节点编码做准备
}while(ht[p].parent!=-1); //判断是否编码结束即循环至最终根节点
k2=0; //预置次小权值节点位置为下标为0处
for(j=0;j<n+i;jparent==-1&&ht[j].weight<m1)
{
m2=m1;
k2=k1;
m1=ht[j].weight;
k1=j;
}
else //当小于当前次小m2则更新m2及其位置
ht[n+i].lchild=k1; //新生节点左孩子指向k1
ht[n+i].rchild=k2; //新生节点右孩子指向k2
}
return ht; //返回哈夫曼树指针
}
void getstree(htnode * ht,int n) //哈夫曼编码算法及打印函数的实现
{
int i,j,c,p; //局部变量的定义
内容要求：
1、初始化(Init)：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立哈夫曼树
2、建立编码表(CreateTable)：利用已经建好的哈夫曼树进行编码，并将每个字符的编码输出。
3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。
4、译码(Decoding)：利用已经建好的哈夫曼树对编码后的字符串进行译码，并输出译码结果。
htnode ht[maxnodenumber]; //定义三叉链表存储数组
typedef struct {//定义保存一个叶子节点哈弗曼编码的结构
int bit[maxbit]; //定义一维数组为编码域
int start; //定义位置域
}hcnodetype; //定义编码类型
htnode * creatstree(int n) //huffmanstree creatstree(int n) //建立哈夫曼树算法实现函数
{
int i,j,m1,m2,k1,k2; //局部变量
for(i=0;i<2*n-1;i++) //初始化各节点
{
ht[i].weight=0; //权重初始化为0
ht[i].parent=-1; //根节点和给左右孩子初始化为-1
ht[i].lchild=-1;
ht[i].rchild=-1;
}