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