《哈夫曼树的建立与实现.doc》由会员分享，可免费在线阅读全文，更多与《哈夫曼树的建立与实现(最终版)》相关文档资源请在帮帮文库(www.woc88.com)数亿文档库存里搜索。

1、字母的总数str[j]=i+；送对应的字母到数组中cnt[j]=tem[i]；存入对应字母的权值}returnj；j是输入字母总数}voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){构造哈夫曼树HTinti,s,s；for(i=；ilt=*num；i++){初始化HT，*num是指哈夫曼树所有的结点数目HT[i]lchild=；HT[i]rchild=；初始化为根结点HT[i]arent=；HT[i]weight=；初始化为根结点}for(i=；ilt=num；i++)输入num个叶子结点的权值HT[i]weight=cnt[i]；赋权值for(i=num+；ilt=*num；i++){select(HT,i,s,s)；在ht[k]中选择arent为且权值最小的两个根结点HT[s]arent=i；HT[s]arent=i；其序号为s和sHT[i]lchild=s；HT[i]rchild=s；i为双亲HT[i]weight=+；送对应字母到数组中

2、lect(HuffmanTreeT,intk,intams,intams){选取最小的根结点的函数inti,j；s=s以s和s作为两个最小节点的变量for(i=；i=’A’amam*lt=’Z’)k=*；找到该字母的位置tem[k]++；}统计各种字符的个数for(i=,j=；ilt=；++i)if(tem[i]!=){j++；str[j]=清华大学出版社，[]苏仕华数据结构课程设计[M]机械工业出版社，[]谭浩强C语言程序设计教程[M]高等教育出版社，致谢对于老师详细的指导和同学们的积极配合予以感谢，同时对各个参考文件的提供出版社以真诚的感谢。附录includeincludeincludeinclude*********************类型相关变量的定义****************************definen叶子结点数definem*n哈夫曼树中的结点数tyedefstruct{charch；相关的字母charbits[]；存放编码位串intlen；该字母编码的长度}CodeNode；编码的类型ty

3、edefCodeNodeHuffmanCode[n+]；所有的叶子结点的编码数组tyedefstruct{intweight；权值intlchild,rchild,arent；左右孩子及双亲指针}HTNode；哈夫曼树结点的类型tyedefHTNodeHuffmanTree[m+]；号单元不用intnum；统计每种字母出现的次数和种类数目**************************建立HuffmanTree**************************voidselect(HuffmanTreeT,intk,intams,intams){在ht[k]中选择arent为且权值最小的两个根结点的算法其序号为s和sinti,j；intmin=；min的数字无何意义只是初始值之后用来记录权值，i为循环最小权值的下标,k为数组结点的总数for(i=；i='A'amam*lt='Z')k=*；找到字母在数组中的下标tem[k]++；字母个数累加}}for(i=,j=；ilt=；++i)if(tem[i]!=){j++；j

4、行和的赋值，进而可以对每一个权值所对应的位置进行编码。图哈夫曼算法实现流程图⑸哈夫曼编码是通过对构成最优二叉树的结点进行有规律的和的编码，之后从根结点往下进行不断地延伸，且在延伸的过程中会途径所有的结点并记住每一个结点所对应的数值开始读取输入的数据统计字符的频率输入字符排序建立哈夫曼树输入字符编码结束是还是并进行记录，进而可以将每个途径的结点所对应的数值记录在数组中。直到所有的结点都遍历了一遍的时候，整个编码的过程也就完成了，而此时数组中所存储的，代码便是每一个结点所对应的编码图哈夫曼编码流程图()构造哈夫曼树其实就是对以上已经建立好的权值利用哈夫曼算法把它建立成一个最优二叉树即哈夫曼树。其详细的过程是通过比较权值域来选取最小的两个权值，进行一步步的合并和删除直到权值域中只剩下唯一的一个所谓的权值时，则整个哈夫曼树的构造便顺利的完成了，而这唯一的一个权值便是整棵二叉树的根结点。开始数组初始化当前位置编码当前位置进数组换下一个位置切换下一个位置继续是否为终点结果查找，输出数组空结束是是图哈夫曼树构造流程图详细设计各模块分别为

5、这两个最小的权值合并成为双亲结点之后在将插入到权值域中，同时将此两个最小的结点删除。按照此方法一步步的运行下去最终使得权值域中只剩下唯一的一个权值，至此最优二叉树便建立好了。并且这个最后的结点便是整棵二叉树中的根结点，在本例子中便是整棵最优二叉树的根结点。图哈夫曼树示意图学年设计总结与体会本学年设计的主要目的是要建立一个哈夫曼树并将其实现。通过构建哈夫曼编码结构体来解决一系列因编码带来的复杂问题。同时利用几个数组来存储字符出现的频率和种类。且在此过程中也用到了哈夫曼编码函数和哈夫曼构建函数等，因而使得整个程序繁而不乱有条不紊的编辑和运行在此次的学年设计中，对于构建哈夫曼树主要的思想是通过记录文件中字符的频率来作为在哈夫曼树构造中必不可少的权值，再根据权值来构造哈夫曼树，进而根据这棵建好的哈夫曼树来进行字符编码，并将其存储在所对应的文件中。参考文献[]严蔚敏，胡学刚数据结构(C语言版)[M]主调函数建立HUFFMANTREE生成HUFFMAN树并写入文件调试与操作说明读出文本输出哈夫曼树存储结构的初态输出哈夫曼树存储结构的终

6、HT[s]weight+HT[s]weight；}for(i=；ilt=num；i++)输入字符集的中字符HC[i]ch=str[i]；字符的种类i=；while(ilt=num)rintf(quot字符%c次数:%d\nquot,HC[i]ch,cnt[i++])；}*************************生成Huffman树并写入文件*****************voidHuffmanEncoding(HuffmanTreeT,HuffmanCodeH){根据哈夫曼树T求哈夫曼编码Hintc,,i；c和分别指示t中孩子和双亲charcd[n]；临时存放编码串，n为字母总数intstart；指示码在cd中的起始位置cd[num]='\'；num为叶子结点的总数for(i=；i){直至上溯到t[c]是树根为止若t[c]是t[]的左孩子，则生成，否则生成cd[start]=(T[]lchild==c)?'':''；c=；使得可以进行循环}strcy(H[i]bits,amcd[start])；H[i]len=n

7、str为编码的指针for(i=；ilt=num；i++)if(HC[i]ch==*str){for(j=；jlt=HC[i]len；j++)Futc(HC[I]bits[j],f)；eak；}str++；}fclose(f)；将文件关闭}调试与操作说明本次测试是通过建立一个名为filetxt的文本文档，其中有一篇英文字母的文章期望程序能将其读出至界面并实现其它相关的功能。运行程序后，我们可以见到以下运行界面。读出文本从filetxt中读取刚输入的字符串并将其输出到显示屏如图所示。图读出文本示意图输出哈夫曼树存储结构的初态下图所示的为哈夫曼树的初态。其中的每行数字分别表示字符的权值，字符的双亲，字符的左孩子，字符的右孩子，而本图为哈夫曼树的初始化如图所示。图哈夫曼树的初态图输出哈夫曼树存储结构的终态该图为哈夫曼树的终态。本图显示的是哈夫曼树的构建以后的其字符的权值，双亲下标，左孩子，右孩子如图所示。图哈夫曼的终态图图哈夫曼树的终态图输出哈夫曼树构成后的抽象图此图的构成首先是从权值域中选取最小的两个权值，在此例中其分别为、通过

8、母的首地址FILE*f；文件的指针if((f=foen(quotfiletxtquot,quotrquot))==NULL)判断该文件是否为空，若是则判空rintf(quot不能打开文件！\nquot)；while(fgets(string,,f)!=NULL)rintf(quot%s\nquot,string)；将所有的字母进行输出fclose(f)；关闭文件return；}voidmain(){charstring[]；用来存储所有的字母char*s,str[]；intcnt[]；用来存储字母的权值HuffmanTreeHT；定义哈夫曼树HuffmanCodeHC；定义哈夫曼结点rintf(quot读出文本为：\nquot)；fileoen(string)；打开字符串所在地文件num=jsq(string,cnt,str)；统计字符的种类及各类字符出现的频率DhuffmanTree(HT,cnt,str)；构造哈夫曼树rintf(quot\nquot)；rintf(quotHuffmanTree的初态：\nquot)；

9、主调函数、建立HuffmanTree、生成HuffmanTree并写入文件。具体过程如下：主调函数代码解释：这是main函数里的各个函数调用情况。fileoen(string)；从C盘内中读取文件num=jsq(string,cnt,str)；统计字符种类及各类字符出现的频率DhuffmanTree(HT,cnt,str)；rintf(“HuffmanTree的初态：\n”)；rint(HT)；输出哈夫曼树的初态ChuffmanTree(HT,HC,cnt,str)；建立哈夫曼树HuffmanEncoding(HT,HC)；生成哈夫曼树rintf(“HuffmanTree的终态：\n”)；rint(“HuffmanTree的终态：\n”)；输入所有权值比较求出两个最小的权值以此两个权值作为左右孩子合并成一棵树，并将这棵树放入到权值域中，且将这两个最小权值删去。权值域的个数为？是哈夫曼树构造成功否结束建立HuffmanTree代码解释：该函数为在ht[lk]中选择atent为且权值最小的根结点的算法，其序号为s和svoids

10、umstart；}}voidcoding(HuffmanCodeHC,char*str){对str所代表的字符串进行构建哈夫曼树并写入文件inti,j；FILE*f；定义文件的指针f=foen(quotcodefiletxtquot,quotwquot)；打开文件的函数while(*str){for(i=；ilt=num；i++)if(HC[i]ch==*str){for(j=；jlt=HC[i]len；j++)futc(HC[i]bits[j],f)；eak；}str++；}fclose(f)；关闭文件}***************输出HuffmanTree存储结构*********************voidrint(HuffmanTreeHT){intx；for(x=；x=str[i]){HT[i]weight=(char)'*'；}}}**************************打开文本************************intfileoen(charstring[]){string[]为

11、cnt[j]=tem[i]；存入对应字母的权值}returnj；j是输入字母总数}代码解释：下面函数用来构造哈夫曼树HT。首先初始化哈夫曼树，然后输入前面统计的各个结点的权值，用for循环来构造哈夫曼树。voidChuffmanTree(HuffmanTreeHT,HuffmanCodeHC,intcnt[],charstr[]){inti,s,s；for(i=；i){直至上溯到t[c]是树根为止Cd[start]=(T[]lchild==c)?’’:’’；c=；}若t[c]是t[]的左孩子则生成；否则生成Strcy(H[i]bits,*cde[start])；H[i]len=numstart；}}代码解释：对str所代表的字符串进行构建哈夫曼树并写入文件。将翻译的二进制码写入文本文件。voidcoding(HuffmanCodeHC,char*str)对str所代表的字符串进行编码并写入文件{inti,j；FILE*f；定义文件的指针f=foen(“codefiletxt”,”w”)；打开文件的函数while(*str)

12、输出哈夫曼的初态rint(HT)；ChuffmanTree(HT,HC,cnt,str)；建立哈夫曼树HuffmanEncoding(HT,HC)；生成哈夫曼树coding(HC,string)；建立电文哈夫曼编码文件rintf(quot\nquot)；rintf(quotHuffmanTree的终态：\nquot)；输出哈夫曼的终态rint(HT)；rintf(quot*************************\nquot)；}评语：评阅教师签名：年月日成绩e(){初始化；利用此函数构造出哈夫曼树for{接受命令；处理命令；}输出字符统计情况；}说明：构造哈夫曼树⑶输出哈夫曼树的存储结构的初态和终态分别调用rint()和rint()来实现voidrint(参数){输出哈夫曼树的初态初始化；输出初态；}说明：输出哈夫曼树的初态voidrint(参数){输出哈夫曼树的终态for{输出终态；}}说明：输出哈夫曼树的终态⑷哈夫曼算法是通过对输入数据的统计，根据其频率来构造出权值，再通过对构造的权值进行建立哈夫曼树。并对其