《数据结构与算法》
课程设计报告
学 号： 2010100****
班级序号： 114103
姓 名： 刘洋
指导教师： 陈启浩
成 绩：
中国地质大学信息工程学院空间信息工程系
20##年 2 月
课程设计报告
一、软件压缩/解压缩软件 Szip（Huffman算法及应用）
1．需求规格说明
利用哈夫曼编码对一个现有文件进行重新编码行成新的文件，可以减小文件大小，减少存储空间，这也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。
即求解的问题是，根据哈夫曼编码的知识写一个压缩/解压缩软件。
2．总体分析与设计
（1）设计思想：
主要的算法思想及其存储结构：采用课程实习已经写过的huffman编码程序对要压缩文件中字符进行读取，统计字符出现频率，并进行字符编码。将编码后的字符以链表形式存储其所编的huffman码，并以该字符建立链表的字典索引。重新读取待压缩文件并根据链表搜索其huffman编码按顺序写入一暂存文件liuyang1.txt中保存。根据liuyang1.txt中的编码进行8个数字一压缩写入压缩文件中。（压缩文件头部首先要写入字典编码等重要信息，以方便解码需求）。解码时首先以二进制形式读取压缩文件中存入的字典编码信息，根据其字符频率信息重新构造huffman树，与此同时将剩余压缩文件中每个字符解压缩成8个字符（与liuyang1.txt对应）写入暂存的文件liuyang3.txt中。再依次据暂存文件liuyang3.txt读取huffman编码数字，根据建立的huffman搜索树进行解码还原成带压缩文件。
（2）设计表示：
具体的压缩实例部分代码：
//主程序中void main（）
//省略其统计字符出现频率的代码
cout<<"开始构建huffman树并压缩……"<<" ";
BinaryTree<Hz> d;
//Hz *c=new Hz[i+1]; Hz是专门用来存储字典的类其中只包含私有变量char letter;字符
int count;字符统计频率这俩个信息。及huffman每个节点均为Hz类型
d=HuffmanTree(c,e-1);//构建huffman树的函数，d为返回的huffman树
SortedChain<BinaryTreeNode<Hz>,char> cc;C=&cc;//定义链表用来存储字典编码信息
co=-1;//变量初始化，用来初始p数组（p用来记录当前01编码）
d.hfbm(hfleaf,co,true);//huffman树类的递归编码程序，压缩、解压缩重复利用此函数编码
//该函数最后一个参数true表示是压缩时用，false表示是在解压时用
ofstream ofile("liuyang1.txt",ios_base::out|ios_base::binary);//建立暂存文件
//……省略部分代码
BinaryTreeNode<Hz> ee;
for(int o=0;o<i;o++)
{ //调用链表搜索函数根据字典索引将01编码写进暂存文件中
int p=cc.Search(char(a[o]),ee);
for(int k=0;k<=ee.i;k++)
ofile<<ee.Le[k];
}
ofile<<'^';//暂存文件中方便标记结束符号
ofile.close();
ifstream iifile("liuyang1.txt",ios_base::in|ios_base::binary);
ofstream oofile(OutputFile.c_str(),ios_base::out|ios_base::binary);
iifile.seekg(0,ios_base::end);
r=(int(iifile.tellg())-1)%8;
oofile<<char(r);//头文件信息：记录最后一个字符中有几位数字是真真实有效的
iifile.seekg(0,ios_base::beg);
oofile<<char(short(e)>>8)<<char(short(e)); //用2个字符记录字典链表节点个数
for(int k=1;k<e;k++)
oofile<<c[k].Letter()<<char(c[k]>>8)<<char (c[k]);//在压缩文件中写入字典信息
//在压缩文件中通过bitset类写入编码并压缩的字符
cout<<"压缩后文件大小"<<oofile.tellp()<<"byte 压缩完毕！"<<endl;
oofile.close();
iifile.close();
//释放动态存储空间 压缩结束！解压缩流程于此类似
（3）详细设计表示：
//具体压缩写入的程序：
while (iifile)
{
for(r=0;r<8;r++)
{iifile.get(ch[r]);
if(ch[r]=='^'){
iifile.get(ch[r]);
break;}}
if (r)
{ int l=r;
if(l<8) ch[l]='\0';
string str(ch);
bitset<8> cbit(str);
unsigned long int io;
io = cbit.to_ulong( );
oofile<<unsigned char(io);}
}
//Huffman编码函数（类似前序遍历的递归函数）
template<class T>
void BinaryTree<T>::hfbm(void(*Visit)(BinaryTreeNode<T> *u,int co,bool a), BinaryTreeNode<T> *t,int co,bool a)
{ if (t)
{ Visit(t,co,a);
co++;
if(t->LeftChild)
{ p[co]='0';
hfbm(Visit, t->LeftChild,co,a);
}
if(t->RightChild)
{ p[co]='1';
hfbm(Visit, t->RightChild,co,a);}
}
}
//具体将字符频率插入到链表的函数
void hfleaf(BinaryTreeNode<Hz> *u,int co,bool a)
{ if (!u->LeftChild &&!u->RightChild && co==-1)
{ u->Le=new char[co+2];
u->i=++co;
p[co]='0';
u->Le[0]=p[0];
if (a)
C->Insert(*u);
WPL+=u->data*(co+1);
}else
if(!u->LeftChild && !u->RightChild)
{ u->Le=new char[co+1];
u->i=co;
for(int k=0;k<=co;k++)
u->Le[k]=p[k];
if (a)
C->Insert(*u);
WPL+=u->data*(co+1);
}
}
3．编码
最难解决的是将8个01字符压缩成8位的字符写入压缩文件中，由于所有编码和未必是8的整数个数，所以同时还要标记最后一个字符的二进制数字中有几位是真实有效的。
具体解决是首先包含头文件#include<bitset>，然后调用bitset类将01字符串转换为二进制与其数值相等的长整数值，即以8位二进制数值为一个无符号字符型变量的值，再写入压缩文件中：bitset<8> cbit(str);unsigned long int io = cbit.to_ulong( );oofile<<unsigned char(io);
对于解决标记最后一个字符的真实有效位数，可以根据暂存文件liuyang1.txt的信息算出最后一位的有效位数:r=(int(iifile.tellg())-1)%8;
4．程序及算法分析
使用说明：在程序运行时有字幕提示一步一步的操作，也可根据以下示例图片来操作。程序运行结果如图所示：
程序首先对ly.txt文件进行压缩生成ly.Haf压缩文件,再继续对liuyang.txt文件压缩生成liuyang.Haf压缩文件；最后再将ly.Haf文件解压生成ly_text.txt文件与ly.txt文件相同，实现了文件的无损压缩和解压。
改进设想及经验与体会：此程序用的是二进制流文件的读入和输出，且是用win32控制台，若要改进则应改用界面更优化的mfc来编写，同时改用cfile类来进行文件的读入写出。
时空复杂度：对于空间复杂度来说，由于压缩解压缩都借助了暂存文件来存储字符，因此在空间上得到了优化；但对于时间复杂度来说，由于要多写进去2个暂存文件中，因此降低了时间复杂性。
5．小结
经验的话是把压缩的具体流程熟悉了一遍，以及处理输入压缩名，更改名字为.Haf结尾的字符串用法：
string InputFile,OutputFile;
cout<<"输入压缩文件名（带后缀）："<<" ";
cin>>InputFile;
OutputFile.assign(InputFile,0,InputFile.find('.'));
OutputFile=OutputFile+".Haf";
cout<<"压缩后文件名为："<<OutputFile<<" ";
这段代码可为第二个题目做小部分铺垫。
（<五号宋体>，具体内容：经验与体会，或需要改进的地方）
6．附录
//前面省略的huffman树的函数以及结点Hz类的代码
//类Hz是huffman树构建的节点数据data的类型
class Hz
{public:
Hz(){count=0;letter=' ';}
void Add(){count++;}
char Letter(){return letter;}
bool operator ==(char x) {if(letter==x)return true;return false;}
operator int() const{return count;}
bool operator <=(Hz a) {return count<=a.count;}
bool operator <(Hz a) {return count<a.count;}
void operator =(int x) {count=x;}
void operator =(char x) {letter=x;}
private:
char letter;//编码的字符
int count;//该字符的频率};
//构建huffman树的函数，参数数组为自定义类Hz(含字符和频率2个私有数据)
BinaryTree<Hz> HuffmanTree(Hz a[],int n) //改为BinaryTree<char>可以，需在该函数作相应修改即可，只是返回一个存了字符二叉树，没有频率对应
{ //根据权重a[1:n]//0:n-1构造HuffmanHuffman树
// 创建一个单节点树的数组
Huffman<Hz,Hz> *w=new Huffman<Hz,Hz>[n+1];
BinaryTree<Hz> z, zero;
Hz az;az='~';
for(int i=1;i<=n; i++)
{ z.MakeTree(a[i], zero, zero);// 外部节点
w[i].weight=a[i];
w[i].tree=z;}
//把数组变成一个最小堆
MinHeap<Huffman<Hz,Hz>> H(1);
H.Initialize(w,n,n);
//将堆中的树不断合并
Huffman<Hz,Hz> x, y;
for(int i=1; i<n; i++)
{ H.DeleteMin(x);
H.DeleteMin(y);
z.MakeTree(az,x.tree, y.tree); //内部节点
x.weight=int(x.weight)+int(y.weight);
x.tree=z;
H.Insert(x);}
H.DeleteMin(x); //最后的树
H.Deactivate();
delete[] w;
return x.tree;}
二、灰度图像压缩/解压缩类的实现（动态规划算法的应用）
1．需求规格说明
针对提供的256色（8位）位图数据，采用教材上第15章动态规划中图像压缩算法（图像分段合并的思想），设计一个类，实现灰度位图数据的压缩和解压过程。
完整的灰度图像类应具有以下功能：
（1）对8位位图数据的读功能，提供ReadBitmap方法。
（2）对8位位图数据的写功能，提供WriteBitmap方法。
（3）灰度图像压缩功能，提供Compress方法。
（4）灰度图像解压功能，提供UnCompress方法。
2．总体分析与设计
（1）设计思想：
主要的算法思想及其存储结构：
对待压缩的文件进行读取，并获取bmp图像相应的头文件信息。将文件中图像色阶的信息转为二进制表示并写入暂存的文件bianma1.txt中；读取暂存的二进制信息并初步合并相邻且位数相等的数值信息得到段落l和位数b数组的初步信息，再将其带入课本中动态规划学习时所用的缩短表示的二进制位数的代码中进行数据优化合并，得到最优压缩的段落ll和位数o数组的信息；据新数组信息重新将bianma1.txt中的图像二进制信息写入暂存文件bianma2.txt中，此时已得到压缩文件后二进制的相应表示，再根据之前压缩的经验用bitset类将此二进制信息转进后缀为.img的压缩文件中（原图像头文件的信息已写入此压缩文件，且随之更改头文件BITMAPINFOHEADER类中的 biSizeImage数值为当前压缩文件中图像信息的实际大小）。解压缩部分是获取压缩文件的头信息并根据biSizeImage值获取压缩图像色阶数据以二进制数值写入暂存文件jiema1.txt中，再将biSizeImage还原至原信息数值，将整个头文件写入解压缩后的bmp图像头信息中，再根据jiema1.txt中得到的二进制分段信息还原至原数值二进制信息并写回到解压缩后的bmp图像数据信息中，完成解压缩。
此处主要是采用定义数组指针，动态分配内存空间来存储分段信息的。
（2）设计表示：
//动态规划合并函数程序
int L = 256, header = 11;int li,pp;//全局变量及常量定义
unsigned int *s,*l,*ll,*b;int *kay;
//动态规划分类函数
int S(int i)
{ if (i == 0) return 0;
if (s[i] > 0) return s[i];
int lsum = l[i], bmax = b[i];
s[i] = S(i-1) + lsum * bmax;
kay[i] = 1;
for (int k = 2; k <= i && lsum+int(l[i-k+1]) <= L; k++) {
lsum += int(l[i-k+1]);
if (bmax < int(b[i-k+1])) bmax = int(b[i-k+1]);
int t = S(i-k);
if (int(s[i]) > t + lsum * bmax) {
s[i] = int unsigned(t + lsum * bmax);
kay[i] = k;}
}
s[i] +=int unsigned(header);
return s[i];
}
//重新标记新段落信息
void Traceback(int kay[], int n)
{ if (n == 0) return;
Traceback(kay, n-kay[n]);
ll[li]=n - kay[n] + 1-pp;
li++;
pp=n - kay[n] + 1;
}
（3）详细设计表示：
主要算法的框架：
fp_s = fopen(fname_s, "rb");//fname_s为定义图像名称的字符指针，部分信息省略
fp_t = fopen(fname_t, "wb");//fname_t为定义压缩文件名称的字符指针，部分信息省略
fseek(fp_s, 0, SEEK_SET);
fread(&aa,sizeof(BITMAPFILEHEADER),1,fp_s);
fseek(fp_s, 14, SEEK_SET);
fread(&a,sizeof(BITMAPINFOHEADER),1,fp_s);
DataSizePerLine= (a.biWidth*a.biBitCount+31)/8; //一个扫描行所占的字节数
DataSizePerLine= DataSizePerLine/4*4; // 字节数必须是4的倍数
//位图数据的大小(不压缩情况下):
DataSize= DataSizePerLine* a.biHeight;
//动态分配空间！！！
image_s = new unsigned char[DataSize];
if (image_s == NULL) {
printf("malloc images_s error\n");
return -1; }
//段落信息等的数组动态分配空间
s=new unsigned int[a.biWidth * a.biHeight+1];
kay=new int[a.biWidth * a.biHeight+1];
l=new unsigned int[a.biWidth * a.biHeight+1];
b=new unsigned int[a.biWidth * a.biHeight+1];
//部分省略
fseek(fp_s, aa.bfOffBits, SEEK_SET);
ofstream ofile("bianma1.txt",ios_base::binary);//图像原始的二进制信息
ofstream omfile("shuju1.txt",ios_base::binary);//图像原始的十进制信息（只是预览方便检查，对压缩没有用处）
fread(image_s, sizeof(unsigned char),DataSize ,fp_s);
for(y = 0; y !=a.biHeight; ++y) {
for(x = 0; x != a.biWidth; ++x) {
pixel= *(image_s+(DataSizePerLine * y + x));
omfile<<unsigned long(pixel)<<' ';
unsigned long k=unsigned long(pixel);
bitset<8> obit(k);
ofile<<obit;//图像色阶的信息转为二进制表示并写入
}
}
//部分省略
ofstream oomfile("shuju2.txt",ios_base::binary);//图像二进制信息的出合并段落l与位数b数组的信息（只是预览方便检查，对压缩没有用处）
ifstream ifile("bianma1.txt",ios_base::binary);
//原图像信息的初步分段代码
ll=new unsigned int[a.biWidth * a.biHeight+1];//新段数组的动态分配空间与初始化
b[0]=ll[0]=0;
for(int r=0;r<k+1 ;r++)
s[r]=0;
cout <<"动态规划预计压缩后的理想大小：" << S(k) << endl;//调用动态规划的优化分段的函数
li=0;pp=1;
Traceback(kay,k);//记录新段落信息
//将新段落ll[]和o[]数据进行统计的代码
ofstream oofile("bianma2.txt",ios_base::binary);//将要压缩的图像二进制信息通过动态规划的合并后的二进制信息
ifile.clear();//重读取bianma1.txt中得图像二进制信息
ifile.seekg(0,ios_base::beg);
int zl,zb,zd=0;
for(ra=1;ra<=li ;ra++){
unsigned long k1=unsigned long(ll[ra]-1);
unsigned long k2=unsigned long(o[ra]-1);
bitset<8> obit1(k1);
bitset<3> obit2(k2);
oofile<<obit1<<obit2;
for(zl=0;zl<ll[ra];zl++)
{
for(int qr=0;qr<8;qr++)
ifile.get(ach[qr]);
for(zb=8-o[ra];zb<8;zb++)
oofile<<ach[zb];
}
}
//开始将bianma2.txt中压缩信息写入压缩文件中
ifstream iifile("bianma2.txt",ios_base::binary);
fseek(fp_t, 0, SEEK_SET);
fwrite(&aa,sizeof(BITMAPFILEHEADER),1,fp_t);
//部分省略
fseek(fp_t, aa.bfOffBits, SEEK_SET);
for(r=0;r<8;r++)
ch[r]=0;
while (iifile)
{ for(r=0;r<8;r++)
{ iifile.get(ch[r]);
if(ch[r]=='^'){
iifile.get(ch[r]);
break;}
}
if (r)
{ int l=r;
if(l<8) ch[l]='\0';
string str(ch);
bitset<8> cbit(str);
unsigned long int io;
io = cbit.to_ulong( );
cc=unsigned char(io);
fwrite(&cc, sizeof(unsigned char),1, fp_t);
}
}
//解压缩部分类似
3．编码
通过File类获取信息时要不停调用fseek()函数来标记位置，当要统计压缩文件结尾的数值时，同时要在解压缩时计算出压缩文件中最后一个字符的有效位数比较复杂。统计压缩文件结尾的大小是通过在压缩文件中更改了头文件biSizeImage数值，再在解压缩时读取后并还原给解压缩文件，而统计有效位数则是通过边还原二进制信息边记录动态规划后信息总数值Z值来计算出来最后一个字符的有效位数。
4．程序及算法分析
使用说明：在程序运行时有字幕提示一步一步的操作，也可根据以下示例图片来操作。程序运行结果如下图所示：
程序首先对text8.bmp文件进行压缩生成t8.img压缩文件,再继续对text0.bmp文件压缩生成t0.img压缩文件；最后再将t8.img文件解压生成t_8.bmp文件与text8.bmp文件相同，实现了文件的无损压缩和解压。
text8.bmp t_8.bmp
改进设想：此程序由于是用数组来进行大量数据的存储，同时又用了多次递归栈调用函数致使空间内存不足，过大的图像会由于递归栈溢出使程序无法继续运行；同时此程序是用win32控制台，若要改进则应改用界面更优化的mfc来编写，同时改用mfc上的bitmap类来进行文件的读入写出。
时空复杂度：空间复杂性上由于要根据图像大小动态分配数组空间，再加上多次递归栈的调用致使空间耗费较大。
5．小结
经验与体会：经过使用MSDN了解了BITMAPINFOHEADER结构，同时查了各种资料学习了读入和输出BMP图像；充分学习了BMP图像的具体框架，分为：
BITMAPFILEHEADER、BITMAPINFO（BITMAPINFOHEADER和 RGBQUAD调色板和不同分辨率预留的空间）以及主要像素信息这几部分。
6．附录
//初步合并得到段落l与位数b数组的信息
while (ifile)
{ int z=1;
for(r=0;r<8;r++)
{ ifile.get(ch[r]);
if (ifile)
{ if((ch[r]=='1' ||r==7)&&z)
{ b[i]=7-r+1;
if (b[i]==b[i-1]&&i-1&& l[k]<L)
l[k]++;
else {oomfile<<"b["<<i<<']'<<b[i]<<endl;
i++;
oomfile<<"l["<<k<<']'<<l[k]<<endl;
k++;
l[k]=1;}
z=0;
}
}
}
}
//动态规划后合并段落得到新数组ll[]
int ra,la,pla=0,t;ll[li]=a.biWidth * a.biHeight;//总长度 : 宽是原先长度
for(ra=1;ra<li ;ra++)
{ t=0;
for (la=0;la<ll[ra];la++ )
t+=l[pla+la+1];
pla+=la;
ll[ra]=t;
}
for(ra=1;ra<li ;ra++)
ll[li]-=ll[ra];
//动态规划后合并段落得到新数组o[]
unsigned int* o=new unsigned int[ra+1];
int ab,ap;
ab=ap=0;//ab是目前真实段落数；ap是所对应目前b的标记段落数；共有li段 由ra记录段落标示
for(ra=1;ra<=li ;ra++)
{ o[ra]=b[++ap];
for (int p=ap+1,ab=l[p-1];ab<int(ll[ra]);p++,ab+=l[p-1])
{ if (o[ra]<b[p])
o[ra]=b[p];
ap=p;}
}
}