压缩与解压实验报告.doc

学生姓名 学 号 专 业 年级、班级 课程名称 实验3 实验项目 文本解压与压缩 实验时间 年 月 日实验指导老师 实验评分 院 系：计 算 机 学 院实验课程：实验3 实验项目：文本压缩与解压指导老师： 开课时间：2010 2011年度第 1学期专 业：班 级：学 生：学 号：一、需求分析1.本程序能够实现将一段由大写字母组成的内容转为哈弗曼编码的编码功能以及将哈弗曼编码翻译为字符的译码功能。2.友好的图形用户界面，直观明了，每一个操作都有相应的提示，用户只需按着提示去做，便能轻松实现编码以及译码的效果，编码及译码结果都被保存成txt文档格式，方便用户查看。3.本程序拥有极大的提升空间，虽然现在只能实现对大写字母的译码以及编码，但通过改进鉴别的算法，即能够实现小写字母乃至其他特殊符号等的编码。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数据对象：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）响应用户操作，输出内容到界面或文本各模块之间的关系如下：主程序控制模块建立哈弗曼树进行哈弗曼编码、译码输出内容到界面或文件三、详细设计1.全局变量、结点int m_gcharnum;/记录字符集大小全局变量int t;/用于输入框弹出次数的计数int *w;/用于存储各个字符权值的数组int x;/用于计算各个哈弗曼结点x坐标的全局变量int initswitch;/用于判断是否已经进行了初始化操作int printtree;/用于判断哈弗曼树是否已经生成的操作HaffTree HF; /哈弗曼树类struct HaffNodeint weight;/记录结点权值int parent;/记录结点双亲序号int lchild;/记录结点左孩子序号int rchild;/记录结点右孩子序号int x;/记录x坐标int y;/记录y坐标int dep;/记录深度int sn;/记录空格个数int k;/0为左孩子，1为右孩子，-1为根string s;struct HaffCodeint bit28;/记录各结点的哈弗曼编码int start;/记录遍历哈弗曼树的起始位置int weight;/记录结点权值;2.哈弗曼树的实现/函数名：Haffman/功能：生成哈弗曼树，为每一个哈弗曼结点生成哈弗曼编码/函数参数：int w引入各个字符的权值/int n字符集大小void HaffTree:Haffman(int w,int n)int i,j,m1,m2,x1,x2;/m1,m2表示最小、次小x1,x2表示左右孩子for(i=0;i2*n-1;i+)/进行初始化操作，记录权值if(in)hti.weight=wi;else hti.weight=0;/赋权值hti.parent=0;/清空父母序号hti.lchild=-1;/清空左孩子序号hti.rchild=-1;/清空右孩子序号for(i=0;in-1;i+)/寻找最小、次小，生成双亲m1=m2=1000;x1=x2=0;for(j=0;jn+i;j+)if(htj.weightm1&htj.parent=0)/如果权值比最小的小，且未获得双亲（未被访问），将其设为最小m2=m1;x2=x1;m1=htj.weight;x1=j;else if(htj.weightm2&htj.parent=0)/如果权值比次小的小，将其设为次小m2=htj.weight;x2=j;htx1.parent=n+i;htx2.parent=n+i;htn+i.weight=htx1.weight+htx2.weight;htn+i.lchild=x1;hthtn+i.lchild.k=0;/为左孩子添加标记htn+i.rchild=x2;hthtn+i.rchild.k=1;/为右孩子添加标记HaffCode cd;int child,parent;for(i=0;in;i+)cd.start=n-1;cd.weight=hti.weight;child=i;parent=htchild.parent;while(parent!=0)/为每个结点设置哈弗曼编码值，左孩子为0，右孩子为1if(htparent.lchild=child)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;child=parent;parent=htchild.parent;for(j=cd.start+1;jn;j+) hci.bitj=cd.bitj;/为每个结点生成哈弗曼编码hci.start=cd.start;hci.weight=cd.weight;3.主函数和其他函数的实现1）哈弗曼树类的成员函数的实现：/函数名：setdep/功能：利用递归，为哈弗曼树各个结点记录深度/函数参数：无void HaffTree:setdep()int i=2*m_gcharnum-2;setdep(i,1);/函数名：setdep/功能：利用递归，为哈弗曼树各个结点记录深度/函数参数：int p引入哈弗曼结点序号/int l记录深度void HaffTree:setdep(int p,int l)if(p!=-1)setdep(htp.lchild,l+1);htp.dep=l;setdep(htp.rchild,l+1);/函数名：setloc/功能：为各个哈弗曼结点确定坐标，以输出到界面/函数参数：无void HaffTree:setloc() setdep();int f=1;if(initswitch=1)stack s;int k;int i=2*m_gcharnum-2;while(!s.empty()|i!=-1)/如果栈不为空且序号不为-1while(i!=-1)s.push(i);/入栈i=hti.lchild;/获取左孩子的序号if(!s.empty()k=s.top();/出栈s.pop();if(k!=-1)htk.x=x+f*10;htk.y=htk.dep*30;i=htk.rchild;/获取右孩子的序号f+;/函数名：setloc2，利用层次遍历思想实现/功能：为各个哈弗曼结点确定坐标，以输出到文档/函数参数：无void HaffTree:setloc2()if(initswitch=1)queue q;int k=2*m_gcharnum-2;htk.sn=1024;/设置第一个结点的空格值为1024个htk.k=-1;/标记第一个结点为根结点int d0=11;int d=1;int p;if(k!=-1)q.push(k);/入队while(!q.empty()while(d FillRect(rect,&m_brushBackground); /用背景画刷填充区域 OnEraseBkgnd(pDC);CPen penblack;/定义画笔CBrush brush1;/定义画刷COLORREF oldbackcolor=RGB(255,255,255);/获取背景颜色penblack.CreatePen(PS_SOLID,2,RGB(255,0,0);/为画笔设定大小和颜色pDC-SelectObject(&penblack);brush1.CreateSolidBrush(oldbackcolor);/为画刷设定颜色pDC-SelectObject(&brush1);if(printtree=1)/如果显示树的按钮已被按下，则执行下面的内容HF.setloc();/设置各个节点坐标/利用非递归中序遍历思想画图stack s;建栈int k;int i=2*m_gcharnum-2;while(!s.empty()|i!=-1)while(i!=-1)s.push(i);/入栈i=HF.hti.lchild;/获取左孩子序号if(!s.empty()k=s.top();/出栈s.pop();if(k!=-1)CString str(HF.htk.s.data();/获取当前哈弗曼结点的数据pDC-TextOut(HF.htk.x,HF.htk.y,str);/输出str的值i=HF.htk.rchild;/获取右孩子序号/画线用if(HF.htk.lchild!=-1)pDC-MoveTo(HF.htk.x+4,HF.htk.y);pDC-LineTo(HF.htHF.htk.lchild.x+4,HF.htHF.htk.lchild.y);if(HF.htk.rchild!=-1)pDC-MoveTo(HF.htk.x+4,HF.htk.y);pDC-LineTo(HF.htHF.htk.rchild.x+4,HF.htHF.htk.rchild.y);/函数名：CP3View:OnHandinput/功能：执行手动输入操作/函数参数：CDC* pDCvoid CP3View:OnHandinput() / TODO: Add your command handler code hereifstream fip(HaffmanTree.txt);/利用文件流打开文件int i;if(!fip)/判断文件HaffmanTree.txt是否已经存在，若存在，则自动读取，若不存在，则手动输入fip.close();fstream fop(HaffmanTree.txt,ios:out);/以写方式打开文件DINIT dint;/打开输入字符集大小对话框dint.DoModal();if(m_gcharnum!=0)t=0;DBLANKW dblankw;/打开输入空格权值对话框dblankw.DoModal();t+;for(t=1;tm_gcharnum;t+)DCHARW dcharw;/打开输入字符及其权值对话框dcharw.DoModal();HF.Haffman(w,m_gcharnum);/生成哈弗曼树及代码fopm_gcharnumendl;for(i=0;im_gcharnum;i+)fopHF.hti.sendl;/写入字符fopHF.hti.weightendl;/写入字符所对应的权值fopHF.hti.parentendl;/写入双亲序号fopHF.hti.lchildendl;/写入左孩子序号fopHF.hti.rchildm_gcharnum;/读取字符集大小char c4;HF.ht=new HaffNode2*m_gcharnum-1;HF.hc=new HaffCodem_gcharnum;w=new intm_gcharnum;for(i=0;ic;HF.hti.s=c;fipwi;/读取字符权值赋给w数组fipHF.hti.parent;/读取双亲序号fipHF.hti.lchild;/读取左孩子序号fipHF.hti.rchild;/读取右孩子序号HF.Haffman(w,m_gcharnum);/生成哈弗曼树fip.close();/关闭文件AfxMessageBox(初始化成功！);initswitch=1;/函数名：CP3View:OnEncodinghinput/功能：执行编译手动输入操作/函数参数：CDC* pDCvoid CP3View:OnEncodinghinput() / TODO: Add your command handler code hereif(initswitch=1)/判断是否已经初始化DTOBETRAIN dtbt;/打开手动输入对话框dtbt.DoModal();elseAfxMessageBox(您尚未执行初始化操作！请先执行初始化操作！);/函数名：CP3View:OnEncodingainput/功能：执行自动编码/函数参数：CDC* pDCvoid CP3View:OnEncodingainput() / TODO: Add your command handler code hereif(initswitch=1)/判断是否已经初始化CString m_path1,m_path2;/m_path1记录需要编码文件的路径,m_path2记录编码完成后文件的保存路径string cmp;char temp;AfxMessageBox(请选择要编码的文件的位置！);CFileDialog hFileDlg(true,NULL,NULL,OFN_FILEMUSTEXIST | OFN_READONLY | OFN_PATHMUSTEXIST,TEXT(文档文本 (*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);if(hFileDlg.DoModal() = IDOK)m_path1 = hFileDlg.GetPathName();/获取编码文件路径UpdateData(FALSE);ifstream ldf(m_path1,ios:in);/以读方式打开文件AfxMessageBox(请选择代码文件的保存位置！);CFileDialog hFileDlg1(false,NULL,NULL,OFN_FILEMUSTEXIST | OFN_READONLY | OFN_PATHMUSTEXIST,TEXT(文档文本 (*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);if(hFileDlg1.DoModal() = IDOK)m_path2 = hFileDlg1.GetPathName();UpdateData(FALSE);ofstream sff(m_path2);/以写方式打开文件while(temp=ldf.get()!=EOF)cmp=temp;int i=0,j=0;if(temp=n)/判断是否为回车sffn;elseif(temp=0x20)/判断是否为空格i=0;elsewhile(cmp!=HF.hti.s)i+;for(j=HF.hci.start+1;jm_gcharnum;j+) sffHF.hci.bitj;/比较字符，寻找对应的字符并将字符对应的哈弗曼编码写入结点AfxMessageBox(代码文件已保存成功！);elseAfxMessageBox(您尚未执行初始化操作！请先执行初始化操作！);/函数名：CP3View:OnDecoding/功能：执行译码操作/函数参数：CDC* pDCvoid CP3View:OnDecoding() / TODO: Add your command handler code hereif(initswitch=1)/判断是否已经初始化CString m_path1,m_path2;/m_path1记录需要译码的文件的路径,m_path2记录译码后保存的文件的路径AfxMessageBox(请选择你需要译码的文件！);CFileDialog hFileDlg(true,NULL,NULL,OFN_FILEMUSTEXIST | OFN_READONLY | OFN_PATHMUSTEXIST,TEXT(文档文本 (*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);if(hFileDlg.DoModal() = IDOK)m_path1 = hFileDlg.GetPathName();UpdateData(FALSE);AfxMessageBox(译码成功，请保存！);CFileDialog hFileDlg1(false,NULL,NULL,OFN_FILEMUSTEXIST | OFN_READONLY | OFN_PATHMUSTEXIST,TEXT(文档文本 (*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);if(hFileDlg1.DoModal() = IDOK)m_path2 = hFileDlg1.GetPathName();UpdateData(FALSE);ifstream ldf(m_path1);/以读方式打开文件ofstream saf(m_path2);/以写方式打开文件char c;int i=2*m_gcharnum-2;while(c=ldf.get()!=EOF)if(c=n)/如果字符为回车，输出回车safendl;elseif(c=1)/如果字符为1，获取右孩子序号，走向右孩子i=HF.hti.rchild;if(c=0)/如果字符值为0，获取左孩子序号走向左孩子i=HF.hti.lchild;if(HF.hti.lchild=-1&HF.hti.rchild=-1)/如果当前结点没有左孩子也没有右孩子，则输出当前结点所存储的字符if(i=0)saf ;i=2*m_gcharnum-2;elsesafHF.hti.s;i=2*m_gcharnum-2;ldf.close();saf.close();elseAfxMessageBox(您尚未执行初始化操作！请先执行初始化操作！);/函数名：CP3View:OnSavhafftree/功能：保存哈弗曼树/函数参数：CDC* pDCvoid CP3View:OnSavhafftree() / TODO: Add your command handler code hereCString m_path;/记录保存哈弗曼树文件的路径CFileDialog hFileDlg(false,NULL,NULL,OFN_FILEMUSTEXIST | OFN_READONLY | OFN_PATHMUSTEXIST,TEXT(文档文本 (*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);if(hFileDlg.DoModal() = IDOK)m_path = hFileDlg.GetPathName();UpdateData(FALSE);ofstream saf(m_path);/*HF.setloc2();/该段内容为输出哈弗曼树到文件的第二种方法，可输出树形，但由于太过占据空间，文档存储时不得不换行，导致树形扭曲，故舍弃此法queue q;int p;int i=0;int d=1;int t1=0,t2=0;int d0=11;int k=2*m_gcharnum-2;if(k!=-1)q.push(k);while(!q.empty()while(d=d0)if(!q.empty()p=q.front();t2=HF.htp.sn;elsed+;break;if(d=HF.htp.dep)for(t1;t1t2-1;t1+)saf ;if(HF.htp.s= |HF.htp.s=)saf0;/如果为空，输出0elsesafHF.htp.s;/否则输出字符q.pop();if(HF.htp.lchild!=-1)q.push(HF.htp.lchild);if(htp.rchild!=-1)q.push(HF.htp.rchild);t1+=2;elsed+;safendl;t1=0;t2=0;/print(2*m_gcharnum-2,1,saf);*/以上内容用于实现输出树到文本，树形，不是凹入树，只是效果不佳，下面的方法则是输出凹入树。stack s;/建栈int k;int i=2*m_gcharnum-2;while(!s.empty()|i!=-1)while(i!=-1)s.push(i);i=HF.hti.rchild;/获取右孩子序号if(!s.empty()k=s.top();s.pop();if(k!=-1)for(int f=0;f6*(HF.htk.dep-1);f+) saf ;/输出空格safHF.htk.sendl;/输出字符i=HF.htk.lchild;/获取左孩子序号saf.close();/关闭文件3）一些对话框按钮的响应函数的实现：/ DBLANKW message handlers/获取字符集大小、字符及其权值的对话框实现代码与该段代码类似/功能：读取空格的权值void DBLANKW:OnOK() / TODO: Add extra validation hereHF.htt.s.assign();CString str1;GetDlgItemText(IDC_EDIT1,str1);/获取编辑框内容wt=atoi(str1);/转换为整型CDialog:OnOK();/ DPRINTCODE message handlers/读取文档按钮/功能：执行从文件中读取操作，将代码文件里的内容以每行50个字符的格式输出到编辑框中void DPRINTCODE:OnButton1() / TODO: Add your control notification handler code hereCString m_path;CFileDialog hFileDlg(true,NULL,NULL,OFN_FILEMUSTEXIST | OFN_READONLY | OFN_PATHMUSTEXIST,TEXT(文档文本 (*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);if(hFileDlg.DoModal() = IDOK)m_path = hFileDlg.GetPathName();UpdateData(FALSE);CFile file1( m_path,CFile:modeRead); char *pBuf; int iLen=file1.GetLength(); pBuf =new chariLen+1; file1.Read(pBuf,iLen); pBufiLen=0; file1.Close(); SetDlgItemText(IDC_EDIT1,pBuf);/写入文档按钮/功能：执行输出到文件操作，将代码文件里的内容以每行50个字符的格式输出到另一文件中void DPRINTCODE:OnButton2() / TODO: Add your control notification handler code hereCString m_path;CFileDialog hFileDlg(false,NULL,NULL,OFN_FILEMUSTEXIST | OFN_READONLY | OFN_PATHMUSTEXIST,TEXT(文档文本 (*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);if(hFileDlg.DoModal() = IDOK)m_path = hFileDlg.GetPathName();UpdateData(FALSE);CFile file;file.Open(m_path,CFile:modeCreate|CFile:modeWrite);CString strValue;GetDlgItemText(IDC_EDIT1,strValue);/此处为编辑框的内容 file.Write(strValue,strValue.GetLength();file.Close();ofstream saf(m_path);int i=0,k=0,t;string str;str=strValue.GetBuffer(0);t=str.length();while(kt)for(i=0;i50;i+)/如果到达第50个，换行if(k=t)break;k+;if(strValuek=n)/如果本身存在换行，输出换行，跳出循环safendl;k+;break;elsesafstrValuek;k+;if(strValuek-1!=n&k!=t)safendl;i=0;saf.close();AfxMessageBox(打印完毕！);/ DTOBETRAIN message handlers/手动输入编译文件的确定按钮/功能：将编辑框内容保存到某一文件并对该文件内容进行编码void DTOBETRAIN:OnOK() / TODO: Add extra validation hereCString m_path;CFileDialog hFileDlg(false,NULL,NULL,OFN_FILEMUSTEXIST | OFN_READONLY | OFN_PATHMUSTEXIST,TEXT(文档文本 (*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);AfxMessageBox(请选择刚才输入的内容所要保存到的位置！);if(hFileDlg.DoModal() = IDOK)m_path = hFileDlg.GetPathName();UpdateData(FALSE);CFile file;file.Open(m_path,CFile:modeCreate|CFile:modeWrite);CString strValue;GetDlgItemText(IDC_EDIT1,strValue);/获取编辑框的内容 file.Write(strValue,strValue.GetLength();/将编辑框内容写入到文档中file.Close();/关闭文档CString m_path2;string cmp;char temp;AfxMessageBox(请选择代码文件的保存位置！);CFileDialog hFileDlg1(false,NULL,NULL,OFN_FILEMUSTEXIST | OFN_READONLY | OFN_PATHMUSTEXIST,TEXT(文档文本 (*.txt)|*.txt|所有文件(*.*)|*.*|),NULL);if(hFileDlg1.DoModal() = IDOK)m_path2 = hFileDlg1.GetPathName();UpdateData(FALSE);ifstream ldf(m_path,ios:in);/以读方式打开文档ofstream sff(m_path2);/以写方式打开文档while(temp=ldf.get()!=EOF)/如果未到达文件结尾，则执行循环体内代码cmp=temp;int i=0,j=0;if(temp=n)/如果为换行，输出换行符到文档sffn;elseif(temp=0x20)i=0;elsewhile(cmp!=HF.hti.s)i+;for(j=HF.hci.start+1;jm_gcharnum;j+) sffHF.hci.bitj;AfxMessageBox(代码文件已保存成功！);CDialog:OnOK();4.函数的调用关系图反映了演示程序的层次结构Haffman印哈弗曼树OnPhafftree印代码文件OnPte译码OnDecoding编码OnEncodinghinputOnEncodingainput初始化OnHandinputOnAutogetMain(主窗口、主文档)Setdepsetloc四、调试分析1.由于一开始时候编写的时候没有注意使用面向对象的思想，并没有建立哈弗曼树类，程序完成后才将其转为面向对象的方式，修改仓促，因而使得哈弗曼树类丧失了封装性。2.由于对CString、string这两种类型不甚熟悉，在实现一些功能，例如输出到界面、输出到文本并且要求控制格式的时候，都屡屡碰壁，即使是现在的输出函数的实现亦未臻于完美。3.在编写本程序的过程中，虽然借鉴了很多功能，美化了界面，但用户界面的设计以及一些功能的实现仍缺乏人性化，而且，在核心程序上并无过多改进，效率与效果都没有提升，反显得本末倒置。4.算法的时空分析1）生成哈弗曼树以及编码的函数 在该函数里面，有六个循环体，其中有两次属于循环体嵌套的状况，每次这种情况出现时，都是两次的嵌套，所以该函数的时间复杂度为O(n2),由此看来耗费的时间是比较多的。2）实现哈弗曼树输出的函数这一函数包括了三个部分，一个是设置结点深度的函数setdep()，另一个为设置结点坐标函数setloc(),还有就是本身的程序。先在逐一分析：对于setdep()，利用的是递归思想，现进行估算，设树高为n，且一个结点占据一层，即有n个结点，在这种情况下，求第一个结点时，最后一个结点需要被调用n-1次，求第二个结点时，最后一个结点需要调用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)。上述两个函数都用了一些变量来做存储，求深度函数需要记录各个结点的深度，而求坐