数据结构哈夫曼课程设计报告

《数据结构哈夫曼课程设计报告》由会员分享，可在线阅读，更多相关《数据结构哈夫曼课程设计报告（15页珍藏版）》请在金锄头文库上搜索。

1、数据结构课程设计报告题 目： 哈夫曼编/译码器 院 （系）： 计算机工程学院 专 业： 信息与计算科学 班 级： 0902 学 生： 陈辉 指导教师： 2010 年 12 月1目 录 1 实验目的 .22 概要设计 .22.1 总体功能结构 22.2 数据结构设计 42.3 方法及原理 53 详细设计和实现 .63.1 创建 Huffman 树 63.2 编码 93.3 译码 114 调试与操作说明 .13总 结 .1621 实验目的设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。【基本要求】(1)初始化：键盘输入字符集大小 n、n 个字符和 n 个权值，建

2、立哈夫曼树；(2)编码：利用建好的哈夫曼树生成哈夫曼编码；(3)输出编码；(4)译码功能；(5)设字符集及频度如下表：字符 空格 A B C D E F G H I J K L M N O P Q R S T U V W X Y Z频度 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 18 1 16 1通过此次课程设计主要达到以下目的：1了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3提高综合运用所学的理论知识和方

3、法独立分析和解决问题的能力；4训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。本程序采用 Visual C+编程实现。2 概要设计2.1 总体功能结构本程序的主要功能是实现对用户输入的字符编码，然后再把编码结果翻译成原字符。但在进行这些操作之前必须做一项工作，就是创建 Huffman 树。3哈 夫 曼 树 又 称 最 优 二 叉 树 ， 是 一 种 带 权 路 径 长 度 最 短 的 二 叉 树 。 所 谓 树 的带 权 路 径 长 度 ， 就 是 树 中 所 有 的 叶 结 点 的 权 值 乘 上 其 到 根 结 点 的 路 径 长 度（ 若 根

4、 结 点 为 0 层 ， 叶 结 点 到 根 结 点 的 路 径 长 度 为 叶 结 点 的 层 数 ） 。 树 的带 权 路 径 长 度 记 为 WPL=(W1*L1+W2*L2+W3*L3+.+Wn*Ln)， N 个 权 值Wi(i=1,2,.n)构 成 一 棵 有 N 个 叶 结 点 的 二 叉 树 ， 相 应 的 叶 结 点 的 路 径 长度 为 Li(i=1,2,.n)。 可 以 证 明 哈 夫 曼 树 的 WPL 是 最 小 的 。 哈 夫 曼 在 上世 纪 五 十 年 代 初 就 提 出 这 种 编 码 时 ， 根 据 字 符 出 现 的 概 率 来 构 造 平 均 长 度最 短

5、 的 编 码 。 它 是 一 种 变 长 的 编 码 。 在 编 码 中 ， 若 各 码 字 长 度 严 格 按 照 码字 所 对 应 符 号 出 现 概 率 的 大 小 的 逆 序 排 列 ， 则 编 码 的 平 均 长 度 是 最 小 的 。总 体 功 能 流 程 如 下 图 ：42.2 数据结构设计2.2.1 Huffman结点结构Huffman 结点结构是本程序的基本结构，所有操作都在此上进行。其中包括存储字符的元素 data，字符的权值 weight，以及左右孩子指针和父指针。typedef struct char data; /结点值int weight; /权值int paren

6、t; /父结点指针int left; /左孩子结点指针int right; /右孩子结点指针huffnode;2.2.2 编码结构编码结构用于存储每个字符的编码，包括用于存储编码的数组和用于记录编码个数的元素。整个结构相当于一个栈结构，采用栈形式存储编码。typedef struct int cdM; /编码串5int top; /串的大小huffcode;2.3 方法及原理2.3.1创建 Huffman树本文创建 Huffman 树是在顺序链表的基础上进行的，建树原理如下：1、根据给定的 n 个权值w1,w2,w3,wn，构造具有 n 棵二叉树的森林 F=T1,T2,T3,Tn，其中每棵二叉

7、树 Ti 只有一个带权值 wi 的根结点，其左右子树均为空。2、重复以下步骤，直到 F 中仅剩下一棵树为止：(1)在 F 中选取两棵根结点的权值最小的二叉树，作为左右子树构造一棵新的二叉树。使新的二叉树的根结点的权值为其左右子树上根结点的权值之和。(2)在 F 中删去这两棵二叉树，把新的二叉树加入 F。最后得到的就是 Huffman 树。2.3.2 编码编码操作需在建立好 Huffman 树的基础上进行。二叉树的叶子结点标记字符，由根结点沿着二叉树路径下行，左分支标记为 0，右分支标记为 1，则每条从根结点到叶子结点的路径唯一表示了该叶结点的二进制编码。编码的时候，我们采用从叶子结点向上回溯的

8、方法编码，如果当前结点是其父结点的左孩子，则编码为 0，如果是右孩子，则编码为 1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。2.3.3 译码译码操作也是在前面创建的 Huffman 树的基础上进行。对译码字符串从头6往后扫描，如果是 1，则当前指针指向右孩子，如果是 0，则指向左孩子。如此下去，直到指针为空时，当前结点的 data 值就是译码。然后再从头开始扫描，进行上面操作，当编码字符串扫描结束时，译码结束。3 详细设计和实现3.1 创建 Huffman树3.1.1 功能描述Huffma

9、n 树是整个程序的核心部分，是编码译码操作的前提。哈 夫 曼 树 又称 最 优 二 叉 树 ， 是 一 种 带 权 路 径 长 度 最 短 的 二 叉 树 。 根 据 字 符 出 现 的 概 率来 构 造 平 均 长 度 最 短 的 编 码 。 它 是 一 种 变 长 的 编 码 。 在 编 码 中 ， 若 各 码 字长 度 严 格 按 照 码 字 所 对 应 符 号 出 现 概 率 的 大 小 的 逆 序 排 列 ， 则 编 码 的 平 均长 度 是 最 小 的 。3.1.2 算法原理首先根据用户输入创建 n 棵子树的森林，然后对所有子树扫描，找出权值最小的两个子树，把它们合并成一棵新的子树

10、，同时把它们的权值之和作为新树的权值。把这两棵子树删掉，再把新树加如到森林中，然后再扫描出权值最小的两棵子树，接着进行同样的操作，直到只剩下一棵树即为 Huffman树。73.3.3 算法流程3.3.4 具体程序void select(huffnode hn,int k,int &s1,int &s2)/选取父结点为空且权值最小的两个结点int minw=200; /暂存最小权值int i;8for(i=1;i=k;i+)if(hni.weightminw&hni.parent=0)minw=hni.weight;s1=i; /s1 存储权值最小结点编号minw=200;for(i=1;i=k

11、;i+)if(hni.weightminw&hni.parent=0&i!=s1)minw=hni.weight;s2=i; /s2 存储权值第二小的结点编号void creatht(huffnode hn,int n) /创建 huffman 树int i;int s1,s2;for(i=n;i2*n-1;i+)select(hn,i,s1,s2);hns1.parent=i+1;hns2.parent=i+1;hni+1.left=s1;9hni+1.right=s2;hni+1.weight=hns1.weight+hns2.weight;3.2 编码3.2.1 功能描述编码的功能就是把字符转换成二进制数来存储3.2.2 算法原理编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结点的左孩子，则编码为 0，如果是右孩子，则编码为 1，如此回溯，直到父结点为空时，该字符的编码就结束了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。3.2.3 算法流程103.2.4 具体程序void Encode(huffnode