哈夫曼编码╱译码器.doc

中北大学数 据 结 构课 程 设 计 说 明 书学生姓名:学 院:专 业:信息管理与信息系统题 目:哈夫曼编码/译码器成绩指导教师 2011年01月06日 哈夫曼编码/译码器1.设计目的数据结构课程主要介绍最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。进行数据结构课程设计要达到以下目的：1 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力；2 初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能；3 提高综合运用所学的理论知识和方法独立分析和解决问题的能力；训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。2. 设计内容和要求设计内容：设计一个利用哈夫曼算法的编码和译码系统，重复地显示并处理以下项目，直到选择退出为止。(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("*哈夫曼编/译码器演示*"); 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）构造哈夫曼树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); printf("请输入第%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->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; num0=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课程设计心得及存在问题通过这次课程设计，我充分理解了用哈夫曼树进行编码问题的基本原理的应用，知道了二叉树的存储结构的算法描述，同时也学会了编写简单的哈夫曼编码的程序。拿到课题时，我感到无从下手，通过在网络上查找资料，我逐渐完成了实验的各项要求。但还是在运行时出现了一些小问题，但基本上完成了老师的要求。通过这次课程设计，我知道了把零碎的知识点放在一起编写程序是很有难度的，我以后会加强这方面的学习。存在的问题是文件的存储以及调用方法有些问题，使得第一个结点无法输出。 8