数据结构实习报告(中国地质大学)

1、需求规格说明

【问题描述】

利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储

空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩解压缩软件。 【基本要求】

（1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。 （2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件。

（3）解压缩。打开已有压缩文件，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。

2．总体分析与设计

【设计思想】

将一待压缩的文件以二进制形式进行读写。压缩过程中，将待压缩文件一次性读入内存，随后对其中出现的字符进行判断和统计，将所得的字符频率创建HuffMan树，并对其进行编码，将源文件的字符用其HuffMan编码代替，组合成满字节写入压缩文件。 【详细设计表示】

变 量 数据类型 Maxsize int

*Key input_char KeyNum int

*Huffman_node huffmantree 成员函数说明： char_judge

功能：判断字符出现的函数；

原型：bool char_judge(char c);//判断字符出现的函数； 返回类型：bool型 参数：c char型 [in] char_add

功能：添加新出现字符的函数； 原型：void char_add(char c); 返回类型：无

参数：c char型 [in] CreateHuffTree 功能：创建哈夫曼树

原型：void CreateHuffTree(); 返回类型：无 参数：无

CreateHuffCode

功能：创建哈夫曼编码

原型：void CreateHuffCode(); 返回类型：无

参数：无

其它函数说明： ArrayOpp 功能：将一个字符数组中的1 字符顺序颠倒 原型：void ArrayOpp(char a[],int n) 返回类型：无

参数：数组 a char型 [in&out] n int型

CompressFile 功能：压缩文件

原型：void CompressFile(FILE *ifp,FILE *ofp);//压缩 返回类型：无

参数：指针ifp FILE型 [in&out] 指针ofp FILE型 [in&out]

DecompressionFile 功能：解压文件

原型：void DecompressionFile(FILE *ifp,FILE *ofp);//解压 返回类型：无

参数：指针ifp FILE型 [in&out] 指针ofp FILE型 [in&out]

FindMax

功能：寻找数组中最大元素下标 原型：void FindMax(int index[],int n,int &flag);//寻找数组中最大元素下标 返回类型：无

参数：数组index int型 [in&out] n 数组长度 [in] flag int型 [in&out]

3． 编码

【遇到的问题及解决方法】 （1）选取合适的数据结构

对于一个工程的实现，到底采用怎样的数据结构，应该考虑到程序的性能和代码的可读性。由于起初对工程的不熟，对于用什么样的数据结构来存储我一直都处在试探中，缺乏一种长久的考虑，这也使得后面的编码过程效率不高。最终冷静下来，自定义了一个文件类和两个辅助结构体，大体的实现框架在总体设计中已给出。

(2)哈夫曼树该如何建立

首先，字符的频率作为关键值，用一个循环，每次找出关键值最小的两个字符，将其组合加入到哈夫曼树中，同时将每个哈夫曼树节点用结构体huffman_node数组存放，每个节点都有其左右孩子和父节点的下标，这有便于后面的哈夫曼编码。 (3)哈夫曼编码的具体实现

哈夫曼编码的具体实现方法：由于哈夫曼树的建立过程中为每个哈夫曼节点标明了左右孩子和父节点，可以从关键值开始，从下往上通过父节点与子节点的关系为子节点进行编码，如果父节点的左孩子是当前子节点，则子节点（含关键值）的哈夫曼编码标为0否则标为1，如此循环下去。这样得到每个叶节点对应的哈夫曼编码的逆序表示，且存放在数组bits中。

然后用一个函数ArrayOpp将其逆序过来，从而真正得到哈夫曼编码。 (4)文件的二进制形式读写操作及其压缩的实现

最主要的还是怎样实现文件的压缩，由于压缩文件中的字符是用其相应的哈夫曼编码代替的，如果只是把字符的哈夫曼编码（也使字符型的数组存放的）写入，将会适得其反，只有将相邻字符的编码组合成一个一个的字节数字写入才能达到节省空间的效果，例如：某字符哈夫曼编码为bits 1 1 1 1 1 1 1 这字符数组内容通过移位可转化为char型数128，如果满一个字节就写入，若未满则继续组合。

4．程序及算法分析

【压缩】

1、先整体扫描文本，统计文本的字符个数 ，种类，以及频率记录下来。

2、根据字符的频率生成相应的huffman树，生成huffman树之后再根据树的结构生成huffman编码。

3、生成压缩文件，文件头部分写入待压缩文件的字符个数，字符种类以及相应的频率，分别用int型，char型数组以及int型数组写入。

4、写入带压缩文件中每个字符对应的huffman编码，按位写入。

按位写入采用移位思想，满8位一写。如源文件中一段字符“ABC”,A的huffman编码为001,B的huffman编码为010，C的为11，刚好满8位。则定义一个unsigned char型变量如c_out（初值为0），用移位将c_out赋值使其机器编码为00101011，刚好8位，再将其作为一个字符写入压缩文件中，直至将带压缩文件的最后一个字符写满。要注意的是:若带压缩文件最后一个字符的huffman编码赋值给c_out后c_out不满8位，则将c_out的其余位都补0。 【解压】

1、读压缩文件的头部分，定义几个变量记录字符个数，种类以及对应的频率。 2、根据字符种类及频率生成huffman树。

3.继续循环读压缩文件每次读一个字符，每读一个字符根据其8位机器码来遍历huffman树，当遇到huffman树的叶子节点时终止，将叶子节点的字符写入解压后的新文件中。当读完最后一个字符后终止循环。

解压正文时每读一个字符，利用移位将该字符的8位机器码取出存入链表中，方便huffman树的遍历。

【分析】

主要的程序集中在两个函数中：CompressFile和DecompressionFile考虑到程序的性能，在对文件的读写过程中，我选择在内存中对文件进行操作，在压缩时，将待压缩文件一次性读入内存，在解压文件时，将待解压文件一次性读入内存，而不是一个字节一个字节地读写文件。

5．小结

通过这次课题实验的程序实践，我实在获益匪浅！数据结构是上个学期开展的一门学科，学习这门学科也是艰辛的，因为它比较难懂，但是这门学科是非常重要的，在以后的程序设计方面这门学科能给我们很大的帮助。

这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程序而努力，翻阅相关书籍、在网上查找资料。因为课本上的基础知识掌握不好，过程中遇到了不少的阻碍，编写程序的进度也比较慢。虽然如此，但是通过自己的努力与老师的指导，我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的基础下写出了本次实验的核心算法，并使其能够正常的运行。

近两周的程序设计，让我体会到了作为一个编程人员的艰难，一个算法到具体实现，再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编好程序后，编程人员还要花很多的时间去完善它，其中包含的心酸，外人是不会明白的。

这次课程设计涉及对大量数据的处理，要做到精益求精，不能忽略任何一处，否则结果将会有很大的不同，总之，最大的感受就是完美源于细节！编程不仅要有一定的理论基础和实践经验，还需要一定的毅力和关注细节的习惯。这次对文件的压缩和解压的实习，使我的调试有了进一步的提高。同时也使我在编程中对文件的存储形式的采取有了一定的了解。希望在以后的实习中，我会有有进一步的提高。

6．附录

【部分核心代码】

void CompressFile(FILE *ifp,FILE *ofp) {

if(!ifp) {

cout<<\

opened!\<

fseek(ifp, 0, SEEK_END); //定位到文件结尾处

int orignflen = ftell(ifp);

char *orignfile=new char [orignflen+1];

fseek(ifp,0,SEEK_SET); //定位到文件起始处

fread(orignfile,1,orignflen,ifp);//将文件内容一次性读到内存中 orignfile[orignflen]=0;

C_file file(512); char c;

for(int i=0;i

c=orignfile[i];

if(!file.char_judge(c))//对原文件字符进行判断和统计

file.char_add(c); }

for(int i=1;i

cout<

file.CreateHuffTree();//创建HuffMan树

file.CreateHuffCode();//创建HuffMan编码

//*******************************************************************//

//写入文件信息

fseek(ifp,0,SEEK_SET);

fwrite(&orignflen,sizeof(int),1,ofp);

fwrite(&file.MaxSize,sizeof(int),1,ofp);

fwrite(&file.KeyNum,sizeof(int),1,ofp);

for(int i=1;i

fwrite(&file.Key[i].data,sizeof(char),1,ofp);

fwrite(&file.Key[i].count,sizeof(int),1,ofp); }

//*******************************************************************//

unsigned char o_c=0; //o_c中存入二进制的位数

int bitnum=0; char x;

for(int k=0;k

c=orignfile[k]; //从内存中取出源文件内容

for (int

i=1;i

{//在文件类对象中检索出相应的关键码

if

(c!=file.Key[i].data)continue; else

{//将哈夫曼编码组合成char型数字

for (int

j=0;j

if (bitnum==8) {//若满8位则构成一字节写入

fwrite(&o_c,1,1,ofp);

bitnum=0; o_c=0;

}

x=file.huffman_node[i].bits[j]; if(x=='1') o_c=(o_c<<1)+1;

else o_c=o_c<<1; bitnum++;

} break; } } }

while(bitnum<8)//最后一个字节未写满则补 {

o_c=o_c<<1; bitnum++; }

fwrite(&o_c,1,1,ofp);//将最后一个字节写入文件

fclose(ifp); fclose(ofp); cout<<\Compressed!\<

void FindMax(int index[],int n,int &flag)

{//找出数组中最大值的下标 由flag返回 for(int i=1;i<=n;i++) {

if (index[i]>=index[i+1]) {

flag=i; } else

flag=i+1; } }

void DecompressionFile(FILE *ifp,FILE *ofp) {

unsigned char i_c=' '; char o_c=' ';

//**************************************************************// //读取压缩文件信息 fseek(ifp,0,SEEK_SET); int orignflen=0; int MaxSize=0; int KeyNum=0;

fread(&orignflen,sizeof(int),1,ifp);

char *depressfile; depressfile=new char[orignflen+1];

fread(&MaxSize,sizeof(int),1,ifp);

C_file file(MaxSize);

fread(&file.KeyNum,sizeof(int),1,ifp);

for(int i=1;i

fread(&file.Key[i].data,sizeof(char),1,ifp);

fread(&file.Key[i].count,sizeof(int),1,ifp); }

//**************************************************************// //重构HuffMan树和编码 file.CreateHuffTree(); file.CreateHuffCode();

fseek(ifp, 12+((file.KeyNum-1)*5), SEEK_END);

long flen = ftell(ifp); char *compressfile=new char [flen+1];

fseek(ifp,0,SEEK_SET); fseek(ifp, 12+((file.KeyNum-1)*5), SEEK_SET);

char t_buff[255],z_buff[255]; t_buff[0]=0; z_buff[0]=0;

//获取最长编码的长度 int *index;

index=new int [file.KeyNum-1]; int flag=0;

for (int i=1;i

index[i]=file.huffman_node[i].count; }

FindMax(index,file.KeyNum-1,flag);

int

p=file.huffman_node[flag].count; int curr_index=0; int l=0; while (true) {

int i;

while (strlen(z_buff)

fread(&i_c,1,1,ifp); itoa(i_c,t_buff,2);

//将读取的一个（字符型）字节的内容转换为char型字符数组

strcat(z_buff,t_buff);

【参考资料】

}

for (i=1;i

if(memcmp(file.huffman_nod

e[i].bits,z_buff,file.huffman_node[i].count)==0)

break; }

strcpy(z_buff,z_buff+file.huffman_node[i].count);

//获得目标字符并存入目标数组 o_c=file.Key[i].data; depressfile[l++]=o_c; if (l==orignflen) {

break; }

}

fseek(ofp,0,SEEK_SET);

fwrite(depressfile,1,l,ofp);//将解压后的文件一次性地写入文件 fclose(ifp); fclose(ofp); cout<<\DeCompressed!\<

《数据结构(用面向对象方法与C++语言描述)》 殷人昆 等编著，清华大学出版社 《数据结构题集》严蔚敏，吴伟民 编著，清华大学出版社 《数据结构及应用算法》严蔚敏，陈文博 编著，清华大学出版社