第六章计算机数据结构试验报告hrbedu.doc

实验名称：文件压缩

实验类型：综合性实验

班级：090611

学号：2009061115

姓名：贲闯

实验日期：2011.6.13

问题描述

哈夫曼编码是一种常用的数据压缩技术，对数据文件进行哈夫曼编码可大大缩短文件的传输长度，提高信道利用率及传输效率。要求采用哈夫曼编码原理，统计文本文件中字符出现的词频，以词频作为权值，对文件进行哈夫曼编码以到达压缩文件的目的，再用哈夫曼编码进行译码解压缩。

统计待压缩的文本文件中各字符的词频，以词频为权值建立哈夫曼树，并将该哈夫曼树保存到文件HufTree.dat中。

根据哈夫曼树〔保存在HufTree.dat中〕对每个字符进行哈夫曼编码，并将字符编码保存到HufCode.txt文件中。

压缩：根据哈夫曼编码，将源文件进行编码得到压缩文件CodeFile.dat。

解压：将CodeFile.dat文件利用哈夫曼树译码解压，恢复为源文件。

2、数据结构设计

根据问题的要求，所以可以创立一个多属性的结构体，如下：

typedefstructtreenode

{

intright;

intleft;

intparent;

unsignedintweights;

intnum;

boollive;

}HuffmanNode,*pHuffmanNode;

3、算法设计

〔1〕初始化哈夫曼树，如：

voidInitHuffmanTree()

{//初始化哈夫曼树

for(inti=0;i=TABLE_SIZE;i++)

{

HuffmanTree[i].num=i;

HuffmanTree[i].left=HuffmanTree[i].right=HuffmanTree[i].parent=-1;

HuffmanTree[i].weights=0;

HuffmanTree[i].live=true;

}

for(inti=TABLE_SIZE+1;iTREE_SIZE;i++)

{

HuffmanTree[i].num=i;

HuffmanTree[i].left=HuffmanTree[i].right=HuffmanTree[i].parent=-1;

HuffmanTree[i].weights=0;

HuffmanTree[i].live=false;

}

HuffmanTree[TABLE_SIZE].weights=1;

HuffmanTree[TREE_SIZE-1].weights=MAX_INT;

}

〔2〕声明一个函数采用哈希表的算法计算权值，如：

intCalWeights(char*Encode_Path)

{

FILE*pFileIn;

intc=0;

pFileIn=fopen(Encode_Path,rb);

if(!pFileIn)

{

printf(cantopenfile!\n);

return-1;

}

while((c=fgetc(pFileIn))!=EOF)

HuffmanTree[c].weights++;

fclose(pFileIn);

return0;

}

〔3〕用冒泡排序法排序，如下：

voidSortWeight()

{

for(inti=0;iTABLE_SIZE;i++)

for(intj=0;jTABLE_SIZE-i;j++)

{

if(HuffmanTree[j].weightsHuffmanTree[j+1].weights)

{

HuffmanNodetemp;

temp=HuffmanTree[j];

HuffmanTree[j]=HuffmanTree[j+1];

HuffmanTree[j+1]=temp;

}

}

}

〔4〕压缩文件的算法，如：

intEnCode(char*Encode_Path,char*Decode_Path)

{

FILE*pFileIn;

FILE*pFileOut;

intc=0;

inti;

charoutput=0;

intbit_offset=7;//位偏移

pFileIn=fopen(Encode_Path,rb);

if(!pFileIn)

{

printf(cantopen1.bmp\n);

return-1;

}

pFileOut=fopen(Decode_Path,wb);

if(!pFileOut)

{

printf(cantopenoutputfile!\n);

return-1;