数据结构哈夫曼压缩软件设计实验报告

东北大学信息科学与工程学院数据结构课程设计报告题目 哈夫曼压缩软件设计课题组长 王健 课题组成员 张颖 刘琪 张晓雨专业名称 计算机科学与技术班级 计1307指导教师 杨雷2015 年 1月课程设计任务书题目：哈夫曼压缩软件设计问题描述：采用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。利用哈夫曼编码的数据压缩技术，设计文本格式的压缩软件或位图格式的压缩软件。设计要求：设计基于哈夫曼编码的压缩软件。（1）采用静态链表的二叉树等数据结构的类实现。（2）创建哈夫曼树。（3）哈夫曼编码和译码。（4）源码、编码和压缩后的信息均以文件形式保存。（5）软件时间和空间性能分析。（6）基于哈夫曼编码的位图压缩软件设计（可选）。指导教师签字：年月日目录1 课题概述41.1 课题任务41.2 课题原理41.3 相关知识42 需求分析52.1 课题调研52.2 用户需求分析53 方案设计53.1 总体功能设计53.2 数据结构设计63.3 函数原型设计63.4 主算法设计73.5 用户界面设计94 方案实现124.1 开发环境与工具124.2 程序设计关键技术124.3 个人设计实现（按组员分工）4.3.1 王健设计实现124.3.2 张颖设计实现174.3.3 刘琪设计实现204.3.4 张晓雨设计实现225 测试与调试255.1 个人测试（按组员分工）255.1.1 王健测试255.1.2 张颖测试265.1.3 刘琪测试275.1.4 张晓雨测试315.2 组装与系统测试325.3 系统运行326 课题总结336.1 课题评价336.2 团队协作336.3 下一步工作336.4 个人设计小结（按组员分工）336.4.1 王健设计小结336.4.2 张颖设计小结346.4.3 刘琪设计小结346.4.4 张晓雨设计小结347 附录A 课题任务分工35A-1 课题程序设计分工35A-2 课题报告分工36 附录B 课题设计文档（光盘）37B-1源程序代码（*.H，*.CPP）37B-2工程与可执行文件）37 附录C 用户操作手册（可选）37C.1 运行环境说明37C.2 操作说明371 课题概述1.1课题任务采用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。利用哈夫曼编码对文本或图像进行数据压缩，设计数据压缩软件。【设计要求】设计基于哈夫曼编码的压缩软件。（1）采用静态链表的二叉树等数据结构。（2）创建哈夫曼树。（3）哈夫曼编码和译码。（4）源码、编码和压缩后的信息均以文件形式保存。（5）其它完善性功能。1.2课题原理1.2.1哈夫曼树：哈夫曼树又称最优二叉树，是一种带权路径长度最短的二叉树。所谓树的带权路径长度，就是树中所有的叶子结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。树的带权路径长度记为WPL=W1*L1+W2*L2+W3*L3+W4*L4+Wn*Ln，n个权值Wi(i=1,2,n)构成一颗有n个叶结点的二叉树，相应的叶结点的路径长度为Li(i=1,2,n)。可证明哈夫曼树的WPL是最小的。1.2.2压缩软件：压缩软件是利用算法将文件有损或无损地处理，以达到保留最多文件信息，而令文件体积变小的应用软件。压缩软件一般同时具有解压缩的功能。压缩软件的的基本原理是查找文件内的重复字节,并建立一个相同字节的词典文件,并用一个代码表示,比如在文件里有几处有一个相同的词中华人民共和国用一个代码表示并写入词典文件,这样就可以达到缩小文件的目的。常见的压缩软件有WinRAR ,好压(Haozip),WinZip,7-Zip,WinMount,Peazip等等。1.2.3哈夫曼压缩：哈夫曼压缩是个无损的压缩算法，一般用来压缩文本和程序文件。哈夫曼压缩属于可变代码长度算法一族。意思是个体符号（例如，文本文件中的字符）用一个特定长度的位序列替代。因此，在文件中出现频率高的符号，使用短的位序列，而那些很少出现的符号，则用较长的位序列。1.3相关知识1.3.1二进制文件的创建、读取、写入操作1.3.2数学统计1.3.3哈夫曼树算法1.3.4获取哈夫曼编码1.3.5压缩文件相关信息1.3.6 C/C+语言的熟悉掌握，一定程度上掌握MFC 2 需求分析2.1课题调研随着计算机技术的发展，人们对文件信息的需求量逐渐增大，不光对文件个数的使用量增加，单个文件的内存也增大到几个G，这种现象的产生，将导致计算机上内存的消耗过大，以及计算机对文件的操作变得十分困难。2.2用户需求分析经过调研，目前用户比较倾向的压缩工具的特点有：使用方便、用户友好，在压缩率以及压缩速度方面表现出色。在这个背景下，我们小组决定运用哈夫曼算法，设计一款符合大众要求的小压缩工具。3 方案设计3.1总体功能设计开始菜单解压压缩结束3.2数据结构设计/压缩函数使用数据结构typedef struct HTNode unsigned char b; /*the charactor*/ long parent,lchild,rchild; /*make a tree*/ char bits256; /*the haffuman code*/ long count; /*the frequency*/HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树t/解压函数使用数据结构struct head unsigned char b; /*the charactor*/ long count; /*the frequency*/ long parent, lch, rch; /*make a tree*/ char bits256; /*the haffuman code*/header512, tmp;3.3函数原型设计void Select(HuffmanTree HT,int x,int &s1,int &s2); /HT数组1x中选出能够建树结点中权值最小两个void Compress(char *filename,char *outputfile); /压缩函数void DeCompress(char *filename, char *outputfile); /解压函数3.4主算法设计压缩算法实现压缩开始统计文件字符/统计字符总数构建哈夫曼树生成哈夫曼编码判断字符读取是否结束打开文件/创建压缩文件寻找该字符对应哈夫曼编码写入压缩文件满八位写入一次否是将总字符数写入压缩文件将哈夫曼树信息写入压缩文件压缩结束解压算法实现解压开始打开压缩文件/创建解压文件读取总字符数flength/读取哈夫曼信息读取压缩文件主信息，读取次数是否小于flength每次读八位，写入字符串中根据读取的哈夫曼编码，找到对应的ASCII将字符写入解压文件关闭文件解压结束否是3.5用户界面设计3.5.1主界面 3.5.2菜单界面3.5.3压缩界面3.5.4解压界面3.5.5查找文件和寻找压缩路径界面4 方案实现4.1开发环境与工具硬件：个人PC软件：VS2013开发环境：C+4.2程序设计关键技术二进制文件的读取、写入；哈夫曼算法；MFC实现图形界面。4.3个人设计实现（按组员分工）4.3.1王健设计实现4.3.1.1实现部分压缩void Compress(char *filename,char *outputfile)/*前面省略其他人的部分*/fseek(ifp,0,SEEK_SET); fwrite(&flength,sizeof(long),1,ofp); /压缩文件前四个字节用于/存放原文件字节数 / fwrite(const void* buffer, size_t size, size_t count, FILE* stream);/* fwrite这个函数以二进制形式对文件进行操作，不局限于文本文件（1）buffer：是一个指针，对fwrite来说，是要获取数据的地址；（2）size：要写入内容的单字节数；（3）count:要进行写入size字节的数据项的个数；（4）stream:目标文件指针;（5）返回实际写入的数据项个数count。*/ fseek(ofp,8,SEEK_SET); /ofp从第九个字节处开始写入压缩编码 buf0=0; f=0; pt1=8; /用于记录写入压缩文件的字节数 while(!feof(ifp) ch=fgetc(ifp); f+; for(i=0;i=8) /每满八位，存储至文件 for(i=0;i8;i+) if(bufi=1) ch=(ch1)|1; /左移一位，用零补，并加一 else ch=ch0) /flength不是八的整数倍，用0补全 strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) ch=(ch1)|1; else ch=ch1; fwrite(&ch,1,1,ofp); pt1+; fseek(ofp,4,SEEK_SET); fwrite(&pt1,sizeof(long),1,ofp); /第二个四字节存放哈夫曼树在/压缩文件的位置 fseek(ofp,pt1,SEEK_SET); fwrite(&n,sizeof(long),1,ofp); /pt1个字节后存放哈夫曼树结点/数 for(i=0;in;i+) /将哈夫曼编码信息存入压缩文件 fwrite(&(HTi.b),1,1,ofp); /单个字节存储一个叶子结点 ch=strlen(HTi.bits); fwrite(&ch,1,1,ofp); /接着存储其哈夫曼编码数 j=strlen(HTi.bits); if(j%8!=0) /每个叶子结点哈夫曼编码不足八位，左移，并补零 for(f=j%8;f8;f+) strcat(HTi.bits,0); while(HTi.bits0!=0) ch=0; for(j=0;j8;j+) if(HTi.bitsj=1) ch=(ch1)|1; else ch=ch1; strcpy(HTi.bits,HTi.bits+8); fwrite(&ch,1,1,ofp); /将哈夫曼编码信息存入压缩文件 fclose(ifp); fclose(ofp);4.3.1.2实现部分MFC实现图形界面/类 Class CHuffmanDlg:public CDialog /主界面类 Class menu:public CDialog /菜单界面类 Class compress:public CDialog /压缩界面类 Class Decompress:public CDialog /解压界面类/主界面类中的函数成员 afx_msg void OnBnClickedOk(); /鼠标按下功能选项按钮afx_msg void OnBnClickedCancel(); /鼠标按下退出/菜单界面类中的函数成员 afx_msg void OnOk2(); /鼠标按下解压按钮 afx_msg void OnBnClickedOk(); /鼠标按下压缩按钮afx_msg void OnBnClickedButton1(); /鼠标按下取消按钮/压缩界面类中的函数成员afx_msg void OnButton1(); /鼠标按下查找1按钮（弹出文件查找界面） afx_msg void OnBnClickedButton2(); /鼠标按下查找2按钮（弹出保存文/件路径界面） afx_msg void OnEnChangeEdit3(); /压缩文件命名编辑框 afx_msg void OnBnClickedButton3(); /鼠标按下取消按钮 afx_msg void OnBnClickedOk(); /鼠标按下确定按钮/解压界面类中的函数成员 afx_msg void OnButton1(); /鼠标按下查找1按钮（弹出文件查找界面） afx_msg void OnBnClickedButton2(); /鼠标按下取消按钮afx_msg void OnEnChangeEdit2(); /鼠标按下取消按钮 afx_msg void OnBnClickedOk(); /鼠标按下确定按钮 afx_msg void OnBnClickedButton4(); /鼠标按下查找2按钮（弹出保存文/件路径界面）4.3.2张颖设计实现实现部分解压/解压功能，此设有调试函数#include#include#include#ifndef HEAD2_H#define HEAD2_Hstruct head unsigned char b; /*the charactor*/ long count; /*the frequency*/ long parent, lch, rch; /*make a tree*/ char bits256; /*the haffuman code*/header512, tmp;void DeCompress(char *filename, char *outputfile) char buf255, bx255; unsigned char c; long i, j, m, n, f, p, l; long flength; /flength文件中存储字节数 FILE *ifp, *ofp; for (i = 0; i 512; +i) headeri.count = 0; ifp = fopen(filename, rb); if (ifp = NULL) exit(0); ofp = fopen(outputfile, wb); if (ofp = NULL) exit(0); fread(&flength, sizeof(long), 1, ifp); /读取前四个字节 ，/flength为原文件字节数 fread(&f, sizeof(long), 1, ifp); /f为压缩文件中哈夫曼树信息前/的字节数 fseek(ifp, f, SEEK_SET); fread(&n, sizeof(long), 1, ifp); /读取哈夫曼树叶子结点数nfor (i = 0; i0) m = p / 8 + 1; else m = p / 8; for (j = 0; jf; l-) /不足八位用零补 strcat(headeri.bits, 0); strcat(headeri.bits, buf); headeri.bitsp = 0; for (i = 0; in; i+) for (j = i + 1; jstrlen(headerj.bits) tmp = headeri; headeri = headerj; headerj = tmp; p = strlen(headern - 1.bits); /最长叶子结点编码长度 fseek(ifp, 8, SEEK_SET); /ifp开始指向原文件内容信息 m = 0; bx0 = 0; while (1) while (strlen(bx)f; l-) strcat(bx, 0); strcat(bx, buf); for (i = 0; in; i+) if (memcmp(headeri.bits, bx, headeri.count) = 0) /比较内存区域headeri.bits和bx的前count个字节 break; strcpy(bx, bx + headeri.count); c = headeri.b; fwrite(&c, 1, 1, ofp); m+; if (m = flength) break; fclose(ifp); fclose(ofp); return;int main() char filename100,outputfile100; int c; char b; printf(n Haffman文件压缩软件解压模块测试：n); printf( 1 解压n); printf( 2 退出nn); printf(请输入序号选择功能： ); scanf(%d%c,&c,&b); if(c=1) printf(请输入要解压的文件名： ); gets(filename); printf(n) ; printf(请输入解压后的文件名： ); gets(outputfile); DeCompress(filename,outputfile); else return 0;4.3.3刘琪设计实现/统计：读入源文件，统计字符出现的次数（即统计权重），顺便根据权重进行从大到小的/排序（主要的话之后的操作会简单一些）； typedef struct HTNode unsigned char b; /*the charactor*/ long parent,lchild,rchild; /*make a tree*/ char bits256; /*the haffuman code*/ long count; /*the frequency*/HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树 typedef char* HuffmanCode; /动态分配数组存储哈夫曼编码表/下面具体代码在head1.h的函数compress里 FILE *ifp,*ofp; HTNode HT512; unsigned char ch; /无符号字符型，可以做数组下表 char buf512; int i,j,f,n,m,s1,s2; long pt1,flength; /flength原文件字节个数，pt1压缩文件中哈夫曼/树信息前字节个数 HTNode tmp; for(i=0;i256;+i) HTi.count=0; ifp=fopen(filename,rb); /原文件 if(ifp=NULL) exit(0); ofp=fopen(outputfile,wb); /压缩文件 if(ofp=NULL) exit(0); flength=0; while(!feof(ifp) fread(&ch,1,1,ifp); HTch.count+; flength+; flength-; /flength表示字节总数，feof判断，结尾重复一次 ，需要减一 HTch.count-; /最后一个字节频率减一 for(i=0;i512;i+) /二次定义结点 if(HTi.count!=0) HTi.b=(unsigned char)i; else HTi.b=0; /NULL HTi.parent=-1; HTi.lchild=HTi.rchild=-1; for(i=0;i256;i+) /排序，大在前，小在后 for(j=i+1;j256;j+) if(HTi.countHTj.count) tmp=HTi; HTi=HTj; HTj=tmp; 4.3.4张晓雨设计实现设计实现哈夫曼树构建、哈夫曼编码生成/构建哈夫曼树功能，生成哈夫曼编码，设有调试函数#include#include#includetypedef struct HTNode unsigned char b; /*the charactor*/ long parent,lchild,rchild; /*make a tree*/ char bits256; /*the haffuman code*/ long count; /*the frequency*/HTNode,*HuffmanTree; /动态分配数组存储哈夫曼树typedef char* HuffmanCode; /动态分配数组存储哈夫曼编码表HTNode HT512;void Select(HuffmanTree HT,int x,int &s1,int &s2) int i,nu,mu; long min1; for(i=0,min1=999999999;iHTi.count) min1=HTi.count; nu=i; s1=nu; for(i=0,min1=999999999;iHTi.count) min1=HTi.count; mu=i; s2=mu; void Compress(const char *filename,const char *outputfile) FILE *ifp,*ofp; unsigned char ch; /无符号字符型，可以做数组下表 char buf512; int i,j,f,n,m,s1,s2; long pt1,flength; /flength原文件字节个数，pt1压缩文件中哈夫曼/树信息前字节个数 HTNode tmp; for(i=0;i256;+i) HTi.count=0; ifp=fopen(filename,rb); /原文件 if(ifp=NULL) exit(0);ofp=fopen(outputfile,wb); /压缩文件 if(ofp=NULL) exit(0); flength=0; while(!feof(ifp) fread(&ch,1,1,ifp); HTch.count+; flength+; flength-; /flength表示字节总数，feof判断，结尾重复一次 ，需要减一 HTch.count-; /最后一个字节频率减一 for(i=0;i512;i+) /二次定义结点 if(HTi.count!=0) HTi.b=(unsigned char)i; else HTi.b=0; /NULL HTi.parent=-1; HTi.lchild=HTi.rchild=-1; for(i=0;i256;i+) /排序，大在前，小在后for(j=i+1;j256;j+) if(HTi.countHTj.count) tmp=HTi; HTi=HTj; HTj=tmp; for(i=0;i256;i+) /统计叶子个数 if(HTi.count=0) break; n=i; /用n表示叶子数 m=2*n-1; /m为总结点数for(i=n;im;+i) /叶子结点生成哈夫曼树 Select(HT,i-1,s1,s2); /在HT1.i-1选择parent为0且/weight最小的两个结点，其序号分别为s1和s2 HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.count=HTs1.count+HTs2.count; for(i=0;in;i+) /生成哈夫曼编码 f=i; HTi.bits0=0; while(HTf.parent!=-1) j=f; f=HTf.parent; if(HTf.lchild=j) j=strlen(HTi.bits); memmove(HTi.bits+1,HTi.bits,j+1); /memmove用于从HTi.bits拷贝j+1个字符到HTi.bits+1，如果目标区域和/源区域有重叠的话， /memmove能够保证源串在被覆盖之前将重叠区域的字节拷贝到目标区域中 HTi.bits0=0; else j=strlen(HTi.bits); memmove(HTi.bits+1,HTi.bits,j+1); HTi.bits0=1; fclose(ifp); fclose(ofp);void Print(HuffmanTree HT,int f,int n) /中序遍历 int i; if(HTf.rchild=-1&HTf.lchild=-1) for(i=0;i=0) printf(-); printf(%d %c %sn,HTf.count,HTf.b,HTf.bits); return; /递归出口 Print(HT,HTf.rchild,n+3); /遍历打印右子树 /访问根节点 for(i=0;i=0) printf(-); printf(%dn,HTf.count); Print(HT,HTf.lchild,n+3); /便利打印左子树lvoid Veiw_Huff(HuffmanTree HT) int i; for(i=511;i=0;i-) if(HTi.parent!=-1|HTi.rchild!=-1|HTi.lchild!=-1) break; printf(哈夫曼树:n); Print(HT,i,5); printf(nnnnnnnnnnn); printf(按任意键返回菜单.); getchar();int main() Compress(test.cpp,test1.cpp); Veiw_Huff(HT); return 0; 5 测试与调试5.1个人测试（按组员分工）5.1.1王健测试1.准备一个图片文件test.jpg2打开应用程序，进入压缩功能3.选择文件和压缩后的地址4.点击确定，进行压缩，生成了test.huf压缩文件5.通过张颖部分的解压功能检验，test.huf信息完整5.1.2张颖测试（使用单独测试函数）1.准备一张图片，利用已编好的压缩程序将图片压缩为后缀为.huf的压缩文件。2.运行解压测试程序，选择功能1 解压。3.输入需要解压的文件名以及解压后的文件名4.文件夹中出现解压后的文件，大小与压缩前文件大小一致，解压成功5.1.3刘琪测试/测试程序#define _CRT_SECURE_NO_WARNINGS#include #include int main() struct Count char c; int count; ; int numbers = 0,i; struct Count w256; for (i = 0; i256; i+) wi.c = i; wi.count = 0; FILE *fp; fp = fopen(a.txt, r); char tmp; while (!feof(fp) tmp = getc(fp); wtmp.count+; for (i = 0; i0) numbers += wi.count; if (wi.c = 10) printf(n number=%dn, wi.count); else if (wi.c = 32) printf(space number=%dn, wi.count); else if (wi.c = 9) printf(t number=%dn, wi.count); else if (wi.c = 0) printf(NULL number=%dn, wi.count); else if (wi.c = 13) printf(carriage return number=%dn, wi.count); else printf(%c number=%dn, wi.c, wi.count); printf(File the totle number of characters=%dn, numbers); fclose(fp); return 0;1. 设置测试程序2. 准备测试文件a.txt3. 程序运行结果5.1.4张晓雨测试测试哈夫曼树、哈夫曼编码1.准备测试文件test.cpp2.运行测试程序3.运行结果如下（生成一个哈夫曼树，以及打印其字符和哈夫曼编码）5.2组装与系统测试1.C语言代码组装 在head1.h中声明、定义Select和Compress； 在head2.h中声明、定义DeCompress；2.将C语言函数封装进MFC图形界面实现中。 在MFC工程中调用Compress和DeCompress函数，实现压缩和解压功能。5.3系统运行1. 准备一个图片文件test.jpg2.运用压缩功能，生成test.huf压缩文件3.运用解压功能，生成test1.jpf解压文件4.比较二者，原文件和压缩文件一样，小组程序实现了哈夫曼无算压缩6 课题总结6.1课题评价小组设计哈夫曼软件小巧，使用方便、用户友好。经过多次验证，我们发现，在压缩率方面较之WinRAR等软件表现更出色，且采取无损压缩，不会产生信息丢失，但在压缩解压速度方面较之其他压缩软件稍次，还有待进一步提高。6.2团队