哈夫曼编码解码报告.doc

目录一、设计思想……………………………………………………….02二、算法流程图…………………………………………………….03三、源代码………………………………………………………….03四、运行结果……………………………………………………….09五、遇到的问题及解决…………………………………………….11六、心得体会……………………………………………………….12一、设计思想哈夫曼的编码与解码:读取txt文件,统计所得到的文件中每个字母的权值,创建哈夫曼树,哈夫曼编码。哈夫曼解码,解码后内容写入到指定的txt文件,让用户选择不同的操作。读取txt文件,里面的内容是由英文单词组成。读取文件的时候传入文件存放的路径、读取方式以及读出以后存放的数组,最终可以得到一个存放目标文件内容的数组。将得到的数组进行字母权值的统计,统计每个字母出现的次数,次数即为每个字母的权值,在这个函数里面统计26个字母在目标文件中出现的次数,并且统计“逗号”、“句号”和“空格”的出现次数。使用的方法:每次从数组中取出一个字符,将字母的ASCII值与字母“a”相减,得到一个小于26的数,将存放权值数组的对应位置进行++运算,特殊的三个符号另作统计,如此可以得到目标文件中每个字母出现的次数。然后将字母出现次数为零的字母去掉重新组成一个字符数组,在配上对应的权值数组,统计完成后将字符数组与权值数组作为结果返回。将得到的字符数组与权值数组作为创建哈夫曼树的依据,哈夫曼树根据每个字母权值的大小来创建,每个节点,包括权值、状态(是否已经在哈夫曼树上,0代表不再哈夫曼树上,1代表在哈夫曼树上)、父节点、左子、右子和字母本身。假设有n个字母,也即是叶子节点,哈夫曼树上的节点应该为2*n–1个。前面的n个节点都有相应的字母,后面生成的n-1个节点是没有相应的字母的,用空字符替代。对每个节点进行初始化。初始化完成以后,开始创建哈夫曼树,每次选取两个权值最小的叶子节点组成一个新的节点,新的节点的左子设置为上面两个权值小的那个节点,右子为上面权值大的那个节点,权值为上面两个节点的权值的和,将上述选取出来的叶子节点标位设置为1,父节点为新创建出来的节点。将新的节点存放到原有的节点数组上,将已用过的节点从节点数组上去除。重复执行上述操作直到只剩下最后一个节点,完成哈夫曼树的创建。根据哈夫曼树进行编码,每次都从叶子节点开始遍历,设置为当前节点,根据此节点的父节点的左子是此节点还是右子是此节点,记录相应的编码0还是1,然后将此父节点设置为当前节点,重复上面的操作,直到当前节点不再具有父节点时得到该叶子节点的哈夫曼编码。将叶子节点用上面的方式进行编码,再用这些编码替换字母,从目标文件的数组中依次取出字母,将字母用相应的哈夫曼编码替代,存放到新的数组,执行完毕后,形成目标文件的哈夫曼编码,将此编码返回。根据哈夫曼树,将哈夫曼编码得到的0和1的字符串译成原先内容。解码的时候每次都站在哈夫曼树的最上面一个节点上,然后从编码得到的数组中每次取出一个字符,在根据取出的字符是‘0’还是‘1’决定是往该节点的左子走还是右子走。重复执行上面的操作,直到遇到叶子节点为止。将对应的叶子节点存放的字母存入解码数组中,重新回到根节点上,再进行上述的操作直到编码数组结束为止。得到的数组即为解码数组,解码数组作为解码的结果返回。写入txt文件,将解码得到的数组、文件的完整路径以及文件的写方式作为参数传入,将数组写入到相应的文件中。给用户相应的选择,0代表退出程序,1代表编码操作,2代表解码操作,每次根据用户的不同输入要求执行相应的功能。用一个循环来完成,当遇到0的时候就不再进行下面的操作,否则就让用户重新输入想要执行的操作。二、算法流程图从文件中读取要进行编码的内容,创建哈夫曼数,哈夫曼编码解码。将解码得到的内容写入到指定的文件中。图1哈夫曼编码译码三、源代码下面给出的是哈夫曼编码解码算法实现程序的源代码:#include<>#include<>#include<>#defineMaxValue100#defineMinValue0typedefstruct{ intflag;//节点的标志位,0代表未存在哈夫曼树上,1代表已存在 intparent; //当前节点的父节点 intleftChild;//当前节点的左子 intrightChild; //当前节点的右子 intweight; //当前节点的权值 charch; //当前节点代表的字母}HaffTree;typedefchar*HaffCode; //存放每个字母哈夫曼编码//从指定的文件中读取内容,并且存放到数组中voidReadFile(charpath[],charway[],chararray[]){