哈夫曼编码和译码系统(附源代码)
- 格式:docx
- 大小:313.97 KB
- 文档页数:42
实训报告题目:哈夫曼编码和译码系统院系:
专业:
姓名:
学号:指导教师:
日期:
一.需求分析•
二.概要设计
(1)建立哈夫曼树、编码•
(2)字符匹配•
(3)哈夫曼树遍历• 3
三.详细设计及编码实现•3
四.流程图
(1)总流程图75
(2)编码实现流程图・16
(3)译码实现流程图・17
五.调试分析
(1 )计算权值-18
(1)生成哈夫曼树,建立编码表• 18 (3)将输入字符编码 19
( 4 )输入新的字符串,进行译码 19
( 5)输入新的二进制数将其译为字符 20
六 . 系统维护 20 七.实验总结 20
八. 源代码 21
一.需求分析
《1》问题描述:在传送电文时,人们总是希望传送时间尽可能短,这就是要求使电文代码长度尽可能短。利用哈夫曼编码进行通信可以大大提高信道利用率,
缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统能够
对待传输数据预先编码,在接收端将传来的数据进行译码。对于双工信道(即可以双向传输信息的信道),每段都需要一个完整的编/译系统。所以为这样的信息收发站写一个哈夫曼的编译码系统。
《2》打开一篇英文文章,统计该文章中每个字符出现的次数,然后以它们作为权值,对每一个字符进行编码,编码完成后再对其编码进行译码。问题补充:
1.从硬盘的一个文件里读出一段英语文章。
2.统计这篇文章中的每个字符出现的次数。
3.以字符出现字数作为权值,构建哈夫曼树,并将哈夫曼树的存储结构的初态和终态进行输出。
4.对每个字符进行编码并将所编码写入文件然后对所编码进行编译。
《3》这个哈夫曼编码译码主要是以英文字母输入进行编码与编译,编码译码过程
由系统自动完成,人工操作部分就是电文的录入,和编译出来时的读操作。
.概要设计
本程序主要用到了三个算法。
(1)哈夫曼树建立、编码
在初始化(I)的过程中间,要用输入的字符和权值建立哈夫曼树并求得哈夫曼编码。先将输入的字符和权值存放到一个结构体数组中,建立哈夫曼树,将计算所得的哈夫曼编码存储到另一个结构体数组中。
(2)串的匹配
在编码(D)的过程中间,要对已经编码过的代码译码,可利用循环,将代码中的与哈夫曼编码的长度相同的串与这个哈夫曼编码比较
(3)哈夫曼遍历
在印哈夫曼树(T)的中,因为哈夫曼树也是二叉树,所以就要利用二叉树的先序遍历将哈夫曼树输出。
三.详细设计及编码实现
构造哈夫曼树的方法如下:
初始化:每个字符就是一个结点,字符的频度就是结点的权;
1、将结点按频度从小到大排序;
2、选取频度最小的两个结点,以它们为儿子,构造出一个新的结点;新结点的权值就是它两个儿子的权值之和;构造之后,从原来的结点序列里删除刚才选出的那两个结点,但同时将新生成的结点加进去;
3、如果结点序列里只剩下一个结点,表示构造完毕,退出。否则回到第一步。编码:
上面已经生成了树,接着就该对该树进行编码了。
可以假定,对某个结点而言,其左孩子在当前阶段的编码为0,右孩子的编码为1。这样就可以通过“树的遍历”的方式来生成字符一一编码对照表。
来到这里,基本上艰苦的已经完成了,对某个具体的字符串编码和解码就只
是简单的“查表一一替换”的工作了。
译码:
译码也是个简单的查表--替换过程。如果利用该种编码发送字符串,则它
的“字符一一编码”对应表也必须发送过去,不然对方是不知道怎么解码的。
对给出的一串编码,从左向右,将编码组合起来并查表,“一旦”找到有匹配的字符,则马上将当前的编码替换为对应的字符。
因为该编码是不会出现”某一个字符的编码是另一个字符编码的缀”这种
情况的,也就是不会出现类似于“00 A B 0010 ”这样的情况,所以译码出来的字符串是唯一的,而且就是原来进行编码的那一个。
代码如下:
(1)求频率遍历过程:
int Frequent(char *p)
char *pt2=p;
int i=0;
ch[0]=*pt2;
freq[0]=0;
while(*pt2!='\0')
{
for(int j=O;jv=i;j++) // 在 ch[0]~ch[i]中遍历是否有 *pt2
{
if(ch[j]==*pt2)
{
freq[j]++;
break;
}
}
if(j>i) //遍历结束,该字符目前频度为1,跳至下一个字符
{
i++;
ch[i]=*pt2;
freq[i]=1;
}
pt2++;
coutvvendlvv" 统计权值:"< for(int j=O;jv=i;j++) coutvv"字符"< return i+1; } (2)预程序处理及结构体定义: #in elude viostream> #in clude using n amespace std; struct HNode { int weight; int pare nt; int LChild; int RChild; }; struct HCode //哈夫曼编码表