数据结构课程设计之赫夫曼编码的应用

学生课程设计题目：赫夫曼编码的应用学生姓名：赵旺学号：124090102042所在院(系)：计算机与信息科学学院专业：2012级计算机科学与技术班级：(二）指导教师：冯韵2014年9月24日目录一、概述.................................................1二、系统分析.............................................1三、概要设计.............................................2四、详细设计.............................................44.1赫夫曼树的建立....................................44.1.1选择选择parent为0且权值最小的两个根结点的算法.................................................54.1.2统计字符串中字符的种类以及各类字符的个数.....74.1.3构造赫夫曼树..................................84.2赫夫曼编码.......................................104.2.1赫夫曼编码算法...............................104.2.2建立正文的编码文件...........................114.3代码文件的译码....................................12五、运行与测试..........................................14六、总结与心得..........................................14参考文献.................................错误!未定义书签。附录.....................................错误!未定义书签。1一、概述本设计是对输入的一串电文字符实现赫夫曼编码，再对赫夫曼编码生产的代码串进行译码，输出电文字符串。在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术。二、系统分析赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。树中从根到每个叶子都有一条路径，对路径上的各分支约定：指向左子树的分支表示“0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。假设每种字符在电文中出现的次数为Wi,编码长度为Li，电文中有n种字符，则电文编码总长为∑WiLi。若将此对应到二叉树上，Wi为叶节点的权，Li为根节点到叶节点的路径长度。2那么，∑WiLi恰好为二叉树上带权路径长度。因此，设计电文总长最短的二进制前缀编码，就是以n种子符出现的频率作权，构造一刻赫夫曼树，此构造过程成为赫夫曼编码。根据设计要求和分析，要实现设计，必须实现以下方面的功能：（1）赫夫曼树的建立；（2）赫夫曼编码的生成；（3）编码文件的译码；三、概要设计程序由哪些模块组成以及模块之间的层次结构、各模块的调用关系；每个模块的功能。voidmain()voidHufffmanEncoding(HuffmanTreeHT,HuffmanCodeHC)//编码部分char*decode(HuffmanCodeHc)//译码voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[])//生成Huffman树voidselect(HufmanTreeHT,intk,int&s1,int&s2)//找寻parent为0,权最小的两个节点3其流程图如下：进行相应的操作输出结果结束构造赫夫曼树程序结束退出对编码串译码对字符串编码开始进行相应的操作4四、详细设计4.1赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含根节点的二叉树。算法的第二步是：将当前森林中的两颗根节点的二叉树，合并成一颗新的二叉树；每合并一次，森林中就减少一棵树，产生一个新节点。显然要进行n-1次合并，所以共产生n-1个新节点，它们都是具有两个孩子分支结点。由此可知，最新求得的赫夫曼树中一共有2n-1个结点，其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们可用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。因此，赫夫曼树的存储结构描述为：#definen100#definem2*n-1typedefstruct{intweight;intlchild,rchild,parent;}HTNode;TtypedefHTNodeHuffmanTree[m+1];54.1.1选择选择parent为0且权值最小的两个根结点的算法voidselect(HuffmanTreeT,intk,int*s1,int*s2){//在HT[1……k]中选择parent为0且权值最小的两个根结点，其开始结束第i个结点权值i=num?创建赫夫曼树输出字符统计情况第i个根结点i=2*num-1?i=num?否是否是否是6序号分别为S1和S2inti,j;intmin1=100;for(i=1;i=k;i++)//查找s1if(T[i].weightmin1&&T[i].parent==0){j=i;min1=T[i].weight;}*s1=j;min1=32767;for(i=1;i=k;i++)//查找s2,不和s1相同if(T[i].weightmin1&&T[i].parent==0&&i!=(*s1)){j=i;min1=T[i].weight;}*s2=j;}74.1.2统计字符串中字符的种类以及各类字符的个数假设电子文件字符串全是大写字母，那么该算法的实现思想是：先定义一个含有26个元素的临时整型数组，用来存储各种字母出现的次数。应为大写字母的ASCII码与整数1~26个元素之间相差64，因此在算法中使用字母减去64作为统计数组的下标对号入座，无须循环判断来实现，从而提高了效率；另外，要求出电文字符串中有多少种字符，并保存这些字符以供编码时使用。统计和保存都比较容易，用一个循环来判断先前统计好的各类字符个数的数组元素是否为零，若不为零，则将其值存入一个数组对应的元素中，同时将其对应的字符也存入另一个数组元素中。具体实现如下：intjsq(char*s,intcnt[],charstr[]){//统计各字符串中各种字母的个数以及字符的种类char*p;inti,j,k;inttemp[27];for(i=1;i=26;i++)temp[i]=0;8for(p=s;*p!='\0';p++){//统计各种字符个数if(*p='A'&&*p='Z'){k=*p-64;temp[k]++;}}j=0;for(i=1,j=0;i=26;i++)//统计有多少种字符if(temp[i]!=0){j++;str[j]=i+64;//将对应的数组送到数组中cnt[j]=temp[i];//存入对应数组的权值}returnj;}4.1.3构造赫夫曼树voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){//构造赫夫曼树HTinti,s1,s2;9for(i=1;i=2*num-1;i++)//初始化HT，左右孩子，双亲，权值都为0{HT[i].lchild=0;HT[i].rchild=0;HT[i].parent=0;HT[i].weight=0;}for(i=1;i=num;i++)//输入num个叶节点的权值HT[i].weight=cnt[i];for(i=num+1;i=2*num-1;i++)//从numd后面开始新建结点存放新生成的父节点{select(HT,i-1,&s1,&s2);//在HT[1……i-1]中选择parent为0且权值最小的两个根结点，其序号分别为s1和s2HT[s1].parent=i;HT[s2].parent=i;//将s1和s2的parent赋值HT[i].lchild=s1;HT[i].rchild=s2;//新结点的左右孩子HT[i].weight=HT[s1].weight+HT[s2].weight;//新结点的权值}for(i=0;i=num;i++)//输入字符集中的字符HC[i].ch=str[i];i=1;while(i=num)printf(字符%c,次数为:%d\n,HC[i].ch,cnt[i++]);}104.2赫夫曼编码要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下：typedefstruct{charch;charbits[n+1];intstart;}CodeNode;typedefCodeNodeHuffmanCode[n];4.2.1赫夫曼编码算法voidHuffmanEncoding(HuffmanTreeHT,HuffmanCodeHC){//根据赫夫曼树HT求赫夫曼编码表ＨＣintc,p,i;charcd[n];intstart;cd[num]='\0';for(i=1;i=num;i++){start=num;11c=i;while((p=HT[c].parent)0)//直至上诉到ht[c]是树根为止{//若HT[c]是HT[p]的孩子，则生成0；否则生成代码1cd[--start]=(HT[p].lchild==c)?'0':'1':c=p;}//endofwhilestrcpy(HC[i].bits,&cd[start]);HC[i].len=num-start;}}4.2.2建立正文的编码文件建立编码文件的基本思想是：将要编码的字符串中的字符逐一与预先生成赫夫曼树时保保存的字符编码对照表进行比较，找到之后，对该字符的编码写入代码文件，直至所有字符处理完毕为止。具体算法如下：viodcoding(huffmanCodeHC,char*str){inti,j;FILE*fp;12fp=fopen(“codefile.tex”,”w”);while(*str){//对电文中字符逐一生成编码并写入文件for(i=1;i=num;i++)if(HC[i].ch==*str){for(j=0;j=HC[i].len;j++)fputc(HC[i].bits[j],fp);break;}str++;}fclose(fp);}4.3代码文件的译码译码的基本思想是:读文件中编码，并与生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。Char*decode(HuffmanCodeHC){//代码文件codefile.tex译码FILE*fp;charstr[254];char*p;staticcharcd[n+1]inti,j,k=0,cjs;13fp=fopen(“codefile.tex”,”r”);while(!feof(fp)){cjs=0;for(i=0;i=num&&cjs==0&&!feof(fp);i++){cd[i]=‘’；cd[i+1]='\0';cd[i]=fgetc(fp);for(j=1;j=num;j++)if(strcmp(HC[i].bits,cd)==0){str[k]=HC[j].ch;k++;cjs=1;break;}}str[k]='\0';;