哈夫曼编码译码器课程设计

1、学年设计报告设计题目哈夫曼树的建立与实现作者姓名所学专业网络工程指导教师2011年8月23日课程设计题目哈夫曼树的建立与实现组长学号班级组别第组专业网络工程组员指导教师学年设计目的通过构建哈夫曼树对数据进行压缩，以节省存储空间。从而可以皿少的内存空间来存储更多的信息，缩短信息的传递时间。学年设计所需环境WindowsXPVC+6.0学年设计任务要求收集有关的资料，对如何构建哈夫曼树有了更加清晰的认识，为哈夫曼树的编写提供了基本的框架。将所输入的数据信息进行编码构造成哈夫曼树。代码的编写和对每段的编码的解释使得源代俏更具可读性。学年设计工作进度计划序号起止日期工作内容分工情况12011年8月23

2、日2011年8月25日编辑打开文件的函数和哈夫曼树的输出初态和终态22011年8月26日2011年8月27日查找资料对哈夫曼树相关的类型变量的定义32011年8月27日2011年8月28日收集图片和生成哈夫曼树并写入文件42011年8月28日2011年8月29日编写主函数以及修改文件的编辑52011年8月29日2011年8月29日构建哈夫曼树和收集相关资料62011年8月29日2011年8月31日编辑代码分配任务等其他相关事宜指导教师签字：年月日教研室审核总见：教研室主任签字：年月日1引言42需求分析43概要设计43.1设计思路及方案.43.2模块的设计及介绍44详细设计84.1主调函数84.

3、2建立HUFFMANTREE94.3生成HUFFMAN树并写入文件105调试与操作说明.115.1读出文本115.2输出哈夫曼树存储结构的初态125.3输出哈夫曼树存储结构的终态125.4输出哈夫曼树构成后的抽象图14学年设计总结与体会.14参考文献158致谢159附录15学年设计的主要内容1引言随着当今信息技术的发展，为了方便和节省信息的存储和传递速度，人们便创建了哈夫曼编码。哈夫曼编码是将文件进行压缩的一种压缩方法。哈夫曼编码的最大的功能是能够用更少的内存空间来存储更多的信息。若要对文件进行编码则必须对其建立哈夫曼树，其次对这个哈夫曼树进行编码。本学年设计的主要目标就是对如何建立哈夫曼树和

4、如何进行编码的一个详细介绍。2需求分析问题描述：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它作为权值，对所有字符进行构建哈夫曼树。问题补充：从硬盘的一个文件里读出一段英语文章；统计这篇文章中的每个字符出现的次数；以字符出现字数作为权值，构建哈夫曼树，并将哈夫曼树的存储结构的初态和终态进行输出。具体介绍：在E盘中预先建立一个filel.txt文档，在文档中编辑一篇文章(大写)。然后运行程序，调用fileopen()函数读出该文章，显示在界面；再调用jsq()函数对该文章的字符种类进行统计，并对每个字符的出现次数进行统计，并且在界面上显示；然后以每个字符出现次数作为权值，调用Chuf

5、fmanTree()函数构建哈夫曼树，并调用print1()和print2()函数将哈夫曼的存储结构的初态和终态进行输出。3.1 3概要设计设计思路及方案假设每种字符在电文中出现的次数为Wi，编码长度为Li,电文中有n种字符，贝U电文编码总长度为(W1*L1)+(W2*L2)+.(Wi*Li)。若将此对应到二叉树上，Wi为叶结点，Li为根结点到叶结点的路径长度。那么，(W1*L1)+(W2*L2)+.(Wi*Li)恰好为二叉树上带权路径长度。以n种字符出现的频率作权，构造一棵哈夫曼树。该系统将实现以下几大功能：从硬盘读取字符串，建立哈夫曼树，输出哈夫曼树的存储结构的初态和终态。模块的设计及介绍

6、从硬盘读取字符串fileopen（参数）（/利用此函数进行对将文件打开实现命令；打印输出；建立HuffmanTree通过三个函数来实现：voidselect(参数)(从数组中选取两个最小的字符作为/根节点的左右结点初始化；for(接受命令；处理命令；说明：在htlk中选择parent为0且权值最小的两个根结点的算法intjsq(参数)/统计字符的种类及其个数初始化；for接受命令；处理命令；说明：统计字符串中各种字母的个数以及字符的种类voidChuffmanTree()初始化；/利用此函数构造出哈夫曼树for接受命令；处理命令；输出字符统计情况；说明：构造哈夫曼树输出哈夫曼树的存储结构的初态

7、和终态分别调用print1()和print2()来实现voidprint1(参数)/输出哈夫曼树的初态初始化；输出初态；说明：输出哈夫曼树的初态/输出哈夫曼树的终态voidprint2（参数）（for（输出终态；说明：输出哈夫曼树的终态哈夫曼算法是通过对输入数据的统计，根据其频率来构造出权值，再通过对构造的权值进行建立哈夫曼树。并对其进行0和1的赋值，进而可以对每一个权值所对应的位置进行编码。输入字符编码图1哈夫曼算法实现流程图哈夫曼编码是通过对构成最优二叉树的结点进行有规律的0和1的编码，之后从根结点往下进行不断地延伸，且在延伸的过程中会途径所有的结点并记住每一个结点所对应的数值直到所有0,

8、1代是0还是1并进行记录，进而可以将每个途径的结点所对应的数值记录在数组中。的结点都遍历了一遍的时候，整个编码的过程也就完成了，而此时数组中所存储的码便是每一个结点所对应的编码开始结束数组初始化当前位置进数组换下一个位置结果查找，输出图2哈夫曼编码流程图(6)构造哈夫曼树其实就是对以上已经建立好的权值利用哈夫曼算法把它建立成一个最优二叉树即哈夫曼树。其详细的过程是通过比较权值域来选取最小的两个权值，进行一步步的合并和删除直到权值域中只剩下唯一的一个所谓的权值时，贝U整个哈夫曼树的构造便顺利的完成了，而这唯一的一个权值便是整棵二叉树的根结点。4详细设计图3哈夫曼树构造流程图各模块分别为主调函数、

9、建立HuffmanTree、生成HuffmanTree并写入文件。具体过程如下:4.1主调函数代码解释：这是main函数里的各个函数调用情况。fileopen(string);num=jsq(string,cnt,str);DhuffmanTree(HT,cnt,str);printf("HuffmanTre初态：n");print1(HT);ChuffmanTree(HT,HC,cnt,str);HuffmanEncoding(HT,HC);printf("HuffmanTre终态：n”);print2("HuffmanTre龄态：n");/

10、从C盘内中读取文件统计字符种类及各类字符出现的频率/输出哈夫曼树的初态建立哈夫曼树生成哈夫曼树建立HuffmanTree代码解释：该函数为在htl.k中选择patent为0且权值最小的根结点的算法，其序号为si和s2.voidselect(HuffmanTreeT,intk,int&s1,int&s2)(inti,j;s2=s1for(i=1;i<=k;i+)if(Ti.weight<min1&&Ti.patent=0)j=i;min1=Ti.weight;s1=j;min1=32767;for(i=1;i<=k;i+)if(Ti.weight

11、<min1&&Ti.patent=0&&i!=s1)j=i;min1=Ti.weight;s2=j;/对所有的字母进行统计种类和出现的次数intjsp(char*s,intcnt,charstr)inti,j,k;char*p;inttemp27;for(i=1;i<=26;i+)tempi=0;for(p=s;*p!=0”;p+)if(*p>='A'&&*p<='Z')k=*p-64;tempk+;for(i=1,j=0;i<=26;+i)if(tempi!=0)j+;strj=i+

12、64;cntj=tempi;returnj;选取最小的根结点的函数/以s1和s2作为两个最小节点的变量利用此循环将最小结点s1找到利用此循环将另一个最小结点s2找到/str存放所有字符，cnt来存放每种字母的权值统计字符串中各种字母的个数以及字存每种字母的个数找到该字母的位置/统计各种字符的个数/送对应字母到数组中/存入对应字母的权值/j是输入字母总数代码解释：下面函数用来构造哈夫曼树HT。首先初始化哈夫曼树，然后输入前面统计的各个结点的权值，用for循环来构造哈夫曼树。voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt,charstr)(i

13、nti,s1,s2;初始化HT,2*num-1是指哈夫曼所有的节/点数目输入num个叶结点的权值for(i=1;i<=2*num-1;i+)HTi.lchild=0;HTi.rchild=0;HTi.patent=0;HTi.weight=0;for(i=1;i<=num;i+)HTi.weight=cnti;for(i=num+1;i<=2*num-1;i+)select(HT,i-1,s1,s2);HTs1.patent=i;HTs2.patent=i;HTi.lchild=s1;HTi.rchild=s2;HTiweight=HTs1.weight*HTs2.weigh

14、t;在htl.k中选择patent为0且权值最小的两个根结点，其序号为s1和s2,i为双亲for(i=0;i<=num;i+);输入字符集中字符HCi.ch=stri;字符种类i=1;while(i<=num)printf(字符c次数：%d',HCi.ch,cnti+);输出统计的情况4.3生成Huffman树并写入文件代码解释：根据所输入的字符构建哈夫曼树T。voidHuffmanEncoding(HuffmanTreeT,HuffmanCodeH)charcdn;intstart;cdnum='0，;for(i=1;i<=num;+i)start=num;

15、c=i;while(p=Tc.patent)>0)Cd-start=(Tp.lchild=c)c=p;intc,p,i;/c和p分别指示t中孩子和双亲临时存放编码串指示码在cd中的起始位置最后一位(第num个)放上串结束符初始位置从叶子结点ti开始上溯直至上溯到tc是树根为止，0，:，1，；若tc是tp的左孩子则生成0；否则生成1Strcpy(Hi.bits,*cdestart);Hi.len=num-start;代码解释：对str所代表的字符串进行构建哈夫曼树并写入文件。将翻译的二进制码写入文本文件。voidcoding(HuffmanCodeHC,char*str)/对str所代表的

16、字符串进行编码并写入文件inti,j;FILE*fp;fp=fopen("codefile.txt”,"w”);while(*str)for(i=1;i<=num;i+)if(HCi.ch=*str)for(j=0;j<=HCi.len;j+)Fputc(HCI.bitsj,fp);break;str+;fclose(fp);定义文件的指针打开文件的函数/str为编码的指针/将文件关闭5调试与操作说明本次测试是通过建立一个名为file1.txt的文本文档，其中有一篇英文字母的文章期望程序能将其读出至界面并实现其它相关的功能。运行程序后，我们可以见到以下运行界面。

17、5.1读出文本从file1.txt中读取刚输入的字符串并将其输出到显示屏如图3所示。K'字符的双亲，字w"C:DocuBentsandSettingsAd>inistratDiYDebuVCppI.exe"读出文本为、nanydifferentsportsoccuronouruniuersitgfrounds,studentscanparteipateinactiuitieslikefootball.basketballFacinfandeuenbaseball.otherstudentsmayenjopsportssuchastennis,giimning，

18、姬dMghJurBpingf.txllothershaveaccc?toactiuitlikeueightliftinsf,skiingrsuchastennissuimningandhighJumpingstHethersJiaueaccesstoactiuitieslikeweightliftingskiingetcrnangdifferentsportoccuronyoupuniuepstyroimdsstudentscanparticipateinactivitieslikefootballbasketballracingandevenbaseballothei*students(na

19、yenjoysportssuchastennissuinmingandhighjur>pingstill图3读出文本示意图5.2输出哈夫曼树存储结构的初态下图所示的为哈夫曼树的初态。其中的每行数字分别表示字符的权值,符的左孩子，字符的右孩子，而本图为哈夫曼树的初始化如图4所示。图4哈夫曼树的初态图5.3输出哈夫曼树存储结构的终态该图为哈夫曼树的终态。本图显示的是哈夫曼树的构建以后的其字符的权值，双亲下标,左孩子，右孩子如图5所示。图5哈夫曼的终态图1"*C:DocuientsandSettingsAdMini3tr&1orDebuECppl,eie*8860448822

20、22469422244894gn16308gJ430Qo*240a1424ea1634s如43ie1043a02244ea446a2246ea2145e898t)虹图6哈夫曼树的终态图25.4输出哈夫曼树构成后的抽象图此图的构成首先是从权值域中选取最小的两个权值，在此例中其分别为4、4.通过这两个最小的权值合并成为双亲结点8.之后在将8插入到权值域中，同时将此两个最小的结点删除。按照此方法一步步的运行下去最终使得权值域中只剩下唯一的一个权值，至此最优二叉树便建立好了。并且这个最后的结点便是整棵二叉树中的根结点，在本例子中456便是整棵最优二叉树的根结点。图6哈夫曼树示意图6学年设计总结与体会本

21、学年设计的主要目的是要建立一个哈夫曼树并将其实现。通过构建哈夫曼编码结构体来解决一系列因编码带来的复杂问题。同时利用几个数组来存储字符出现的频率和种类。且在此过程中也用到了哈夫曼编码函数和哈夫曼构建函数等，因而使得整个程序繁而不乱有条不紊的编辑和运行在此次的学年设计中，对于构建哈夫曼树主要的思想是通过记录文件中字符的频率来作为在哈夫曼树构造中必不可少的权值，再根据权值来构造哈夫曼树，进而根据这棵建好的哈夫曼树来进行字符编码，并将其存储在所对应的文件中。7参考文献严蔚敏,胡学刚.数据结构（C语言版）M.清华大学出版社，2007苏仕华.数据结构课程设计M.机械工业出版社，2007谭浩强.C语言程序

22、设计教程M.高等教育出版社，20068致谢对于老师详细的指导和同学们的积极配合予以感谢，同时对各个参考文件的提供出版社以真诚的感谢。9附录#include<stdio.h>include<string.h>include<stdlib.h>#include<fstream.h>*类型相关变量的定义*/#definen100叶子结点数#definem2*n-1哈夫曼树中的结点数typedefstructcharch;相关的字母charbits9;/存放编码位串intlen;/该字母编码的长度CodeNode;编码的类型typedefCodeNode

23、HuffmanCoden+1;/所有的叶子结点的编码数组typedefstructintweight;/权值intlchild,rchild,parent;左右孩子及双亲指针HTNode;哈夫曼树结点的类型typedefHTNodeHuffmanTreem+1;/0号单元不用intnum;统计每种字母出现的次数和种类数目/*建立HuffmanTree/*/voidselect(HuffmanTreeT,intk,int&s1,int&s2)在ht1k中选择parent为0且权/值最小的两个根结点的算法其序号为si和s2inti,j;intmin1=101;/mini的数字无何意

24、义只是初始值之后用来记录权值，i为循环最小权值的下标,k为数组结点的总数for(i=1;i<=k;i+)if(Ti.weight<min1&&Ti.parent=0)j=i;min1=Ti.weight;赋权值s1=j;min1=32767;找到权值最小的其中之一for(i=1;i<=k;i+)if(Ti.weight<min1&&Ti.parent=0&&i!=s1)/不让s2和s1的数组下标重合j=i;min1=Ti.weight;s2=j;intjsq(char*s,intcnt,charstr)inti,j,k;c

25、har*p;inttemp27;for(i=1;i<=26;i+)tempi=0;for(p=s;*p!='0'p+)if(*p>='A'&&*p<='Z')k=*p-64;tempk+;for(i=1,j=0;i<=26;+i)if(tempi!=0)/找到权值最小的其中之一/str存放所有字符，cnt来存放每种字母的权值统计字符串中各种字母的个数以及字/符的种类，s为数组/的首地址指针/存每种字母的个数初始化为0/找到字母在数组中的下标字母个数累加j+;strj=i+64;cntj=tempi;/j为字

26、母的总数送对应的字母到数组中存入对应字母的权值returnj;/j是输入字母总数voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt,charstr)(inti,s1,s2;for(i=1;i<=2*num-1;i+)(HTi.lchild=0;HTi.rchild=0;HTi.parent=0;HTi.weight=0;for(i=1;i<=num;i+)HTi.weight=cnti;for(i=num+1;i<=2*num-1;i+)(在ht1.k中选择parent为0且权值HTs1.parent=i;HTs2.pare

27、nt=i;HTi.lchild=s1;HTi.rchild=s2;/构造哈夫曼树HT/初始化HT,2*num-1是指哈夫曼树所/有的结点数目初始化为根结点初始化为根结点输入num个叶子结点的权值/赋权值select(HT,i-1,s1,s2);/最小的两个根结点其序号为s1和s2/i为双亲HTi.weight=HTs1.weight+HTs2.weight;for(i=0;i<=num;i+)输入字符集的中字符HCi.ch=stri;字符的种类i=1;while(i<=num)printf("字符%c次数:dn”,HCi.ch,cnti+);/*生成Huffman树并写入

28、文件*/voidHuffmanEncoding(HuffmanTreeT,HuffmanCodeH)根据哈夫曼树T求哈夫曼编码Hintc,p,i;/c和p分别指示t中孩子和双亲charcdn;intstart;cdnum='0'for(i=1;i<=num;+i)(start=num;c=i;while(p=Tc.parent)>0)(cd-start=(Tp.lchild=c)?'0':'1'c=p;strcpy(Hi.bits,&cdstart);Hi.len=num-start;voidcoding(HuffmanCod

29、eHC,char*str)(inti,j;FILE*fp;fp=fopen("codefile.txt","w");while(*str)(for(i=1;i<=num;i+)if(HCi.ch=*str)(for(j=0;j<=HCi.len;j+)fputc(HCi.bitsj,fp);break;str+;fclose(fp);临时存放编码串，n为字母总数/指示码在cd中的起始位置/num为叶子结点的总数/对所有的叶子节点进行大循环的编码/从最后的叶子结点上溯编码从叶子结点ti开始上溯直至上溯到tc是树根为止若tc是tp的左孩子，贝U生

30、成0,否则/生成1使得可以进行循环/对str所代表的字符串进行构建哈夫曼树并写入文件定义文件的指针打开文件的函数关闭文件/*输出HuffmanTree存储结构*/voidprint1(HuffmanTreeHT)intx;for(x=1;x<=2*num-1;x+)(HTx.parent=0;HTx.lchild=0;HTx.rchild=0;printf("%11d%dt%dn”,HTx.weight,HTx.parent,HTx.lchild,HTx.rchild);printf("n");voidprint2(HuffmanTreeHT)(intk;for(k=1;k<=2*num-1;k+)(printf("%dt%dt%