课程设计哈夫曼编码编程实现

《课程设计哈夫曼编码编程实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、湖南科技学院课程设计报告课程名称：数据结构课程设计课程设计题目：哈夫曼编码编程实现系：数学与计算科学系专业：信息与计算科学年级、班：姓名：学号：指导教师：职称：讲师2011年12月15课程设计课题：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本，试设计一个哈夫曼编码系统。功能要求：从键盘输入一段报文（如"whatdidyoudothatmadeyousohappy"）或从文档中读取，输出这段报文的哈夫曼编码。课题分析：由课题的要求，在编程中要实现字符统计、哈夫曼树的建立及该树的哈夫曼编码的读取。这

2、三者顺序进行。实现思路1、字符统计：字符统计是为了计算出字符的频数，以之构成哈夫曼树叶子结点的权。在实现中，本人采用一个链表表示字符的统计信息。并把所有字符关联到一起。这个链表在后面称为承载统计字符链表。在链表中的结点是一个结构体。structinformation_node{charch;intfrequency;structinformation_node*next;}*head0;其中ch用来记录相应的字符。frequency用来记录字符出现的字符的频数，最后用来构成哈夫曼树叶子结点的权重。以head0来指向该链表。其中

3、，本人在这个链表中的表头的结点，本人不用作统计字符的记录。而以其表头结点的frequancy来记录该链表中字符和数。便于后面的函数实现。voidstatistics(){charch;while((ch=cin.get())!='#')//从输入流中断获取字符if(!find_record(ch))//如果在承载字符的链表中以有那个字符，就不记录。退回调用函//数。recording(ch);//如果在承载字符的链表中没那个字符，就向那个链表插入一个结点//来记录那个字符。elsecount(ch);//由于有该字符，向承载统

4、计字符链表中就该字符结点的个数记录项加1.}2、构建哈夫曼树：在构建哈夫曼树就用其构建的方法，即哈夫曼树中树从叶子结点开始建立。每次由无父结点的结点中选出两个权重最小的两结点，把它们的权重之和来构建一个新结点的权重，并且用那两个结点要记录它们的父结点就是那个新结点。再重复如上的操作，直到最后的树的建成。而哈夫曼编码的读取，可用树的遍历的方法。这里，本人用树的双亲表示法来表示树的结构。15创建了2*n-1哈夫曼树结点空间，给存储哈夫曼树结点的那个空间的前n个空间输入n个结点值，这n个结点是叶子结点（其中n是统计的不同字符各数）。

5、它们的相关数据来自承载统计字符链表中的相应数据，一个叶子结点，就要读取一个承载统计字符链表的一个结点的数据。而剩余的空间用来存放其它的结点，因为一棵哈夫曼树如果有n个叶子结点，那么这棵树总共有2*n-1个结点。叶子结点以输入，那就是存在如何构树的问题了，本人采用双亲表示法来表示树的结点。在每个结点是一个结构体类型。structhuffman_number_node{charch;intdata;intparent;intleft_child;intright_child;}*head;ch为字符。data用来记录权重。pare

6、nt用来记录该结点的位置，如果其无父结点，其值为-1，left_child来记录其左子结点的位置，无左子树，就记录为0。ritht_child用来记录右子结点的位置。如果无右子结点就把它记录为0。最后用head来指向那个存储空间。这样就能很好的指把所有的结点关联起来，构成一棵树。利用构成哈夫曼树的方法，来构成一棵哈夫树。enter_huffman_values(n);//哈夫曼树叶子结点的输入creat_huffman_tree(number,n);//创建哈夫曼树3、从哈夫曼树中读哈夫曼编码：本人采用从以叶子结点开始，来读哈

7、夫曼码元。读的方法是从叶子结点开始，然后就顺着叶子结点所记录的父结点。访问其父结点。在父结点中记录其是左子树，就向栈中输入码元0.否则是1.如此继续下去，直到访问到根结点。这时，这个叶子结点的哈夫曼编码就可由前面读取码元的反向打印得来。在前面读码元中，本人用一个栈来存放读到的0与1.这样栈的输出结果就是那上叶子结点的哈夫编码。编程代码实现及详尽解释main.cpp#include#include#include#include#include

8、ows.h>usingnamespacestd;boolfind_record(charcha);//找出已存入的字符voidrecording(charch);//插入新字符voidparticular_recording(charch);//判断字符是否在承载不同的字符的