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

1、滁州学院本科学年设计1 学学 年年 设设 计计 报报 告告设计题设计题目目 哈夫曼树的建立与实现 作者姓名作者姓名 所学所学专业专业 网络工程 指指导导教教师师 2011 年年 8 月月 23 日日滁州学院本科学年设计2学年设计任务书学年设计任务书课程设计题目 哈夫曼树的建立与实现组长学号班级组别第 组专业网络工程组员指 导 教 师学 年 设 计 目 的 通过构建哈夫曼树对数据进行压缩，以节省存储空间。从而可以用更少的内存空间来存储更多的信息，缩短信息的传递时间。学年设计所需环境Windows XP VC+ 6.0 学年设计任务要求 收集有关的资料，对如何构建哈夫曼树有了更加清晰的认识，为哈夫

2、曼树的编写提供了基本的框架。 将所输入的数据信息进行编码构造成哈夫曼树。 代码的编写和对每段的编码的解释使得源代码更具可读性。 学年设计工作进度计划序号起止日期工 作 内 容分工情况1 2011 年 8 月 23 日2011 年 8 月 25 日编辑打开文件的函数和哈夫曼树的输出初态和终态 2 2011 年 8 月 26 日 2011 年 8 月 27 日 查找资料对哈夫曼树相关的类型变量的定义 3 2011 年 8 月 27 日 2011 年 8 月 28 日 收集图片和生成哈夫曼树并写入文件 42011 年 8 月 28 日2011 年 8 月 29 日 编写主函数以及修改文件的编辑 5

3、2011 年 8 月 29 日 2011 年 8 月 29 日 构建哈夫曼树和收集相关资料6 2011 年 8 月 29 日 2011 年 8 月 31 日 编辑代码分配任务等其他相关事宜 指导教师签字： 年 月 日教研室审核意见：教研室主任签字： 年 月 日滁州学院本科学年设计3目目 录录1 引引 言言.42 需需求求分分析析.43 概概要要设设计计.43.1 设计思路及方案.43.2 模块的设计及介绍.54 详详细细设设计计.84.1 主调函数.84.2 建立 HUFFMANTREE.94.3 生成 HUFFMAN树并写入文件.105 调调试试与与操操作作说说明明.115.1 读出文本.1

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

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

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

7、盘读取字符串，建立哈夫曼树，输出哈夫曼树的存储结构的初态和终态。3.2 模块的设计及介绍模块的设计及介绍 从硬盘读取字符串滁州学院本科学年设计5fileopen(参数) /利用此函数进行对将文件打开 实现命令； 打印输出； 建立 HuffmanTree通过三个函数来实现:void select(参数) /从数组中选取两个最小的字符作为/根节点的左右结点初始化；for 接受命令；处理命令；说明：在 htl.k中选择 parent 为 0 且权值最小的两个根结点的算法int jsq（参数） / 统计字符的种类及其个数初始化；for接受命令；处理命令；说明：统计字符串中各种字母的个数以及字符的种类v

8、oid ChuffmanTree()初始化； /利用此函数构造出哈夫曼树 for接受命令；处理命令； 输出字符统计情况；说明：构造哈夫曼树 输出哈夫曼树的存储结构的初态和终态分别调用 print1()和 print2（）来实现void print1（参数） /输出哈夫曼树的初态滁州学院本科学年设计6 初始化；输出初态；说明：输出哈夫曼树的初态void print2（参数） /输出哈夫曼树的终态for输出终态；说明：输出哈夫曼树的终态 哈夫曼算法是通过对输入数据的统计，根据其频率来构造出权值，再通过对构造的权值进行建立哈夫曼树。并对其进行 0 和 1 的赋值，进而可以对每一个权值所对应的位置进行

9、编码。 图 1 哈夫曼算法实现流程图 哈夫曼编码是通过对构成最优二叉树的结点进行有规律的 0 和 1 的编码，之后从根结点往下进行不断地延伸，且在延伸的过程中会途径所有的结点并记住每一个结点所对应的开开始始读读取取输输入入的的数数据据统统计计字字符符的的频频率率输输入入字字符符排排序序建建立立哈哈夫夫曼曼树树输输入入字字符符编编码码结结束束滁州学院本科学年设计7数值是 0 还是 1 并进行记录，进而可以将每个途径的结点所对应的数值记录在数组中。直到所有的结点都遍历了一遍的时候，整个编码的过程也就完成了，而此时数组中所存储的0，1 代码便是每一个结点所对应的编码图 2 哈夫曼编码流程图(6) 构

10、造哈夫曼树其实就是对以上已经建立好的权值利用哈夫曼算法把它建立成一个最优二叉树即哈夫曼树。其详细的过程是通过比较权值域来选取最小的两个权值，进行一步步的合并和删除直到权值域中只剩下唯一的一个所谓的权值时，则整个哈夫曼树的构造便顺利的完成了，而这唯一的一个权值便是整棵二叉树的根结点。开开始始数数组组初初始始化化当当前前位位置置编编码码当当前前位位置置进进数数组组换换下下一一个个位位置置切切换换下下一一个个位位置置继继续续是是否否为为终终点点结结果果查查找找，输输出出数数组组空空结结束束是是是是滁州学院本科学年设计8图 3 哈夫曼树构造流程图4 详细设计详细设计各模块分别为主调函数、建立 Huff

11、man Tree、生成 Huffman Tree 并写入文件。具体过程如下：4.1 主调函数主调函数代码解释：这是 main 函数里的各个函数调用情况。 fileopen（string） ； /从 C 盘内中读取文件 num=jsq(string,cnt,str); /统计字符种类及各类字符出现的频率 DhuffmanTree(HT,cnt,str); printf(“HuffmanTree 的初态：n”); print1(HT); /输出哈夫曼树的初态 ChuffmanTree(HT,HC,cnt,str); /建立哈夫曼树 HuffmanEncoding(HT,HC); /生成哈夫曼树 p

12、rintf(“HuffmanTree 的终态：n”); print2(“HuffmanTree 的终态：n”);输输入入所所有有权权值值比比较较求求出出两两个个最最小小的的权权值值以以此此两两个个权权值值作作为为左左右右孩孩子子合合并并成成一一棵棵树树，并并将将这这棵棵树树放放入入到到权权值值域域中中，且且将将这这两两个个最最小小权权值值删删去去。权权值值域域的的个个数数为为1？是是哈哈夫夫曼曼树树构构造造成成功功否否结结束束滁州学院本科学年设计9 4.2 建立建立 HuffmanTree代码解释：该函数为在 htl.k中选择 patent 为 0 且权值最小的根结点的算法，其序号为s1 和

13、s2.void select (HuffmanTree T,int k,int &s1,int &s2) /选取最小的根结点的函数int i, j;s2=s1 /以 s1 和 s2 作为两个最小节点的变量for(i=1;i=k;i+) if(Ti.weightmin1 &Ti.patent=0) /利用此循环将最小结点 s1 找到 j=i; min1=Ti.weight;s1=j; min1=32767;for(i=1;i=k;i+) /利用此循环将另一个最小结点 s2 找到if(Ti.weightmin1 &Ti.patent=0 &i!=s1) j=

14、i; min1=Ti.weight; s2=j;/对所有的字母进行统计种类和出现的次数int jsp(char *s,int cnt,char str) /str存放所有字符，cnt来存放每种字int i ,j,k; /母的权值char *p; /统计字符串中各种字母的个数以及字int temp27; /存每种字母的个数for(i=1;i=A&*p=Z) k=*p-64; /找到该字母的位置 tempk+; /统计各种字符的个数for（i=1,j=0;i=26;+i） if(tempi!=0) j+; strj=i+64; /送对应字母到数组中 cntj=tempi; /存入对应字母的

15、权值return j； /j 是输入字母总数滁州学院本科学年设计10代码解释：下面函数用来构造哈夫曼树 HT。首先初始化哈夫曼树，然后输入前面统计的各个结点的权值，用 for 循环来构造哈夫曼树。void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt,char str) int i,s1 ,s2; for(i=1;i=2*num-1;i+) /初始化 HT，2*num-1 是指哈夫曼所有的节/点数目HTi.lchild=0;HTi.rchild=0; HTi.patent=0;HTi.weight=0;for(i=1;i=num;i+)

16、/输入 num 个叶结点的权值 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.weight; /在 htl.k中选择 patent 为 0 且权值最小的两/个根结点，其序号为 s1 和 s2，i 为双亲for（i=0；i=num；i+） ； /输入字符集中字符HCi.ch=stri; /字符种类i=1;while(i=num) printf(“字

17、符%c 次数：%d”,HCi.ch,cnti+); /输出统计的情况 4.3 生成生成 Huffman 树并写入文件树并写入文件代码解释：根据所输入的字符构建哈夫曼树 T 。void HuffmanEncoding (HuffmanTree T,HuffmanCode H) int c,p,i; /c 和 p 分别指示 t 中孩子和双亲 char cdn; /临时存放编码串 int start; /指示码在 cd 中的起始位置 cdnum=0; /最后一位（第 num 个）放上串结束符 for(i=1;i0) /直至上溯到 tc是树根为止 Cd-start=(Tp.lchild=c) ?0:1

18、;滁州学院本科学年设计11 c=p; /若 tc是 tp的左孩子则生成 0；否则生成1Strcpy(Hi.bits,*cdestart);Hi.len=num-start;代码解释：对 str 所代表的字符串进行构建哈夫曼树并写入文件。将翻译的二进制码写入文本文件。void coding(HuffmanCode HC, char *str) /对 str 所代表的字符串进行编码并写入文件int i,j;FILE *fp; /定义文件的指针fp=fopen(“codefile.txt”,”w”); /打开文件的函数while(*str) /str 为编码的指针 for(i=1;i=num;i+)

19、 if(HCi.ch=*str) for(j=0;j=HCi.len;j+) Fputc(HCI.bitsj,fp); break;str+; fclose(fp); /将文件关闭 5 调试与操作说明调试与操作说明本次测试是通过建立一个名为 file1.txt 的文本文档，其中有一篇英文字母的文章期望程序能将其读出至界面并实现其它相关的功能。运行程序后，我们可以见到以下运行界面。5.1 读出文本读出文本从 file1.txt 中读取刚输入的字符串并将其输出到显示屏如图 3 所示。滁州学院本科学年设计12 图 3 读出文本示意图5.2 输出哈夫曼树存储结构的初态输出哈夫曼树存储结构的初态下图所示

20、的为哈夫曼树的初态。其中的每行数字分别表示字符的权值，字符的双亲，字符的左孩子，字符的右孩子，而本图为哈夫曼树的初始化如图 4 所示。图 4 哈夫曼树的初态图5.3 输出哈夫曼树存储结构的终态输出哈夫曼树存储结构的终态该图为哈夫曼树的终态。本图显示的是哈夫曼树的构建以后的其字符的权值，双亲下标，左孩子，右孩子如图 5 所示。滁州学院本科学年设计13图 5 哈夫曼的终态图 1图 6 哈夫曼树的终态图 2滁州学院本科学年设计145.4 输出哈夫曼树构成后的抽象图输出哈夫曼树构成后的抽象图 此图的构成首先是从权值域中选取最小的两个权值，在此例中其分别为 4、4. 通过这两个最小的权值合并成为双亲结点

21、 8.之后在将 8 插入到权值域中，同时将此两个最小的结点删除。按照此方法一步步的运行下去最终使得权值域中只剩下唯一的一个权值，至此最优二叉树便建立好了。并且这个最后的结点便是整棵二叉树中的根结点，在本例子中 456 便是整棵最优二叉树的根结点。图 6 哈夫曼树示意图6 学年设计学年设计总结与体会总结与体会本学年设计的主要目的是要建立一个哈夫曼树并将其实现。通过构建哈夫曼编码结构体来解决一系列因编码带来的复杂问题。同时利用几个数组来存储字符出现的频率和种类。且在此过程中也用到了哈夫曼编码函数和哈夫曼构建函数等，因而使得整个程序繁而不乱有条不紊的编辑和运行在此次的学年设计中，对于构建哈夫曼树主要

22、的思想是通过记录文件中字符的频率来作为在哈夫曼树构造中必不可少的权值，再根据权值来构造哈夫曼树，进而根据这棵建好的哈夫曼树来进行字符编码，并将其存储在所对应的文件中。 滁州学院本科学年设计157 参考文献参考文献 1 严蔚敏，胡学刚.数据结构（C 语言版）M. 清华大学出版社，20072 苏仕华. 数据结构课程设计M.机械工业出版社，20073 谭浩强. C 语言程序设计教程M.高等教育出版社，20068 致谢致谢 对于老师详细的指导和同学们的积极配合予以感谢，同时对各个参考文件的提供出版社以真诚的感谢。9 附录附录 # include# include# include# include/*

23、类型相关变量的定义*/# define n 100 /叶子结点数# define m 2*n-1 /哈夫曼树中的结点数typedef struct char ch; /相关的字母 char bits9; /存放编码位串 int len; /该字母编码的长度CodeNode; /编码的类型typedef CodeNode HuffmanCoden+1; /所有的叶子结点的编码数组typedef struct int weight; /权值 int lchild,rchild,parent; /左右孩子及双亲指针HTNode; /哈夫曼树结点的类型typedef HTNode HuffmanTre

24、em+1; /0 号单元不用int num; /统计每种字母出现的次数和种类数目/ *建立 HuffmanTree/*/void select(HuffmanTree T,int k,int &s1,int &s2) /在 ht1.k中选择 parent 为 0 且权/值最小的两个根结点的算法滁州学院本科学年设计16 /其序号为 s1 和 s2 int i,j;int min1=101; /min1 的数字无何意义只是初始值之后/用来记录权值，i 为循环/最小权值的下标,k 为数组结点的总数 for(i=1;i=k;i+) if (Ti.weightmin1 &Ti.p

25、arent=0) j=i; min1=Ti.weight; /赋权值 s1=j; min1=32767; /找到权值最小的其中之一 for (i=1; i=k; i+) if(Ti.weightmin1 &Ti.parent=0 & i!=s1)/不让 s2 和 s1 的数组下标重合 j=i ; min1=Ti.weight; /找到权值最小的其中之一 s2=j ;int jsq(char *s, int cnt ,char str) /str存放所有字符，cnt来存放每种字/母的权值 /统计字符串中各种字母的个数以及字/符的种类，s 为数组/的首地址指针 int i,j,k;

26、 char *p; int temp27; /存每种字母的个数 for(i=1;i=A &*p=Z ) k=*p-64; /找到字母在数组中的下标 tempk+; /字母个数累加 for(i=1,j=0;i=26;+i) 滁州学院本科学年设计17 if( tempi !=0) j+; /j 为字母的总数 strj=i+64; /送对应的字母到数组中 cntj=tempi; /存入对应字母的权值 return j; /j 是输入字母总数void ChuffmanTree(HuffmanTree HT,HuffmanCode HC,int cnt, char str) /构造哈夫曼树 HT

27、 int i,s1,s2; for(i=1;i=2*num-1;i+) /初始化 HT，2*num-1 是指哈夫曼树所/有的结点数目 HTi.lchild=0;HTi.rchild=0; /初始化为根结点 HTi.parent=0;HTi.weight=0; /初始化为根结点 for(i=1;i=num;i+) /输入 num 个叶子结点的权值 HTi.weight=cnti; /赋权值 for(i=num+1;i=2*num-1;i+) select(HT,i-1,s1,s2); /在 ht1.k中选择 parent 为 0 且权值 /最小的两个根结点 HTs1.parent=i;HTs2.

28、parent=i; /其序号为 s1 和 s2 HTi.lchild=s1;HTi.rchild=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 树并写入文件*/void HuffmanEncoding(HuffmanTree T,HuffmanCode H)滁州学院本科学年设计18 /根据哈夫曼树 T 求哈夫曼编码 H int

29、 c,p,i; /c 和 p 分别指示 t 中孩子和双亲 char cdn; /临时存放编码串，n 为字母总数 int start; /指示码在 cd 中的起始位置 cdnum=0; /num 为叶子结点的总数 for(i=1;i0) /直至上溯到 tc是树根为止 /若 tc是 tp的左孩子，则生成 0，否则/生成 1 cd-start=(Tp.lchild=c)?0:1; c=p; /使得可以进行循环 strcpy(Hi.bits,&cdstart); Hi.len=num-start; void coding(HuffmanCode HC,char *str) /对 str 所代表

30、的字符串进行构建哈夫曼/树并写入文件 int i,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); /关闭文件 滁州学院本科学年设计19/*输出 HuffmanTree 存储结构*/void print1(HuffmanTree HT) int x; 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