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

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

第一篇：数据结构实习报告(中国地质大学)1、需求规格说明【问题描述】利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压缩解压缩软件。【基本要求】（1）压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析结果（包括数据集大小，每个数据的权值，压缩前后文件的大小），在屏幕上输出。（2）压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后的数据一起写入文件中，形成压缩文件。（3）解压缩。打开已有压缩文件，读取其中的哈夫曼编码，构建哈夫曼树，读取其中的数据，进行译码后，写入文件，完成解压缩。2．总体分析与设计【设计思想】将一待压缩的文件以二进制形式进行读写。压缩过程中，将待压缩文件一次性读入内存，随后对其中出现的字符进行判断和统计，将所得的字符频率创建HuffMan树，并对其进行编码，将源文件的字符用其HuffMan编码代替，组合成满字节写入压缩文件。【详细设计表示】变量数据类型Maxsizeint*Keyinput_charKeyNumint*Huffman_nodehuffmantree成员函数说明：char_judge功能：判断字符出现的函数；原型：boolchar_judge(charc);//判断字符出现的函数；返回类型：bool型参数：cchar型[in]char_add功能：添加新出现字符的函数；原型：voidchar_add(charc);返回类型：无参数：cchar型[in]CreateHuffTree功能：创建哈夫曼树原型：voidCreateHuffTree();返回类型：无参数：无CreateHuffCode功能：创建哈夫曼编码原型：voidCreateHuffCode();返回类型：无参数：无其它函数说明：ArrayOpp功能：将一个字符数组中的1字符顺序颠倒原型：voidArrayOpp(chara[],intn)返回类型：无参数：数组achar型[in&out]nint型CompressFile功能：压缩文件原型：voidCompressFile(FILE*ifp,FILE*ofp);//压缩返回类型：无参数：指针ifpFILE型[in&out]指针ofpFILE型[in&out]DecompressionFile功能：解压文件原型：voidDecompressionFile(FILE*ifp,FILE*ofp);//解压返回类型：无参数：指针ifpFILE型[in&out]指针ofpFILE型[in&out]FindMax功能：寻找数组中最大元素下标原型：voidFindMax(intindex[],intn,int&flag);//寻找数组中最大元素下标返回类型：无参数：数组indexint型[in&out]n数组长度[in]flagint型[in&out]3．编码【遇到的问题及解决方法】（1）选取合适的数据结构对于一个工程的实现，到底采用怎样的数据结构，应该考虑到程序的性能和代码的可读性。由于起初对工程的不熟，对于用什么样的数据结构来存储我一直都处在试探中，缺乏一种长久的考虑，这也使得后面的编码过程效率不高。最终冷静下来，自定义了一个文件类和两个辅助结构体，大体的实现框架在总体设计中已给出。(2)哈夫曼树该如何建立首先，字符的频率作为关键值，用一个循环，每次找出关键值最小的两个字符，将其组合加入到哈夫曼树中，同时将每个哈夫曼树节点用结构体huffman_node数组存放，每个节点都有其左右孩子和父节点的下标，这有便于后面的哈夫曼编码。(3)哈夫曼编码的具体实现哈夫曼编码的具体实现方法：由于哈夫曼树的建立过程中为每个哈夫曼节点标明了左右孩子和父节点，可以从关键值开始，从下往上通过父节点与子节点的关系为子节点进行编码，如果父节点的左孩子是当前子节点，则子节点（含关键值）的哈夫曼编码标为0否则标为1，如此循环下去。这样得到每个叶节点对应的哈夫曼编码的逆序表示，且存放在数组bits中。然后用一个函数ArrayOpp将其逆序过来，从而真正得到哈夫曼编码。(4)文件的二进制形式读写操作及其压缩的实现最主要的还是怎样实现文件的压缩，由于压缩文件中的字符是用其相应的哈夫曼编码代替的，如果只是把字符的哈夫曼编码（也使字符型的数组存放的）写入，将会适得其反，只有将相邻字符的编码组合成一个一个的字节数字写入才能达到节省空间的效果，例如：某字符哈夫曼编码为bits1111111这字符数组内容通过移位可转化为char型数128，如果满一个字节就写入，若未满则继续组合。4．程