《哈夫曼编码╱译码器.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）主函数功能：创建主界面，使用户进行选择，如
6、果选择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(*哈夫曼编/译码器演示*); do printf(n1. 初始化 2. 编码 3.显示编码表 4. 退出); printf(n请选择：); scanf(%d,&ch
7、ose); switch (chose) case 1: settree(); /建立二叉树 break; case 2: code(); /进行编码 break; case 3: disp(); /建立编码表 break; case 4: exit(0); / 退出 default: printf(输入错误！); while(1);（2）构造哈夫曼树void settree(void) int i,j,k; struct node *p1,*p2,*s,*p; void gochar(struct node *); /将树以先序存入文件 void setcode(struct node *)
8、; /编码 void weight(struct node *p); /将权值存入指定文件 printf(输入字符集的大小：); scanf(%d,&n); for(i=0;ic); getchar(); printf(请输入该字符的权值:); scanf(%d,&p-weight); getchar(); p-parent=NULL; p-rchild=NULL; p-lchild=NULL; numi=p; /将结点保存在数组中 for(i=0;in-1;i+) /将结点按从小到大排序 for(j=i+1;jweightnumj-weight) s=numi; numi=numj; num
9、j=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; num0=p; /存放根结点 for(i=1;ik;i+) numi=numi+1; k-; /待添加的结点数组长度减1 for(i=0;ik-1;i+) /排序 for
10、(j=i+1;jweightnumj-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课程设计心得及存在问题通过这次课程设计，我充分理解了用哈夫曼树进行编码问题的基本原理的应用，知道了二叉树的存储结构的算法描述，同时也学会了编写简单的哈夫曼编码的程序。拿到课题时，我感到无从下手，通过在网络上查找资料，我逐渐完成了实验的各项要求。但还是在运行时出现了一些小问题，但基本上完成了老师的要求。通过这次课程设计，我知道了把零碎的知识点放在一起编写程序是很有难度的，我以后会加强这方面的学习。存在的问题是文件的存储以及调用方法有些问题，使得第一个结点无法输出。 8