《数据结构课程设计报告---哈夫曼编码器》由会员分享，可在线阅读，更多相关《数据结构课程设计报告---哈夫曼编码器（19页珍藏版）》请在金锄头文库上搜索。
1、计 算 机 工 程 学 院课 程 设 计 报 告课程名称：数据结构课程设计设计题目： 哈夫曼编码器 院 系： 计算机工程学院 班 级： 软件 1102 组 别： 15 学生姓名: 吴超 学 号: 1101306229 起止日期: 2011 年 12 月 26 日 31 日 目 录1、设计目的 .22、需求分析 .32.1 选题的意义及背景2.2 基本要求2.3 运行环境及开发工具3、概要设计 .43.1 设计思想3.2 程序框图3.3 方法及原理3.4 主要数据结构4、详细设计 .74.1 创建哈夫曼树4.2 编码4.3 源程序5、调试与操作说明 .146、总结与体会 .157、致谢 .16设
2、计目的1、 利用学过的数据结构知识设计一个简单的哈夫曼编/译码器系统。2、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2需求分析2.1、选题的意义和背景利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这是要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原） 。对于双工信道
3、（即可以双向传输信息的信道） ，每端都需要一个完整的编/译码系统。2.2、基本要求(1)初始化：键盘输入字符集大小 n、n 个字符和 n 个权值，建立哈夫曼树；(2)编码：利用建好的哈夫曼树生成哈夫曼编码；(3)输出编码；(4)设字符集及频度如下表：字符A B C D E F G H I J K L M频度186 64 13 22 32 103 21 15 47 57 1 5 32 20 字符N O P Q R S T U V W X Y Z频度57 63 15 1 48 51 80 23 8 18 1 16 12.3、运行环境及开发工具本程序采用 Visual C+6.0 编程实现。3概要设
4、计3.1 设计思想本程序的主要功能是实现对用户输入的字符编码，然后再把编码结果翻译成原字符。但在进行这些操作之前必须做一项工作，就是创建 Huffman 树。哈 夫 曼 树 又 称 最 优二 叉 树 ， 是 一 种 带 权 路 径 长 度 最 短 的 二 叉 树 。 所 谓 树 的带 权 路 径 长 度 ， 就 是 树 中 所 有 的 叶 结 点 的 权 值 乘 上 其 到根 结 点 的 路 径 长 度 （ 若 根 结 点 为 0 层 ， 叶 结 点 到 根 结 点的 路 径 长 度 为 叶 结 点 的 层 数 ） 。 树 的 带 权 路 径 长 度 记 为WPL=(W1*L1+W2*L2+W
5、3*L3+.+Wn*Ln)， N 个 权 值Wi(i=1,2,.n)构 成 一 棵 有 N 个 叶 结 点 的 二 叉 树 ， 相 应的 叶 结 点 的 路 径 长 度 为 Li(i=1,2,.n)。 可 以 证 明 哈 夫曼 树 的 WPL 是 最 小 的 。 哈 夫 曼 在 上 世 纪 五 十 年 代 初 就 提出 这 种 编 码 时 ， 根 据 字 符 出 现 的 概 率 来 构 造 平 均 长 度 最短 的 编 码 。 它 是 一 种 变 长 的 编 码 。 在 编 码 中 ， 若 各 码 字长 度 严 格 按 照 码 字 所 对 应 符 号 出 现 概 率 的 大 小 的 逆 序 排
6、列 ， 则 编 码 的 平 均 长 度 是 最 小 的 。43.2 程序框图及流程图哈夫曼编/译码器初始化 退出编码3.3 方法及原理3.3.1创建 Huffman 树本文创建 Huffman 树是在顺序链表的基础上进行的，建树原理如下：1、根据给定的 n 个权值w1,w2,w3,wn，构造具有 n 棵二叉树的森林 F=T1,T2,T3,Tn，其中每棵二叉树 Ti 只有一个带权值 wi 的根结点，其左右子树均为空。2、重复以下步骤，直到 F 中仅剩下一棵树为止：(1)在 F 中选取两棵根结点的权值最小的二叉树，作为左右子树构造一棵新的二叉树。使新的二叉树的根结点的权值为其左右子树上根结点的权值
7、之和。(2)在 F 中删去这两棵二叉树，把新的二叉树加入 F。最后得到的就是 Huffman 树。3.3.2 编码编码操作需在建立好 Huffman 树的基础上进行。二叉树的叶子结点标记字符，由根结点沿着二叉树路径下行，左分支标记为 0，右分支标记为 1，则每条从根结点到叶子结点的路径唯一表示了该叶结点的二进制编码。编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结点的左孩子，则编码为 0，如果是右孩子，则编码为 1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。3.4 主要
8、的数据结构3.4.1 Huffman 结点结构Huffman 结点结构是本程序的基本结构，所有操作都在此上进行。其中包括存储字符的元素 data，字符的权值 weight，以及左右孩子指针和父指针。typedef struct char ch; /结点值int weight; /权值int parent; /父结点指针int lchild; /左孩子结点指针int rchild; /右孩子结点指针huffnode;详细设计4.1 创建 Huffman 树4.1.1 功能描述Huffman 树是整个程序的核心部分，是编码译码操作的前提。哈夫 曼 树 又 称 最 优 二 叉 树 ， 是 一 种 带
9、 权 路 径 长 度 最 短 的 二 叉 树 。 根据 字 符 出 现 的 概 率 来 构 造 平 均 长 度 最 短 的 编 码 。 它 是 一 种 变 长 的编 码 。 在 编 码 中 ， 若 各 码 字 长 度 严 格 按 照 码 字 所 对 应 符 号 出 现 概率 的 大 小 的 逆 序 排 列 ， 则 编 码 的 平 均 长 度 是 最 小 的 。4.1.2 算法原理首先根据用户输入创建 n 棵子树的森林，然后对所有子树扫描，找出权值最小的两个子树，把它们合并成一棵新的子树，同时把它们的权值之和作为新树的权值。把这两棵子树删掉，再把新树加如到森林中，然后再扫描出权值最小的两棵子树，
10、接着进行同样的操作，直到只剩下一棵树即为 Huffman 树。 4.1.3 算法流程 74.2 编码4.2.1 功能描述编码的功能就是把字符转换成二进制数来存储4.2.2 算法原理编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结点的左孩子，则编码为 0，如果是右孩子，则编码为 1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。 4.2.3 算法流程4.4 源程序#include#include#include#include#includetypedef struct /哈
11、夫曼树的结构体char ch;int weight; /权值int parent,lchild,rchild;htnode,*hfmtree;typedef char *hfmcode;void Select(hfmtree &HT,int a,int *p1,int *p2) /Select函数，选出 HT 树到 a 为止，权值最小且 parent 为 0 的 2 个节点int i,j,x,y;for(j=1;jy)*p1=y;*p2=x;else*p1=x;*p2=y;void hfmcoding(hfmtree &HT,hfmcode &HC,int n) /构建哈夫曼树 HT，并求出 n 个字符的哈夫曼编码 HCint i,start,c,f,m,w;int p1,p2;char *cd,z;if(nchoice;if(choice=I|choice=i) /初始化哈夫曼树coutn;hfmcoding(HT,HC,n);for(i=1;icode;cout编码码值为：codeendl;input_file.close();else /如果选了选项之外的就让用户重新选择cout您没有输入正确的步骤，请重新输入！endl;cout
