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

数据结构实验二哈夫曼树及哈夫曼编码译码的实现福建农林大学金山学院实验报告系(教研室):专业:计算机科学与技术年级:08实验课程:姓名:学号:实验室号:_______计算机号:实验时间:指导教师签字:成绩:实验二:哈夫曼树及哈夫曼编码译码的实现(验证性、4学时)一、实验目的和要求构建哈夫曼树及哈夫曼编码,输出哈夫曼树及哈夫曼编码,完成编码与译码的算法。(1)掌握树的有关操作算法(2)熟悉树的基本存储方法(3)学习利用树求解实际问题二、实验内容和原理定义哈夫曼树的存储结构;输入要编码的字符权重,根据权重建立哈夫曼树,并进行编码,最后输出哈夫曼编码。三、实验环境硬件:(1)学生用微机(2)多媒体教室或远程教学(3)局域网环境软件:(1)WindowsXP中文操作系统(2)、算法描述及实验步骤1(算法描述(1).建立哈夫曼树的算法定义各节点类型其中应包含两类数据一是权重域weight;一是指针域而指针域中应该包括指向左右孩子和指向双亲的指针这里分别用lchild、rdhild和parent来表示因此可用静态三叉链表来实现,在实际构造中由于是叶子节点来构造新的根节点其构造过程中仅与叶子节点的权重有关而与其数据域无关所以构造过程中不用考虑其数值域,并且在链表中从叶子开始存放,让后不断的将两颗最小权值的子树合并为一颗权值为其和的较大的子树,逐步生成各自内部节点直到树根。(2).哈夫曼编码的算法将建立的哈夫曼树从每个叶子节点开始沿着双亲域回到根节点,梅走一步进行编码得到一位编码值;由于每个叶子节点的哈夫曼编码是从根节点到相应的叶子的路径的各个分支的代码组成的0和1序列,所以先得到了低位编码后得到高位编码因此可用一维数组从后向前来存放各位编码值,并用start来记录编码的起始位置。2(算法流程图构建哈夫曼树算法流程inti,j,m1,m2,k1,k2;i=0;I<2*n-1;ht[i].weight=0;ht[i].parent=-1;ht[i].lchild=-1;ht[i].rchild=-1;i++;i=0;I<n;Scanf(“%d”,&ht[i].weight)i++;i=0;I<n-I;M1=maxvalue;M2=maxvalue;K1=0;k2=0J=0;J<n+i;Ht[j].parent==-1&&ht[j].weight<m2YNM2=m1;k2=k1;Ht[j].parent==-1&&ht[j].weight<m2M1=ht[j].weight;YNK1=j;M2=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;哈夫曼编码算法流程Inti,j,c,p;Hcodetypecd[n];I=0;I<n;C=I;j=maxbit;j--;p=ht[p].lchild;YHt[p].lchild==cNCd[i].bit[j]=0;Cd[i].bit[j]=1;c=p;Ht[p].parent=-1;I++;I=0;I<n;J=cd[i].start;J<maxbit;Printf(“%d