数据结构课程设计报告---哈夫曼编码器

《数据结构课程设计报告---哈夫曼编码器》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、计算机工程学院课程设计报告课程名称：数据结构课程设计设计题目：哈夫曼编码器院系：计算机工程学院班级：软件1102组别：15学生姓名:吴超学号:起止日期: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设计目的1、利用学过的数据结构知识设计一个简单的哈夫曼编/译码器系统。2、了解并掌握数据结构与算

2、法的设计方法，具备初步的独立分析和设计能力；3、初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；4、提高综合运用所学的理论知识和方法独立分析和解决问题的能力；5、训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2需求分析2.1、选题的意义和背景利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这是要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的

3、编/译码系统。2.2、基本要求(1)初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树；(2)编码：利用建好的哈夫曼树生成哈夫曼编码；(3)输出编码；(4)设字符集及频度如下表：字符ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度57631514851802381811612.3、运行环境及开发工具本程序采用VisualC++6.0编程实现。3概要设计3.1设计思想本程序的主要功能是实现对用户输入的字符编码，然后再把编码结果翻译成原字符。但在进行这些操作之前必须做

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

5、它是一种变长的编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。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中选取两棵根结点的权值最小的二叉

6、树，作为左右子树构造一棵新的二叉树。使新的二叉树的根结点的权值为其左右子树上根结点的权值之和。(2)在F中删去这两棵二叉树，把新的二叉树加入F。最后得到的就是Huffman树。3.3.2编码编码操作需在建立好Huffman树的基础上进行。二叉树的叶子结点标记字符，由根结点沿着二叉树路径下行，左分支标记为0，右分支标记为1，则每条从根结点到叶子结点的路径唯一表示了该叶结点的二进制编码。编码的时候，我们采用从叶子结点向上回溯的方法编码，如果当前结点是其父结点的左孩子，则编码为0，如果是右孩子，则编码为1，如此回溯，直到父结点为空时，该字符的编码就结束

7、了，对应编码结构中的编码数组就是该字符的编码。如此操作，直到所有叶子结点都扫描一遍为止，即编码结束。3.4主要的数据结构3.4.1Huffman结点结构Huffman结点结构是本程序的基本结构，所有操作都在此上进行。其中包括存储字符的元素data，字符的权值weight，以及左右孩子指针和父指针。typedefstruct{charch;//结点值intweight;//权值intparent;//父结点指针intlchild;//左孩子结点指针intrchild;//右孩子结点指针}huffnode;详细设计4.1创建Huffman树4.1.1

8、功能描述Huffman树是整个程序的核心部分，是编码译码操作的前提。哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。根据字符出现