哈弗曼编码实验报告.docx
《哈弗曼编码实验报告.docx》由会员分享，可在线阅读，更多相关《哈弗曼编码实验报告.docx（17页珍藏版）》请在冰点文库上搜索。
哈弗曼编码实验报告
一.实验目的
1、掌握哈夫曼树的构造和应用
2、利用哈夫曼方法及其编/译码技术实现对传输信息编码/译码系统.
二.实验内容
1、哈夫编码/译码器简介
本例说明，先前快速远距离通信的主要手段是电报，即将需传送的文字转换成由二进制的字符组成的字符串。
在传送电文时，希望总长尽可能地短，如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，以减少经费。
哈夫曼树就是根据此原理设计出来的一种存储结构。
2、问题描述
哈夫曼树很易求出给定字符集及其概率（或频度）分布的最优前缀码。
哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。
该技术一般可将数据文件压缩掉20％至90％，其压缩效率取决于被压缩文件的特征。
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时，降低传输成本。
但是，这要求在发送端通过一个编码系统对待传送电文须预先编码，在接收须将传送来的数据进行译码。
请自行设计实现一个具有初始化、编码、译码、输入/输出等功能的哈夫曼码的编码/译码系统。
并实现以下报文的编码和译码：
“thisprogramismyfavorite”。
3．测试数据
某通信的电文字符集为26个英文字母及空格字符，其出现频度如下表所示：
4、设计思想描述
（1）问题分析。
（2）哈夫曼树中各结点的结构描述（如上图）。
（3）哈夫曼树的存储结构描述。
5、主要算法设计与实现
（1）哈弗曼树的定义（动态分配数组存储哈夫曼树）
typedefstruct{
charch;//键值
intweight;//权值
intselected;//编码值
intparent,lchild,rchild;//各节点的值
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
（2）定义用于译码的树
typedefstructTreeNode{
structTreeNode*lchild;//结构指针
structTreeNode*rchild;
charcode;
chardata;
}TreeNode,*Tree;
（3）哈夫曼树函数的设计
voidHuffmanCoding（HuffmanTree&HT,HuffmanCode&HC,int*&w,intn）{//建立哈弗曼树
intm=2*n-1,i,j,s1,s2,start,f;
char*cd;
HuffmanTreep;
if（n<=1）return;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;//0号单元未使用
for（p=HT+1,i=1;i<=n;i++,p++,w++）{
p->weight=*（w+1）;
p->selected=p->lchild=p->rchild=p->parent=0;
}
for（;i<=m;i++,p++）
p->selected=p->parent=p->lchild=p->rchild=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;
}
printf（"\n哈弗曼树表\n"）;//打印哈弗曼树表
printf（"iweightparentlchildrchild\n"）;
for（p=HT+1,i=1;i<=m;i++,p++）
printf（"%2d%6d%6d%6d%6d\n",i,p->weight,p->parent,p->lchild,p->rchild）;
printf（"\n"）;
//从叶子到根逆向求每个字符的哈夫曼编码
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;//分配n个字符编码的头指针向量
cd=（char*）malloc（n*sizeof（char））;//分配求编码的工作空间
cd[n-1]='\0';//编码结束符
for（i=1;i<=n;i++）{//逐个字符求哈夫曼编码
start=n-1;//编码结束位置for（j=i,f=HT[i].parent;f!
=0;j=f,f=HT[f].parent）{//从叶子到根逆向求编码
if（HT[f].lchild==j）
cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=（char*）malloc（（n-start）*sizeof（char））;//为第i个字符编码分配空间
strcpy（HC[i],&cd[start]）;//从cd复制编码到HC
}
free（cd）;//释放工作空间
}
（4）对编码函数的设计
voidCodeInput（intn,int*&w,char*&code）{//字符及权值的输入
inti;
w=（int*）malloc（（n+1）*sizeof（int））;//分配权值的工作空间
code=（char*）malloc（（n+1）*sizeof（char））;//分配字符的工作空间
printf（"请输入字符以及权值:
\n"）;
for（i=1;i<=n;i++）{
fflush（stdin）;//清除缓从区间
scanf（"%c%d",&code[i],&w[i]）;
}
}
voidEncoding（Sentence&sentence,char*&code,HuffmanCode&HC,intn）{//編码
charc,t,*pp;
inti;
Sentencep,q;
sentence=（Sentence）malloc（sizeof（S））;
q=sentence;
q->next=NULL;
printf（"请输入待编码的字符串:
\n"）;
fflush（stdin）;
while（scanf（"%c",&c）!
=EOF&&c!
='\n'）{
for（i=1;i<=n;i++）{
t=code[i];
if（c==t）{
pp=HC[i];
break;
}
}
for（i=0;pp[i]!
='\0';i++）{
p=（Sentence）malloc（sizeof（S））;
p->c=pp[i];
q->next=p;
p->next=NULL;
q=p;
}
}
p=sentence->next;
printf（"\n编码后的语句:
\n"）;
while（p!
=NULL）{
printf（"%c",p->c）;
p=p->next;
}
printf（"\n"）;
}
（5）对译码函数的设计
voidDecoding（Sentence&sentence,char*&code,HuffmanCode&HC,Tree&root,intn）{//译码
Treep,q;
Sentencer=sentence->next;
inti,j;
charc,*t;
root=（Tree）malloc（sizeof（TreeNode））;
root->lchild=NULL;
root->rchild=NULL;
for（i=1;i<=n;i++）{
t=HC[i];
q=root;
for（j=0;jc=t[j];
if（q->lchild!
=NULL）{
if（q->lchild->code==c）{
q=q->lchild;
}
elseif（q->rchild!
=NULL）{
q=q->rchild;
}
else{
p=（Tree）malloc（sizeof（TreeNode））;
p->lchild=NULL;
p->rchild=NULL;
p->code=c;
if（t[j+1]!
='\0'）
p->data='n';
else
p->data=code[i];
q->rchild=p;
q=p;
}
}
else{
p=（Tree）malloc（sizeof（TreeNode））;
p->lchild=NULL;
p->rchild=NULL;
p->code=c;
if（t[j+1]!
='\0'）
p->data='n';
else
p->data=code[i];
q->lchild=p;
q=p;
}
}
}
q=root;
printf（"\n解码后的语句:
\n"）;
while（r!
=NULL）{
c=r->c;
if（q->lchild!
=NULL）{
if（q->lchild->code==c）{
q=q->lchild;
if（q->lchild==NULL）{
printf（"%c",q->data）;
q=root;
}
}
else{
q=q->rchild;
if（q->lchild==NULL）{
printf（"%c",q->data）;
q=root;
}
}
}
else{
printf（"%c",q->data）;
q=root;
}
r=r->next;
}
printf（"\n\n"）;
return;}
三实验结果
根据此次实验的设计，我们编写出相应的源代码，在运行时可以得到相应的功能：
其运行界面如下图所示：
在上面输入所需输入字符集大小。
如输入26个英文字母及空格时
所得的哈弗曼树（如下图部分）及哈弗曼编码（如下图部分）
当输入带编码语句“thisprogrameismyfavorite”时，按回车，出现其编码后的语句及译码后的语句如下图：
四实验总结
通过本次数据结构的课程设计，我学习了很读我之前上课没懂的知识。
并在老师指导下，我对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。
当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。
这次课程设计中我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存保存数据，在老师的指导下改正了错误和疏漏，使我们的程序有了更高的质量。
有时还是会遇到一些这样或那样的问题，在这时就要看团体的力量，遇到困难时我们组会聚集到一块儿合力讨论，尽力把它解决，每次解决了一个问题之后就会给自己多了一份自信，对今后的学习和程序的设计有了更大的信心。
再次我真心的感谢老师对我们的帮助与指导。
我会更加努力学习数据结构方面的知识，来完善自己的学习。
五代码
#include
#include
#include
typedefstruct{
charch;
intweight;
intselected;
intparent,lchild,rchild;
}HTNode,*HuffmanTree;//动态分配数组存储哈夫曼树
typedefstructS{
charc;
structS*next;
}S,*Sentence;//用于待编码的语句
typedefchar**HuffmanCode;//动态分配数组存储哈夫曼编码表
typedefstructTreeNode{
structTreeNode*lchild;
structTreeNode*rchild;
charcode;
chardata;
}TreeNode,*Tree;//用于解码的树
voidSelect（HuffmanTree&HT,intposition,int*s1,int*s2）{//选择函数
inti,j,t;
intp,q;
intfirst,second;
for（i=1;i<=position;i++）
if（HT[i].selected==0）{
first=HT[i].weight;
break;
}
for（j=i+1;j<=position;j++）
if（HT[j].selected==0）{
second=HT[j].weight;
break;
}
if（first>second）{
t=first;
first=second;
second=t;
}
for（i=j+1;i<=position;i++）{
if（HT[i].selected==0）{
t=HT[i].weight;
if（tsecond=first;
first=t;
}
elseif（tsecond=t;
}
}
}
for（i=1;i<=position;i++）{
if（HT[i].selected==0&&HT[i].weight==first）{
HT[i].selected=1;
p=i;
break;
}
}
for（i=1;i<=position;i++）{
if（HT[i].selected==0&&HT[i].weight==second）{
HT[i].selected=1;
q=i;
break;
}
}
if（p>q）{
t=q;
q=p;
p=t;
}
*s1=p;
*s2=q;
return;
}
voidHuffmanCoding（HuffmanTree&HT,HuffmanCode&HC,int*&w,intn）{//建立哈弗曼树
intm=2*n-1,i,j,s1,s2,start,f;
char*cd;
HuffmanTreep;
if（n<=1）
return;
HT=（HuffmanTree）malloc（（m+1）*sizeof（HTNode））;//0号单元未使用
for（p=HT+1,i=1;i<=n;i++,p++,w++）{
p->weight=*（w+1）;
p->selected=p->lchild=p->rchild=p->parent=0;
}
for（;i<=m;i++,p++）
p->selected=p->parent=p->lchild=p->rchild=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;
}
printf（"\n哈弗曼树表\n"）;//打印哈弗曼树表
printf（"iweightparentlchildrchild\n"）;
for（p=HT+1,i=1;i<=m;i++,p++）
printf（"%2d%6d%6d%6d%6d\n",i,p->weight,p->parent,p->lchild,p->rchild）;
printf（"\n"）;
//从叶子到根逆向求每个字符的哈夫曼编码
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;//分配n个字符编码的头指针向量
cd=（char*）malloc（n*sizeof（char））;//分配求编码的工作空间
cd[n-1]='\0';//编码结束符
for（i=1;i<=n;i++）{//逐个字符求哈夫曼编码
start=n-1;//编码结束位置
for（j=i,f=HT[i].parent;f!
=0;j=f,f=HT[f].parent）{//从叶子到根逆向求编码
if（HT[f].lchild==j）
cd[--start]='0';
else
cd[--start]='1';
}
HC[i]=（char*）malloc（（n-start）*sizeof（char））;//为第i个字符编码分配空间
strcpy（HC[i],&cd[start]）;//从cd复制编码到HC
}
free（cd）;//释放工作空间
}
voidCodeInput（intn,int*&w,char*&code）{//字符及权值的输入
inti;
w=（int*）malloc（（n+1）*sizeof（int））;//分配权值的工作空间
code=（char*）malloc（（n+1）*sizeof（char））;//分配字符的工作空间
printf（"请输入字符以及权值:
\n"）;
for（i=1;i<=n;i++）{
fflush（stdin）;//清除缓从区间
scanf（"%c%d",&code[i],&w[i]）;
}
}
voidEncoding（Sentence&sentence,char*&code,HuffmanCode&HC,intn）{//编码
charc,t,*pp;
inti;
Sentencep,q;
sentence=（Sentence）malloc（sizeof（S））;
q=sentence;
q->next=NULL;
printf（"请输入待编码的字符串:
\n"）;
fflush（stdin）;
while（scanf（"%c",&c）!
=EOF&&c!
='\n'）{
for（i=1;i<=n;i++）{
t=code[i];
if（c==t）{
pp=HC[i];
break;
}
}
for（i=0;pp[i]!
='\0';i++）{
p=（Sentence）malloc（sizeof（S））;
p->c=pp[i];
q->next=p;
p->next=NULL;
q=p;
}
}
p=sentence->next;
printf（"\n编码后的语句:
\n"）;
while（p!
=NULL）{
printf（"%c",p->c）;
p=p->next;
}
printf（"\n"）;
}
voidDecoding（Sentence&sentence,char*&code,HuffmanCode&HC,Tree&root,intn）{//解码
Treep,q;
Sentencer=sentence->next;
inti,j;
charc,*t;
root=（Tree）malloc（sizeof（TreeNode））;
root->lchild=NULL;
root->rchild=NULL;
for（i=1;i<=n;i++）{
t=HC[i];
q=root;
for（j=0;jc=t[j];
if（q->lchild!
=NULL）{
if（q->lchild->code==c）{
q=q->lchild;
}
elseif（q->rchild!
=NULL）{
q=q->rchild;
}
else{
p=（Tree）malloc（sizeof（TreeNode））;
p->lchild=NULL;
p->rchild=NULL;
p->code=c;
if（t[j+1]!
='\0'）
p->data='n';
else
p->data=code[i];
q->rchild=p;
q=p;
}
}
else{
p=（Tree）malloc（sizeof（TreeNode））;
p->lchild=NULL;
p->rchild=NULL;
p->code=c;
if（t[j+1]!
='\0'）
p->data='n';
else
p->data=code[i];
q->lchild=p;
q=p;
}
}
}
q=root;
printf（"\n解码后的语句:
\n"）;
while（r!
=NULL）{
c=r->c;
if（q->lchild!
=NULL）{
if（q->lchild->code==c）{
q=q->lchild;
if（q->lchild==NULL）{
printf（"%c",q->data）;
q=root;
}
}
else{
q=q->rchild;
if（q->lchild==NULL）{
printf（"%c",q->data）;
q=root;
}
}
}
else{
printf（"%c",q->data）;
q=root;
}
r=r->next;
}
printf（"\n\n"）;
return;
}
intmain（void）{//主函数
HuffmanTreeHT;
HuffmanCodeHC;
Treeroot;
int*w,n,i;
char*code;
printf（"\t\t设字符集为26个英文字母，其出现频度如下表所示:
\n"）;
printf（"\t\t******************************************\n"）;
printf（"\t\t字符|空格|a|b|c|d|e|f|g|h|\n"）;
printf（"\t\t频度|186|64|13|22|32|103|21|15|47|\n"）;printf（"\n"）;
printf（"\t\t字符|i|j|k|l|m|n|o|p|q|\n"）;
printf（"\t\t频度|57|1|5|32|20|57|63|15|1|\n"）;printf（"\n"）;
printf（"\t\t字符|r|s|t|u|v|w|x|y|z|\n"）;
printf（"\t\t频度|48|51|80|23|8|18|1|16|1|\n"）;
printf（"\t\t******************************************\n"）;
printf（"请输入字符集大小n（整型）:
\n"）;
scanf（
升级会员 