《数据结构实习报告》由会员分享，可在线阅读，更多相关《数据结构实习报告（9页珍藏版）》请在金锄头文库上搜索。
1、1、需求规格说明【问题描述】利用哈夫曼编码进行对已有文件进行重新编码可以大大提高减小文件大小，减少存储 空间。但是，这要求在首先对一个现有文件进行编码行成新的文件，也就是压缩。在文件使 用时，再对压缩文件进行解压缩，也就是译码，复原原有文件。试为完成此功能，写一个压 缩解压缩软件。【基本要求】(1) 压缩准备。读取指定被压缩文件，对文件进行分析，建立哈夫曼树，并给出分析 结果(包括数据集大小，每个数据的权值，压缩前后文件的大小)，在屏幕上输出。(2) 压缩。利用已建好的哈夫曼树，对文件进行编码，并将哈夫曼编码及文件编码后 的数据一起写入文件中，形成压缩文件。(3) 解压缩。打开已有压缩文件，读
2、取其中的哈夫曼编码，构建哈夫曼树，读取其中的 数据，进行译码后，写入文件，完成解压缩。2总体分析与设计【设计思想】 将一待压缩的文件以二进制形式进行读写。压缩过程中，将待压缩文件一次性读入内存， 随后对其中出现的字符进行判断和统计，将所得的字符频率创建 HuffMan 树，并对其进行 编码，将源文件的字符用其HuffMan编码代替，组合成满字节写入压缩文件。详细设计表示】变量Maxsize*KeyKeyNum *Huffman_node数据类型int input_char int huffmantree成员函数说明： char_judge功能：判断字符出现的函数；原型：bool char_ju
3、dge(char c);/判断字符出现的函数；返回类型：bool型 参数：c char型inchar_add功能：添加新出现字符的函数； 原型： void char_add(char c); 返回类型：无参数：c char型inCreateHuffTree 功能：创建哈夫曼树 原型： void CreateHuffTree();返回类型：无参数：无CreateHuffCode 功能：创建哈夫曼编码 原型： void CreateHuffCode(); 返回类型：无参数：无其它函数说明：ArrayOpp功能：将一个字符数组中的 1 字符顺序颠倒 原型：void ArrayOpp(char a,
4、int n) 返回类型：无参数：数组 a char 型 in&out nint 型DecompressionFile 功能：解压文件 原型： void DecompressionFile(FILE *ifp,FILE *ofp);/解压 返回类型：无参数：指针 ifpFILE 型in&out指针 ofpFILE 型in&outCompressFile 功能：压缩文件 原型： void CompressFile(FILE *ifp,FILE*ofp);/压缩 返回类型：无 参数：指针 ifpFILE 型in&out指针 ofpFILE 型in&outFindMax 功能：寻找数组中最大元素下标
5、原型 voidFindMax(intindex,intn,int&flag);/寻找数组中最大元素下标 返回类型：无参数：数组 index int 型 in&outn 数组长度 inflag int 型 in&out3编码【遇到的问题及解决方法】(1) 选取合适的数据结构对于一个工程的实现，到底采用怎样的数据结构，应该考虑到程序的性能和代码的可读 性。由于起初对工程的不熟，对于用什么样的数据结构来存储我一直都处在试探中，缺乏一 种长久的考虑，这也使得后面的编码过程效率不高。最终冷静下来，自定义了一个文件类和 两个辅助结构体，大体的实现框架在总体设计中已给出。(2) 哈夫曼树该如何建立首先，字符
6、的频率作为关键值，用一个循环，每次找出关键值最小的两个字符，将其组 合加入到哈夫曼树中，同时将每个哈夫曼树节点用结构体huffman_node数组存放，每个节 点都有其左右孩子和父节点的下标，这有便于后面的哈夫曼编码。(3) 哈夫曼编码的具体实现哈夫曼编码的具体实现方法：由于哈夫曼树的建立过程中为每个哈夫曼节点标明了左右 孩子和父节点，可以从关键值开始，从下往上通过父节点与子节点的关系为子节点进行编码 如果父节点的左孩子是当前子节点，则子节点(含关键值)的哈夫曼编码标为0 否则标为1， 如此循环下去。这样得到每个叶节点对应的哈夫曼编码的逆序表示，且存放在数组bits中。 然后用一个函数 Arr
7、ayOpp 将其逆序过来，从而真正得到哈夫曼编码。（4）文件的二进制形式读写操作及其压缩的实现 最主要的还是怎样实现文件的压缩，由于压缩文件中的字符是用其相应的哈夫曼编码代 替的，如果只是把字符的哈夫曼编码（也使字符型的数组存放的）写入，将会适得其反，只 有将相邻字符的编码组合成一个一个的字节数字写入才能达到节省空间的效果，例如：某字 符哈夫曼编码为bits 1 1 1 1 1 1 1这字符数组内容通过移位可转化为char型数128，如 果满一个字节就写入，若未满则继续组合。4程序及算法分析【压缩】1、先整体扫描文本，统计文本的字符个数 ，种类，以及频率记录下来。2、根据字符的频率生成相应的h
8、uffman树，生成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位，再将 其作为一个字
9、符写入压缩文件中，直至将带压缩文件的最后一个字符写满。要注意的是:若 带压缩文件最后一个字符的huffman编码赋值给c_out后c_out不满8位，则将c_out的其 余位都补 0。【解压】1、读压缩文件的头部分，定义几个变量记录字符个数，种类以及对应的频率。2、根据字符种类及频率生成huffman树。3、继续循环读压缩文件每次读一个字符，每读一个字符根据其8位机器码来遍历 huffman树，当遇到huffman树的叶子节点时终止，将叶子节点的字符写入解压后的新文件 中。当读完最后一个字符后终止循环。解压正文时每读一个字符，利用移位将该字符的8位机器码取出存入链表中，方便 huffman 树
10、的遍历。分析】主要的程序集中在两个函数中：CompressFile和DecompressionFile考虑到程序的性 能，在对文件的读写过程中，我选择在内存中对文件进行操作，在压缩时，将待压缩文件一 次性读入内存，在解压文件时，将待解压文件一次性读入内存，而不是一个字节一个字节地 读写文件。5小结通过这次课题实验的程序实践，我实在获益匪浅！数据结构是上个学期开展的一门学科， 学习这门学科也是艰辛的，因为它比较难懂，但是这门学科是非常重要的，在以后的程序设 计方面这门学科能给我们很大的帮助。这次的程序设计对我来说无疑是一个具大的考验，从接起课题后，我就一直为实现程 序而努力，翻阅相关书籍、在网上
11、查找资料。因为课本上的基础知识掌握不好，过程中遇到 了不少的阻碍，编写程序的进度也比较慢。虽然如此，但是通过自己的努力与老师的指导， 我对这次实验的原理有了一定的理解，通过参照从网上找到的源程序，终于在其它源程序的 基础下写出了本次实验的核心算法，并使其能够正常的运行。近两周的程序设计，让我体会到了作为一个编程人员的艰难，一个算法到具体实现， 再到应用层面的开发是需要有一段较长的路要走的，不是一朝一夕就可以实现的，而且在编 好程序后，编程人员还要花很多的时间去完善它，其中包含的心酸，外人是不会明白的。这次课程设计涉及对大量数据的处理，要做到精益求精，不能忽略任何一处，否则结果 将会有很大的不同
12、，总之，最大的感受就是完美源于细节！编程不仅要有一定的理论基础和 实践经验，还需要一定的毅力和关注细节的习惯。这次对文件的压缩和解压的实习，使我的 调试有了进一步的提高。同时也使我在编程中对文件的存储形式的采取有了一定的了解。希 望在以后的实习中，我会有有进一步的提高。6附录【部分核心代码】void CompressFile(FILE *ifp,FILE *ofp) opened!endl;elseif(!ifp)fseek(ifp, 0, SEEK_END);/定位到文件结尾处coutInPutFile cannot beint orignflen = ftell(ifp);char *or
13、ignfile=new char orignflen+1;fseek(ifp,0,SEEK_SET); /定位到文件起始处fread(orignfile,1,orignflen,ifp); /将文件内容一次性读到内存中orignfileorignflen=0;C_file file(512);char c;for(int i=0;iorignflen;i+)c=orignfilei;if (!file.char_judge(c)/对原文件字符进行判断和统计file.char_add(c);for(int i=1;ifile.KeyNum;i+)coutfile.Keyi.count* *4*
14、*4*A* A A J J J J J J J J J J J J J J J J J J J J J J J J *A* *A*A*A* /xr xr rZf*r xr xr /写入文件信息 fseek(ifp,0,SEEK_SET);fwrite(&orignflen,sizeof(int),1,o fp);fwrite(&file.MaxSize,sizeof(int), 1,ofp);fwrite(&file.KeyNum,sizeof(int),1 ,ofp);for(int i=1;ifile.KeyNum;i+)har),1,ofp);fwrite(&file.Keyi.count,sizeof(int),1,ofp);/ / *4 *4 *4 *4 *4 *4 *4 *4 *4 *4 *4 *4 *
