void operator =(char x) {letter=x;}
private:
char letter;//编码的字符
int count;//该字符的频率};
//构建huffman树的函数，参数数组为自定义类Hz(含字符和频率2个私有数据)
BinaryTree<Hz> HuffmanTree(Hz a[],int n) //改为BinaryTree<char>可以，需在该函数作相应修改即可，只是返回一个存了字符二叉树，没有频率对应
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];
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)
H.Deactivate();
delete[] w;
return x.tree;}
二
1
针对提供的256色（8位）位图数据，采用教材上第15章动态规划中图像压缩算法（图像分段合并的思想），设计一个类，实现灰度位图数据的压缩和解压过程。
完整的灰度图像类应具有以下功能：
（1）对8位位图数据的读功能，提供ReadBitmap方法。
5
经验的话是把压缩的具体流程熟悉了一遍，以及处理输入压缩名，更改名字为.Haf结尾的字符串用法：
string InputFile,OutputFile;
cout<<"输入压缩文件名（带后缀）："<<"";
cin>>InputFile;
OutputFile.assign(InputFile,0,InputFile.find('.'));
{
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;
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();
//释放动态存储空间压缩结束！解压缩流程于此类似
（
//具体压缩写入的程序：
while (iifile)
（
具体的压缩实例部分代码：
//主程序中void main（）
//省略其统计字符出现频率的代码
cout<<"开始构建huffman树并压缩……"<<"";
BinaryTree<Hz> d;
//Hz *c=new Hz[i+1];Hz是专门用来存储字典的类其中只包含私有变量char letter;字符
int count;字符统计频率这俩个信息。及huffman每个节点均为Hz类型
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);//头文件信息：记录最后一个字符中有几位数字是真真实有效的
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树类的递归编码程序，压缩、解压缩重复利用此函数编码
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;}
OutputFile=OutputFile+".Haf";
cout<<"压缩后文件名为："<<OutputFile<<"";
这段代码可为第二个题目做小部分铺垫。
（<五号宋体>，具体内容：经验与体会，或需要改进的地方）
6
//前面省略的huffman树的函数以及结点Hz类的代码
//类Hz是huffman树构建的节点数据data的类型
改进设想及经验与体会：此程序用的是二进制流文件的读入和输出，且是用win32控制台，若要改进则应改用界面更优化的mfc来编写，同时改用cfile类来进行文件的读入写出。
时空复杂度：对于空间复杂度来说，由于压缩解压缩都借助了暂存文件来存储字符，因此在空间上得到了优化；但对于时间复杂度来说，由于要多写进去2个暂存文件中，因此降低了时间复杂性。
{//调用链表搜索函数根据字典索引将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);
{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;
即求解的问题是，根据哈夫曼编码的知识写一个压缩/解压缩软件。
2
（
主要的算法思想及其存储结构：采用课程实习已经写过的huffman编码程序对要压缩文件中字符进行读取，统计字符出现频率，并进行字符编码。将编码后的字符以链表形式存储其所编的huffman码，并以该字符建立链表的字典索引。重新读取待压缩文件并根据链表搜索其huffman编码按顺序写入一暂存文件liuyang1.txt中保存。根据liuyang1.txt中的编码进行8个数字一压缩写入压缩文件中。（压缩文件头部首先要写入字典编码等重要信息，以方便解码需求）。解码时首先以二进制形式读取压缩文件中存入的字典编码信息，根据其字符频率信息重新构造huffman树，与此同时将剩余压缩文件中每个字符解压缩成8个字符（与liuyang1.txt对应）写入暂存的文件liuyang3.txt中。再依次据暂存文件liuyang3.txt读取huffman编码数字，根据建立的huffman搜索树进行解码还原成带压缩文件。
//该函数最后一个参数true表示是压缩时用，false表示是在解压时用
ofstream ofile("liuyang1.txt",ios_base::out|ios_base::binary);//建立暂存文件
//……省略部分代码
BinaryTreeNode<Hz> ee;
for(int o=0;o<i;o++)
{//根据权重a[1:n]//0:n-1构造HuffmanHuffman树
//创建一个单节点树的数组