《哈夫曼编译码器》实验报告

1、哈夫曼编/译码器作者：田正英 联系方式： 目录 一、实验目的 二、实验内容 三、语言 四、环境 五、功能设计概述 六、详细设计 七、测试结果 八、收获与心得 九、程序代码哈夫曼编/译码器1、 实验目的1. 熟练掌握哈夫曼编译原理2. 掌握程序设计步骤二、实验内容根据哈夫曼编码原理，设计一个程序，在已知相关字符和字符对应权值（文件中存在或者用户输入）的情况下，根据用户要求对相应内容进行编码、译码等相应操作。3、 语言C语言四、编译环境Microsoft Visual C+5、 功能设计概述1. 从标准输入端输入相关的字符和权值2. 根据相关字符和权值构造哈夫曼树，并将该树的相关信息写入指定文件3

2、. 若编译码前未对哈夫曼树进行初始化，则默认为指定文件中已纯在该哈夫曼树，并将其读入到内存（因此未初始化前一定要确定指定文件中存在哈夫曼树，否则会将空树读入内存）4. 将编码结果写入指定文件 5. 将指定文件中编码内容进行哈夫曼译码6. 标准端输出已保存到相关文件中的信息（哈夫曼树存储内容、代码、译码后内容）7. 输出哈夫曼树直观图并保存到指定文件8. 用户选择界面6、 详细设计typedef struct Htnodeint lchild,rchild,parent;float weight;char data; Htnode;1. 哈夫曼树结构体：分别存储该节点左右孩子、双亲节点、该节点权

3、值、以及该节点对应字符。typedef struct Hcodechar cdsize;int start;Hcode;分别存储相应字符对应代码以及代码开始位置。此处 size 宏定义为 128 。2. 输入Inputgetchar();printf(请输入初始化字符和权值，输入#结束n);do/ 输入字符及权值 (*n)+;scanf(%c, &t*n.data);/ 注意 空格也要算字符，也要输入权值 if (t*n.data != #) scanf(%f, &t*n.weight);getchar(); while (t*n.data != #); 用户根据相关提示输入需要字符和权值（输

4、入#结束）。函数中两处用到getchar() 函数，第一处是为吸收从调用方可能引进的回车，第二处是为吸收每次输入完成后的回车。第一处可视情况添加（为保证健壮性，最好添加），第二处必须添加。3. 初始化相关函数 CreatHt、CreatHcode、Initializationfor (int j = n; j2 * n - 1; j+)float min1 = 32000;float min2 = 32000;int node1 = -1;int node2 = -1;for (int k = 0; kj; k+)if (bk.parent = -1)if (bk.weight min1)mi

5、n2 = min1;node2 = node1;min1 = bk.weight;node1 = k;else if (bk.weight min2)min2 = bk.weight;node2 = k;bj.lchild = node1;bj.rchild = node2;bnode1.parent = bnode2.parent = j;bj.weight = min1 + min2;以上为CreatHt函数部分代码。找出叶子节点中（0 n-1）最小的一个和第二小的一个节点， 由这两个节点生成双亲节点（n 2*n-1），双亲节点伪权值为该两节点权值（或伪权值）之和。重复以上操作直到所有节点

6、（2*n-1个）都确定了父子关系。Hcode ch;for (int i = 0; in; i+)ch.start = n;int f = bi.parent;int c = i;while (f != -1)if (bf.rchild = c)ch.cdch.start- = 1;else ch.cdch.start- = 0;c = f;f = bf.parent;ch.start+;cdi = ch;以上为CreatHcode函数部分代码。从叶子节点（存储字符的节点）倒序找双亲节点，判断是双亲左孩子还是右孩子，若是左孩子则在字符代码数组最后一位填0（ start标记前移一位），若是右孩子

7、则在字符代码数组最后一位填1（ start标记前移一位）。重复以上操作直到找到根结点。注意start标记的处理，此处一错满盘皆输，而且难发现错误原因。FILE *fp = fopen(op, wb+); for (int i = 0; i2 * n - 1; i+)if (in)fprintf(fp, %ct, ti.data);else fprintf(fp, #t, ti.data);fprintf(fp, %.2ft, ti.weight);fprintf(fp, %dt, ti.parent);fprintf(fp, %dt, ti.lchild);fprintf(fp, %d, ti

8、.rchild);fprintf(fp, rn);以上是Initialization函数部分代码。将所有节点信息及节点间对应关系保存到指定文件。下次编译时则无需以上繁琐的初始化过程，只需从文件中读取即可。4. 编码Encodingint j = 0;while (!feof(bb)strj = fgetc(bb);j+;int rt = 0;for (int i = 0; ij; i+) /对 str 中每个字符进行编译 for (int k = 0; kn; k+) / 在原码中查找该字符 if (pk.data = stri)for (int a = dk.start; a = n; a+

9、)codert+ = dk.cda;以上为Encoding函数部分代码。将源文件字符读到自定义缓冲区str中，将str中每个字符在初始化字符中查找，若找到则将该字符对应代码写到 code 中。其中j起到计数的作用，记录源文件字符个数。5. 译码Decodingint cs = 0;ip = 0;flag1 = 1;while (ip != len)flag1 = 1;for (int j = 0; jn & flag1; j+)/遍历每一个字符，直到找到为止 int flag2 = 1;int i = dj.start;for (; i = n & flag2; i+)if (dj.cdi !

10、= codip + i - dj.start)flag2 = 0;if (flag2 = 1)ip = ip + i - dj.start;strcs+ = pj.data;flag1 = 0;以上为Decoding函数部分代码。将初始化字符中每一个字符代码和要编译内容相应位置代码进行比对 ，若找到符合的，则相对应字符写入字符数组str中。其中ip 起计数作用，记录共编译的代码长度。ip = ip + i - dj.start;将每个已找到字符代码长度累加，ip = len时译码完成。6. 文件中哈夫曼树读入到内存 ReadHtFile*n = 0;while (!feof(fp) fscan

11、f(fp, %c, &ti.data);if (ti.data != #) (*n)+;fgetc(fp);fscanf(fp, %f, &ti.weight);fgetc(fp);fscanf(fp, %d, &ti.parent);fgetc(fp);fscanf(fp, %d, &ti.lchild);fgetc(fp);fscanf(fp, %d, &ti.rchild);fgetc(fp);i+;(*n)- -;将指定文件中的哈夫曼树写入到内存 ，fgetc(fp)是为读取每个数据之间制表符或者回车符，此处要格外小心，极易出错，稍偏差一位后面就全部错位。此处是以文本文件方式读取(若以

12、二进制方式读取应注意回车符处理)。注意：若用二进制方式读文件则行末需读两个字符 7. 标准端输出Output、OutputHt、OutputCode、OutputFile、OutputTfor (int i = 0; in; i+) int len = n - codi.start + 1;int h = len + 1;printf(%c , ati.data);printf(%.2f t, ati.weight);for (int j = 0; jh; j+)printf();printf(n);for (int k = n; k2 * n - 1; k+)int len = 0;int

13、f = k;while (atf.parent != -1)len+;f = atf.parent;int h = len + 1;printf(%c , atk.data);printf(%.2f t, atk.weight);for (int j = 0; jh; j+)printf();printf(n);以上为Output函数部分代码。将哈夫曼树直观图（凹入式）输出到标准端，第一个for循环输出叶子节点，第二个for循环输出非叶子节点 。叶子节点直接根据代码长度输出，该叶子节点深度等于代码长度加1，而非叶子节点则需逆向找双亲（与叶子节点求代码过程类似），直到找到根结点，将到根结点经过的

14、边数加1即其深度。fgets(str, maxsize - 1, pp);while (!feof(pp)printf(%s, str);fgets(str, maxsize - 1, pp);以上为OutputHt函数的部分代码。将哈夫曼树存储内容输出到标准端（字符、双亲、孩子、权值）。fgets(str, maxsize - 1, cdd);while (!feof(cdd)printf(%s, str);fgets(str, maxsize - 1, cdd); 以上为OutputCode函数部分代码。将编码后的代码内容输出到标准端。fgets(str, maxsize - 1, ott

15、);while (!feof(ott)fgets(str, maxsize - 1, ott);printf(%s, str);以上为OutputFile函数部分代码。将译码后的内容输出到标准端。for (int i = 0; in; i+)/ 输入叶子节点 int len = n - codi.start + 1;int h = len + 1;fprintf(ote, %c , ati.data);fprintf(ote, %.2f t, ati.weight);for (int j = 0; jh; j+)fprintf(ote, );fprintf(ote, n);for (int k

16、 = n; k2 * n - 1; k+)/输入非叶子节点 int len = 0，f = k;while (atf.parent != -1)len+;f = atf.parent;int h = len + 1;fprintf(ote, %c , atk.data);fprintf(ote, %.2f t, atk.weight);for (int j = 0; jh; j+)fprintf(ote, );fprintf(ote, n);以上为OutputT函数部分代码。将哈夫曼树直观图（凹入式）输出到指定文件。此函数与 Output函数相似，此处不再讲述。8. 用户选择界面mainswi

17、tch (flag)case 1: /初始化并保存printf(初始化将会删除原文件中的哈夫曼树，确认初始化吗？是（1）否（2）：);scanf(%d, &yn);switch (yn)getchar();case 1: /确认初始化Input(op, t, co, &nn); CreatHt(t, nn);/构造哈夫曼树 CreatHcode(t, co, nn);Initialization(t, op, nn);/ 将哈夫曼树写入到指定文件tag = 1;break;case 2: break;default:printf(选择有误n);break;case 2:if (!tag)Rea

18、dHtFile(op, t, co, &nn);CreatHt(t, nn);CreatHcode(t, co, nn);tag = 1;Encoding(be, cod, t, co, nn);break;case 3: if (!tag)ReadHtFile(op, t, co, &nn);CreatHt(t, nn);CreatHcode(t, co, nn);tag = 1;Decoding(cod, out, t, co, nn);break; case 4: /显示哈夫曼树存储内容case 5: /显示代码case 6: /显示译码后内容case 7: /显示哈夫曼树直观图并保存i

19、f (!tag)/若内存中不存在哈夫曼树，则需要从文件中读取，并在内存中构造哈夫曼树 ReadHtFile(op, t, co, &nn);CreatHt(t, nn);/构造哈夫曼树 CreatHcode(t, co, nn);tag = 1;Output(op, be, cod, out, outtree, flag, t, co, nn);/输出哈夫曼树直观图，并保存到指定文件 break;case Q: /退出break;default:printf(输入的选择有误，请重新输入n);/输入错误以上为main函数部分代码。用户根据菜单及相应提示进行需要的操作，每执行完一次操作重新输出菜单

20、等待用户下一个操作（错误输入会有相关提示），初始化会使文件中哈夫曼树被删除，因此也会有相关提醒，直到用户输入Q退出程序。7、 测试结果1. 查看菜单 2. 初始化3. 编码 4. 译码5. 显示代码6.显示译码后内容7. 显示哈夫曼树存储内容8. 显示哈夫曼树直观图9. Q退出10. 查看文件ToBeTran.txt （源文件）Codefile.txt（代码文件）TextFile.txt（译码文件）hfmTree.txt（哈夫曼树存储内容文件）TreePrint.txt（哈夫曼树直观图文件）8、 收获与心得本人历经3天才完成这个实验项目，开始两天写代码，隔了一段时间又花了一天写实验报告，收获颇

21、多。这是我第一次写这么长代码的一个程序（算了一下大概600行），平时也一直写代码但都是小程序（200左右）。而且我是非常认真地做这个实验，我觉得应该自己独立完成，不要上网查别人的代码，更不能抄，这样才能有所提高。对于写这个程序，一开始我是从小的方面入手，先把输入的函数完成，调试无误后再写初始化函数，经过多次输入并调试，在文件中查看，确认无误后再写下一个函数，待所有函数写完再来设计用户选择界面，做这一步操作时需该动一些函数的结构，比如输出函数Output，需要引入主函数的标志flag。程序完工后，再进行整体调试，尽可能找到最多的bug，这个过程往往是最耗时的，比如函数过多很难定位是哪里出现问题。

22、测试数据我也做了好几次改的，开始是一句话，挺好，成功了，改成多行就出错了，其中就包含回车符的处理。然后改成一大篇文章，又出现一些bug，比如数组不够大等问题，这些问题耽误了我好长一段时间，后来经过改动，比如把编码数组和译码数组移到函数外，使之变成全局变量，还不能掉了static。写的过程是艰辛的但每写完一个函数都会有成就感，当看到自己写的程序正常的跑起来的时候，整个人都是高兴的。而且还能收获很多知识，更加熟练地掌握了哈夫曼编码的原理和算法设计。以前都不知道数该用在何处，写完这个程序看到了所学的树形结构的应用。 深刻掌握了文件操作的方法和细节（克服了文本文件和二进制文件读取极易出错的地方）。总之

23、是自己独立完成的，一定会有收获。九、程序代码1. 头文件“Hf.h”#define _CRT_SECURE_NO_WARNINGS#include#include#define size 128 /存储字符相应代码#define maxsize 1024*10 / 存储需要编码的内容#define maxlen 1024*100 / 存储译码后代码typedef struct Htnodeint lchild;int rchild;int parent;float weight;char data; Htnode;typedef struct Hcodechar cdsize;/ 下标从 st

24、art 到 n , n 也算 int start;Hcode;void Input(char *op, Htnode *t, Hcode *co, int *n);void ReadHtFile(char *op, Htnode *t, Hcode *co, int *n);void Initialization(Htnode *t, char *op, int n);void CreatHt(Htnode *b, int n);void CreatHcode(Htnode *b, Hcode *cd, int n);void Encoding(char *b, char *t, Htnode

25、 *p, Hcode *d, int n);void Decoding(char *t, char *end, Htnode *p, Hcode *d, int n);void Output(char *p, char *b, char *cd, char *ot, char *ott, char ip, Htnode *at, Hcode *cod, int n);void OutputT(char *outtree, Htnode *at, Hcode *cod, int n);void OutputFile(char *ot);void OutputCode(char *cd);void

26、 OutputHt(char *p);2. 源文件“HFmain.cpp”/ 功能：哈夫曼编/译码器 / 作者：田正英/时间：2016/12/1#includehf.hint main()/功能：用户选择界面Htnode tsize;/存放每个字符相关信息（双亲、孩子、数据、权值） Hcode cosize;/存放每个字符的代码 及起始读码位置 char *op = E:hfmTree.txt;/存放哈夫曼树存储内容路径 char *be = E:ToBeTran.txt;/需要译码文件路径 char *cod = E:Codefile.txt;/写入代码的文件路径 char *out = E

27、:TextFile.txt;/译码结果写入的文件路径 char *outtree = E:TreePrint.txt;/ 将哈夫曼直观图写入指定文件 int nn = 0;char flag = 0;/程序功能选择 int tag = 0;/判断内存中是否存在哈夫曼树 ，1 存在 ， 0 不存在 while (flag != Q)printf(* * * * * * * * * * * * * * * * * *n);/ 用户选择界面 printf(* * 1.初始化并保存tt* *n* * 2.编码并保存tt* *n* * 3.译码并保存tt* *n* * 4.显示哈夫曼树存储内容t* *n

28、);printf(* * 5.显示代码ttt* *n* * 6.显示译码后内容tt* *n* * 7.显示哈夫曼树直观图并保存t* *n* * Q.退出ttt* *n);printf(* * * * * * * * * * * * * * * * * *n请选择需要执行的内容：);scanf( %c, &flag);getchar();int yn = 0;switch (flag)case 1: /初始化并保存printf(初始化将会删除原文件中的哈夫曼树，确认初始化吗？是（1）否（2）：);/危险操作再次确认 scanf(%d, &yn);switch (yn)getchar();case

29、 1: /确认初始化Input(op, t, co, &nn); /输入字符及权值, 并将字符代码初始化为 0 以保健壮 CreatHt(t, nn);/构造哈夫曼树 CreatHcode(t, co, nn);Initialization(t, op, nn);/ 将哈夫曼树写入到指定文件tag = 1;break;case 2: /不初始化break;default:printf(选择有误n);break;case 2: /编码并保存if (!tag)/若内存中不存在哈夫曼树，则需要从文件中读取，并在内存中构造哈夫曼树 ReadHtFile(op, t, co, &nn);CreatHt(

30、t, nn);/构造哈夫曼树 CreatHcode(t, co, nn);tag = 1;Encoding(be, cod, t, co, nn);/对文件中内容进行编码，并将编码内容写入指定文件 break;case 3: /译码并保存if (!tag)/若内存中不存在哈夫曼树，则需要从文件中读取，并在内存中构造哈夫曼树 ReadHtFile(op, t, co, &nn);CreatHt(t, nn);/构造哈夫曼树 CreatHcode(t, co, nn);tag = 1;Decoding(cod, out, t, co, nn);/将已编码完成的内容进行 译码 并写入到指定文件 br

31、eak;case 4: /显示哈夫曼树存储内容case 5: /显示代码case 6: /显示译码后内容case 7: /显示哈夫曼树直观图并保存if (!tag)/若内存中不存在哈夫曼树，则需要从文件中读取，并在内存中构造哈夫曼树 ReadHtFile(op, t, co, &nn);CreatHt(t, nn);/构造哈夫曼树 CreatHcode(t, co, nn);tag = 1;Output(op, be, cod, out, outtree, flag, t, co, nn);/输出哈夫曼树直观图，并保存到指定文件 break;case Q: /退出break;default:p

32、rintf(输入的选择有误，请重新输入n);/输入错误printf(n_n);/执行完毕，准备执行下个任务 printf(_n);return 0;3. 源文件“Initialization.cpp”/功能：根据相关字符和权值构造哈夫曼树，并将该树的相关信息写入指定文件#includehf.hvoid CreatHt(Htnode *b, int n) /构造哈夫曼树结构关系 for (int i = 0; i2 * n - 1; i+)bi.lchild = bi.rchild = bi.parent = -1;for (int j = n; j2 * n - 1; j+)float min

33、1 = 32000;float min2 = 32000;int node1 = -1;int node2 = -1;for (int k = 0; kj; k+)if (bk.parent = -1)if (bk.weight min1)min2 = min1;node2 = node1;min1 = bk.weight;node1 = k;else if (bk.weight min2)min2 = bk.weight;node2 = k;bj.lchild = node1;bj.rchild = node2;bnode1.parent = bnode2.parent = j;bj.wei

34、ght = min1 + min2;for (int j = n; j2 * n - 1; j+)/ 将所有非叶子节点数据域赋 # 以便观察 bj.data = #;void CreatHcode(Htnode *b, Hcode *cd, int n)/ 求哈夫曼字符代码 Hcode ch;for (int i = 0; in; i+)ch.start = n;int f = bi.parent;int c = i;while (f != -1)if (bf.rchild = c)ch.cdch.start- = 1;else ch.cdch.start- = 0;c = f;f = bf.

35、parent;ch.start+;cdi = ch;void Initialization(Htnode *t, char *op, int n) /将哈夫曼树中各节点信息写入指定文件 FILE *fp = fopen(op, wb+);/ 打开要写入哈夫曼树的文件 if (!fp)printf(cannot open hfmTree.txtn);printf(初始化失败n);return;for (int i = 0; i2 * n - 1; i+) / 将哈夫曼树写入到指定文件 if (in)fprintf(fp, %ct, ti.data);else fprintf(fp, #t, ti

36、.data);fprintf(fp, %.2ft, ti.weight);fprintf(fp, %dt, ti.parent);fprintf(fp, %dt, ti.lchild);fprintf(fp, %d, ti.rchild);fprintf(fp, rn);fclose(fp);printf(初始化完成n);4. 源文件“Input.cpp”/功能：从标准输入端输入相关的字符和权值 #includehf.hvoid Input(char *op, Htnode *t, Hcode *co, int *n) /从标准输入端输入哈夫曼树 字符和权值 (*n) = -1;getchar

37、();printf(请输入初始化字符和权值，输入#结束n);do/ 输入字符及权值 (*n)+;scanf(%c, &t*n.data);/ 注意 空格也要算字符，也要输入权值 if (t*n.data != #) scanf(%f, &t*n.weight);getchar(); while (t*n.data != #);for (int j = 0; j = *n; j+)/字符代码初始化 memset(coj.cd, 0, *n + 1);5. 源文件“Decoding.cpp”/功能：将指定文件中编码内容进行哈夫曼译码#includehf.hstatic char codmaxlen

38、;/用于存放编码后的内容，准备译码 static char strmaxsize;/用于存放译码后的内容 void Decoding(char *t, char *end, Htnode *p, Hcode *d, int n)/将指定文件中编码内容进行哈夫曼译码 FILE *te = fopen(t, rb+); / 打开需要译码内容所在的文件 if (!te)printf(cannot open Codefile.txtn);printf(译码失败n);return;FILE *en = fopen(end, w+);/打开要写入译码结果的文件 if (!en)printf(cannot

39、open TextFile.txtn);return;fscanf(te, %s, cod);int len = strlen(cod);/求代码长度 int cs = 0;int ip = 0;int flag1 = 1;while (ip != len)flag1 = 1;for (int j = 0; jn & flag1; j+)/遍历每一个字符，直到找到为止 int flag2 = 1;int i = dj.start;for (; i = n & flag2; i+)/每一个字符代码和要编译内容相应位置代码进行比对 ，直至符合为止 if (dj.cdi != codip + i -

40、 dj.start)flag2 = 0;if (flag2 = 1)ip = ip + i - dj.start;strcs+ = pj.data;flag1 = 0;strcs = 0; /最后一个字符赋值为结束符，保证健壮 fprintf(en, %s, str);/译码后内容写入指定文件 fclose(te);fclose(en);printf(译码完成n);6. 源文件“Encoding.cpp”/功能：将编码结果写入指定文件 #includehf.hstatic char strmaxsize;static char codemaxlen;/存入字符串编码结果 void Encodi

41、ng(char *b, char *t, Htnode *p, Hcode *d, int n)/将编码结果写入指定文件 FILE *bb = fopen(b, r+); / 打开需要编码内容所在的文件 if (!bb)printf(cannot open ToBeTran.txtn);printf(编码失败n);return;FILE *cc = fopen(t, wb+); /打开要写入编码结果的文件 if (!cc)printf(cannot open Codefile.txtn);return;int j = 0;while (!feof(bb)strj = fgetc(bb);j+;

42、strj = 0;int rt = 0;for (int i = 0; ij; i+) /对 str 中每个字符进行编译 for (int k = 0; kn; k+) / 在原码中查找该字符 if (pk.data = stri) /若找到 则拷贝该字符代码到 code 中 for (int a = dk.start; a = n; a+)codert+ = dk.cda;codert = 0;/最后一个字符赋值为结束符，保证健壮 fprintf(cc, %sn, code);/编译后内容写入指定文件 fclose(bb);fclose(cc);printf(编码完成n);7. 原文件“Re

43、adHtFile.cpp”/功能：若编译码前未对哈夫曼树进行初始化，则默认为指定文件中已纯在该哈夫曼树，并将其读入到内存/注意：因此未初始化前一定要确定指定文件中纯在哈夫曼树#includehf.hvoid ReadHtFile(char *op, Htnode *t, Hcode *co, int *n) /从指定文件读取哈夫曼树 *n = 0;FILE *fp = fopen(op, r);/ 打开要读入哈夫曼树的文件 if (!fp)printf(cannot open hfmTree.txtn);printf(请确认该文件是否存在，若不存在请选择初始化该文件n);return;int i = 0;while (!feof(fp) / 将指定文件中的哈夫曼树写入到内存 ，注意：若用二进制方式读文件则行末需读两个字符 fscanf(fp, %c, &ti.data);if (ti.data != #) (*n)+;fgetc(fp);fscanf(fp, %f, &ti.weight);fgetc(fp);fscanf(fp, %d, &ti.parent);fgetc(fp);fscanf(fp, %