基于哈夫曼编码的压缩软件数 据 结 构 课 程 设 计

1、 数 据 结 构 课 程 设 计 设计题目： 基于哈夫曼编码的压缩软件 学生姓名： 贾明 周俊 张旭 专业班级： 10 计科特色班B 指导教师： 余云 完成时间： 2021/5/11 信息工程 院 计算机科学与技术 系 安徽新华学院课程设计成绩评定表 本科 课题名称基于哈夫曼编码的压缩软件院 系信息工程学院年级专业10计科特色学 号姓 名组成员分工成 绩1042157134贾明设计及编写程序；修改程序；编写文档1042157156张旭设计及编写程序；修改程序；负责文档的图片编辑1042157157周俊查找资料，收集信息；设计及调试程序编写及整理文档课题设计目的与设计意义1、课题设计目的： 通过

2、运用哈夫曼树的知识编写该压缩与解压软件，能使学生将所学的理论知识应用起来，有效地运用到解决实际问题中去，提高学生的自身的编程能力，从而到达学以致用的目的。 2、课题设计意义：通过这次课题实验的程序实践，我们了解额数据结构是本学期开 展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方 面这门学科能给我们很大的帮助。同时，学习这门学科也是艰辛的， 这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中 领悟。 指导教师：年 月 日第一章 课程设计内容3第二章 需求分析3第三章 概要设计4第四章 调试情况，设计技巧及体会5第五章 测试结论8第六章 设计技巧8第七章 心得体会9第八章

3、参考文献9第九章 附录:源代码9 课程设计内容 1 应用系统分析，建立该系统的功能模块框图及界面的组织和设计；2 分析系统中的各个函数及它们之间的关系；3 根据问题描述，设计系统的结构体及各个函数；4 设计哈夫曼树的构造算法和哈夫曼编码算法；5 完成设计的系统各个应用模块；6 将各个模块整合进行功能测试。 需求分析 需求分析目的 为明确软件需求、安排工程规划与进度、组织软件开发与测试，供设计人员、开发 人员参考。工程开发方案时间开发内容5月8日读取文本文件，并统计文件中字母个数5月9日建立哈夫曼树对文件，进行哈夫曼编码5月10日压缩与解压缩任务目标能比拟完善的对txt文件进行压缩和解压缩。数据

4、字典名称：字符频率别名：weight描述：读取文本文件，并统计文件中字母个数定义：字符频率 字符 + 数量 名称：结点别名：HTNode描述：建立哈夫曼树的叶子和非叶子结点定义：结点 数量 + 字符 + 双亲结点 + 左孩子结点 + 右孩子结点位置：编码文件功能划分 压缩 解压缩 概要设计 哈夫曼压缩软件1.建立哈夫曼树。根据哈夫曼编码技术，可以将已经给出的字母的使用频率建立一个哈夫曼树，即以二叉树的形式将英文字母和空格存储。?2 .编码。利用二叉树的遍历知识，左孩子用“0表示，右孩子用“1表示，将输入的一组英文句子进行编码。3 .测试和输出。程序要求的测试的英文句子是：“knowledge

5、is power，输出每一个字母然后给出相应的哈夫曼编码。本程序输入字母以“#结束。?4 .译码。本程序要求对已编码的数字能够给以反编码。 调试情况，设计技巧及体会 测试过程 运行程序 压缩文件 解压文件 退出 测试结论 能较好地对文本文档进行压缩和解压缺乏的是其它对类型的文件不适用 设计技巧 本软件可对字母、汉字可以实现共同压缩，压缩率在20%以上，压缩后对哈夫曼树进行保存，以便后面解压，对叶子结点只保存其字符、左孩子、右孩子，对非叶子结点保存左孩子和右孩子。解压时从根结点开始，利用哈夫曼树进行解压，遇到0，找左孩子，遇到1找右孩子，到叶子结点时，输出字符。 心得体会 通过这次课题实验的程序

6、实践，我从中获益匪浅！数据结构是本学期开展的一门学科，学习好这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。同时，学习这门学科也是艰辛的，这不仅需要我们要发挥我们的聪明才志，还需要我们在不断的实践中领悟。这次的程序设计对我们来说无疑是一个检验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。通过小组的努力与老师的指导，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的根底下写出了本次实验的核心算法，并使其能够正常的运行。这次课程设计，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较

7、长的路要走的。非常感谢在背后一直给我指导的老师和同学，他们的支持和鼓励让我在遇到困难而坚持下来了，让我走到了今天这一步，完成了课程的设计。今后，我会更加努力的学习专业知识，提高自我的能力。 参考文献 严蔚敏、吴伟民主编数据结构C语言版清华大学出版社，2002杨秋辉等著.数据结构与算法C+版.清华大学出版社 ,2021金远平著.数据结构C+描述.清华大学出版社,2005 许卓群等著.数据结构与算法.高等教育出版社,2004严蔚敏、吴伟民.数据结构习题集C语言版.清华大学出版社,2002 附录:源代码 #include #include #include #include struct head

8、unsigned char b; /记录字符在数组中的位置long count; /字符出现频率权值 long parent,lch,rch; /定义哈夫曼树指针变量char bits256; /定义存储哈夫曼编码的数组 header512,tmp;/*压缩*/void compress char filename255,outputfile255,buf512; unsigned char c; long i,j,m,n,f; long min1,pt1,flength,length1,length2; double div;FILE *ifp,*ofp; printf "t请您输

9、入需要压缩的文件：" ; gets filename ; ifp fopen filename,"rb" ; if ifp NULL printf "nt文件翻开失败!nn" ; return; printf "t请您输入压缩后的文件名：" ; gets outputfile ; ofp fopen strcat outputfile,".hub" ,"wb" ; if ofp NULL printf "nt压缩文件失败!nn" ; return; flength

10、0; while !feof ifp fread &c,1,1,ifp ; headerc.count+; /字符重复出现频率+1 flength+; /字符出现原文件长度+1 flength-; length1 flength; /原文件长度用作求压缩率的分母headerc.count-; for i 0;i 512;i+ if headeri.count! 0 headeri.b unsigned char i; /*将每个哈夫曼码值及其对应的ASCII码存放在一维数组headeri中， 且编码表中的下标和ASCII码满足顺序存放关系*/ else headeri.b 0; hea

11、deri.parent -1;headeri.lch headeri.rch -1; /对结点进行初始化 for i 0;i 256;i+ /根据频率权值大小，对结点进行排序，选择较小的结点进树 for j i+1;j 256;j+ if headeri.count headerj.count tmp headeri; headeri headerj; headerj tmp; for i 0;i 256;i+ if headeri.count 0 break; n i; /外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1.m 2*n-1;for i n;i

12、m;i+ /构建哈夫曼树 min1 999999999; /预设的最大权值，即结点出现的最大次数 for j 0;j i;j+ if headerj.parent! -1 continue; /parent! -1说明该结点已存在哈夫曼树中，跳出循环重新选择新结点*/ if min1 headerj.count pt1 j; min1 headerj.count; continue; headeri.count headerpt1.count; headerpt1.parent i; /依据parent域值结点层数确定树中结点之间的关系 headeri.lch pt1; /计算左分支权值大小

13、min1 999999999; for j 0;j i;j+ if headerj.parent! -1 continue; if min1 headerj.count pt1 j; min1 headerj.count; continue; headeri.count+ headerpt1.count; headeri.rch pt1; /计算右分支权值大小 headerpt1.parent i; for i 0;i n;i+ /哈夫曼无重复前缀编码 f i; headeri.bits0 0; /根结点编码0 while headerf.parent! -1 j f; f headerf.p

14、arent; if headerf.lch j /置左分支编码0 j strlen headeri.bits ; memmove headeri.bits+1,headeri.bits,j+1 ; /依次存储连接“0“1编码 headeri.bits0 '0' else /置右分支编码1 j strlen headeri.bits ; memmove headeri.bits+1,headeri.bits,j+1 ; headeri.bits0 '1' fseek ifp,0,SEEK_SET ; /从文件开始位置向前移动0字节，即定位到文件开始位置fwrite

15、 &flength,sizeof int ,1,ofp ;/*用来将数据写入文件流中，参数flength指向欲写入的数据地址，总共写入的字符数以参数size*int来决定，返回实际写入的int数目1*/ fseek ofp,8,SEEK_SET ; buf0 0; /定义缓冲区,它的二进制表示00000000f 0; pt1 8; /*假设原文件第一个字符是"A"，8位2进制为01000001，编码后为0110识别编码第一个'0'，那么我们就可以将其左移一位，看起来没什么变化。下一个是'1'，应该|1，结果00000001 同理4位都

16、做完，应该是00000110，由于字节中的8位并没有全部用完，我们应该继续读下一个字符，根据编码表继续拼完剩下的4位，如果字符的编码缺乏4位，还要继续读一个字符，如果字符编码超过4位，那么我们将把剩下的位信息拼接到一个新的字节里*/while !feof ifp c fgetc ifp ; f+; for i 0;i n;i+ if c headeri.b break; strcat buf,headeri.bits ; j strlen buf ; c 0; while j 8 /对哈夫曼编码位操作进行压缩存储 for i 0;i 8;i+ if bufi '1' c c 1

17、 |1; else c c 1; fwrite &c,1,1,ofp ; pt1+; /统计压缩后文件的长度 strcpy buf,buf+8 ; /一个字节一个字节拼接 j strlen buf ; if f flength break; if j 0 /对哈夫曼编码位操作进行压缩存储 strcat buf,"00000000" ; for i 0;i 8;i+ if bufi '1' c c 1 |1; else c c 1; fwrite &c,1,1,ofp ; pt1+; fseek ofp,4,SEEK_SET ; fwrite

18、&pt1,sizeof long ,1,ofp ; fseek ofp,pt1,SEEK_SET ; fwrite &n,sizeof long ,1,ofp ; for i 0;i n;i+ fwrite & headeri.b ,1,1,ofp ; c strlen headeri.bits ; fwrite &c,1,1,ofp ; j strlen headeri.bits ; if j%8! 0 /假设存储的位数不是8的倍数，那么补0 for f j%8;f 8;f+ strcat headeri.bits,"0" ; while

19、headeri.bits0! 0 c 0; for j 0;j 8;j+ /字符的有效存储不超过8位，那么对有效位数左移实现两字符编码的连接 if headeri.bitsj '1' c c 1 |1; /|1不改变原位置上的“0“1值 else c c 1; strcpy headeri.bits,headeri.bits+8 ; /把字符的编码按原先存储顺序连接 fwrite &c,1,1,ofp ; length2 pt1-;div double length1- double length2 / double length1; /计算文件的压缩率fclose i

20、fp ; fclose ofp ; printf "nt压缩文件成功!n" ; printf "t压缩率为 %f%nn",div*100 ; return; /*解压缩*/void uncompress char filename255,outputfile255,buf255,bx255; unsigned char c; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; printf "t请您输入需要解压缩的文件：" ; gets filename ; ifp fopen strc

21、at filename,".hub" ,"rb" ; if ifp NULL printf "nt文件翻开失败!n" ; return; printf "t请您输入解压缩后的文件名：" ; gets outputfile ; ofp fopen outputfile,"wb" ; if ofp NULL printf "nt解压缩文件失败!n" ; return; fread &flength,sizeof long ,1,ifp ; /读取原文件长度，对文件进行定位

22、fread &f,sizeof long ,1,ifp ; fseek ifp,f,SEEK_SET ; fread &n,sizeof long ,1,ifp ; for i 0;i n;i+ fread &headeri.b,1,1,ifp ; fread &c,1,1,ifp ; p long c; /读取原文件字符的权值 headeri.count p; headeri.bits0 0; if p%8 0 m p/8+1; else m p/8; for j 0;j m;j+ fread &c,1,1,ifp ; f c; itoa f,buf,

23、2 ; /将f转换为二进制表示的字符串 f strlen buf ; for l 8;l f;l- strcat headeri.bits,"0" ; strcat headeri.bits,buf ; headeri.bitsp 0; for i 0;i n;i+ /根据哈夫曼编码的长短，对结点进行排序 for j i+1;j n;j+ if strlen headeri.bits strlen headerj.bits tmp headeri; headeri headerj; headerj tmp; p strlen headern-1.bits ; fseek i

24、fp,8,SEEK_SET ; m 0; bx0 0; while 1 /通过哈夫曼编码的长短，依次解码，从原来的位存储复原到字节存储 while strlen bx unsigned int p fread &c,1,1,ifp ; f c; itoa f,buf,2 ; f strlen buf ; for l 8;l f;l- /在单字节内对相应位置补0 strcat bx,"0" ; strcat bx,buf ; for i 0;i n;i+ if memcmp headeri.bits,bx,headeri.count 0 break; strcpy b

25、x,bx+headeri.count ; /*从压缩文件中的按位存储复原到按字节存储字符， 字符位置不改变*/ c headeri.b; fwrite &c,1,1,ofp ; m+; /统计解压缩后文件的长度 if m flength break; /flength是原文件长度 fclose ifp ; fclose ofp ; printf "nt解压缩文件成功!n" ; if m flength /对解压缩后文件和原文件相同性比拟进行判断根据文件大小 printf "t解压缩文件与原文件相同!nn" ; else printf "t解压缩文件与原文件不同!nn" ;return; /*主函数*/int main int c; while 1 /菜单工具栏 printf "t _n" ; printf "n" ; printf "t * 压缩、解压缩 小工具 * n" ; printf "t _n&