实验三HUFFUMA编码的构造.docVIP

实验三 Huffuma编码的构造 【实验】【实验】【实验目的要求】1．理解和掌握树型结构的特点和基本操作； 2．利用数组存储哈夫曼编码并定义所需的属性结构； 3．掌握哈夫曼树的结构特点和哈夫曼编码的构造算法及应用。 【实验类型】 验证性 【实验时数】 学时 【参考资料】 1．数据结构2．【实验内容】 哈夫曼树利用哈夫曼树的的构造算法进行哈夫曼编码的构造。 (1) 定义 (2) 仔细理解和分析哈夫曼编码构造算法，编写程序； (3) 调试并修改程序，得到正确的实验结果。 【实验】 typedef struct { char ch; 表示结点的字符值； int weight; 结点的权值 int lchild,rchild,parent; 结点左、右孩子和双亲结点在数组中的下标值 }HTNODE; HTNODE huftree[2n-1]； 定义了一维数组huftree，数组长度为2n-1。 定义一个数组cd，专门用于存放各个叶子结点代表的字符值和各个叶子结点字符对应的编码。因此，该数组元素应该包含两部分： typedef struct { char *code; 用于指向字符对应的编码字符串 char leaf; 叶子结点代表的字符值 }CODE; 所以，数组定义为：CODE cd[n]; 3、用一个整型数组w来存放按升序排列的叶子的权值。 int w[n]; 4、算法分析：(以{a,b,c,d,e}权值分别为1，2，3，4，5的字符为例) (1)用一维数组huftree来存储哈夫曼树(0号元素不用)，初始状态为： (2) 选取结点生成内部结点，一共要生成n-1个内点（用k来表示生成内点的个数）。 每次都要选取从未用过的当前权值最小的两个结点来生成新的结点，则在数组中就要选取parent为0，权值最小的两个结点生成内点，通过课堂讲解可以知道符合条件的两个结点的下标s1和s2与当前生成的内点个数k之间存在关系：s1=2k-1；s2=s1+1；由它们产生的内点的权值： sum=huftree[s1].weight+huftree[s2].weight; 然后，将生成的新内点按权值升序插入到数组huftree中，可以采取从后往前进行权值比较，直到找到合适的位置(j+1)将其插入，并且将产生的这个新内点与它的左右孩子结点(s1结点和s2结点)的关系进行体现： huftree[s1].parent=j+1; huftree[s2].parent=j+1; huftree[j+1].lchild=s1; huftree[j+1].rchild=s2; 依次类推，最终的huftee数组为： 至此，整棵产生的哈夫曼树已经全部完成，并存储在数组huftree中，产生的哈夫曼树为： 由树中叶子结点开始向上回溯，从叶到根。若当前结点是左孩子，则得‘0’，否则得‘1’，得到了反序的编码字符串存入到字符数组temp中，然后根据得到的编码串的实际长度来开辟空间，由数组cd中code指针域指向，再存放各个叶结点代表的字符值，得到相应的编码对照表：