《哈夫曼编译码器》实验报告(共35页).doc
《《哈夫曼编译码器》实验报告(共35页).doc》由会员分享,可在线阅读,更多相关《《哈夫曼编译码器》实验报告(共35页).doc(35页珍藏版)》请在得力文库 - 分享文档赚钱的网站上搜索。
1、精选优质文档-倾情为你奉上哈夫曼编/译码器作者:田正英 联系方式: 目录 一、实验目的 二、实验内容 三、语言 四、环境 五、功能设计概述 六、详细设计 七、测试结果 八、收获与心得 九、程序代码哈夫曼编/译码器1、 实验目的1. 熟练掌握哈夫曼编译原理2. 掌握程序设计步骤二、实验内容根据哈夫曼编码原理,设计一个程序,在已知相关字符和字符对应权值(文件中存在或者用户输入)的情况下,根据用户要求对相应内容进行编码、译码等相应操作。3、 语言C语言四、编译环境Microsoft Visual C+5、 功能设计概述1. 从标准输入端输入相关的字符和权值2. 根据相关字符和权值构造哈夫曼树,并将该
2、树的相关信息写入指定文件3. 若编译码前未对哈夫曼树进行初始化,则默认为指定文件中已纯在该哈夫曼树,并将其读入到内存(因此未初始化前一定要确定指定文件中存在哈夫曼树,否则会将空树读入内存)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.w
5、eight 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.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);fprin
8、tf(fp, %d, ti.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.sta
9、rt; a = n; a+)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+
10、)if (dj.cdi != 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 (!f
11、eof(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, %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
13、 len = 0;int 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, max
15、size - 1, ott);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,
16、n);for (int k = 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.
17、用户选择界面mainswitch (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
18、:if (!tag)ReadHtFile(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: /
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 哈夫曼编译码器 哈夫曼编 译码器 实验 报告 35
限制150内