哈夫曼编译码器数据结构实践环节实验报告

编辑:阿文时间:2020-06-24 17:46:05
哈夫曼编译码器数据结构实践环节实验报告,洛阳理工学院,设计主题哈夫曼编码器解码器,然后设计一个以它们为权重的哈夫曼编解码系统,降低传输成本,试为这样的信息收发站编写一个哈夫曼码的编译码系统。

洛阳理工学院

课程设计说明书

课程名称数据结构

设计主题哈夫曼编码器/解码器

计算机科学与技术专业

班级 ________***xx

学号:b12******x

姓名***

竣工日期:2017年6月14日

【问题描述】

打开一篇英文文章,计算文章中每个字符的次数,然后设计一个以它们为权重的哈夫曼编解码系统。采用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本。这要求在发送端由编码系统对发送的数据进行预编码,在接收端对发送的数据进行解码(恢复)。

对于双工信道(即可以在两个方向上传输信息的信道),每端都需要一个完整的编码/解码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。

【基本要求】

以每个字符出现的次数为权值,建立哈夫曼树,求出哈夫曼编码,对文件yuanwen中的正文进行编码,将结果存到文件yiwen中,再对文件yiwen中的**进行译码,结果存到textfile中。一个完整的系统应具有以下功能:

(1) i:初始化(initialization)。从终端读取字符集大小n,字符数n,权值n,建立huffman树,保存到hfmtree文件中。

(2) e:编码(encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmtree中读入),对文件tobetran中的正文进行编码,然后将结果存入文件codefile中。

(3) d:译码(decoding)。利用已建好的哈夫曼树将文件codefile中的**进行译码,结果存入文件textfile中。

【测试数据】

用下表给出的字符集和频度的实际统计数据建立哈夫曼树,并实现以下英文的编码和译码:“i like playing football”。

【算法思想】

哈夫曼编解码器的主要功能是先建立哈夫曼树,然后利用哈夫曼树生成哈夫曼码,再进行解码。

在数据通信中,通常需要将发送的文本转换成由二进制字符0和1组成的二进制字符串,称为编码。构造一棵哈夫曼树,规定哈夫曼树中的左分之代表0,右分支代表1,则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码,称之为哈夫曼编码。

最简单的二进制编码是等长编码。若采用不等长编码,让出现频率高的字符具有较短的编码,让出现频率低的字符具有较长的编码,这样可能缩短传送电文的总长度。哈夫曼树课用于构造使电文的编码总长最短的编码方案

(1) 主要流程图如图1-1所示。

(2) 设计包括以下几个方面:①heffman树的建立

哈夫曼树的建立由赫夫曼算法的定义可知,初始森林中共有n棵只含有根结点的二叉树。算法的第二步是将两棵根结点权值最小的二叉树合并成一棵新的二叉树;每次合并时,都会在林中减少一棵树,并生成一个新结点。

显然,需要n-1合并,所以共产党有n-1个新结点,都是有两个子结点的分支结点。可以看出,最终的huffman树有2n-1个结点,其中n个结点是初始森林的n个孤立结点。在heffman树中不存在度为1的分支结点。

我们可以使用大小为2n--1的一维数组来存储heffman树中的结点。

② 哈夫曼编码

要求电文的哈夫曼编码,必须先定义哈夫曼编码类型,根据设计要求和实际需要定义的类型如下:

typeset struct codenode;//编码结构的类型

③ **文件的译码

译码的基本思想是:读文件中编码,并与原先生成的哈夫曼编码表比较,遇到相等时,即取出其对应的字符存入一个新串中。

【模块划分】

1) 问题分析哈夫曼树的定义

一。huffman树节点的数据类型定义为:

typedef struct哈夫曼树的结构

char ch;

int weight权值

int parent,lchild,rchild;

}htnode,*hfmtree;

2) 实现的功能如下

1、void hfmcoding(hfmtree &ht,hfmcode &hc,int n)初始化哈夫曼树,处理inputhuffman(huffman hfm)函数得到的数据,按照哈夫曼规则建立2叉树。此函数块调用select()函数。

2、void select(hfmtree &ht,int a,int *p1,int *p2select函数,选出ht树到a为止,权值最小且parent为0的2个节点

3、encoding

编码功能:对输入字符进行编码

4、decoding

译码功能: 利用已建好的哈夫曼树将文件codefile.txt中的**进行译码,结果存入文件textfile.dat 中。

5.主函数的简要说明,主函数主要设计的是一个分支语句,让用户挑选所实现的功能。

利用链式树存储,然后调用统计频率函数、排序函数、建立哈夫曼函数、编码函数、解码函数来实现功能。

3) 系统功能模块图:

【数据结构】

(1) 哈夫曼树的存储结构描述如下:

#定义n 50/叶结点数

#define m 2*n-1//huffman树中的结点总数

typedef struct htnode;//树中的结点类型

typedef htnode huffmantree[m+1];

②哈夫曼树的算法

void createht(htnode ht,int n调用输入的数组ht,和节点数n

ht[lnode].parent=i;ht[rnode].parent=i两个最小节点的父节点是i

ht[i].weight=ht[lnode].weight+ht[rnode].weight两个最小节点的父节点权值为两个最小节点权值之和

ht[i].lchild=lnode;ht[i].rchild=rnode父节点的左节点和右节点

}}(2) 哈夫曼密码

void createhcode(htnode ht,hcode hcd,int n)

hc.startstart指向霍夫曼**hc.cd中的第一个字符

hcd[i]=hc; }}

void disphcode(htnode ht,hcode hcd,int n) //输出哈夫曼编码的列表

printf("n"); }}

void edithcode(htnode ht,hcode hcd,int n) //编码函数

}}(3) 哈夫曼解码

void dehcode(htnode ht,hcode hcd,int n) //译码函数

if(m==j当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据

}}【测试情况】

(1) 程序运行时,输入的主界面如图所示:

(2) 选择1,进入并创建一个名为yunwen的文件,如图所示:

(3)输入英语原文为 i like playing football ,如图所示:

(4) 程序对原始文本进行编码并输出结果,如下图所示:

【心得】

在我自己课程设计中,就在编写好源**后的调试中出现了不少的错误,遇到了很多麻烦及困难,我的调试及其中的错误和我最终找出错误,修改为正确的能够执行的程序中,通过分析,我学到了:

在定义头文件时可多不可少,即我们可多写些头文件,肯定不会出错,但是若没有定义所引用的相关头文件,必定调试不通过;

在执行译码操作时,不知什么原因,总是不能把要编译的二进制数与编译成的字符用连接号连接起来,而是按顺序直接放在一起,视觉效果不是很好。还有就是,很遗憾的是,我们的哈夫曼编码/译码器没有像老师要求的那样完成编一个文件的功能,这是我们设计的失败之处。

通过本次数据结构的课程设计,我学习了很多在上课没懂的知识,并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解,更巩固了课堂中学习有关于哈夫曼编码的知识

【源程序】

#include

#include

#include

#define n 5000

#define m 128//leaf结点的数目,即字符类的总数

#define m 2*m-1//huffman树中的节点数

char ch[n记录原文字符数组

char yw[n记录译文字符数组

typedef char * hcode[m+1]; //存放哈夫曼字符编码串的头指针的数组

typedef struct

dangenode记录单个字符的类别和出现次数

typedef struct

jilunode计算原始文本中的字符类型数

typedef struct node

htnode,hn[m];//静态三叉的哈夫曼树的定义

void jianliwenjian()

printf("文件已建立,名称为:yuanwen");

fclose(fp关闭文件

}输入原始文本后,将其保存到文件中

printf("请输入原文(结束标志为:^)n");

do while(ch判断结束

getchar接收回车命令

fclose(fp关闭文件

void min_2(hn ht,int n,int *tag1,int *tag2)//在建哈夫曼树的过程中,选择权值小的两

个结点 int i,min,s;

min=n;

for(i=1;i<=n;i++)

if(ht[i].weight

min=n;

for(i=1;i<=n;i++)

if(ht[i].weight

if(ht[*tag1].weight==ht[*tag2].weight&&ht[*tag2].lchild!=0)

} void chuangjian(jilunode * jilu,hn ht建立哈夫曼树、以及对原

while(!feof(fp判断文件指示标志是否移动到了文件尾处

}jilu->tag--;

fclose(fp关闭文件

printf("原文中的各字符统计状况如下:n");

printfn");

for(i=1;i<=jilu->tag;i++)

printf("n");

for(i=1;i<=2*(jilu->tag)-1;i++)

else

}for(i=jilu->tag+1;i<=2*(jilu->tag)-1;i++) }

void bianma(jilunode * jilu,hn ht,hcode hc,int n哈夫曼树建完后,对叶

子结点逐个编码

char * cd;

int start,i,p,c;

cd=(char *)malloc((n+1)*sizeof(char)); //申请存储字符的临时空间

cd[n-1]='加结束标志

for(i=1;i<=n;i++)

printf("%c的编码为:%sn",jilu->b[i].a,&cd[start]);

hc[i]=(char *)malloc((n-start)*sizeof(char)); //为字符数组分配空间

strcpy(hc[i],&cd[start]);//将临时空间中的编码复制到字符数组中

}free(cd释放临时空间

}void bianmabaocun(hcode hc,jilunode * jilu将原文以编码的形式保存到

文件yiwen中

int i,j;

file *fp;

if((fp=fopen("yiwen","wb"))==null) //以写的方式打开文件

for(i=0;i<=n&&ch[i]!='^';i++)

{for(j=1;j<=jilu->tag;j++)

if(ch[i]==jilu->b[j].a)

{fputs(hc[j],fp将文件中的字符输出到字符数组中

printf("%s",hc[j]);