数据结构实习报告.doc

数据结构实习报告姓名：吴加剑班级：114102学号：20101000094学院：信息工程学院第一题：软件压缩/解压缩软件 Szip（Huffman算法及应用）一需求规格说明：问题：利用哈夫曼编码进行对已经存在的文件进行重新编码，也就是压缩，然后再对该文件进行解码，即解压。二总体分析与设计（1） 设计思想：存储结构主要是采取动态分配内存的方法用数组进行存储，在进行压缩的时候写进文件的表头是自己定义的结构体，我把码长在0-8之间，8-16之间，16-32之间的分别定义了结构体，这三种结构体都具备data（即ASCII码值），码长，不同的是记录哈夫曼编码的指针类型，根据码长的不同指针类型分别为BYTE类型，WORD类型， unsigned int类型。主要的算法思想是Huffman算法思想和移位，拼接（2） 设计表示：我设计的是先读出需要压缩的文件，然后利用哈弗曼将其重新编码从而达到压缩的目的，解压缩则刚好相反。（3） 详细设计表示：主要算法框架是：先读一遍文件，统计出每个ASCII码值的频率，并将不为0的频率当作参数来建立Huffman树，然后获得他们的Huffman编码，码长和ASCII值，把码长在0-8之间的写在一起，8-16之间的写在一起，16-32之间的写在一起，然后写进文件，这就是表头。然后再读一遍原文件，一个字节一个字节的读，然后将他们拼成32位写进一个新的文件，这就是压缩后的文件。解码的时候先从压缩的文件中将表头读出来，然后再依次读32位，根据表头信息来进行解码。三 编码 首先比较困难的是Huffman传参数的下标，我是从0开始的，而书上的函数代码参数下标是从1开始的，这个问题比较好解决，只要将建Huffman树的函数中有一个地方的数组下标减1就可以了。第二个问题是有很多ASCII码的频率为0，此时需要将它们从数组中删除，下面的一个问题比较难解决，因为想让表头尽可能的小，所以我想分情况，码长在0-8之间的指针用BYTE类型，码长在8-16之间的指针用WORD类型，码长在16-32之间的码长用unsigned int类型，但是一开始写成了通用的结构体，结果码长的指针用的是void型，结果读出来的时候长度不是因指针的长度不同而改变，所以我就改成了用三个不同的结构体，并且分别记录下每个结构体的个数。接下来在压缩拼位时一开始用错了，用成了有符号的，结果发现错了，而且还有一个错误是在右移32位是和我预先设想的不同，所以我将其单独列为了一种情况。接下来就是解码的过程，对我来说，一开始写解码的代码不是很费时间，但是有很多情况没有想全面，结果调程序花了好几天的时间，而且一开始压的时候比原文件都大，始终想不通是为什么，最后才发现是循环的控制条件写错了，我把两个个数弄混了，现在我的程序还有一点点的问题，就是中间解码的时候会有一点乱码，解码时还有一个问题就是最后读最后一次的时候会有不足32位的情况，这时要将多余的位数记下来，否则解码的时候会有多余的字符。四 程序及算法分析 使用说明：首先选择数字0或1或2，0代表结束，1代表压缩，2代表解压缩，然后键入文件的地址，再按回车键就行了。程序运行结果：压缩后的文件在一个文本文档中，而还原后的文件在另一个文件中。改进思想：可以用重构Huffman树来解码，这样出错的几率就小了，还有，有的地方控制循环的条件可以缩小一点。经验与体会：通过做题目一使我对Huffman编码的思想有了具体而深刻的体会，对文件的读写函数更加了解了，也亲自操作了移位与拼接。对指针的运用更加灵活了。时间复杂度：因为我为了拼接和解码的时候方便些，所以在一开始做了些准备工作，所以循环用的比较多，有的时候是外面一个循环，里面还有一个循环，所以时间复杂度有点高，大部分函数到了n的平方级别。五 附录/哈夫曼编码压缩解压缩程序.cpp #include #include #include #include struct head 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; cout请您输入需要压缩的文件：; gets(filename); ifp=fopen(filename,rb);/以二进制方式打开filename if(ifp=NULL) cout文件打开失败!; return; cout请您输入压缩后的文件名：; gets(outputfile); ofp=fopen(strcat(outputfile,.hub),wb); if(ofp=NULL) cout压缩文件失败!; return; flength=0; while(!feof(ifp) fread(&c,1,1,ifp); /读取文件 headerc.count+; /字符重复出现频率+1 flength+; /字符出现原文件长度+1flength-; length1=flength; /原文件长度用作求压缩率的分母 headerc.count-; for(i=0;i512;i+) if(headeri.count!=0) headeri.b=(unsigned char)i; /*将每个哈夫曼码值及其对应的ASCII码存放在一维数组headeri中， 且编码表中的下标和ASCII码满足顺序存放关系*/ else headeri.b=0; headeri.parent=-1;headeri.lch=headeri.rch=-1; /对结点进行初始化 for(i=0;i256;i+) /根据频率（权值）大小，对结点进行排序，选择较小的结点进树 for(j=i+1;j256;j+) if(headeri.countheaderj.count) tmp=headeri; headeri=headerj; headerj=tmp; for(i=0;i256;i+) if(headeri.count=0) break; n=i; /外部叶子结点数为n个时，内部结点数为n-1，整个哈夫曼树的需要的结点数为2*n-1. m=2*n-1; for(i=n;im;i+) /构建哈夫曼树 min1=999999999; /预设的最大权值，即结点出现的最大次数 for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count=headerpt1.count; headerpt1.parent=i; /依据parent域值（结点层数）确定树中结点之间的关系 headeri.lch=pt1; /计算左分支权值大小 min1=999999999; for(j=0;jheaderj.count) pt1=j; min1=headerj.count; continue; headeri.count+=headerpt1.count; headeri.rch=pt1; /计算右分支权值大小 headerpt1.parent=i; for(i=0;in;i+) /哈夫曼无重复前缀编码 f=i; headeri.bits0=0; /根结点编码0 while(headerf.parent!=-1) j=f; f=headerf.parent; 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(&flength,sizeof(int),1,ofp);/*用来将数据写入文件流中，参数flength指向欲写入的数据地址，总共写入的字符数以参数size*int来决定，返回实际写入的int数目1*/ fseek(ofp,8,SEEK_SET); buf0=0; /定义缓冲区,它的二进制表示00000000 f=0; pt1=8; /*假设原文件第一个字符是A，8位2进制为01000001，编码后为0110识别编码第一个0，那么我们就可以将其左移一位，看起来没什么变化。下一个是1，应该|1，结果00000001 同理4位都做完，应该是00000110，由于字节中的8位并没有全部用完，我们应该继续读下一个字符，根据编码表继续拼完剩下的4位，如果字符的编码不足4位，还要继续读一个字符，如果字符编码超过4位，那么我们将把剩下的位信息拼接到一个新的字节里*/ while(!feof(ifp) c=fgetc(ifp); f+; for(i=0;i=8) /对哈夫曼编码位操作进行压缩存储 for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c0) /对哈夫曼编码位操作进行压缩存储 strcat(buf,00000000); for(i=0;i8;i+) if(bufi=1) c=(c1)|1; else c=c1; fwrite(&c,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); for(i=0;in;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;f8;f+) strcat(headeri.bits,0); while(headeri.bits0!=0) c=0; for(j=0;j8;j+) /字符的有效存储不超过8位，则对有效位数左移实现两字符编码的连接 if(headeri.bitsj=1) c=(c1)|1; /|1不改变原位置上的“0”“1”值 else c=c1; strcpy(headeri.bits,headeri.bits+8); /把字符的编码按原先存储顺序连接 fwrite(&c,1,1,ofp); length2=pt1-;div=(double)length1-(double)length2)/(double)length1; /计算文件的压缩率 fclose(ifp); fclose(ofp); cout压缩文件成功!; cout压缩率为 div*100%endl; return; /*解压缩*/void uncompress() char filename255,outputfile255,buf255,bx255; unsigned char c; long i,j,m,n,f,p,l; long flength; FILE *ifp,*ofp; cout请您输入需要解压缩的文件：; gets(filename); ifp=fopen(strcat(filename,.hub),rb); if(ifp=NULL) cout文件打开失败!; return; cout请您输入解压缩后的文件名：; gets(outputfile); ofp=fopen(outputfile,wb); if(ofp=NULL) cout解压缩文件失败!; return; fread(&flength,sizeof(long),1,ifp); /读取原文件长度，对文件进行定位 fread(&f,sizeof(long),1,ifp); fseek(ifp,f,SEEK_SET); fread(&n,sizeof(long),1,ifp); for(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); m=0; bx0=0; while(1) /通过哈夫曼编码的长短，依次解码，从原来的位存储还原到字节存储 while(strlen(bx)f;l-) /在单字节内对相应位置补0 strcat(bx,0); strcat(bx,buf); for(i=0;in;i+) if(memcmp(headeri.bits,bx,headeri.count)=0) break; strcpy(bx,bx+headeri.count); /*从压缩文件中的按位存储还原到按字节存储字符， 字符位置不改变*/ c=headeri.b; fwrite(&c,1,1,ofp); m+; /统计解压缩后文件的长度 if(m=flength) break; /flength是原文件长度 fclose(ifp); fclose(ofp); cout解压缩文件成功!; if(m=flength) /对解压缩后文件和原文件相同性比较进行判断（根据文件大小）cout解压缩文件与原文件相同!; else cout解压缩文件与原文件不同!; return; 第二题：灰度图像压缩/解压缩类的实现（动态规划算法的应用）一需求规格说明： 问题：对位图图像进行压缩和解压。二总体分析与设计设计思想：存储结构主要是采取动态分配内存的方法用数组进行存储，题目二的表头不同于题目一，它的表头前面是固定的Fileheader，Infoheader和调色板。主要算法思想是动态规划思想和移位，拼接。设计表示：我建立的MFC是基于对话框的，我的工程名字叫做BitMapCompress，题目二的调用过程比题目一简单，就两个类，由BitMapCompressDlg来调用我自己写的类MyMap，MyMap里有读位图，压缩，写文件和解压，具体调用如下图： BitMapCompressDlg MyMap （4） 详细设计表示：先读位图，将里面的Fileheader，Infoheader和调色板读出来，然后将位图的灰度值读出来，放进一个GLubyte型的数组里，然后进行第一次分段，把像素存储位相同的分在一起，并记录下段的长度和存储的位数，再利用动态规划的思想进行第二次分段，找出每段中存储位数最长的，然后算出总的位数，再计算出所需int型数组的长度，将每个灰度值按其需要的长度拼成32位然后一次性写进文件，在此之前还需要将Fileheader，Infoheader和调色板写进文件。这就是压缩过的图像。解码的时候先从压缩的文件中将Fileheader，Infoheader和调色板读出来，然后根据前面记录下来的段的长度和存储位数进行解码。三 编码 最开始困惑的是怎么读位图，因为一开始不知道老师给了读位图的函数，所以不知道怎么开始。第二个遇到的问题是不知道位图有一个调色板，最后在网上搜了一下才明白调色板的结构。我还犯了一个错误是把将灰度值为0的表示位数写成了0，造成死循环，接下来一个很困扰我的问题是压缩时我想利用题目一中压缩的办法，就得把每个m_data每个位数都记录下来，可是一开始我把段数和m_data的个数给弄混了，所以就花了很长时间。因为压缩用得是题目一的方法，所以出的问题不是很多，到了解码的时候又出现了好多的问题。最开始困扰我的是记录每段长度的类型，因为要写进文件，所以希望它尽可能的小，所以一开始采用的是BYTE型，但是一旦大于256，就会出错，变成了另外的一个数，但是用int存又太大，所以就把每个位数都减1，这样就不会出现之前那样的问题了，但是用的时候要加1。四程序及算法分析 使用说明： 当第一次弹出对话框时，按ReadMap，然后选择要压缩的图像，第二次弹出对话框时，按Compress，然后新建一个文本文档，第三次弹出对话框时，按Decode，然后选择刚才新建的那个文本文档，然后它会接着弹出一个对话框，此时再新建一个图像，最终还原成的图像就在最后建的那个图像中，而压缩的图像在第一次新建的文本文档中。程序运行结果：压缩后的图像在一个文本文档中，而还原后的图像在另一个文件中。改进思想：压缩后的文本文档可以用题目一的Huffman方法再压一次。这样压完的图像就更小了。而且图像的表头也可以拼完后写进去。或者也用Huffman压一遍。经验与体会：通过做题目二使我对动态规划思想有了一次具体而深刻的体会。对位图的读写函数了解了一些，对位图的构成明白了一些。时间复杂度：与题目一相同，大部分函数的时间复杂度都为n的平方级别。五 附录 读位图： bool MyMap:ReadBMP(CString filename)GLuinttype = GL_RGBA;/ Set the default OpenGL mode to RGBAGLuintm_bpp;/ Image color depth in bits per pixelGLuintm_width;/ Image widthGLuintm_height; / Image heightFILE* file = fopen(filename, rb);if (file=NULL)MessageBox(NULL, Could not open texture file, ERROR, MB_OK);return false;fread(&FileHeader, sizeof(BITMAPFILEHEADER), 1, file);/ Read the bitmap file headerif (FileHeader.bfType != 0x4D42)/ Check for the universal bitmap idMessageBox(NULL, Could not match BMP type, ERROR, MB_OK);fclose(file);return false;fread(&InfoHeader, sizeof(BITMAPINFOHEADER), 1, file);/ Read the bitmap information header switch(InfoHeader.biBitCount) case 1:size=2; break; case 4:size=16; break; case 8:size=256; break; default:size=0; break; color=new RGBQUADsize;fread(color,sizeof(RGBQUAD),size,file);fseek(file, FileHeader.bfOffBits, SEEK_SET);/ Advance the file pointer to the beginning of the bitmap datam_width = InfoHeader.biWidth;m_height = InfoHeader.biHeight;m_bpp = InfoHeader.biBitCount;ImageSize = m_width * m_height * m_bpp/8;m_data = new unsigned char ImageSize;/ Allocate the bitmap image dataif (m_data=NULL)/ Confirm memory allocationMessageBox(NULL, Could not allocate memory for image, SHUTDOWN ERROR,MB_OK | MB_ICONINFORMATION);fclose(file);return false;fread(m_data, 1, ImageSize, file);/ Read the bitmap image dataif (m_data=NULL)/ Make sure bitmap image data was readMessageBox(NULL, Could not read image data, SHUTDOWN ERROR,MB_OK | MB_ICONINFORMATION);fclose(file);return false;return true; 最优分段：void MyMap:Vbits(BYTE l, BYTE b, int n, int s, int kay)int L=256,header=11;s0=0;for(int i=1;i=n;i+)int lsum=li;int bmax=bi;si=si-1+lsum*bmax;kayi=1;for(int k=2;k=i&lsum+li-k+1=L;k+)lsum+=li-k+1;if(bmaxsi-k+lsum*bmax)si=si-k+lsum*bmax;kayi=k;si+=header;void MyMap:Traceback(int kay,int n)int *p;int temp=n;p=new intn;int m=0;int k=0;while(n)pm=n-kayn;m+;n=n-kayn;Second=new intm+1;for(int i=0,j=m-1;i=0;i+,j-)Secondi=pj+1;Secondm=temp+1;m_count=m;压缩： void MyMap:Compress(CString cs)BYTE *max;/记每一段的位数减1max=new BYTEm_count;for(int i=0;im_count;i+)maxi=0;int c=0;/记总的位数/int k=0;int n=0;BYTE more=0;unsigned int *arry;BYTE *l;/记录每段的长度l=new BYTEm_count;int s=0;for(int i=0;im_count;i+)int s=0;for(int t=Secondi;tmaxi) maxi=BitPerPixelt;li=s-1;c=c+(li+1)*maxi; n=c/32; more=c-n*32; if(more=0) arry=new unsigned intn; for(int i=0;in;i+) arryi=0; m_s=n; else arry=new unsigned intn+1; for(int i=0;in+1;i+) arryi=0; m_s=n+1; int *number; number=new intImageSize; int flag=0; int m=0; int amount=32; int j=0; while(mm_count) for(int i=0;ilm+1;i+) numberflag=maxm; flag+; m+; for(int i=0;inumberi) arryj=(unsigned int)m_dataiextra)|arryj); amount=32-extra; j+; if(amount!=32) arryj=(unsigned int)m_dataiamount)|arryj); bool flg=false; flg=m_wfile.Open(cs,CFile:modeCreate| CFile:modeWrite,0); if(flg) m_wfile.Write(&FileHeader,sizeof(BITMAPFILEHEADER); m_wfile.Write(&InfoHeader, sizeof(BITMAPINFOHEADER); m_wfile.Write(color,sizeof(RGBQUAD)*size); m_wfile.Write(l,sizeof(BYTE)*m_count); m_wfile.Write(max,sizeof(BYTE)*m_count); m_wfile.Write(arry,sizeof(unsigned int)*m_s); if(more) m_wfile.Write(&more,sizeof(BYTE); m_wfile.Close(); 解压： void MyMap:Decode(CString c)BITMAPFILEHEADERm_FileHeader;BITMAPINFOHEADERm_InfoHeader;RGBQUAD *m_color; m_color=new RGBQUADsize;BYTE *m_max;m_max=new BYTEm_count;BYTE *m_l;m_l=new BYTEm_count;unsigned int *m_arry;m_arry=new unsigned intm_s;bool flg=false;bool f=false;BYTE m_more;GLubyte *data;data=new GLubyteImageSize;flg=m_rfile.Open(c,CFile:modeRead,0);CFile m_file;CFileDialog diaTool(true);CString cs;if(diaTool.DoModal()=IDOK)cs=diaTool.GetPathName();f=m_file.Open(cs,CFile:modeCreate| CFile:modeWrite,0);if(flg)m_rfile.R