哈夫曼编码╱译码器

《哈夫曼编码╱译码器》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、中北大学数据结构课程设计说明书   学生姓名:学院:专业:信息管理与信息系统 题目:哈夫曼编码/译码器成绩指导教师 2011年01月06日8哈夫曼编码/译码器1.设计目的《数据结构》课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：1了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3提高综合运用

2、所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2.设计内容和要求设计内容：设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。(1) 将权值数据存放在数据文件(文件名为data.txt，位于当前目录中)；(2) 分别采用动态和静态存储结构;初始化：键盘输入字符集大小n、n个字符和n个权值，建立哈夫曼树;(3) 编码：利用建好的哈夫曼树生成哈夫曼编码；输出编码；设计要求：(1)符合课题要求，实现相应功能；(2)

3、要求界面友好美观，操作方便易行；(3)注意程序的实用性、安全性。3．本设计所采用的数据结构（1）二叉树的链式存储结构typedefstructBTNode{ElemTypedata;structBTNode*Lchild,*Rchild,*parent;}BTNode;8（2）先序遍历二叉树（3）哈夫曼树的构造（4）进行哈夫曼编码的基本过程4．功能模块详细设计4.1详细设计思想（1）该程序利用了二叉树的链式存储结构（三叉链表结点），其定义了四个域：一个数据域，两个分别指向左右子结点的指针域，以及一个指向其双亲结点的指针域，typed

4、efstructBTNode{ElemTypedata;structBTNode*Lchild,*Rchild,*parent;}BTNode;（2）Huffman树的构造①根据n个权值{w1,w2,…,wn}，构造成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树只有一个权值为wi的根结点，没有左、右子树；②在F中选取两棵根结点权值最小的树作为左、右子树构造一棵新的二叉树，且新的二叉树根结点权值为其左、右子树根结点的权值之和；③在F中删除这两棵树，同时将新得到的树加入F中；④重复②、③，直到F只含一颗树为止。(3)Hu

5、ffman编码方法①以字符集C作为叶子结点，次数或频度集W作为结点的权值来构造Huffman树。规定Huffman树中左分支代表“0”，右分支代表“1”。②从根结点到每个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该结点所对应的编码，称之为Huffman编码。③由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个字符的Huffman编码不可能是另一个字符的Huffman编码的前缀。（4）程序使用了二叉树的先序遍历，其递归算法为：voidPreorderTraverse(BTNode*T){if

6、(T!=NULL){visit(T->data);/*访问根结点*/PreorderTraverse(T->Lchild);8PreorderTraverse(T->Rchild);}}4.2核心代码（1）主函数功能：创建主界面，使用户进行选择，如果选择1，则根据输入的值建立赫夫曼树，如果选择2，则进行赫夫曼编码，如果选择3，则输出赫夫曼编码表，如果选择4，则退出运行界面。voidmain(void){intchose;voidsettree(void);//建立树voidcode(void);//对文件编码voiddisp(voi

7、d);//建立编码表root=(structnode*)malloc(sizeof(structnode));printf("*******************哈夫曼编/译码器演示******************************");do{printf("1.初始化2.编码3.显示编码表4.退出");printf("请选择：");scanf("%d",&chose);switch(chose){case1:settree();//建立二叉树break;case2:code();//进行编码break;8cas

8、e3:disp();//建立编码表break;case4:exit(0);//退出default:printf("输入错误！");}}while(1);}（2）构造哈夫曼树voidsettree(void){inti,j,k;stru