数据结构实验报告.doc

数据结构实验报告1实验目的a.学会使用哈夫曼进行对文本文件的编码与译码。b.通过对哈夫曼的编码与译码，能够理解通信领域中的数据传输的压缩原理。c.通过对哈夫曼的编码/译码器的研究与分析，能够彻底的理解软件设计的一般步骤和方法，灵活地运用各种数据结构进行操作，熟练地把所学地数据结构应用地软件开发当中，提高软件设计水平，增强程序设计能力。2.2软件主要功能a.压缩：实现对文本文件的压缩，生成一个比原文件还小的压缩文件。b.解压：能够对已经压缩的这个文件进行解压，恢复原来的文本文件。2.3实验主要目标a.读取文本文件，并统计文件中字符个数b.建立Huffman树c.对文件进行Huffman编码2.4功能扩展a.在实现对文本文件进行编码与译码功能完成后，实现对文本文件中的任意字符进行编码，包括汉字。b.实现a功能后，实现对其他的如PDF等文件进行编码与译码。三、概要设计说明书说明这个程序的主要功能模块的划分，详细说明各个模块的程序流程。3.1编码过程文本文件统计文件当中每个字符出现的概率根据字符出现的概率建立哈夫曼树对文件进行编码生成一个文本文件生成一个非文本压缩文件3.2解码过程压缩文件生成一个文本文件对该文件根据哈夫曼树进行译码将解码后字符存入新的文件生成解压后的文件3.3程序流程图3.4程序流程文字描述根据题目要求，哈夫曼解压缩软件工可以分为两个主要过程，现就这两个过程进行描述：a、压缩：首先从源文本文件当中读取数据，统计出字符各自出现的概率；在此基础上，根据统计出的概率建立哈夫曼树，并将该哈夫曼树的存储结果用文件保存；哈夫曼树建立好后，然后进行哈夫曼编码，并且将各个字符编码后的0、1码存储在文件当中；再一次读取源文件，对源文件进行压缩，将压缩后的二进制代码存储在文本文件中，生成一个文本文件；最后，对这个文本文件进行处理，生成一个二进制文件，其中一个字节代表上一个文件的8个0、1码。 b、解压：首先根据二进制文件生成一个文本文件，这个文本文件比那个二进制文件要大，其中一个字节代表压缩文件的1位；按照哈夫曼树，将哈夫曼文件当中的哈夫曼编码生成对应的字符，存储在一个文本文件当中。至此，哈夫曼的编码/译码器就实现了。四、详细设计说明书说明程序当中对哈夫曼编码与译码所用的数据结构（ADT），说明各个模块的函数关系，说明各个函数所使用的算法，画出函数关系图，说明输入与输出。4.1编码过程数据流图（DFD）4.2编码具体过程a.统计原文本文件的字符出现的概率算法描述：使用数据结构：typedef struct char letter; /记录该字符是whatint count; /统计该字符出现的次数float probability; /记录该字符的概率Letter;#define N_LETTER 123 /定义字符的种类个数算法描述：void CacuProbability(Letter *le) /*初始化统计字符的数组，让le中的letter存入一个变量，数组的编号与字符的ASCII码相同*/for(i = 0; i N_LETTER; i+) lei.letter = i; /存入ASCII为0122之间的所有字符lei.count = 0; /初始化字符个数为零bability = 0; /初始化各个字符出现的概率为零/*主要字符下表与ASCII码对应关系 (48:0)(49:1)(50:2)(51:3)(52:4)(53:5)(54:6)(55:7)(56:8)(57:9)(58:)(59:;)(60:)(63:?)(64:)(65:A)(66:B)(67:C)(68:D)(69:E)(70:F)(71:G)(72:H)(73:I)(74:J)(75:K)(76:L)(77:M)(78:N)(79:O)(80:P)(81:Q)(82:R)(83:S)(84:T)(85:U)(86:V)(87:W)(88:X)(89:Y)(90:Z)(91:)(92:)(93:)(94:)(95:_)(96:)(97:a)(98:b)(99:c)(100:d)(101:e)(102:f)(103:g)(104:h)(105:i)(106:j)(107:k)(108:l)(109:m)(110:n)(111:o)(112:p)(113:q)(114:r)(115:s)(116:t)(117:u)(118:v)(119:w)(120:x)(121:y) (122:z)*/*统计字符出现的个数*/all_num = 0;while(!feof(fp) ch = read_a_letter(fp); /从原文件中读取一个字符all_num = all_num + 1; /统计所有的字符个数i = ch; /将ch强制转化为其对应的ASCII值lei.count = lei.count + 1; /让对应的字符数量增加一个/*计算频率*/for(i = 0; i N_LETTER; i+) bability = (float)lei.count / (float)all_num;b.使用静态三叉链表实现哈夫曼树，其数据结构类型定义如下：#define N_LEAF 20 /叶子结点个数的最大值#define M 2*N_LEAF 1 /所有结点个数的最大值typedef struct /存储哈夫曼树的结构体定义float weight; /存放结点的权值int parent; /存放父亲结点的下标int LChild; /存放左孩子结点的下标int RChild; /存放右孩子结点的下标HTNode;HTNode htM+1; /把存放哈夫曼树的结构体定义为一个宏,0号单元不用算法描述：/*创建哈夫曼树htM+1,w存放的是N_LEAF个叶子结点的权值*/void CreateHuffmanTree(int w) for(i = 1; i = N_LEAF; i+) /1-N_LEAF号单元存放叶子结点，对其初始化hti = wi, 0, 0, 0;for(i = N_LEAF + 1; i = M; i+) /N_LEAF + 1-M号单元存放非叶子结点，对其初始化hti = 0, 0, 0, 0;for(i = N_LEAF + 1; i = M; i+) /创建非叶子结点，建立哈夫曼树/*在ht1-hti-1之间找出两个权值最小并且其父结点是0的结点，返回单元序号，存*在min1和min2*/select(i 1, &min1, &min2);hti.weight = htmin1.weight + htmin2.weight; /修改父结点的权值hti.LChild = min1; /修改父结点的左孩子指向hti.RChild = min2; /修改父结点的右孩子指向htmin1.parent = htmin2.parent = i; /修改左右孩子的父亲结点/*这个函数会被创建哈夫曼树的函数所调用，其功能是：选择ht1-htn之间的两个权值*最小并且其父结点是0的结点，并且将其所对应的序号存放在min1和min2当中*/void select(int n, int *min1, int *min2) int i, flag1 = 1, flag2 = 1; /flag1和flag2用来标记（*min1）和（*min2）是否赋值float x; /x记录找到最小的权值/*给(*min1)和(*min2)初始化*/for(i = 1; i (*min1)*/if(ht*min1.weight ht*min2.weight) (*min1) = (*min1) + (*min2);(*min2) = (*min1) - (*min2);(*min1) = (*min1) - (*min2);/*找到最小的值给（*min1），用x记录（*min1）的权值并将（*min1）的权值改为一个较大的值*/for(i = 1; i hti.weight) *min1 = i;x = ht*min1.weight;ht*min1.weight = 2;/*用同样的方法，找出权值最小的值，并将其赋给（*min2），实际当中这样（*min2）当中存放的权值次小的值*/for(i = 1; i hti.weight) *min2 = i;/*将记录的（*min1）的原始值赋给原来的，这样（*min1）当中存放的是权值最小的，而（*min2）当中存放的是权值次小的值*/ht*min1.weight = x; c.对哈夫曼树进行哈夫曼编码，并且将结果写到哈夫曼编码的文件当中/*从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码*/void CreateHuffmanCode(char hc, int n) char ch8;int start, child, parent, i;cd = (char *)malloc(n