《文件压缩与解压实验报告.pdf》由会员分享，可在线阅读，更多相关《文件压缩与解压实验报告.pdf（18页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、院院系：计系：计 算算 机机 学学 院院实验课程：实验实验课程：实验 3 3实验项目：文本压缩与解压实验项目：文本压缩与解压指导老师：指导老师：开课时间：开课时间：20102010 2011 2011 年度第年度第 1 1 学期学期专专业：业：班班级：级：学学生：生：学学号：号：一、需求分析一、需求分析1.本程序能够实现将一段由大写字母组成的内容转为哈弗曼编码的编码功能以及将哈弗曼编码翻译为字符的译码功能。2.友好的图形用户界面，直观明了，每一个操作都有相应的提示，用户只需按着提示去做，便能轻松实现编码以及译码的效果，编码及译码结果都被保存成txt文档格式，方便用户查看。3.本程序拥有极大的提
2、升空间，虽然现在只能实现对大写字母的译码以及编码，但通过改进鉴别的算法，即能够实现小写字母乃至其他特殊符号等的编码。4.本程序可用于加密、解密，压缩后文本的大小将被减小，更方便传输5.程序的执行命令包括：1）初始化 2）编码 3）译码 4）印代码文件 5）印哈弗曼树 6）退出6.测试数据（1）THIS PROGRAM IS MY FAVOURITE（2）THIS IS MY FAVOURITE PROGRAM BUT THE REPORT IS NOT二、概要设计二、概要设计为实现上述功能，应有哈弗曼结点，故需要一个抽象数据类型。1.哈弗曼结点抽象数据类型定义为：ADT HaffTree数据对
3、象：HaffNode*ht，HaffCode*hc基本操作：Haffman(int w,int n)操作结果：构造哈弗曼树及哈弗曼编码，字符集权值存在数组 w，大小为 n setdep()setdep(int p,int l)操作结果：利用递归，p 为哈弗曼节点序号，l 为哈弗曼节点深度setloc()操作结果：设置哈弗曼节点坐标，用以输出到界面setloc2()操作结果：设置哈弗曼节点坐标，用以输出到文本，默认状态下不启用 ADT HaffTree2.本程序包含 4 个模块1）主程序模块：接受用户要求，分别选择执行初始化编码译码印代码文件印哈弗曼树退出2）哈弗曼树单元模块建立哈弗曼树3）哈弗
4、曼编码单元模块进行哈弗曼编码、译码4）响应用户操作，输出内容到界面或文本各模块之间的关系如下：主程序控制模块建立哈弗曼树进行哈弗曼编码、译码输出内容到界面或文件三、详细设计三、详细设计1.全局变量、结点int m_gcharnum;弗曼树的实现eight=wi;elsehti.weight=0;arent=0;child=-1;child=-1;eightm1&htj.parent=0)eight;htx1.parent=n+i;htx2.parent=n+i;htn+i.weight=htx1.weight+htx2.weight;htn+i.lchild=x1;hthtn+i.lchild
5、.k=0;child=x2;hthtn+i.rchild.k=1;eight;child=i;parent=htchild.parent;while(parent!=0)child=child)for(j=+1;jn;j+)hci.bitj=j;tart=;=0;else if(htj.weightMoveTok.x+4,k.y);pDC-LineTok.lchild.x+4,k.lchild.y);ifk.rchild!=-1)pDC-MoveTok.x+4,k.y);pDC-LineTok.rchild.x+4,k.rchild.y);endl;eightendl;arentendl;ch
6、ildendl;childc;i.s=c;fipwi;arent;child;child;xt)|*.txt|所有文(*.*)|*.*|),NULL);if()=IDOK)m_path1=();xt)|*.txt|所有文件(*.*)|*.*|),NULL);if()=IDOK)m_path2=();UpdateData(FALSE);件ofstream sff(m_path2);i+;for(j=i.start+1;jm_gcharnum;j+)sffi.bitj;xt)|*.txt|所有文件(*.*)|*.*|),NULL);if()=IDOK)AfxMessageBox(译码成功，请保存！
7、);CFileDialoghFileDlg1(false,NULL,NULL,OFN_FILEMUSTEXIST|m_path1=();UpdateData(FALSE);OFN_READONLY|OFN_PATHMUSTEXIST,TEXT(文档文本(*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);if()=IDOK)ifstream ldf(m_path1);child;if(c=0)child;m_path2=();UpdateData(FALSE);ifi.lchild=-1&i.rchild=-1);i=2*m_gcharnum-2;();();elseAfxM
8、essageBox(您尚未执行初始化操作！请先执行初始化操作！);xt)|*.txt|所有文件(*.*)|*.*|),NULL);if()=IDOK)ofstream saf(m_path);/*();n;elsed+;break;if(d=p.dep)for(t1;t1t2-1;t1+)saf;ifp.s=|p.s=)saf0;child!=-1)p.lchild);m_path=();UpdateData(FALSE);if(htp.rchild!=-1)p.rchild);t1+=2;elsed+;safendl;t1=0;t2=0;child;ep-1);f+)saf;endl;chi
9、ld;);CString str1;GetDlgItemText(IDC_EDIT1,str1);xt)|*.txt|所(*.*)|*.*|),NULL);if()=IDOK)m_path=();UpdateData(FALSE);CFile file1(m_path,CFile:modeRead);char*pBuf;int iLen=();pBuf=new chariLen+1;(pBuf,iLen);pBufiLen=0;();SetDlgItemText(IDC_EDIT1,pBuf);xt)|*.txt|所有文件(*.*)|*.*|),NULL);有文件if()=IDOK)m_pat
10、h=();UpdateData(FALSE);CFile file;(m_path,CFile:modeCreate|CFile:modeWrite);CString strValue;GetDlgItemText(IDC_EDIT1,strValue);xt)|*.txt|所有(*.*)|*.*|),NULL);AfxMessageBox(请选择刚才输入的内容所要保存到的位置！);if()=IDOK)m_path=();UpdateData(FALSE);CFile file;(m_path,CFile:modeCreate|CFile:modeWrite);CString strValue
11、;GetDlgItemText(IDC_EDIT1,strValue);xt)|*.txt|所有(*.*)|*.*|),NULL);if()=IDOK)m_path2=();UpdateData(FALSE);ifstream ldf(m_path,ios:in);i+;文件文件for(j=i.start+1;jm_gcharnum;j+)sffi.bitj;AfxMessageBox(代码文件已保存成功！);CDialog:OnOK();4.函数的调用关系图反映了演示程序的层次结构初始化OnHandinputHaffmanMain(主窗口、主文档)编码OnEncodinghinput译码On
12、Decoding印代码文件OnPte印哈弗曼树OnPhafftreeSetdepsetloc四、调试分析四、调试分析1.由于一开始时候编写的时候没有注意使用面向对象的思想，并没有建立哈弗曼树类，程序完成后才将其转为面向对象的方式，修改仓促，因而使得哈弗曼树类丧失了封装性。2.由于对 CString、string 这两种类型不甚熟悉，在实现一些功能，例如输出到界面、输出到文本并且要求控制格式的时候，都屡屡碰壁，即使是现在的输出函数的实现亦未臻于完美。3.在编写本程序的过程中，虽然借鉴了很多功能，美化了界面，但用户界面的设计以及一些功能的实现仍缺乏人性化，而且，在核心程序上并无过多改进，效率与效果
13、都没有提升，反显得本末倒置。4.算法的时空分析1）生成哈弗曼树以及编码的函数在该函数里面，有六个循环体，其中有两次属于循环体嵌套的状况，每次这种情况出现时，都是两次的嵌套，所以该函数的时间复杂度为 O(n2),由此看来耗费的时间是比较多的。2）实现哈弗曼树输出的函数这一函数包括了三个部分，一个是设置结点深度的函数 setdep()，另一个为设置结点坐标函数 setloc(),还有就是本身的程序。先在逐一分析：对于 setdep()，利用的是递归思想，现进行估算，设树高为n，且一个结点占据一层，即有n 个结点，在这种情况下，求第一个结点时，最后一个结点需要被调用 n-1 次，求第二个结点时，最后
14、一个结点需要调用 n-2 次，故对最后一个结点而言，执行完递归操作，它共计被调用 1+2+3+n-1 即 n*(n-1)/2 次，而它的前一个结点被调用 次数将少它一次，故 一共要用的时间 T=1+2+n*(n-1)/2 即 n2*(n-1)2/8+n*(n-1)/4,故时间复杂度为 O(n4),耗费时间巨大。对于 setloc()，用了三个循环，其中包含一个二次循环嵌套，所以时间复杂度为 O(n2)。上述两个函数都用了一些变量来做存储，求深度函数需要记录各个结点的深度，而求坐标则需要记录每个结点的坐标，这些都使程序动用了更多的空间。五、用户手册五、用户手册1.本程序的运环境为 Windows
15、 操作系统，执行文件为2.进入演示程序后即显示用户界面3.选择手动输入可手动输入字符集，当然也可以自动读取字符集4.选择编码，则有两个选项手动输入、从文件中读取。5.选择手动输入，则弹出对话框，可在编辑框里面编辑。6.选择从文件中读取，需要先打开需要读取的文件。7.编码完毕后，要保存代码文件。8.之后就可以选择译码操作了，同样是需要选择译码文件以及保存译码结果到另一个文件。9.执行印代码操作，则弹出对话框，按按钮读取文本，可将文本中的内容读入到编辑框中显示，选择保存文本，可将编辑框内容保存到自定义文本。10.印哈弗曼树操作同样有两个选项，一个是在当前界面显示树，另一个将树保存到文件当中。六、测
16、试结果六、测试结果1.执行初始化操作，选择手动输入，根据提示依次输入字符集大小、空格权值以及各字符及其权值，生成。选择自动输入从现有的从读取字符集及其权值。2.执行编码操作，选择手动输入，弹出对话框，在编辑框里输入测试数据 1 并保存文档，打开保存文档能看到测试数据 1。选择从文本中读取操作后，可从中读取数据，默认为测试数据 2 的数据。最后生成代码文件。将测试数据 1 编码后得到的编码为：000010编码成功。3.执行译码操作，选择刚才保存的文本，翻译结果保存到自定义文本中，在该测试中被保存至中，译码测试数据1 之后，中的内容为：THIS PROGRAM IS MYFAVOURITE，可见译
17、码成功。4.选择印代码文件操作，按下读取文件按钮，读取文档，则其内容显示到编辑框里面，按保存文件，将显示的内容保存到自定义文档中，默认为，输出格式为每行 50 个字符。以下是测试数据 2 在中的情况:0010000100010100000010100100001101由于测试数据 2 里面含有换行符，所以第三行还没有够 50 个字符便换行了。5.执行印哈弗曼树操作，选择显示哈弗曼树，则哈弗曼树显示到界面，选择保存哈弗曼树，则哈弗曼树以凹入表方式保存于自定义文档中。6.执行退出操作，退出程序。七、附录七、附录原程序文件名清单：/输入空格权值对话框实现单元 /输入各字符权值对话框实现单元 /输入字符集大小对话框实现单元 /打印代码文件对话框实现单元 /编码对话框实现单元 /哈弗曼树结点与代码结点定义单元 /主窗口实现单元 /资源类实现单元 /用户界面及画图实现单元