哈夫曼树编码以及译码 - 实验报告

华北水利水电大学 数据结构 实验报告

2013 ～2014 学年 第 一 学期 级 计算机科学与技术专业

班级： 学号： 姓名：

实验三：哈夫曼编/译码器

一． 实验目的

掌握哈夫曼树编码原理

二．实验内容

根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求赫夫曼编码，并能把给定的编码进行译码。 基本要求：

（1）初始化：从键盘输入一字符串（或读入一文件），统计出现的字符和每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树。对各个字符进行哈夫曼编码，最后打印输出字符及每个字符对应的哈夫曼编码。

（2）编码：利用已建好的哈夫曼树对“输入串”进行哈夫曼编码，最后打印输入串对应的哈夫曼编码（写入文件）。 （3）计算压缩比（选作） （4）译码：利用已建好的哈夫曼树对给定的一串代码进行译码，并打印输出得到的字符串。（选作）

测试数据：对字符串{casbcatbsatbat}进行编码；对电文“1101000”译码。字符集D={ ？},出现频率为w={？}

三． 程序源代码

#include #include #include

///.............数据结构的构造.......... typedef struct HTNode {

int weight; int parent; int lchild; int rchild;

HTNode(int w,int p,int l,int r) {

weight=w; parent=p; lchild=l; rchild=r; }

}HTNode,*HuffmanTree;

typedef char ** HuffmanCode;

typedef struct ///译码参照表 {

char word; char* code; }LNode,*List;

///.......选取最小和次小的......

void Select(HuffmanTree & HT,int num,int *s1,int *s2) {

int i;

for(i=1;i<=num;i++) {

if(HT[i].parent==0) {

*s1=i; break; } }

for(i=1;i<=num;i++) {

if(HT[i].parent==0) {

if(HT[*s1].weight>HT[i].weight) *s1=i; } }

for(i=1;i<=num;i++) {

if(i==*s1) continue;

if(HT[i].parent==0) {

*s2=i; break; } }

for(i=1;i<=num;i++) {

if(HT[i].parent==0) {

if(i==*s1) continue;

if(HT[*s2].weight>=HT[i].weight) *s2=i; } } }

///..........哈夫曼树构造函数.......... void HuffmanTreeCoding(HuffmanTree &HT,HuffmanCode &HC,int *w, int n) {

int i,c,m,start; int f,s1,s2; char *cd;

HuffmanTree p; if(n<=1) return; m=2*n-1;

HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));

for(p=HT+1,i=1;i<=n;++i,++p,++w) *p=HTNode(*w,0,0,0); for(;i<=m;++i,++p) *p=HTNode(0,0,0,0); for(i=n+1;i<=m;++i) {

Select(HT,i-1,&s1,&s2); ////调用选取最小和次小的函数 HT[s1].parent=i; HT[s2].parent=i; HT[i].lchild=s1; HT[i].rchild=s2;

HT[i].weight=HT[s1].weight+HT[s2].weight; }

HC=(HuffmanCode)malloc((n+1)*sizeof(char *)); cd=(char *)malloc(n*sizeof(char)); cd[n-1]='\\0';

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

start=n-1;

for(c=i,f=HT[i].parent;f!=0;c=f,f=HT[f].parent) {

if(HT[f].lchild==c) cd[--start]='0'; else cd[--start]='1'; }

HC[i]=(char *)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); }

free(cd); }

///.............译码函数................

int Translate(List ArrayList,char* s1,char *s2)

{

int i,j,k=0; int num=0; int len;

for(i=1;i<=5;i++) {

len=strlen(ArrayList[i].code); for(j=0;j

if(s1[k]==ArrayList[i].code[j]) {

++j; ++k; } else {

k=k-j; break; } }

if(j==len) {

s2[num++]=ArrayList[i].word; i=0; } }

return num; }

///判断是否存在

int Locate(char c,char *s,int *num) {

int i,j=0;

for(i=0;s[i]!='\\0';i++) {

if(s[i]==c) {

(*(num+i))++; j=1; } }

return j; }

///...........................................

int main() {

//要编码的字符串''casbcatbsatbat'' ///要译码\

char *transcode_result=(char*)malloc(sizeof(char)); HuffmanTree HT; HuffmanCode HC; List ArrayList;

ArrayList=(List)malloc(6*sizeof(LNode)); int i,num; int len=3; int j=0; int k=0;

char *transcode=(char*)malloc(100*sizeof(char)); char *code=(char*)malloc(100*sizeof(char)); char *s=(char*)malloc(len*sizeof(char)); int *w=(int *)malloc(len*sizeof(int)); printf(\请输入要编码的电文：\\n\ gets(code);

printf(\请输入要译码的电文：\\n\ gets(transcode);

for(i=0;code[i]!='\\0';i++) ////分析要编码的电文，并统计他们的权值

{

if(!Locate(code[i],s,w)) {

if(j>=len) {

s=(char*)realloc(s,10*sizeof(char)); w=(int*)realloc(w,10*sizeof(int)); len+=10; }

s[j]=code[i]; w[j]=1; j++;

} }

HuffmanTreeCoding(HT,HC,w,j); ///调用编码函数 for(i=1;i<=j;i++) {

ArrayList[i].word=s[i-1]; ArrayList[i].code=HC[i]; }

num=Translate(ArrayList,transcode,transcode_result); //调用译码函数

printf(\输出编码结果:\\n\ for(i=1;i<=j;i++) {

printf(\ puts(ArrayList[i].code); }

printf(\译码结果是:\\n\ for(i=0;i

printf(\ }

printf(\ return 0; }

四． 运行结果

五． 实验总结

在这次实验中，利用哈夫曼树进行编码，由于参考书中的哈夫曼编码的原理以及书中的算法，思路很明确，但在实现的过程中依然遇到了不少问题。首先是自己定义的结构体类型初始化的问题。利用原先那种“{}“初始化方法，再编译时总是出现错误，但在语法上没有错误。后来查询了MSDN,了解到这种错误在于自己定义的结构体在初始化时要利用一个构造函数。

其次是统计你输入的一段字符串中出现的各种字符以及出现的次数。我在做的过程中由于不知道要建立数组的长度，在动态创建的过程中，总是出现未利用的空间出现乱码。后来我通过专门建立一个变量来统计用到的数组长度，终于解决了这个问题。

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