哈夫曼编码译码器

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

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

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

4、pe 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树。规定h

5、uffman树中左分支代表“0”，右分支代表“1” 。 从根结点到每个叶子结点所经历的路径分支上的“0”或“1”所组成的字符串，为该结点所对应的编码，称之为huffman编码。由于每个字符都是叶子结点，不可能出现在根结点到其它字符结点的路径上，所以一个字符的huffman编码不可能是另一个字符的huffman编码的前缀。（4）程序使用了二叉树的先序遍历，其递归算法为： void preordertraverse(btnode *t) if (t!=null) visit(t->data) ; /* 访问根结点 */preordertraverse(t->lchild) ;preor

6、dertraverse(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("*哈夫曼编/译码器演示*&quo

7、t;); do printf("n1. 初始化 2. 编码 3.显示编码表 4. 退出"); printf("n请选择："); scanf("%d",&chose); switch (chose) case 1: settree(); /建立二叉树 break; case 2: code(); /进行编码 break; case 3: disp(); /建立编码表 break; case 4: exit(0); / 退出 default: printf("输入错误！"); while(1);（2）构造哈夫曼

8、树void settree(void) int i,j,k; struct node *p1,*p2,*s,*p; void gochar(struct node *); /将树以先序存入文件 void setcode(struct node *); /编码 void weight(struct node *p); /将权值存入指定文件 printf("输入字符集的大小："); scanf("%d",&n); for(i=0;i<n;i+) p=(struct node *)malloc(sizeof(struct node); print

9、f("请输入第%d个字符",i+1); scanf("%c",&p->c); getchar(); printf("请输入该字符的权值:"); scanf("%d",&p->weight); getchar(); p->parent=null; p->rchild=null; p->lchild=null; numi=p; /将结点保存在数组中 for(i=0;i<n-1;i+) /将结点按从小到大排序 for(j=i+1;j<n;j+) if(numi-&

10、gt;weight>numj->weight) s=numi; numi=numj; numj=s; numn=null; /结束标志 /*开始建立树*/ k=n; while(num1!=null) p=(struct node *)malloc(sizeof(struct node); p1=num0; p2=num1; p->lchild=p1; p->rchild=p2; p->parent=null; p1->parent=p; p2->parent=p; p->weight=p1->weight+p2->weight; n

11、um0=p; /存放根结点 for(i=1;i<k;i+) numi=numi+1; k-; /待添加的结点数组长度减1 for(i=0;i<k-1;i+) /排序 for(j=i+1;j<k;j+) if(numi->weight>numj->weight) s=numi; numi=numj; numj=s; root=num0；/建立完毕（3）进行哈夫曼编码void setcode(struct node *p) /进行编码，存入数组中 if(p->lchild=null&&p->rchild=null) tmpcodet='0' strcpy(p->code,tmpcode); else tmpcodet+='0' setcode(p->lchild); t-; tmpcodet+='1' /静态存储 setcode(p->rchild); t-; 5课程设计心得及存在问题通过这次课程设计，我充分理解了用哈夫曼树进行编码问题的基本原理的应用，知道了二叉