哈夫曼编码╱译码器.doc

中北大学 数 据 结 构 课 程 设 计 说 明 书 ? ? ? 学生姓名: 学 院: 专 业: 信息管理与信息系统? 题 目: 哈夫曼编码/译码器 成绩 指导教师 ? 2011年01月06日 哈夫曼编码/译码器 1.设计目的 《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的： 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力； 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能； 提高综合运用所学的理论知识和方法独立分析和解决问题的能力； 训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。 设计内容和要求 设计内容：设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。 (1)?将权值数据存放在数据文件(文件名为data.txt，位于当前目录中)； (2)?分别采用动态和静态存储结构; 初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树;(3)?编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码； 设计要求： (1) 符合课题要求，实现相应功能； (2) 要求界面友好美观，操作方便易行； (3) 注意程序的实用性、安全性。 3．本设计所采用的数据结构 （1）二叉树的链式存储结构 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 , *parent ; }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” 。 ② 从根结点到每个叶子结点所经历的路径分支上的“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）主函数 功能：创建主界面，使用户进行选择，如果选择1，则根据输入的值建立赫夫曼树，如果选择2，则进行赫夫曼编码，如果选择3，则输出赫夫曼编码表，如果选择4，则退出运行界面。 void main(void) { int chose; void settree(void); //建立树 void code(void); //对文件编码 void disp(void); //建立编码表 root=(struct node*)malloc(sizeof(struct node)); printf(*******************哈夫曼编/译码器演示**********************