哈夫曼编码译码器课程设计

课 程 设 计 说 明 书

课程名称：数据结构与算法 设计题目：哈夫曼编\\译码器 院系：计算机科学与信息工程学院 学生姓名：刘文杰

学号： 16031210229 专业班级：软件工程16-2 指导教师：孙高飞

2017年 12 月 11日

设计题目 哈夫曼编\\译码器 限定人数 3 采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度不小于5000字节。 读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。 设字符集及频度如下表： 问题描述 字符 空格 A B C D E F G H I J 1 K L M 5 32 20 频度 186 64 13 22 32 103 21 15 47 57 字符 N O P Q R 1 S T U V W X Y Z 8 18 1 16 1 频度 57 63 15 48 51 80 23 1、根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码 2、读取文本文件，并对文件内容编码，生成编码文件 3、对编码文件进行译码，获得恢复文件 4、比较恢复文件和原文件是否相同。 基本要求与说明

课 程 设 计 任 务 书

设计题目 学生姓名 设计要求： 1.根据哈夫曼树编码原理，构造哈夫曼树，创建一套哈夫曼编码。 2.读取文本文件，并对文件内容编码，生成编码文件。 3.对编码文件进行译码，获得恢复文件。 4.比较恢复文件和原文件是否相同。 哈夫曼编\\译码器 刘文杰 所在院系 计算机科学与专业、年级、班 信息工程学院 软件工程16-2 学生应完成的工作： 1.学生应认真学习参考程序，理解每个文件、每个函数以及各个变量的作用和意义。在此基础上进一步改进程序，最后正确地运行程序。 2. 对程序进行测试，设计详细的测试计划，然后根据测试计划设计测试用例，对程序进行测试。测试时应注意对各种边缘情况进行测试。 3.完成课程设计报告。 参考文献阅读： 1.严蔚敏．数据结构（C语言版）．清华大学出版社，2011 2.谭浩强．C程序设计（第四版）．清华大学出版，2010 3.蒋立翔．C++程序设计技能百练 [M]．中国铁道出版社，2004 工作计划： 1. 小组审题，查阅资料，进行设计前的必要资料准备（3天）。 2. 把程序完整运行出来（4天）。 3. 增加改进程序（3天）。 4. 写课程设计报告（3天）。 5. 提交课程设计报告及答辩（1天） 任务下达日期：2017年 12月 01日 任务完成日期：2017年 12月 19日 指导教师（签名）：学生（签名）：

哈夫曼编\\译码器

摘要：采用哈夫曼编码思想实现对字符串的编码，以及对编码的解码。字符串的长度

不小于5000字节。读取要编码的文本文件，将文件的内容进行编码，生成新的文件。对编码文件进行解码，获得文本文件。将译码的文本文件和原文件进行比较，恢复文件和原文件必须完全一致。

关键词：

构建哈夫曼树哈弗曼编码哈夫曼译码字符串编码打印编码函数

目 录

1.设计背景 ..................................................... 1 1.1哈夫曼树的介绍 .......................................... 1 1.2设计的作用、目的 ........................................ 1 1.3设计任务及要求 .......................................... 2 2.设计方案 ..................................................... 2 2.1实验内容 ................................................ 2 2.2操作思路 ................................................ 2 2.3基本操作 ................................................ 3 3. 方案实施 .................................................... 4 3.1 C语言编程 .............................................. 4 3.2程序介绍 ............................................... 12 3.3程序流程图以及说明 ..................................... 13 图3 主程序流程图 ......................................... 13 4. 结果与结论 ................................................. 14 4.1程序运行结果 ........................................... 14 4.2总结 ................................................... 16 5. 收获与致谢 ................................................. 17 6. 参考文献 ................................................... 17

1.设计背景

1.1哈夫曼树的介绍

Huffman Tree，中文名是哈夫曼树或霍夫曼树或者赫夫曼树，它是最优二叉树。 定义：给定n个权值作为n个叶子结点，构造一棵二叉树，若树的带权路径长度达到最小，则这棵树被称为哈夫曼树。 (01) 路径和路径长度

定义：在一棵树中，从一个结点往下可以达到的孩子或孙子结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。 (02)结点的权及带权路径长度

定义：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。 (03) 树的带权路径长度

定义：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL。

1.2设计的作用、目的

通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。主要目的是加深对理论知识的理解，掌握查阅有关资料的技能，提高实践技能，培养独立分析问题、解决问题及实际应用的能力。 通过课程设计各环节的实践，应达到如下要求：

1．理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2．根据哈夫曼编码算法，考虑一个有多种可能符号（各种符号发生的概率不同）的信源，得到哈夫曼编码和码树； 3．掌握哈夫曼编码的优缺点；

1

4．通过完成具体编码算法的程序设计和调试工作，提高编程能力，深刻理解信源编码、信道编译码的基本思想和目的，掌握编码的基本原理与编码过程，增强逻辑思维能力，培养和提高自学能力以及综合运用所学理论知识去分析解决实际问题的能力，逐步熟悉开展科学实践的程序和方法。

1.3设计任务及要求

1. 理解无失真信源编码的理论基础，掌握无失真信源编码的基本方法； 2. 掌握哈夫曼编码/费诺编码方法的基本步骤及优缺点；

3. 深刻理解信道编码的基本思想与目的，理解线性分组码的基本原理与编码过程；

2.设计方案

2.1实验内容

假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，哈夫曼树的构造规则为：

1.将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；

2. 在森林中选出根结点的权值最小的两棵树进行合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和； 3. 从森林中删除选取的两棵树，并将新树加入森林；

4. 重复(02)、(03)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。

2.2操作思路

以{5,6,7,8,15}为例，来构造一棵哈夫曼树。

第1步：创建森林，森林包括5棵树，这5棵树的权值分别是5,6,7,8,15。 第2步：在森林中，选择根节点权值最小的两棵树(5和6)来进行合并，将它们作为一颗新树的左右孩子(谁左谁右无关紧要，这里，我们选择较小的作为左孩子)，并且新树

2

的权值是左右孩子的权值之和。即，新树的权值是11。 然后，将\树5\和\树6\从森林中删除，并将新的树(树11)添加到森林中。

第3步：在森林中，选择根节点权值最小的两棵树(7和8)来进行合并。得到的新树的权值是15。 然后，将\树7\和\树8\从森林中删除，并将新的树(树15)添加到森林中。 第4步：在森林中，选择根节点权值最小的两棵树(11和15)来进行合并。得到的新树的权值是26。 然后，将\树11\和\树15\从森林中删除，并将新的树(树26)添加到森林中。

第5步：在森林中，选择根节点权值最小的两棵树(15和26)来进行合并。得到的新树的权值是41。 然后，将\树15\和\树26\从森林中删除，并将新的树(树41)添加到森林中。

此时，森林中只有一棵树(树41)。这棵树就是我们需要的哈夫曼树！

3. 方案实施

3.1 C语言编程

#include #include #include

#define MAX 99999 #define N 27 //定义最多节点个数 #define M 2*N - 1 //中间节点个数

typedefstruct { int weight; int parent; intLChild; intRChild;

}HTNode,HuffmanTree[M+1];//因为零号单元不使用

typedefchar*HuffmanCode[N+1];

HuffmanCode co;//创建全局变量用于储存HuffmanCode char CH[N];

int weight[N] ={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1};

3

HuffmanTreeht;

char word[30];//全局变量用于储存键入的内容 voidInit_CH() { inti; CH[26] =' '; CH[0] ='A'; for(i=1;i<26;i++) CH[i] ='A'+i; for(i=0;i<27;i++) printf(\,CH[i]); }

void select(int*sr,int*sl,int n) { inti,point; point= MAX; for(i=0;i

voidInitHuffmanCode() { inti,sr,sl; for(i=1;i<=N;i++) { ht[i].weight = weight[i-1]; ht[i].parent = 0; ht[i].LChild= 0;

4

ht[i].RChild= 0; } for(i=N+1;i<=M;i++) { ht[i].weight = 0; ht[i].parent = 0; ht[i].LChild= 0; ht[i].RChild= 0; } printf(\初始化完成------\\n\); for(i=N+1;i<=M;i++) { select(&sr,&sl,i-1); ht[i].weight =ht[sr].weight +ht[sl].weight; ht[sr].parent =i; ht[sl].parent =i; ht[i].LChild=sr; ht[i].RChild=sl; } for(i=1;i<=M;i++) { printf(\,ht[i].parent,i); } }

voidCreateHuffmanCode() { FILE *trans; inti,start,p,c; char*cd; cd= (char*)malloc(N*sizeof(char)); cd[N-1] ='\\0'; for(i=1;i<=N;i++) { start= N-1; c =i; p =ht[i].parent; while(p) { --start; if(ht[p].LChild== c) cd[start] ='0'; else cd[start] ='1'; c = p;

5

p =ht[p].parent; } co[i] = (char*)malloc((N-start)*sizeof(char)); strcpy(co[i],&cd[start]); printf(\,co[i],i); } if((trans=fopen(\,\))==NULL) { printf(\); exit(0); } fputs(\哈夫曼编码表初始化如下------\\n\,trans); for(i=0;i

voidInputHuffmanWord() { FILE *fp; if((fp=fopen(\,\)) == NULL) { printf(\); exit(0); } printf(\请输入以'#'结束的大写字母字符串:\\n\); while(strcmp(word,\)!=0) { fputs(word,fp); gets(word); } fclose(fp); }

//选择原码输入类型 voidSelectInputType() { system(\); int point; while(1) {

6

printf(\从键盘键入编码内容\\n\); printf(\从文件中读取编码内容\\n\); printf(\退出\\n\); scanf(\,&point); system(\); switch(point) { case 0:InputHuffmanWord();break; case 1: printf(\将编码内容保存在storeWord.txt文件即可。\\n\); printf(\请进行下一步操作！\\n\); break; case 2:printf(\已经退出输入编码内容。。。\\n\);return ; default:printf(\);break; } } }

//编码

voidHuffman_Encod() { int p =M,i,flag; FILE *Input,*Output; charch; if((Output =fopen(\,\)) == NULL) { printf(\); exit(0); } if((Input =fopen(\,\)) == NULL) { printf(\); exit(0); } while(!feof(Output))//遇到输入文件的结束标识 { flag= 0; ch=fgetc(Output); //putchar(ch); for(i=0;i

7

} } if(flag == 0) { fputc('*',Input); } } fclose(Output); fclose(Input); }

//译码

voidHuffman_Decod() { FILE *fp,*Input; int p =M,i=0; charch; if((fp=fopen(\,\)) == NULL) { printf(\); exit(0); } if((Input =fopen(\,\)) == NULL) { printf(\); exit(0); } ch=fgetc(fp); while(!feof(fp)) { if(ch=='0') p =ht[p].LChild; elseif(ch=='1') p =ht[p].RChild; elseif(ch=='*') { fputs(\,Input); putchar(ch); } else printf(\); if(ht[p].LChild== 0 &&ht[p].RChild== 0) { fputc(CH[p-1],Input); putchar(CH[p-1]);

8

p = M; } ch=fgetc(fp); } fclose(fp); fclose(Input); printf(\); }

//译码与原码比较 voidCompare_word() { char ch_1,ch_2; int flag = 1; FILE *origin,*decod; if((origin =fopen(\,\)) == NULL) { printf(\); exit(0); } if((decod=fopen(\,\)) == NULL) { printf(\); exit(0); } while(!feof(decod)) { ch_1 =getc(decod); ch_2 =getc(origin); if(ch_1 !='*') { if(ch_1 != ch_2) flag= 0; } } fclose(decod); fclose(origin); if(flag == 0) printf(\原码与译码不相符！\\n\); else printf(\原码与译码相符！\\n\); }

void main() { int point;

9

}

Init_CH();

InitHuffmanCode(); CreateHuffmanCode(); while(1) {

printf(\哈夫曼编译器 ******\\n\); printf(\初始化哈夫曼表\\n\); printf(\输入编码内容\\n\); printf(\开始编码\\n\); printf(\开始译码\\n\);

printf(\与译码与原码比较\\n\); printf(\退出哈夫曼编译器\\n\); scanf(\,&point); system(\); switch(point) {

case 0:

printf(\哈夫曼表初始化完成！\\n请进行下一步操作！\\n\); break; case 1:

SelectInputType(); break; case 2:

Huffman_Encod();

printf(\编码结束！请进行下一步操作！\\n\); break; case 3:

Huffman_Decod();

printf(\译码结束！已将译码内容存放storeWord_1.txt!\\n\); printf(\请进行下一步操作！\\n\); break; case 4:

Compare_word(); break; case 5:

printf(\已经退出编译器。。。\\n\); return ;

default:printf(\);break; } }

10

3.2程序介绍

本程序的编码和运行都是在Visual C++ 6.0中实现的，在Visual Stdio中也能实现， 整个程序虽然看似庞大，但编写过程清晰，采用模块化编写，各个问题逐个击破，也方便对程序的管理和运行。整个程序的编写分为五大部分,五大部分紧密相连，环环相扣，共同实现程序的编码。

在上述存储结构上实现的哈夫曼算法可大致描述为(设T的类型为HuffmanTree)：

(1)初始化

将T[0．．m-1]中2n-1个结点里的三个指针均置为空(即置为-1)，权值置为0。 (2)输入

读入n个叶子的权值存于向量的前n个分量(即T[0．．n-1])中。它们是初始森林中n个孤立的根结点上的权值。 (3)合并

对森林中的树共进行n-1次合并，所产生的新结点依次放人向量T的第i个分量中(n≤i≤m-1)。每次合并分两步：

①在当前森林T[0．．i-1]的所有结点中，选取权最小和次小的两个根结点[p1]和T[p2]作为合并对象，这里0≤p1，p2≤i-1。

② 将根为T[p1]和T[p2]的两棵树作为左右子树合并为一棵新的树，新树的根是新结点T[i]。具体操作：

将T[p1]和T[p2]的parent置为i，

将T[i]的lchild和rchild分别置为p1和p2 新结点T[i]的权值置为T[p1]和T[p2]的权值之和。 注意：

11

合并后T[pl]和T[p2]在当前森林中已不再是根，因为它们的双亲指针均已指向了T[i]，所以下一次合并时不会被选中为合并对象。

3.3程序流程图以及说明

主程序

说明

开始 定义全局数组 a, b, c ,d 定义全局变量 定义变量 n, x, y, K, 数组 a 一维，存放输入概率 数组 b，二维存放编码过程概率 数组 c，三维，存放编码每个位置即时编码； 数组 d，一维存放码长 i 为整型变量 计数编码次数 m 为整型 n， x 为控制循环整型变量， y 为检错控制整型变量， K 为存放平均码长浮点型变量， H 为存放信源熵浮点型变量， 三重循环初始化，使其所有值为 2 初始 显示“请输入消息个数”，响蜂鸣器 输出提示 获取 N y=xiaoxi() Y ordination(m,a); 输出编码过程中产生的新概率 调用获取概率函数，将返回值给 y Y=0 存在错误，结束程序 调用获取概率函数，将返回值给 y 输出码字 输出平均码长、 信源熵，编码效率，冗余度 结束

图3 主程序流程图

12

4. 结果与结论

4.1程序运行结果

为了最大化优化程序，尽可能美观，设计了五个输入选择步骤，可多次进行选择输入输出操作，输入时可从键盘键入或者从文件指定路径获取。

printf(\哈夫曼编译器 ******\\n\printf(\初始化哈夫曼表\\n\

13

printf(\输入编码内容\\n\printf(\开始编码\\n\printf(\开始译码\\n\printf(\与译码与原码比较\\n\printf(\退出哈夫曼编译器\\n\

printf(\请输入以'#'结束的大写字母字符串:\\n\while(strcmp(word,\{

fputs(word,fp); gets(word); }

fclose(fp); }

根据编写的程序，通过while循环，在输入#时程序输入结束，即可进行译码，并将译码内容，通过程序存放在C盘中。

14

译码内容存放在指定位置，找到打开即可见。

最后可审核源码译码是否相符，退出哈夫曼编译器。

15

4.2总结

本次课程设计，让我对哈夫曼编码以及C语言有了更深的理解和操作能力。开始针对题目进行分析，将所涉及的知识点，及相关函数做了分析，大体能够把握整体的设计流程及思路。再通过查阅相关资料，使自己的知识也更加丰富了，明白了哈夫曼编码的原理以及仿真的实现。

首先对给题目进行了计算，进行哈夫曼编码，求出平均码长，编码效率，开始时不是很顺利，以前学的很多书本上的东西记得不太清楚了，经过复习课本的内容，掌握原理后顺利求出结果。然后是利用C语言编写程序，由于我现在正在公司实习，接触到编程的东西比较多，所以对C语言编程还是比较熟悉的，所以我选择使用C语言来实现仿真，仔细研究后得到程序的算法，还有我也参考了一部分网上的算法，但是在运行时还是出错了，之后又经过几次的修改，终于得出了结果，可是和自己计算的码却是相反的，而其它结果却是相同，让我疑惑了，我又仔细想了想了，原因应该出现在编码的时候，在编码过程中如果0和1赋值相反的话，就会出现这种情况，但是两种的码字应该都是正确的。过而能改，善莫大焉。在课程设计过程中，我们不断发现错误，不断改正，不断领悟，不断获取最终的检测调试环节，本身就是在践行过而能改，善莫大焉的知行观。这次课程设计终于顺利完成了，在设计中遇到了很多问题，最后在同事的指导下，终于迎刃而解。在今后社会的发展和学习实践过程中，一定要不懈努力，不能遇到问题就想到要退缩，一定要不厌其烦的发现问题所在，然后一一进行解决，只有这样，才能成功的做成想做的事，才能在今后的道路上劈荆斩棘，而不是知难而退，那样永远不可能收获成功，收获喜悦，也永远不可能得到社会及他人对你的认可!

最后通过这次课程设计使我懂得了理论与实际相结合是很重要的，只有理论 知识是远远不够的，只有把所学的理论知识与实践相结合起来，从理论中得出结 论，才能真正为社会服务，在设计过程中虽然遇到了一些问题，但经过一次又一 次的思考，一遍又一遍的检查终于找出了原因所在，也暴露出了前期我在这方面 的知识欠缺和经验不足。实践出真知，通过亲自动手制作，我掌握的知识不再是纸上谈兵，而且提高了自己的动手能力和独立思考的能力。在这过程中我收获颇丰，在此期间也得到了同学的热心帮助，在这里忠心的感谢。这个课程设计对以后的工作也很有帮助，我会在以后的工作中多将理论与实际结合，从根本上解决问题，逐步提高自己的能力。

16

5. 收获与致谢

通过这次实验让我更深刻的了解了获取输入内容，编码函数以及打印编码函数的过程。虽然在进行过程中遇到了很多问题，但在老师的帮助下和与小组成员的讨论下，都一一解决了。这次课程设计加强了我的分析问题能力和解决问题能力，也提高了我的设计和程序编码的能力。在这过程中，让我们体会到了团队的力量。感谢我的队友的帮助和张老师这一学期来的教学。

6. 参考文献

[1] 严蔚敏 . 数据结构（C语言版）[M] . 北京：清华大学出版社，2011. [2] 耿国华 . 数据结构——C语言描述[M] . 北京：高等教育出版社，2011. [3] 张铭 . 数据结构与算法 . 北京：高等教育出版社，2008.

[4] 殷人昆 . 数据结构（C语言描述）[M] . 北京：清华大学出版社，2011. [5] 胡学钢 . 数据结构（C语言版）[M] . 北京：高等教育出版社，2008.

17

指导教师评语： 1、课程设计报告： a、内容： 不完整□ 完整 □ 详细 □ b、方案设计： 较差 □ 合理 □ 非常合理□ c、实现： 未实现□ 部分实现□ 全部实现□ d、文档格式： 不规范□ 基本规范□ 规范 □ 2、出勤： 全勤 □ 缺勤次 3、答辩： a、未能完全理解题目，答辩情况较差 □ b、部分理解题目，部分问题回答正确 □ c、理解题目较清楚，问题回答基本正确 □ d、理解题目透彻，问题回答流利 □ 课程设计报告成绩：，占总成绩比例： 50% 课程设计其它环节成绩： 环节名称： 出勤 ，成绩：，占总成绩比例： 20% 环节名称： 答辩 ，成绩：，占总成绩比例： 30% 总 成 绩： 指导教师签字： 年 月 日

18

本文来源：https://www.bwwdw.com/article/rxr3.html