哈夫曼编码解码报告

1、目 录一、设计思想.02二、算法流程图.03三、源代码.03四、运行结果.09五、遇到的问题及解决.11六、心得体会.12一、设计思想哈夫曼的编码与解码：读取txt文件，统计所得到的文件中每个字母的权值，创建哈夫曼树，哈夫曼编码。哈夫曼解码，解码后内容写入到指定的txt文件，让用户选择不同的操作。读取txt文件，里面的内容是由英文单词组成。读取文件的时候传入文件存放的路径、读取方式以及读出以后存放的数组，最终可以得到一个存放目标文件内容的数组。将得到的数组进行字母权值的统计，统计每个字母出现的次数，次数即为每个字母的权值，在这个函数里面统计26个字母在目标文件中出现的次数，并且统计“逗号”、“

2、句号”和“空格”的出现次数。使用的方法：每次从数组中取出一个字符，将字母的ASCII值与字母“a”相减，得到一个小于26的数，将存放权值数组的对应位置进行 + 运算，特殊的三个符号另作统计，如此可以得到目标文件中每个字母出现的次数。然后将字母出现次数为零的字母去掉重新组成一个字符数组，在配上对应的权值数组，统计完成后将字符数组与权值数组作为结果返回。将得到的字符数组与权值数组作为创建哈夫曼树的依据，哈夫曼树根据每个字母权值的大小来创建，每个节点，包括权值、状态（是否已经在哈夫曼树上，0 代表不再哈夫曼树上，1 代表在哈夫曼树上）、父节点、左子、右子和字母本身。假设有n个字母，也即是叶子节点，哈

3、夫曼树上的节点应该为2*n 1个。前面的n个节点都有相应的字母，后面生成的n-1个节点是没有相应的字母的，用空字符替代。对每个节点进行初始化。初始化完成以后，开始创建哈夫曼树，每次选取两个权值最小的叶子节点组成一个新的节点，新的节点的左子设置为上面两个权值小的那个节点，右子为上面权值大的那个节点，权值为上面两个节点的权值的和，将上述选取出来的叶子节点标位设置为1，父节点为新创建出来的节点。将新的节点存放到原有的节点数组上，将已用过的节点从节点数组上去除。重复执行上述操作直到只剩下最后一个节点，完成哈夫曼树的创建。根据哈夫曼树进行编码，每次都从叶子节点开始遍历，设置为当前节点，根据此节点的父节点

4、的左子是此节点还是右子是此节点，记录相应的编码 0 还是 1，然后将此父节点设置为当前节点，重复上面的操作，直到当前节点不再具有父节点时得到该叶子节点的哈夫曼编码。将叶子节点用上面的方式进行编码，再用这些编码替换字母，从目标文件的数组中依次取出字母，将字母用相应的哈夫曼编码替代，存放到新的数组，执行完毕后，形成目标文件的哈夫曼编码，将此编码返回。根据哈夫曼树，将哈夫曼编码得到的 0 和 1 的字符串译成原先内容。解码的时候每次都站在哈夫曼树的最上面一个节点上，然后从编码得到的数组中每次取出一个字符，在根据取出的字符是0还是1决定是往该节点的左子走还是右子走。重复执行上面的操作，直到遇到叶子节点

5、为止。将对应的叶子节点存放的字母存入解码数组中，重新回到根节点上，再进行上述的操作直到编码数组结束为止。得到的数组即为解码数组，解码数组作为解码的结果返回。写入txt文件，将解码得到的数组、文件的完整路径以及文件的写方式作为参数传入，将数组写入到相应的文件中。给用户相应的选择，0 代表退出程序，1 代表编码操作，2 代表解码操作，每次根据用户的不同输入要求执行相应的功能。用一个循环来完成，当遇到 0 的时候就不再进行下面的操作，否则就让用户重新输入想要执行的操作。二、算法流程图从文件中读取要进行编码的内容，创建哈夫曼数，哈夫曼编码解码。将解码得到的内容写入到指定的文件中。图1 哈夫曼编码译码三

6、、源代码下面给出的是哈夫曼编码解码算法实现程序的源代码：#include #include #include #define MaxValue 100#define MinValue 0typedef structint flag; /节点的标志位，0 代表未存在哈夫曼树上，1 代表已存在 int parent;/当前节点的父节点 int leftChild; /当前节点的左子 int rightChild;/当前节点的右子 int weight;/当前节点的权值 char ch;/当前节点代表的字母 HaffTree;typedef char *HaffCode;/存放每个字母哈夫曼编码 /

7、从指定的文件中读取内容，并且存放到数组中 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,fp);/将文件的内容读入到字符数组中 printf(%s,array); printf(n);fclose(fp); /完成读取以后将文件关闭 /获得每个字母对应的权值，并将存在的字母存为数组，且将对应的权值返回 void Get

8、Weight(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差值 switch(m)case -53:letterWeight26+;break; /如果差值为 -53，则为逗号 case -51:letterWeight27+;break; /如果差值为 -51，则为句号 case -65:letterWeight

9、28+;break; /如果差值为 -65，则为空格 default:letterWeightm+;/根据不同的差值，对应的字母权值加 1 printf(tletterttweightn);for(i = 0; i 29; i+) /取出文件中没有出现的字母 if(letterWeighti != 0)switch(i)case 26:existLettersj+ = ,;/若存在逗号，则存入数组 weightk+ = letterWeighti;printf(t,tt%dn, letterWeighti);break;case 27:existLettersj+ = .;/若存在句号，则存入

10、数组 weightk+ = letterWeighti;printf(t.tt%dn, letterWeighti);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 CreateHaf

11、fTree(int weight, HaffTree haffTree, char 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 = ch

12、i;else /为n - 1个非叶子节点初始化 haffTreei.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;m1 = m2 = MinValue;/选取两个权值最小的节点 for(j = 0; j n +i; j+)if(haffTreej.weight = x1&haffTreej.flag = 0)

13、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 = n +i; /将左子的父节点设置为新构造的节点 haffTreem1.flag = 1;/设置标志位 1 haffTreem2.parent = n +i;/将右子的父节点设置为新构造的节点haffTreem2.flag

14、= 1;/设置标志位 1 haffTreen +i.leftChild = m1;/父节点的左子为 m1 haffTreen +i.rightChild = m2;/父节点的右子为 m2/父节点的权值为左子的权值与右子的权值的和 haffTreen +i.weight = haffTreem1.weight +haffTreem2.weight;/进行哈夫曼树的编码，将编码形成的结果作为数组返回 void EncodeHaffTree(HaffTree haffTree, int n, HaffCode haffCode, char chr, char target, char encode)

15、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(i = 0; i n; i+)start = n -1;/编码的开始位置 child = i;/设置当前节点 parent = haffTreechild.parent;/设置父节点为当前节点的父节点 while(parent != -1)

16、/如果当前节点存在父节点，则继续匹配 if(haffTreeparent.leftChild = child)/如果父节点的左子是当前节点 ch-start = 0;/将字符 0 存入数组 else/如果父节点的右子是当前节点 ch-start = 1;/将字符 1 存入数组 child = parent;/设置当前节点 parent = haffTreechild.parent;/获取当前节点的父节点 haffCodei = (char *)malloc(n - start)*sizeof(char);strcpy(haffCodei, &chstart);/存放当前叶子节点的哈夫曼编码 f

17、ree(ch);/printf(*对所给的字符进行编码*n);printf(编码后的字符串为：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 = r

18、oot = 2*n - 2;/设置遍历开始，根节点 printf(解码后的字符串为：n); for(i = 0; i strlen(encode); i+)if(encodei = 0)/如果当前字符为 0 ，则当前节点为原节点的左子 p = haffTreep.leftChild;else if(encodei = 1)/如果当前字符为 1 ，则当前节点为原节点的右子 p = haffTreep.rightChild;/如果当前节点既没有右子，又没有右子，则将对应的字符存入编码数组 if(haffTreep.leftChild = -1&haffTreep.rightChild = -1)r

19、esultj+ = 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: ); /根据文件的路径及打开方式，将指定的数组内容写入到指定的文件中 void WriteFile(char path, char way, char array) FILE *fp;fp=fopen(path, w

20、ay);fputs(array, fp);fclose(fp);main()char target100;/从文件中读取的数据放到target数组中 ReadFile(F:Test.txt, r, target);int letterWeight29=0; /存放每个字符的权值 int weight29=0;/存放去除权值为零后的字符权值 char existLetters29=0; /存放文件中所有的字符GetWeight(target, letterWeight, existLetters, weight);int n = strlen(existLetters);char resultn

21、;/存放解码形成的内容 HaffTree haffTreen*2 -1;/定义哈夫曼树 HaffCode haffCoden;/定义哈夫曼编码 printf(*构建哈夫曼数树*n); CreateHaffTree(weight, haffTree ,existLetters); /创建哈夫曼树 Print();int c;scanf(%d,&c);/根据用的选择执行相应的功能 while(c != 0)switch(c)case 1:printf(*对哈夫曼树进行编码*n); printf(编码前的字符串为：n%sn,target);char encode1000=0;/存放编码形成的内容 E

22、ncodeHaffTree(haffTree, n, haffCode, existLetters, target, 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);/执行玩用户选择的功能以后，继续让用

23、户进行选择，直到用户选择退出程序 Print();scanf(%d,&c);四、运行结果计算每个字母的权值的运行结果如下：图 2 计算字母的权值哈夫曼编码的运行结果如下：图 3 哈夫曼编码哈夫曼解码的运行结果如下：图 4 哈夫曼解码五、遇到的问题及解决这部分我主要遇到了如下三个问题，其内容与解决方法如下所列：l 为题1：在解码的时候不知道怎么将哈夫曼编码解码成原来的文件内容。用匹配的方法去找哈夫曼编码对应的内容，每次都匹配最长的一个然后输出对应的内容，但是这样匹配很容易出错，总是解码出错误的内容。而且匹配的时候用的时间特别长。为题1的解决方法：从编码表中最长的编码开始，进行与编码数组进行匹配，

24、当匹配到对应的编码的时候就将该编码的字母存入解码数组中，将编码表的起始位置重新设置，再进行上面的匹配，直到将整个编码数组解码完。这种方法进行的比较相当繁琐。新的解码方法不再使用上面的方法，解码的算法改成，首先把当前节点设置成根节点，根据得到的哈夫曼编码，看当前节点是否有下一个节点，如果有下一个节点，跟据哈夫曼树判定是将左子变成当前节点还是将右子变成当前节点。然后继续判断是否有下一个节点，重复上面的操作。当遇到当前节点没有下一个节点的时候，则将对应的叶子节点对应的字母替换哈夫曼编码，然后重新将当前节点设置为根节点，继续解析下一个字符，直到将整个哈夫曼编码都解码后得到的就是原来的内容了，这样做可以

25、省去原先的重复的比较，而且新的方法不会出现解码的错误，因为每一个都是判断当前节点是否有下一个节点来看当前当前的编码是否结束，而结束的条件只有一种可能就是当前节点是叶子节点。一旦遇到的节点是叶子节点，就将当前的节点对应的字母存入解码数组。最终形成的就是正确的内容。l 问题2：在获得每个字母权值的时候，一开始从文件中读取的内容，想用比较来实 现获得每个字母对应的权值，发现可能的情况太多，实现起来很麻烦。而且还有可能出现标点符号的情况，如果读取一个字符就比较一次取得对应的权值加 1，会形成大量的比较，运行起来比较慢。问题2 的解决方法：因为对字母的统计涉及到多个英文字母的统计，如果只是单纯的从数组中取得一个字母就进行比较，每次都有可能进行很多此的比较，才能知道应该把那个字母的权值做加 1运算。这样如果一个文件中存在大量的字母的时候会造成运行效率很低，而且重复的字母也会进行同样的操作，这是没有任何实际意义的。设计新的算法，从数组中取得一个字符，将此字符的ASCII与字符a的ASCII做减法运算，可以得到126的数字，根据得到的数字，在权值数组的相应位置加1运算，比如得到的数字为 12，则将weight12+，如果遇到标点符号，则做特殊的处理，在本算法中将逗号、句号和空格做相应的处理分别存放在权值数组的后三位中，这样就不用再做大量的比较运算，只要进行一次扫描就可以计算出每个字母的权