《2022年2022年哈夫曼编码解码报告 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年哈夫曼编码解码报告 .pdf（12页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、目录一、设计思想 .02 二、算法流程图 .03 三、源代码 .03 四、运行结果 .09 五、遇到的问题及解决 .11 六、心得体会 .12 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 12 页 - - - - - - - - - 哈夫曼编码与解码的实现- 1 - 一、设计思想哈夫曼的编码与解码：读取 txt 文件，统计所得到的文件中每个字母的权值，创建哈夫曼树，哈夫曼编码。哈夫曼解码，解码后内容写入到指定的txt 文件，让用户选择不同的操作。读取 txt 文件，里
2、面的内容是由英文单词组成。读取文件的时候传入文件存放的路径、读取方式以及读出以后存放的数组，最终可以得到一个存放目标文件内容的数组。将得到的数组进行字母权值的统计，统计每个字母出现的次数，次数即为每个字母的权值，在这个函数里面统计26 个字母在目标文件中出现的次数，并且统计“逗号”、 “句号”和“空格”的出现次数。使用的方法：每次从数组中取出一个字符，将字母的ASCII值与字母“ a”相减，得到一个小于26 的数，将存放权值数组的对应位置进行+ 运算，特殊的三个符号另作统计，如此可以得到目标文件中每个字母出现的次数。然后将字母出现次数为零的字母去掉重新组成一个字符数组，在配上对应的权值数组，统
3、计完成后将字符数组与权值数组作为结果返回。将得到的字符数组与权值数组作为创建哈夫曼树的依据，哈夫曼树根据每个字母权值的大小来创建， 每个节点， 包括权值、 状态（是否已经在哈夫曼树上，0 代表不再哈夫曼树上，1 代表在哈夫曼树上） 、父节点、左子、右子和字母本身。假设有n 个字母，也即是叶子节点，哈夫曼树上的节点应该为2*n 1 个。前面的 n 个节点都有相应的字母，后面生成的n-1个节点是没有相应的字母的，用空字符替代。对每个节点进行初始化。初始化完成以后，开始创建哈夫曼树， 每次选取两个权值最小的叶子节点组成一个新的节点，新的节点的左子设置为上面两个权值小的那个节点，右子为上面权值大的那个
4、节点，权值为上面两个节点的权值的和，将上述选取出来的叶子节点标位设置为1，父节点为新创建出来的节点。将新的节点存放到原有的节点数组上，将已用过的节点从节点数组上去除。重复执行上述操作直到只剩下最后一个节点，完成哈夫曼树的创建。根据哈夫曼树进行编码，每次都从叶子节点开始遍历，设置为当前节点，根据此节点的父节点的左子是此节点还是右子是此节点，记录相应的编码0 还是1，然后将此父节点设置为当前节点， 重复上面的操作， 直到当前节点不再具有父节点时得到该叶子节点的哈夫曼编码。 将叶子节点用上面的方式进行编码，再用这些编码替换字母，从目标文件的数组中依次取出字母，将字母用相应的哈夫曼编码替代，存放到新的
5、数组，执行完毕后，形成目标文件的哈夫曼编码，将此编码返回。根据哈夫曼树， 将哈夫曼编码得到的0 和 1 的字符串译成原先内容。解码的时候每次都站在哈夫曼树的最上面一个节点上，然后从编码得到的数组中每次取出一个字符，在根据取出的字符是0还是 1决定是往该节点的左子走还是右子走。重复执行上面的操作，直到遇到叶子节点为止。将对应的叶子节点存放的字母存入解码数组中，重新回到根节点上，再进行上述的操作直到编码数组结束为止。得到的数组即为解码数组，解码数组作为解码的结果返回。写入 txt 文件，将解码得到的数组、文件的完整路径以及文件的写方式作为参数传入，将数组写入到相应的文件中。给用户相应的选择，0 代
6、表退出程序，1 代表编码操作， 2 代表解码操作，每次根据用户的不同输入要求执行相应的功能。用一个循环来完成，当遇到0 的时候就不再进行下面的操作，否则就让用户重新输入想要执行的操作。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 12 页 - - - - - - - - - 哈夫曼编码与解码的实现- 2 - 二、算法流程图从文件中读取要进行编码的内容，创建哈夫曼数， 哈夫曼编码解码。将解码得到的内容写入到指定的文件中。图 1 哈夫曼编码译码三、源代码下面给出的是哈夫曼编
7、码解码算法实现程序的源代码：#include #include #include #define MaxValue 100 #define MinValue 0 typedef struct int flag; /节点的标志位， 0 代表未存在哈夫曼树上，1 代表已存在int parent; /当前节点的父节点int leftChild; /当前节点的左子int rightChild; /当前节点的右子int weight; /当前节点的权值char ch; /当前节点代表的字母名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名
8、师精心整理 - - - - - - - 第 3 页，共 12 页 - - - - - - - - - 哈夫曼编码与解码的实现- 3 - HaffTree; typedef char *HaffCode; /存放每个字母哈夫曼编码/从指定的文件中读取内容，并且存放到数组中void ReadFile(char path, char way, char array) FILE *fp; int i =0; /根据路径和打开方式打开指定的文件，判断操作是否成功if(fp=fopen(path, way)=NULL) printf(cant open the file); fgets(array,100
9、,fp);/ 将文件的内容读入到字符数组中printf(%s,array); printf(n); fclose(fp); /完成读取以后将文件关闭 /获得每个字母对应的权值，并将存在的字母存为数组，且将对应的权值返回void GetWeight(char array,int letterWeight, char existLetters, int weight) int i, j=0, k=0, m, n = strlen(array);/n 代表 array 数组的长度for(i = 0; i n; i+) m = arrayi-a; /计算当前字母与字符a 的 ASCII 差值switc
10、h(m) case -53:letterWeight26+;break; /如果差值为-53，则为逗号case -51:letterWeight27+;break; /如果差值为-51，则为句号case -65:letterWeight28+;break; /如果差值为-65，则为空格default:letterWeightm+; /根据不同的差值，对应的字母权值加1 printf(tletterttweightn); for(i = 0; i 29; i+) /取出文件中没有出现的字母 if(letterWeighti != 0) switch(i) case 26: existLetter
11、sj+ = ,; /若存在逗号，则存入数组weightk+ = letterWeighti; printf(t,tt%dn, letterWeighti);break; case 27: 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 12 页 - - - - - - - - - 哈夫曼编码与解码的实现- 4 - existLettersj+ = .; /若存在句号，则存入数组weightk+ = letterWeighti; printf(t.tt%dn, letter
12、Weighti);break; case 28: existLettersj+ = ; /若存在空格，则存入数组weightk+ = letterWeighti; printf(t 空格 tt%dn,letterWeighti);break; default: existLettersj+ = i +a; /一般情况还原字母存入weightk+ = letterWeighti; printf(t%ctt%dn,i+a,letterWeighti); /根据每个字母的权值，创建哈夫曼树void CreateHaffTree(int weight, HaffTree haffTree, char
13、ch) int i, j, x1, x2, m1, m2, n, k; n = strlen(ch); /计算字母数组的长度for(i = 0; in*2 -1; i+) /为哈夫曼树的2*n -1 个节点初始化 if(in) /为 n 个叶子节点初始化 haffTreei.weight = weighti; haffTreei.flag = 0; haffTreei.parent = -1; haffTreei.leftChild = -1; haffTreei.rightChild = -1; haffTreei.ch = chi; else /为 n - 1 个非叶子节点初始化 haff
14、Treei.weight = 0; haffTreei.flag = 0; haffTreei.parent = -1; haffTreei.leftChild = -1; haffTreei.rightChild = -1; haffTreei.ch = ; for(i = 0; in -1; i+) /构造哈夫曼树 x1 = x2 = MaxValue; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 12 页 - - - - - - - - - 哈夫曼编码与解码的实
15、现- 5 - m1 = m2 = MinValue; /选取两个权值最小的节点for(j = 0; j n +i; j+) if(haffTreej.weight = x1&haffTreej.flag = 0) x2 = x1; x1 = haffTreej.weight; /x1 代表左子的权值m2 = m1; m1 = j; /m1 代表左子的下标 else if(haffTreej.weight x2&haffTreej.flag = 0) x2 = haffTreej.weight; /x2 代表右子的权值m2 = j; /m2 代表右子的下标 haffTreem1.parent =
16、 n +i; /将左子的父节点设置为新构造的节点haffTreem1.flag = 1; /设置标志位1 haffTreem2.parent = n +i; /将右子的父节点设置为新构造的节点haffTreem2.flag = 1; /设置标志位1 haffTreen +i.leftChild = m1; /父节点的左子为m1 haffTreen +i.rightChild = m2; /父节点的右子为m2 /父节点的权值为左子的权值与右子的权值的和haffTreen +i.weight = haffTreem1.weight +haffTreem2.weight; /进行哈夫曼树的编码，将编
17、码形成的结果作为数组返回void EncodeHaffTree(HaffTree haffTree, int n, HaffCode haffCode, char chr, char target, char encode) int child, parent, start, i, j=0; char *ch; ch = (char *)malloc(n*sizeof(char); /分配可以放得下n 个字符的内存空间/分配可以放得下n +1 个字符指针的内存空间haffCode = (HaffCode *)malloc(n+1)*sizeof(char *); chn -1 =0; for(
18、i = 0; i n; i+) start = n -1; /编码的开始位置child = i; /设置当前节点parent = haffTreechild.parent; /设置父节点为当前节点的父节点while(parent != -1) /如果当前节点存在父节点，则继续匹配名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 12 页 - - - - - - - - - 哈夫曼编码与解码的实现- 6 - if(haffTreeparent.leftChild = chil
19、d) /如果父节点的左子是当前节点 ch-start = 0; /将字符0 存入数组 else /如果父节点的右子是当前节点 ch-start = 1; /将字符1 存入数组 child = parent; /设置当前节点parent = haffTreechild.parent; /获取当前节点的父节点 haffCodei = (char *)malloc(n - start)*sizeof(char); strcpy(haffCodei, &chstart); /存放当前叶子节点的哈夫曼编码 free(ch); /printf(*对所给的字符进行编码*n); printf( 编码后的字符串
20、为：n); for(i = 0; istrlen(target); i+) /将目标文件编码作为结果返回 for(j = 0; j n; j+) if(targeti = chrj) strcat(encode, haffCodej); printf(%s,haffCodej); /根据哈夫曼树进行哈夫曼解码，结果存入数组返回void DecodeHaffTree(HaffTree haffTree, int n, char encode, char result) int root, p, i, j=0; p = root = 2*n - 2; /设置遍历开始，根节点printf( 解码后的
21、字符串为：n); for(i = 0; i strlen(encode); i+) if(encodei = 0) /如果当前字符为0 ，则当前节点为原节点的左子 p = haffTreep.leftChild; else if(encodei = 1) /如果当前字符为1 ，则当前节点为原节点的右子 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 12 页 - - - - - - - - - 哈夫曼编码与解码的实现- 7 - p = haffTreep.rightChi
22、ld; /如果当前节点既没有右子，又没有右子，则将对应的字符存入编码数组if(haffTreep.leftChild = -1&haffTreep.rightChild = -1) resultj+ = haffTreep.ch; printf(%c,haffTreep.ch); p = root; /重新回到根节点，继续解码 void Print() /打印功能的选择表 printf(n*选择功能 *n); printf(0. 退出程序 n); printf(1. 哈夫曼编码 n); printf(2. 哈夫曼解码 n); printf(please input num 1 or 2: );
23、 /根据文件的路径及打开方式，将指定的数组内容写入到指定的文件中void WriteFile(char path, char way, char array) FILE *fp; fp=fopen(path, way); fputs(array, fp); fclose(fp); main() char target100; / 从文件中读取的数据放到target 数组中ReadFile(F:Test.txt, r, target); int letterWeight29=0; /存放每个字符的权值int weight29=0; /存放去除权值为零后的字符权值char existLetters
24、29=0; /存放文件中所有的字符GetWeight(target, letterWeight, existLetters, weight); int n = strlen(existLetters); char resultn; /存放解码形成的内容HaffTree haffTreen*2 -1; /定义哈夫曼树HaffCode haffCoden; /定义哈夫曼编码printf(*构建哈夫曼数树*n); CreateHaffTree(weight, haffTree ,existLetters); /创建哈夫曼树Print(); int c; scanf(%d,&c); 名师资料总结 -
25、- -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 12 页 - - - - - - - - - 哈夫曼编码与解码的实现- 8 - /根据用的选择执行相应的功能while(c != 0) switch(c) case 1: printf(*对哈夫曼树进行编码*n); printf( 编码前的字符串为：n%sn,target); char encode1000=0; /存放编码形成的内容EncodeHaffTree(haffTree, n, haffCode, existLetters, tar
26、get, encode); break; case 2: printf(n*对得到的编码进行解码*n); printf( 解码前的字符串为：n%sn,encode); DecodeHaffTree(haffTree, n, encode, result); WriteFile(F:writeFile.txt, w, result); break; default: printf(input error ,please input correct num:1 or 2); /执行玩用户选择的功能以后，继续让用户进行选择，直到用户选择退出程序Print(); scanf(%d,&c); 四、运行结
27、果计算每个字母的权值的运行结果如下：图 2 计算字母的权值名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 12 页 - - - - - - - - - 哈夫曼编码与解码的实现- 9 - 哈夫曼编码的运行结果如下：图 3 哈夫曼编码哈夫曼解码的运行结果如下：图 4 哈夫曼解码名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 12 页 - - - - -
28、 - - - - 哈夫曼编码与解码的实现- 10 - 五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：为题 1：在解码的时候不知道怎么将哈夫曼编码解码成原来的文件内容。用匹配的方法去找哈夫曼编码对应的内容，每次都匹配最长的一个然后输出对应的内容，但是这样匹配很容易出错，总是解码出错误的内容。而且匹配的时候用的时间特别长。为题 1 的解决方法： 从编码表中最长的编码开始，进行与编码数组进行匹配，当匹配到对应的编码的时候就将该编码的字母存入解码数组中，将编码表的起始位置重新设置，再进行上面的匹配，直到将整个编码数组解码完。这种方法进行的比较相当繁琐。新的解码方法不再使
29、用上面的方法，解码的算法改成，首先把当前节点设置成根节点，根据得到的哈夫曼编码，看当前节点是否有下一个节点，如果有下一个节点，跟据哈夫曼树判定是将左子变成当前节点还是将右子变成当前节点。然后继续判断是否有下一个节点， 重复上面的操作。当遇到当前节点没有下一个节点的时候，则将对应的叶子节点对应的字母替换哈夫曼编码，然后重新将当前节点设置为根节点，继续解析下一个字符，直到将整个哈夫曼编码都解码后得到的就是原来的内容了，这样做可以省去原先的重复的比较， 而且新的方法不会出现解码的错误，因为每一个都是判断当前节点是否有下一个节点来看当前当前的编码是否结束，而结束的条件只有一种可能就是当前节点是叶子节点
30、。 一旦遇到的节点是叶子节点，就将当前的节点对应的字母存入解码数组。最终形成的就是正确的内容。问题 2：在获得每个字母权值的时候，一开始从文件中读取的内容，想用比较来实现获得每个字母对应的权值，发现可能的情况太多，实现起来很麻烦。而且还有可能出现标点符号的情况，如果读取一个字符就比较一次取得对应的权值加1，会形成大量的比较，运行起来比较慢。问题2 的解决方法：因为对字母的统计涉及到多个英文字母的统计，如果只是单纯的从数组中取得一个字母就进行比较，每次都有可能进行很多此的比较，才能知道应该把那个字母的权值做加1 运算。这样如果一个文件中存在大量的字母的时候会造成运行效率很低， 而且重复的字母也会
31、进行同样的操作，这是没有任何实际意义的。设计新的算法，从数组中取得一个字符，将此字符的ASCII 与字符 a 的 ASCII 做减法运算，可以得到 126 的数字，根据得到的数字，在权值数组的相应位置加1 运算，比如得到的数字为12，则将weight12+ ，如果遇到标点符号，则做特殊的处理，在本算法中将逗号、 句号和空格做相应的处理分别存放在权值数组的后三位中，这样就不用再做大量的比较运算， 只要进行一次扫描就可以计算出每个字母的权值了。得到这些权值以后就可以进行判断其中的一些字母是否出现过，根据权值是否等于零判断对应的字母是否出现过， 把没有出现过的字母舍弃，把有权值的字母挨个存储在字符数
32、组中，在对应配上相应的权值， 这样就可以实现想要的效果了，计算每个字母的权值，为创建哈夫曼树做好准备。为题 3：文件的读取出现错误，读取出的文件内容只有最后一个单词。问题 3 的解决方法：原来使用的是fscanf 来进行文件的读取，这个函数的读取是空格分开读取的，遇到空格就开始重新存放，所以最终存放的就是最后一个单词。用fgets 函数来实现读取可以将整个文件的内容读取到指定的数组中，这样存放的数组是正确的。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 12 页 -
33、- - - - - - - - 哈夫曼编码与解码的实现- 11 - 六、心得体会通过哈夫曼编码解码的编写，我对哈夫曼编码解码有了更深刻的认识，也明白了这部分知识在信息技术应用中的重要地方。在编写代码的过成中我发现了学习上的很多问题，在遇到文件读取的时候总会得到错误的信息， 还有动态数组的应用，对这两部分的知识特别的陌生，以后在学习中要加强这些知识的学习， 以达到熟练掌握的程度，平时的学习中虽然很少用到的知识也应该经常练习，否则用的时候就陌生无从下手了。还有在写代码的时候总是出现一些莫名奇妙的错误，后来检查发现很多都是自己的精神不够集中，而且思路不清晰。这些问题让我明白了一个道理，作为一个程序员
34、，时刻都要保持思路的清晰，这样可以省去很多没必要的麻烦。而这次作业， 给自己一个不得不动手操作的机会，有问题自己想办法解决，平时也和同学一块交流学到很多自己平时没有注意到的知识。最后程序调试出来的时候，会觉得真的很高兴。我知道，我们现在的水平还很差，要想学习好这门课，在以后就要多动手操作，书上的例题或算法， 最好都自己编写程序实现，那样可以加深对算法的理解，也可以提高我们编程的水平。平时老师演示的算法，最好自己都去实现一遍。否则很难真正理解算法。也没法把算法用好同时，很多的东西，理解了，可是在实现的时候还是有很多的错误发生，在以后的练习和实践中，应该多动手，遇到问题多思考，虽然很多想法都不能实现，但是通过思考，我们可以学到更多的知识。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 12 页 - - - - - - - - -