1、 1 课程设计报告课程设计报告 课程名称： 数据结构课程设计 课程设计题目： 哈夫曼编码编程实现 系： 数学与计算科学系 专 业： 信息与计算科学 年级、班： 姓 名： 学 号： 指导教师： 职 称： 讲师 2011 年 12 月 2 课程设计课题： 利用哈夫曼编码进行通信可以大大提高信道利用率， 缩短信息传输时间， 降低传输成本， 试设计一个哈夫曼编码系统。功能要求：从键盘输入一段报文（如“what did you do that made you so happy“）或从文档中读取，输出这段报文的哈夫曼编码。 课题分析： 由课题的要求， 在编程中要实现字符统计、 哈夫曼树的建立及该树的哈夫
2、曼编码的读取。 这三者顺序进行。 实现思路 1、字符统计： 字符统计是为了计算出字符的频数，以之构成哈夫曼树叶子结点的权。在实现中，本人采用 一个链表表示字符的统计信息。 并把所有字符关联到一起。 这个链表在后面称为承载统计字 符链表。在链表中的结点是一个结构体。 struct information_node char ch; int frequency; struct information_node *next; *head0; 其中 ch 用来记录相应的字符。frequency 用来记录字符出现的字符的频数，最后用来构成哈 夫曼树叶子结点的权重。以 head0 来指向该链表。其中，本人
3、在这个链表中的表头的结点， 本人不用作统计字符的记录。而以其表头结点的 frequancy 来记录该链表中字符和数。便于 后面的函数实现。 void statistics() char ch; while(ch=cin.get()!=#)/从输入流中断获取字符 if (!find_record(ch)/如果在承载字符的链表中以有那个字符，就不记录。退回调用函 /数。 recording(ch);/如果在承载字符的链表中没那个字符，就向那个链表插入一个结点 /来记录那个字符。 else count(ch);/ 由于有该字符，向承载统计字符链表中就该字符结点的个数记录项加 1. 2、构建哈夫曼树：
4、 在构建哈夫曼树就用其构建的方法， 即哈夫曼树中树从叶子结点开始建立。 每次由无父结点 的结点中选出两个权重最小的两结点， 把它们的权重之和来构建一个新结点的权重， 并且用 那两个结点要记录它们的父结点就是那个新结点。 再重复如上的操作， 直到最后的树的建成。 而哈夫曼编码的读取， 可用树的遍历的方法。 这里， 本人用树的双亲表示法来表示树的结构。 创建了 2*n-1 哈夫曼树结点空间， 给存储哈夫曼树结点的那个空间的前 n 个空间输入 n 个结 点值，这 n 个结点是叶子结点（其中 n 是统计的不同字符各数） 。它们的相关数据来自承载 3 统计字符链表中的相应数据， 一个叶子结点， 就要读取
5、一个承载统计字符链表的一个结点的 数据。而剩余的空间用来存放其它的结点，因为一棵哈夫曼树如果有 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 来记录其左子结点
6、的位置，无左子树，就记录为 0。ritht_child 用来记录右子结点 的位置。如果无右子结点就把它记录为 0。最后用 head 来指向那个存储空间。这样就能很 好的指把所有的结点关联起来， 构成一棵树。 利用构成哈夫曼树的方法， 来构成一棵哈夫树。 enter_huffman_values( n);/哈夫曼树叶子结点的输入 creat_huffman_tree(number,n);/创建哈夫曼树 3、从哈夫曼树中读哈夫曼编码： 本人采用从以叶子结点开始，来读哈夫曼码元。读的方法是从叶子结点开始，然后 就顺着叶子结点所记录的父结点。访问其父结点。在父结点中记录其是左子树，就向栈中输 入码元 0.否则是 1.如此继续下去，直到访问到根结点。这时，这个叶子结点的哈夫曼编码就 可由前面读取码元的反向打印得来。在前面读码元中，本人用一个栈来存放读到的 0 与 1. 这样栈的输出结果就是那上叶子结点的哈夫编码。 编程代码实现及详尽解释 main.cpp #include #include #include #includ
