哈弗曼树的建立_编码和译码操作

1、 北京工商大学课程设计报告 编号：北京工商大学_数据结构_课程设计(报告)院 （系）:_ _班 级:_ _学 号:_ _姓 名:_ _同组学生：_指导教师_成 绩_实践地点：_实践时间： Huffman树的建立及编码【课程设计目的】 通过对哈夫曼树的概念、构造算法的理解，进行编码，从而掌握赫夫曼树的编码原则。 【课程设计任务】霍夫曼（Huffman）编码原理是一种利用二叉树实现的编码原理霍夫曼（Huffman）编码是1952年为文本文件而建立，是一种统计编码。属于无损压缩编码。 霍夫曼编码的码长是变化的，对于出现频率高的信息，编码的长度较短；而对于出现频率低的信息，编码长度较长。这样，处理全部

2、信息的总码长一定小于实际信息的符号长度。霍夫曼编码具有一些明显的特点： 1) 编出来的码都是异字头码，保证了码的唯一可译性。 2) 由于编码长度可变。因此译码时间较长，使得霍夫曼编码的压缩与还原相当费时。 3) 编码长度不统一，硬件实现有难度。 4) 对不同信号源的编码效率不同，当信号源的符号概率为2的负幂次方时，达到100的编码效率；若信号源符号的概率相等，则编码效率最低。 5) 由于"0"与"1"的指定是任意的，故由上述过程编出的最佳码不是唯一的，但其平均码长是一样的，故不影响编码效率与数据压缩性能输入:从终端读入字符集大小n,以及n个字符和n个权值

3、,建立哈弗曼树.输出:从终端读入的字符集最终输出编译后的哈弗曼编码,字符集形式输出.【设计思路】 （1） 定义哈弗曼树的结点结构；（2）定义哈弗曼编码的结构.；（3）构造哈弗曼树；（4）构造n棵只有一个叶结点的二叉树，并找出根结点权值最小的两棵树；（5）输出字符的哈弗曼编码。【概要设计 (流程)】1程序用到的抽象数据类型的定义:typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree;2主模块的流程以及各子模块的主要功能:主main函数调用了HuffmanTree HT函

4、数, HuffmanCode HC=NULL;函数,HuffmanCoding(HT,HC,w,n);函数,最终实现编译功能.【构造哈夫曼树的算法】 （1）根据与n个权值W1,W2,Wn对应的n个结点 构成具有n棵二叉树的森 林。F=T1，T2，,Tn其中,每棵二叉树Ti(1<=i<=n)都只有一个权值为Wi的根结 点，其左、右子树均为空；（2）在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树，且置新树的根结点的权值为其左、右子树上根 结点的权值之和；（3）从F中删除构成新树的那两棵树，同时把新树加入F中；（4）重复（2）和（3）步，直到F中只含有一棵树为 止，此树便

5、是哈夫曼树。【详细设计】具体代码实现如下： #include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct unsigned int weight; unsigned int parent,lchild,rchild; HTNode,*HuffmanTree; typedef char *HuffmanCode; typedef struct unsigned int s1; unsigned int s2; MinCode; void Error(char *message

6、); void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,unsigned int *w,unsigned int n); MinCode Select(HuffmanTree HT,unsigned int n); void Error(char *message) fprintf(stderr,"Error:%sn",message); exit(1); void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,unsigned int *w,u

7、nsigned int n)unsigned int i,s1=0,s2=0; HuffmanTree p; char *cd; unsigned int f,c,start,m; MinCode min; if(n<=1) Error("Code too small!"); m=2*n-1; HT=(HuffmanTree)malloc(m+1)*sizeof(HTNode); for(p=HT,i=0;i<=n;i+,p+,w+) p->weight=*w; p->parent=0; p->lchild=0; p->rchild=0;

8、 for(;i<=m;i+,p+) p->weight=0; p->parent=0; p->lchild=0; p->rchild=0; for(i=n+1;i<=m;i+) min=Select(HT,i-1); s1=min.s1; s2=min.s2; HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight; printf("HT List:n"); printf("Numberttwei

9、ghtttparentttlchildttrchildn"); for(i=1;i<=m;i+) printf("%dtt%dtt%dtt%dtt%dn",i,HTi.weight,HTi.parent,HTi.lchild,HTi.rchild); HC=(HuffmanCode)malloc(n+1)*sizeof(char *); cd=(char *)malloc(n*sizeof(char *); cdn-1='0' for(i=1;i<=n;i+) start=n-1; for(c=i,f=HTi.parent;f!=0;c

10、=f,f=HTf.parent) if(HTf.lchild=c) cd-start='0' else cd-start='1' HCi=(char *)malloc(n-start)*sizeof(char *); strcpy(HCi,&cdstart); free(cd); MinCode Select(HuffmanTree HT,unsigned int n) unsigned int min,secmin; unsigned int temp; unsigned int i,s1,s2,tempi; MinCode code; s1=1;s2

11、=1; for(i=1;i<=n;i+) if(HTi.parent=0)min=HTi.weight; s1=i; break; tempi=i+; for(;i<=n;i+) if(HTi.weight<min&&HTi.parent=0) min=HTi.weight; s1=i; for(i=tempi;i<=n;i+) if(HTi.parent=0&&i!=s1) secmin=HTi.weight; s2=i; break; for(i=1;i<=n;i+) if(HTi.weight<secmin&&a

12、mp;i!=s1&&HTi.parent=0) secmin=HTi.weight; s2=i; if(s1>s2) temp=s1; s1=s2; s2=temp; code.s1=s1; code.s2=s2; return code; void main() HuffmanTree HT=NULL; HuffmanCode HC=NULL; unsigned int *w=NULL; unsigned int i,n; printf("Input n:n"); scanf("%d",&n); w=(unsigned i

13、nt *)malloc(n+1)*sizeof(unsigned int *); w0=0; printf("Enter weight:n"); for(i=1;i<=n;i+) printf("w%d=",i); scanf("%d",&wi); HuffmanCoding(HT,HC,w,n); printf("HuffmanCode:n"); printf("NumberttWeightttCoden"); for(i=1;i<=n;i+) printf("%dtt%dtt%sn",i,wi,HCi); 【运行结果】截图一 【心得体会】本实验是有老师提供模板，然后自己增加功能函数的代码实现的。因此，在完成未完成的功能函数之前还必须要细心阅读所给出代码，整体观察各个部分之前的联系，搞清楚已给出和未完成的代码功能之后，才根据算法，设计出该功能的函数代码。在实验过程中，大大小小的问题是难免的，有些解决不了的，就问了这方面比较擅长的同学，也在网上进行了提问，通过大家的帮忙克服了不少的问题，小问题都是马虎造成的，都要进行反复地