哈夫曼编码╱译码器.doc
《哈夫曼编码╱译码器.doc》由会员分享,可在线阅读,更多相关《哈夫曼编码╱译码器.doc(9页珍藏版)》请在三一文库上搜索。
1、中北大学数 据 结 构课 程 设 计 说 明 书学生姓名:学 院:专 业:信息管理与信息系统题 目:哈夫曼编码/译码器成绩指导教师 2011年01月06日 哈夫曼编码/译码器1.设计目的数据结构课程主要介绍最常用的数据结构,阐明各种数据结构内在的逻辑关系,讨论其在计算机中的存储表示,以及在其上进行各种运算时的实现算法,并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的:1 了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力;2 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能;3 提高综合运用所学的理论知识和方法独立分析和解决问题的能力
2、;训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。2. 设计内容和要求设计内容:设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。(1)将权值数据存放在数据文件(文件名为data.txt,位于当前目录中);(2)分别采用动态和静态存储结构; 初始化:键盘输入字符集大小n、n个字符和n个权值,建立哈夫曼树;(3)编码:利用建好的哈夫曼树生成哈夫曼编码;输出编码;设计要求:(1) 符合课题要求,实现相应功能;(2) 要求界面友好美观,操作方便易行;(3) 注意程序的实用性、安全性。3本设计所采用的数据结构(1)二叉树的
3、链式存储结构 typedef struct BTNode ElemType data ;struct BTNode *Lchild , *Rchild , *parent ;BTNode; (2)先序遍历二叉树(3)哈夫曼树的构造(4)进行哈夫曼编码的基本过程4功能模块详细设计4.1 详细设计思想(1)该程序利用了二叉树的链式存储结构(三叉链表结点),其定义了四个域:一个数据域,两个分别指向左右子结点的指针域,以及一个指向其双亲结点的指针域, typedef struct BTNode ElemType data ;struct BTNode *Lchild , *Rchild , *pare
4、nt ;BTNode; (2)Huffman树的构造 根据n个权值w1, w2,wn,构造成n棵二叉树的集合F=T1, T2,Tn,其中每棵二叉树只有一个权值为wi的根结点,没有左、右子树; 在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树,且新的二叉树根结点权值为其左、右子树根结点的权值之和; 在F中删除这两棵树,同时将新得到的树加入F中; 重复、,直到F只含一颗树为止。(3)Huffman编码方法以字符集C作为叶子结点,次数或频度集W作为结点的权值来构造 Huffman树。规定Huffman树中左分支代表“0”,右分支代表“1” 。 从根结点到每个叶子结点所经历的路径分支上
5、的“0”或“1”所组成的字符串,为该结点所对应的编码,称之为Huffman编码。由于每个字符都是叶子结点,不可能出现在根结点到其它字符结点的路径上,所以一个字符的Huffman编码不可能是另一个字符的Huffman编码的前缀。(4)程序使用了二叉树的先序遍历,其递归算法为: void PreorderTraverse(BTNode *T) if (T!=NULL) visit(T-data) ; /* 访问根结点 */PreorderTraverse(T-Lchild) ;PreorderTraverse(T-Rchild) ; 4.2 核心代码(1)主函数功能:创建主界面,使用户进行选择,如
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼 编码 译码器
链接地址:https://www.31doc.com/p-10173890.html