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