项目实训2016--石一龙介绍.doc

《算法分析与设计》 ——哈夫曼编码的设计与实现 姓名： 栾小飞 所属班级： 13软件G3班 所在系部： 信息学院 指导教师： 陈娟 时间： 2016年5月 实验目的 1、掌握哈夫曼编码原理；? 2、熟练掌握哈夫曼树的生成方法； 3、设计哈夫曼树编码系统，锻炼编程能力，巩固哈夫曼算法，熟悉遍历方法 二、实验内容 在编程中要实现字符统计、哈夫曼树的建立及该树的哈夫曼编码的读取，这三者顺序进行。 三、实验步骤 1、字符统计： 字符统计是为了计算出字符的频数，以之构成哈夫曼树叶子结点的权。在实现中，本人采用一个链表表示字符的统计信息。并把所有字符关联到一起。这个链表在后面称为承载统计字符链表。在链表中的结点是一个结构体。 struct information_node { char ch; int frequency; struct information_node *next; } *head0; 其中ch用来记录相应的字符。frequency用来记录字符出现的字符的频数，最后用来构成哈夫曼树叶子结点的权重。以head0来指向该链表。其中，本人在这个链表中的表头的结点，本人不用作统计字符的记录。而以其表头结点的frequancy来记录该链表中字符和数。便于后面的函数实现。 void statistics() { char ch; while((ch=cin.get())!=#)//从输入流中断获取字符 if (!find_record(ch))//如果在承载字符的链表中以有那个字符，就不记录。退回调用 //函数。 recording(ch);//如果在承载字符的链表中没那个字符，就向那个链表插入一个结 //点来记录那个字符。 else count(ch);// 由于有该字符，向承载统计字符链表中就该字符结点的个数记录项 //加1. } 2、构建哈夫曼树： 在构建哈夫曼树就用其构建的方法，即哈夫曼树中树从叶子结点开始建立。每次由无父结点的结点中选出两个权重最小的两结点，把它们的权重之和来构建一个新结点的权重，并且用那两个结点要记录它们的父结点就是那个新结点。再重复如上的操作，直到最后的树的建成。而哈夫曼编码的读取，可用树的遍历的方法。这里，本人用树的双亲表示法来表示树的结构。 创建了2*n-1哈夫曼树结点空间，给存储哈夫曼树结点的那个空间的前n个空间输入n个结点值，这n个结点是叶子结点（其中n是统计的不同字符各数）。它们的相关数据来自承载统计字符链表中的相应数据，一个叶子结点，就要读取一个承载统计字符链表的一个结点的数据。而剩余的空间用来存放其它的结点，因为一棵哈夫曼树如果有n个叶子结点，那么这棵树总共有2*n-1个结点。叶子结点以输入，那就是存在如何构树的问题了，本人采用双亲表示法来表示树的结点。在每个结点是一个结构体类型。 struct huffman_number_node { char ch; int data; int parent; int left_child; int right_child; } *head; ch为字符。data用来记录权重。parent用来记录该结点的位置，如果其无父结点，其值为-1，left_child来记录其左子结点的位置，无左子树，就记录为0。ritht_child用来记录右子结点的位置。如果无右子结点就把它记录为0。最后用head来指向那个存储空间。这样就能很好的指把所有的结点关联起来，构成一棵树。利用构成哈夫曼树的方法，来构成一棵哈夫树。 enter_huffman_values( n);//哈夫曼树叶子结点的输入 creat_huffman_tree(number,n);//创建哈夫曼树 从哈夫曼树中读哈夫曼编码： 本人采用从以叶子结点开始，来读哈夫曼码元。读的方法是从叶子结点开始，然后就顺着叶子结点所记录的父结点。访问其父结点。在父结点中记录其是左子树，就向栈中输入码元0.否则是1.如此继续下去，直到访问到根结点。这时，这个叶子结点的