数据结构实验二哈夫曼树及哈夫曼编码译码的实现

福建农林大学金山学院实验报告系（教研室）：专业：计算机科学与技术年级：08实验课程：姓名：学号：实验室号：_______计算机号：实验时间：指导教师签字：成绩：实验二：哈夫曼树及哈夫曼编码译码的实现（验证性、4学时）一、实验目的和要求构建哈夫曼树及哈夫曼编码，输出哈夫曼树及哈夫曼编码，完成编码与译码的算法。（1）掌握树的有关操作算法（2）熟悉树的基本存储方法（3）学习利用树求解实际问题二、实验内容和原理定义哈夫曼树的存储结构；输入要编码的字符权重，根据权重建立哈夫曼树，并进行编码，最后输出哈夫曼编码。三、实验环境硬件：（1）学生用微机（2）多媒体教室或远程教学（3）局域网环境软件：（1）WindowsXP中文操作系统（2）TurboC3.0四、算法描述及实验步骤1．算法描述(1).建立哈夫曼树的算法定义各节点类型其中应包含两类数据一是权重域weight；一是指针域而指针域中应该包括指向左右孩子和指向双亲的指针这里分别用lchild、rdhild和parent来表示因此可用静态三叉链表来实现，在实际构造中由于是叶子节点来构造新的根节点其构造过程中仅与叶子节点的权重有关而与其数据域无关所以构造过程中不用考虑其数值域，并且在链表中从叶子开始存放，让后不断的将两颗最小权值的子树合并为一颗权值为其和的较大的子树，逐步生成各自内部节点直到树根。(2).哈夫曼编码的算法将建立的哈夫曼树从每个叶子节点开始沿着双亲域回到根节点，梅走一步进行编码得到一位编码值；由于每个叶子节点的哈夫曼编码是从根节点到相应的叶子的路径的各个分支的代码组成的0和1序列，所以先得到了低位编码后得到高位编码因此可用一维数组从后向前来存放各位编码值，并用start来记录编码的起始位置。2．算法流程图构建哈夫曼树算法流程In-I;In;I2*n-1;inti,j,m1,m2,k1,k2;i=0;ht[i].weight=0;ht[i].parent=-1;ht[i].lchild=-1;ht[i].rchild=-1;i++;i=0;Scanf(“%d”,&ht[i].weight)i++;i=0;M1=maxvalue;M2=maxvalue;K1=0;k2=0J=0;Jn+i;Ht[j].parent==-1&&ht[j].weightm2YNM2=m1;k2=k1;M1=ht[j].weight;K1=j;Ht[j].parent==-1&&ht[j].weightm2YNM2=ht[j].weight;K2=j;J++Ht[k1].parent=n+I;ht[k2].parent=n+I;ht[n+i].weight=ht[k1].weight+ht[k2].weightHt[n+i].lchild=k1;ht[n+i].rchild=k2;I++;Returnht;哈夫曼编码算法流程In;In;Ht[p].parent=-1;Inti，j，c，p；Hcodetypecd[n];I=0;C=I;j=maxbit;j--;p=ht[p].lchild;YHt[p].lchild==cNCd[i].bit[j]=0;Cd[i].bit[j]=1;c=p;I++;I=0;J=cd[i].start;Jmaxbit;Printf(“%d”,cd[i].bit[j]);printf(“\n”);I++;3．代码仅作参考--redbatzero#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;}五、调试过程出现该错误是因为type识别不了，即定义哈夫曼树时确切的说是type并不能定义htnode*标识符为huffmanstree：typehtnode*huffmanstree这个小错误可以通过连个方法来修改一是将type改为typedef，当然直接删除该定义完全不会影响程序的执行，但在定义建立哈夫曼树函数时返回值应直接用htnode*；该错原因是参数未能成功传递，其中的ht[p]系统当做是未定义的类型可知，在getstree（htnodeht，intn）时正确的应当是传递哈夫曼树的头指针即数组首地址ht因此改为getstree（htnode*ht，intn）六、实验结果通过改正后成功编译连接，进行数据测试{5,20,12,7,47，9}当然编码因为定义时大小的左右排序是不同的所以编码也不唯一，但在这里是以左小右大来分布的，所以编码结果符合预期的。所构造哈夫曼树如图所示七、总结该实验不仅让我加深了对哈夫曼树的理解，更是让我惊叹该算法的强大，一个简单的数组类型数据加之简单的链表在实现该算法后让我理解了基础理论知识的重要性，倘若在不知道这个算法的情况下。我不知道自己得花多少的时间来实现编码，或许最终还不一定能够很好的实现编码，更别说优化了。尤其树的基本存储方法更加深了我对树的理解。4797125100011110200附录：