实验四-赫夫曼

/目录TOＣ\o＂1－3”\h\z\ｕHYPＥRLIＮK\ｌ”＿Ｔｏc３3９３98４0９”1。概述 PAGＥREF_Toc339398４０9\h1HＹPERLINK\ｌ”_Toｃ３3９39８4１0”1.１问题描述ﻩPAGEＲＥF_Tｏｃ３３93９８４1０\h13.系统分析ﻩPＡGEＲEF_Toｃ３39398４12\h1HYPERLIＮK\l＂_Toc3393９8413”4。1系统功能模块图 PAGEREF＿Toc33９398413\h2HＹＰERLIＮK\l＂_Toc３393９８414”5．１赫夫曼树的存储结构定义 PAＧEREF_Ｔoc339３９8４１４\h3HＹPERLIＮK\ｌ"_Toc3393９8４15”5。2赫夫曼算法及其实现ﻩＰAGEREF_Toｃ３393９84１５＼h3HYPＥＲLINK＼ｌ"_Tｏc3３939８416"５.3统计字符串中字符的种类以及各类字符的个数 ＰＡGEＲEF_Toc33939８４１6＼ｈ3HYPEＲLINＫ\l＂_Ｔoc３393984１7”5.4赫夫曼编译码系统功能模块ﻩPＡＧＥREF_Toc33939８417\h3HYＰＥRLＩNK\l"_Tｏｃ3３9３９８４18"6。主要代码结构ﻩＰＡＧEREF_Toc339３9８４1８\h4HYPＥRLIＮＫ＼l”＿Tｏｃ33939841９＂6．1定义赫夫曼编码类型如下 ＰＡGEREF＿Ｔoｃ339398４19\h４ＨYＰEＲＬINK\l”_Toc339398420"6。2赫夫曼编码算法 PＡGEREＦ＿Toc339３９8420\h４HＹＰＥRLINK\ｌ"_Toc３３９３98421＂6．３建立正文的编码文件ﻩPＡGEＲEF_Toc339３9842１\h5HYPERLINK\l”_Tｏc３3９398４22”7。主要代码段分析 PAGEＲEF_Toc３3939８4２2\ｈ6ＨＹPERＬINK\l＂_Toc３393９842３”7．1赫夫曼编码的结构定义 ＰＡGEREF＿Toc3３9398423\h6HYPＥＲLINK\l”_Toc３３９3９84２4"7.2赫夫曼编码算法ﻩPAGＥREF_Toｃ３3939８424\ｈ6ＨＹＰＥRLINK\ｌ”_Ｔoc33９3984２5"８.运行与测试ﻩ３９３9８4２5＼h7HYＰERLINK＼l”_Toｃ339３９8４26"８。1测试数据及结果ﻩPＡGERＥF_Toc３3９3９8426＼h7HYPERＬINK\l”_Toc33939８42７＂9。总结和心得 PＡGＥREF_Toｃ339398427\ｈ8ＨYPＥＲLINK\l＂_Tｏc3３93984２8”参考文献ﻩPAＧEＲEF_Toc3393９８４2８＼h8HＹＰERLINK\l”_Tｏc3３９3９8429”１0.附:源代码 ＰＡGERＥF_Ｔoｃ339398429＼ｈ9１．概述1。１问题描述利用赫夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间，降低传输成本.这要求在发送端通过一个编码系统对待传输数据预先编码,对于双工信道(即可以双向传输信息的信道）,每端都需要一个完整的编码系统。2。现状分析在当今信息爆炸时代，如何采用有效的数据压缩技术节省数据文件的存储空间和计算机网络的传送时间已越来越引起人们的重视，赫夫曼编码正是一种应用广泛且非常有效的数据压缩技术.赫夫曼编码是一种编码方式，以赫夫曼树—即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。赫夫曼编码使用一张特殊的编码表将源字符(例如某文件中的一个符号）进行编码.赫夫曼编码的应用很广泛，利用赫夫曼树求得的用于通信的二进制编码称为赫夫曼编码。树中从根到每个叶子都有一条路径,对路径上的各分支约定：指向左子树的分支表示“０”码，指向右子树的分支表示“1"码,取每条路径上的“0”或“1”的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。赫夫曼译码输入字符串可以把它编译成二进制代码，输入二进制代码时可以编译成字符串．赫夫曼编码是已被证明的一种有效的熵编码方式，在诸如文本、图像、视频压缩及通信、密码等信息压缩编码标准中被广泛使用。目前广泛应用的许多其他高效数据压缩算法。3.系统分析利用二叉树结构实现赫夫曼编／解码器.基本要求:1、初始化：能够对输入的任意长度的字符串进行统计,统计每个字符的频度,并建立赫夫曼树.２、建立编码表（CreatｅTabｌe)：利用已经建好的赫夫曼树进行编码,并将每个字符的编码输出.3、编码（Ｅｎｃoding):根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码（Dｅcoｄing)：利用已经建好的赫夫曼树对编码后的字符串进行译码，并输出译码结果。４.概要设计４．１系统功能模块图赫夫曼编\译码器的主要功能是先建立赫夫曼树,然后利用建好的赫夫曼树生成赫夫曼编码后进行译码。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串,称之为编码。构造一棵赫夫曼树,规定赫夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为赫夫曼编码。最简单的二进制编码方式是等长编码.若采用不等长编码,让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。赫夫曼树课用于构造使电文的编码总长最短的编码方案。赫夫曼编码/译码器赫夫曼编码/译码器类型及相关变量的定义建立赫夫曼树生成赫夫曼文件赫夫曼译码4.1系统功能模块图5.详细设计5.１赫夫曼树的存储结构定义#defｉnｅn１00//叶子结点数#deｆinem２*ｎ-1／／赫夫曼树中结点总数ｔyｐedefstruct{intweiｇhｔ；//权值ｉｎtlchild，rchild，ｐaｒent；／／左右孩子及双亲指针｝HTNｏｄe；／／树中结点类型tyｐedｅfHTNodeHuffmanTree[m＋1］;//零号单元不用5。2赫夫曼算法及其实现①根据给定的ｎ个权值｛w1，w２,···ｗn},构成n棵二叉树的集F=｛T1,T2，···Ｔn｝，其中每棵二叉树Tｉ中只有一个带权为ｗi的根结点，其左右子树均空.②在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和.③在F中删除这两棵树,同时将新得到的二叉树加入Ｆ中。④重复②和③，直到Ｆ只含一棵树为止,这棵树便是赫夫曼树。5.３统计字符串中字符的种类以及各类字符的个数该算法的主要实现思想是:先定义一个含有２6个元素的临时整型数组,用来存储各种字母出现的次数.因为大写字母与小写字母相差64位，所以在算法中我们可以使用字母减去64作为统计数组的下标对号入座。在统计和保存过程中,我们用一个循环来判断先前统计的各类字符是否为零，若不为零，则将其存入一个数组对应得元素中,同时将其对应的字符也存入另一个数组元素中。5。４赫夫曼编译码系统功能模块（1）赫夫曼建树模块:根据输入的字符和频率,完成赫夫曼树的构造,并根据赫夫曼树求赫夫曼编码。(2)编码模块:读取文本文件进行编码，编码结果存入到新文件。（3)译码模块：读取编码文件并解码，打开存储编码的文件，根据所读取的编码文件中的每字符，利用赫夫曼树进行解码.（4）输出模块:将解码后的每个字母写入到一个新的文件中。6.主要代码结构６.1定义赫夫曼编码类型如下ｔｙｐｅdｅfｓtrｕct{charcｈ；／/存放编码的字符charbits[n＋1];／/存放编码的位置intｓtart；／/编码起始位置}CodｅNode；typedefCｏdｅNodｅHuｆfｍaｎCodｅ［n］;6.２赫夫曼编码算法ｖoidHuffmanEｎcoｄing(HuffmanＴｒｅeHT,ＨuffmanＣodｅHC){ﻩintc,p,i；ﻩcharcd[n］;ﻩintstａrｔ； cｄ[num]＝’\0'； ｆｏｒ（i=1;ｉ<=num;i+＋) ｛ﻩ staｒｔ＝num；ﻩﻩc=i；ﻩﻩwｈile（（ｐ=HT［c］.parｅnt）〉0) ﻩ｛ﻩ ｃｄ［—-starｔ]=(ＨT［p]．lchilｄ＝=ｃ）？’0':’１＇； c=ｐ；ﻩ ｝ ﻩstrcｐy(HC[i］。bits，＆cd［staｒt]）； ﻩHC［i].lｅn=ｎum—ｓtart; }｝6．3建立正文的编码文件建立正文的编码文件的基本思想是：将要编码的字符串中的字符逐一与预先生成赫夫曼树是保存的字符编码对照表进行比较，找到之后,对该字符的编码写入代码文件，直至所有的字符处理完为止。具体实现算法如下：vｏidｃoding(ＨｕffmanCodeＨC,char＊str)｛ ｉｎｔi,j；ﻩFＩLE＊ｆp; ｆp=ｆopeｎ("ｃｏdｅ”,"w”)；ﻩｗhilｅ（＊str）｛ﻩﻩfor（i=１；i〈=ｎum;ｉ++） ﻩ iｆ（HＣ[ｉ］。ch＝=*str)｛ ﻩ ﻩfｏr(j=０;j＜ＨC［i］。ｌeｎ;ｊ+＋） ﻩﻩ ﻩｆｐutc（HC[i]．biｔｓ［ｊ],ｆp);ﻩﻩﻩﻩbrｅａk; ﻩﻩ}ﻩﻩ ｓtr++； ｝ fclosｅ（fp）;}7。主要代码段分析赫夫曼编码可以用于通信技术，它的定义是树从根结点到每个叶子结点的路径上的各分支进行约定，指向左子树对的分支表示“０”码,指向右子树的分支表示“1”码，取每条路径上的“0”或“1"的序列作为和各个叶子对应的字符的编码，这就是赫夫曼编码。7。１赫夫曼编码的结构定义typedefｓｔrucｔ｛ｃhaｒｃh；//存放编码的字符chaｒbitｓ[n+1];/／存放编码的位置inｔsｔart；／/编码起始位置}CodeNoｄe；tｙpedefＣodeNｏdｅＨuｆｆmanＣode［n］;７．２赫夫曼编码算法ｖｏidHufｆmａnEncoｄiｎg（HｕffmａnＴｒｅeHT,HuffｍanＣodｅHC){//根据赫夫曼树HT求赫夫曼编码HＣ intc,ｐ，i;／/ｃ和ｐ分别指示HT中孩子和双亲的位置ﻩcharcd［n]；/／临时存放编码串ﻩintstarｔ；／/指示编码在cd中起始位置ﻩcd［nｕm]='\０'；//最后一位放上结束符 for（ｉ＝１;i＜=nｕｍ;ｉ++)ﻩ{ start＝nｕm;//起始位置 ﻩｃ=i;//从叶子结点HT[ｉ］开始上溯ﻩ ｗhｉlｅ（（p=HT［c］。parenｔ）＞0)／／直至上溯到HＴ[c］是树根为止ﻩﻩ｛//若HＴ[c]是ＨＴ[p］的左孩子,则生成0;否则生成代码１ﻩ ｃd［——stａrt］=（ＨT［p].lcｈｉld==c)?＇０’:＇1’； ﻩﻩc=p;ﻩﻩ｝ ﻩｓtrcpｙ（HC［i]．bitｓ，&ｃd[stａrｔ］）；ﻩ HC[i］。lｅn＝num—ｓｔart;ﻩ}}8.运行与测试8.１测试数据及结果输入：NOMANＣＡNＤOＴWOＴHINＧSATＯNＣE，得出结果：9．总结和心得通过这次课程设计,我们学习了很多在上课没懂的知识，并对求赫夫曼树及赫夫曼编码/译码的算法有了更加深刻的了解.更巩固了课堂中学习有关于赫夫曼编码的知识．参考文献[1]《数据结构课程设计》—－—--苏仕华等编著［2］《数据结构(C语言版）》———-—严蔚敏吴伟民编著［3］《C程序设计（第三版）》-—--—-谭浩强著１0．附：源代码#inｃlude＜stdio．h〉#incｌudｅ<string。ｈ＞/＊（1）类型及相关变量的定义＊/＃defｉnｅｎ100/／叶子结点数＃defineｍ2*n—1/／赫夫曼树中的结点总数typｅｄefｓtｒuct{ｃｈarch；ｃｈａrｂiｔs［9］;//存放编码位串inｔleｎ；/／编码长度｝ＣodeNｏde;typedefCodeＮoｄeHuｆfmanＣｏde[ｎ+1];typｅdefstｒucｔ{ｉntｗeigｈt；//权值intｌchild，rcｈｉld，parent;//左右孩子及双亲指针}HTNode；//树中的结点类型typedefHＴNodeHuffmanＴｒｅe[ｍ+1];//0号单元不可用iｎtnｕｍ；/／字母类型的个数/＊（2)建立赫夫曼树的三个函数＊/voiｄsｅｌecｔ(ＨufｆmａnＴrｅｅT,intk，int*ｓ1，ｉnt*s２）{//在HＴ[1……k］中选择paｒent为0且权值最小的两个根结点，其序号分别为S1和S２iｎｔi,j;iｎtｍin1＝１00；foｒ（i=１;i〈=k;i＋＋)//查找s１iｆ（Ｔ［i]．wｅigｈt〈mｉn1＆＆T［i].pａreｎt==0）｛j＝ｉ;mｉｎ１＝T［i］．weｉghｔ;}(＊ｓ1)＝j;mｉn1＝３276７；for(i＝1;i〈=k；i+＋)//查找s2,不和s1相同ｉf（T［ｉ］.ｗｅｉgｈt＜min1＆&T［i］.parenｔ==0&&i！=(＊s1)){ｊ=i;miｎ1＝T［i］。weight；｝(＊s2）=ｊ;｝inｔjｓq（ｃhar*s，iｎｔcnt[],cｈａrsｔr[］)｛//统计各字符串中各种字母的个数以及字符的种类char*p;intｉ，j，k；iｎtteｍp[27];for(ｉ=1；i〈＝2６；i++)teｍp[i］=0;for（ｐ＝s；＊p!=’\０';p++){//统计各种字符个数iｆ(＊p>='A’＆&*ｐ〈＝＇Z'）{k=＊p-６4；temp［k]+＋；｝｝j＝0；fｏr(i=1,ｊ＝0；i<=26；i++）//统计有多少种字符if（tｅmp[i］!=0)｛ｊ++;ｓtｒ[j]=i+64；／/将对应的数组送到数组中ｃnt［j］＝temp[ｉ];//存入对应数组的权值｝ｒｅturnj；}vｏidCｈｕfｆmanＴree（ＨｕffmａnTｒeeHＴ,HｕffmanＣodeHC，iｎtcnt[］,ｃhaｒstr［]）｛/／构造赫夫曼树HTinti，s1，s2;for（i=１；i<=２＊num-1；i++)//初始化HT，左右孩子，双亲，权值都为0｛HＴ[i］.lchｉld=0；HT[i].rchild=0；HT[i］．ｐareｎｔ=０；HT[ｉ]．weiｇhｔ=0;｝foｒ（i=1；ｉ＜=num;ｉ++）//输入num个叶节点的权值HＴ[i].ｗｅiｇht=cnt［i］；for（i=num+１；i<=2＊ｎｕm-１；i＋+)／／从nｕmｄ后面开始新建结点存放新生成的父结点｛select(HT,i—1，＆s1，&ｓ2);//在ＨＴ[１……i－1］中选择paｒent为0且权值最小的两个根结点,其序号分别为s1和s2HT[ｓ1].ｐａｒent=i;HＴ［s2］。parenｔ=i；//将s1和s2的parｅnt赋值HT［i］.lchild=ｓ1;HT［i]．rｃhｉｌd=s２;//新结点的左右孩子HT[ｉ］．wｅｉｇｈt=HＴ［s1]．wｅight+HT［s2]。wｅight;／/新结点的权值}for（i＝0;ｉ＜=nuｍ；i++)/／输入字符集中的字符HC［i].cｈ=str[i］；i=１;ｗhile（i<＝num）pｒｉntf(”字符％c,次数为：%d\n"，ＨＣ[i］.ch，ｃnｔ[i+＋］）；｝/＊(3）生成赫夫曼编码文件的两个函数＊／voiｄHuffmaｎＥncoｄｉnｇ(ＨｕｆｆmanＴreeHＴ，HｕfｆmanCodeHC）｛//根据赫夫曼树HＴ求赫夫曼编码表HCiｎtc，p，ｉ;/／ｃ和p分别指示T中孩子和双亲的位置charcd[n];//临时存放编码串inｔstart;／／指示编码在cd中的起始位置cd［nｕm］='\0'；//最后一位放上串结束符for(i=1;i<=num；i++）{staｒt=num；//初始位置c=i；／/从叶子节点T[ｉ］开始上溯whilｅ（(p=HT［ｃ］．parｅnt)>0)/／直至上溯到HＴ[c]是树根为止｛／／若T[c]是T［p］的做孩子，则生成0;否则生成代码１ｃd［--start］=(HT[ｐ］.lｃhild==ｃ)?'0＇:’1'；／／cd数组用来存放每一个字母对应的０1编码,c=p；｝／／endofwｈilesｔrcpy（ＨC[i］.ｂitｓ，＆ｃd[stａrt］)；／／将cｄ数组中德01代码复制到i结点中／＊prｉntf（"字符%c：＂，HC[i]。ch)；for（j=staｒt;cｄ［ｊ]!=0；j++） ｐrintｆ（”%c＂，cd［ｊ］)；priｎtf（”＼n”);＊/ＨＣ[i］.len＝nｕm—start；｝//ｅndoffor}ｖoiｄｃodiｎg(HufｆmanＣodeＨＣ,char*ｓtｒ）｛//对str所代表的字符串进行编码，并写入文件ｉｎｔi，j;FＩLＥ*fp；ｆp＝foｐen（”coｄe”,"w")；while(*stｒ){for(i=1;i＜＝nuｍ;i++)ｉf(HC[ｉ]。ch＝=＊sｔr)｛foｒ（ｊ=0;j<HC[ｉ］．len；j++){fputｃ(HC[i].biｔs［j],fp）；}break；}ｓtｒ＋＋；}ｆclose(ｆp）；｝/＊（4)电码的译文*/cｈａr＊dｅcode（HuffmanＣodｅHC){／／代码文件cooｄ的译码