数据结构综合实验报告.doc

-
. z
. I ffman树à2翻开需压缩文件à3将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出à4文件压缩完毕。
其中，步骤1和步骤3是压缩过程的关键。
步骤1:这里所要做工作是得到Haffman数中各叶子结点字符出现的频率并进展创立。
统计字符出现的频率可以有很多方法:如每次创立前扫描被创立的文件，"实时〞的生成各字符的出现频率；或者是创立前即做好统计。本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率。当前，也可以根据被压缩文件的特性有针对性的进展统计，如要压缩C语言的源文件，则可事先对多篇C语言源文件中出现的字符进展统计,这样，会创立出高度相对较"矮〞的Haffman树，从而提高压缩效果。
步骤3: 将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出，这是本压缩程序中最关键的局部。
这里涉及"转换〞和"输出〞两个关键步骤：
"转换〞局部大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码，可以将每个Haffman码值及其对应的ascii码存放于如下所示的构造体中：
typedef struct
{
char asciiCode;
unsigned long haffCode;
int haffCodeLen;
}HaffCode;
创立由该构造体结点所组成的，长度为128的一维数组codeList[128]
-
. z
. I
. . r . .
且codeList中的下标和asciiCode满足下面的顺序存放关系：
codeList[i].asciiCode=i;
这样的话，查找*个字符inChar的haffman编码的工作便变得相当轻松了,如下：
sHaffCode=codeList[inChar].haffCode;
数组codeList[128]的创立可以采用*种遍历方式下的按找到的字符进展置数的方式，十分的方便。
/*Code2:
codeList的创立算法,采用前序遍历的方式进展创立.
*/
void preHaffListMake(PHtTree inTree,int rootInde*,unsigned long youBiao,int sDepth,
HaffCode* inList)
{
if(inTree->ht[rootInde*].llinkInde*==-1&&inTree->ht[rootInde*].rlinkInde*==-1)
{
inList[inTree->ht[rootInde*].info].haffCode=youBiao;
inList[inTree->ht[rootInde*].info].haffCodeLen=sDepth;
}
else
{
preHaffListMake(inTree,inTree->ht[rootInde*].llinkInde*,youBiao<<1,sDepth+1,inList);
preHaffListMake(inTree,inTree->ht[rootInde*].rlinkInde*,(youBiao<<1)|0*01,sDepth+1,inList);
}
}
"输出〞局部是最重要的局部，也是最易出错的局部。
这里，涉及到C语言的位操作,要求这个算法能处理好以下几个问题：
1)每个字符所对应的haffCode的比特位长度由5~23位不等长，不可少输，多输，输错任何一位，后一个字符的haffCode要紧跟在前一个字符的haffCode后面。
2)最后一个字符要能合理的完毕。这主要是为解压缩考虑的，比方，在最后一个要输出的haffCode的最后一位，它恰好是位于最后一个有效字符的第一位，剩下的七个比特位是要用无效的haffCode加以填充的。否则，如果填充的haffC