数据结构课程设计：电文编码译码(哈夫曼编码)详解.doc

福建农林大学 计算机与信息学院 数据结构课程设计 设计：哈夫曼编译码器 姓名：韦邦权 专业：2013级计算机科学与技术 学号班级完成日期：2013.12.28 哈夫曼编译码器 一、需求分析 在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。哈夫曼编码是一种编码方式，以哈夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这张编码表的特殊之处在于，它是根据每一个源字符出现的估算概率而建立起来的（出现概率高的字符使用较短的编码，反之出现概率低的则使用较长的编码，这便使编码之后的字符串的平均期望长度降低，从而达到无损压缩数据的目的）。typedef struct { char data; //结点字符 int weight; //权值 int parent; //双亲结点 int lchild; //左孩子结点 int rchild; //右孩子结点 }HTNode; ② 哈夫曼编码 要求电文的哈夫曼编码，必须先定义哈夫曼编码类型，根据设计要求和实际需要定义的类型如下： typedet struct { char cd[N]; // 存放编码的数组 int start; //从start 开始读cd中的哈夫曼编码 }Hcode; // 编码结构体类型 ③ 代码文件的译码 译码的基本思想是：读文件中编码，并与原先生成的哈夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。 四、详细设计 ①字符统计 int jsq(char *s,int cnt[],char str[]) {char *p; int i,j,k; for(i=1;i=256;i++) cnt[i]=0; for(p=s;*p!=\0;p++) { k=*p; cnt[k]++; } j=0; for(i=1,j=0;i=256;i++) if(cnt[i]!=0) { j++; } return j; } ②哈夫曼树的算法 void CreateHT(HTNode ht[],int n,char str[],int cn[]) //创建哈夫曼树函数 {for(int input=1;input=256;input++) { str[input]=input; } int l=0; for(int output=1;output=256;output++) { if(cn[output] !=0) {ht[l].data=str[output]; //按字母顺序将出现的字母依次存入数组ht[] ht[l].weight=cn[output]; l++; } } int i,k,lnode,rnode; int min1,min2; for (i=0;i2*n-1;i++) ht[i].parent=ht[i].lchild=ht[i].rchild=0; //所有结点的相关域置初值0 for (i=n;i2*n-1;i++) //构造哈夫曼树 { min1=min2=MAX; //int的范围是-32768-32767 lnode=rnode=0; //lnode和rnode记录最小权值的两个结点位置 for (k=0;k=i-1;k++) //选出每次外层循环最小权值的两个结点 { if (ht[k].parent==0) //只在尚未构造二叉树的结点中查找 { if (ht[k].weightmin1) //比min1小时 { min2=min1;rnode=lnode; min1=ht[k].weight;lnode=k; }