哈弗曼编码实验报告Word下载.docx
《哈弗曼编码实验报告Word下载.docx》由会员分享，可在线阅读，更多相关《哈弗曼编码实验报告Word下载.docx（17页珍藏版）》请在冰点文库上搜索。
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）;
selected=p->
lchild=p->
rchild=p->
parent=0;
}
for（;
=m;
i++,p++）
parent=p->
rchild=0;
for（i=n+1;
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"
）;
//打印哈弗曼树表
iweightparentlchildrchild\n"
printf（"
%2d%6d%6d%6d%6d\n"
i,p->
weight,p->
parent,p->
lchild,p->
rchild）;
\n"
//从叶子到根逆向求每个字符的哈夫曼编码
HC=（HuffmanCode）malloc（（n+1）*sizeof（char*））;
//分配n个字符编码的头指针向量
cd=（char*）malloc（n*sizeof（char））;
//分配求编码的工作空间
cd[n-1]='
\0'
;
//编码结束符
for（i=1;
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
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））;
//分配字符的工作空间
请输入字符以及权值:
i++）{
fflush（stdin）;
//清除缓从区间
scanf（"
%c%d"
&
code[i],&
w[i]）;
voidEncoding（Sentence&
sentence,char*&
code,HuffmanCode&
HC,intn）{//編码
charc,t,*pp;
Sentencep,q;
sentence=（Sentence）malloc（sizeof（S））;
q=sentence;
q->
next=NULL;
请输入待编码的字符串:
fflush（stdin）;
while（scanf（"
%c"
c）!
=EOF&
&
c!
='
\n'
）{
for（i=1;
t=code[i];
if（c==t）{
pp=HC[i];
break;
}
for（i=0;
pp[i]!
p=（Sentence）malloc（sizeof（S））;
c=pp[i];
q->
next=p;
q=p;
p=sentence->
next;
\n编码后的语句:
while（p!
=NULL）{
p->
c）;
p=p->
}
（5）对译码函数的设计
voidDecoding（Sentence&
HC,Tree&
root,intn）{//译码
Treep,q;
Sentencer=sentence->
inti,j;
charc,*t;
root=（Tree）malloc（sizeof（TreeNode））;
root->
lchild=NULL;
root->
rchild=NULL;
t=HC[i];
q=root;
for（j=0;
j<
strlen（HC[i]）;
j++）{
c=t[j];
if（q->
lchild!
lchild->
code==c）{
q=q->
lchild;
elseif（q->
rchild!
rchild;
else{
p=（Tree）malloc（sizeof（TreeNode））;
code=c;
if（t[j+1]!
）
data='
n'
data=code[i];
rchild=p;
lchild=p;
q=root;
\n解码后的语句:
while（r!
c=r->
c;
lchild==NULL）{
q->
data）;
r=r->
\n\n"
return;
三实验结果
根据此次实验的设计，我们编写出相应的源代码，在运行时可以得到相应的功能：
其运行界面如下图所示：
在上面输入所需输入字符集大小。
如输入26个英文字母及空格时
所得的哈弗曼树（如下图部分）及哈弗曼编码（如下图部分）
当输入带编码语句“thisprogrameismyfavorite”时，按回车，出现其编码后的语句及译码后的语句如下图：
四实验总结
通过本次数据结构的课程设计，我学习了很读我之前上课没懂的知识。
并在老师指导下，我对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。
当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。
这次课程设计中我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存保存数据，在老师的指导下改正了错误和疏漏，使我们的程序有了更高的质量。
有时还是会遇到一些这样或那样的问题，在这时就要看团体的力量，遇到困难时我们组会聚集到一块儿合力讨论，尽力把它解决，每次解决了一个问题之后就会给自己多了一份自信，对今后的学习和程序的设计有了更大的信心。
再次我真心的感谢老师对我们的帮助与指导。
我会更加努力学习数据结构方面的知识，来完善自己的学习。
五代码
#include<
stdio.h>
stdlib.h>
string.h>
typedefstructS{
charc;
structS*next;
}S,*Sentence;
//用于待编码的语句
typedefchar**HuffmanCode;
//动态分配数组存储哈夫曼编码表
//用于解码的树
voidSelect（HuffmanTree&
HT,intposition,int*s1,int*s2）{//选择函数
inti,j,t;
intp,q;
intfirst,second;
=position;
i++）
if（HT[i].selected==0）{
first=HT[i].weight;
for（j=i+1;
j++）
if（HT[j].selected==0）{
second=HT[j].weight;
if（first>
second）{
t=first;
first=second;
second=t;
for（i=j+1;
t=HT[i].weight;
if（t<
first）{
second=first;
first=t;
elseif（t<
if（HT[i].selected==0&
HT[i].weight==first）{
HT[i].selected=1;
p=i;
HT[i].weight==second）{
q=i;
if（p>
q）{
t=q;
p=t;
*s1=p;
*s2=q;
=1）
return;
//编码结束位置
for（j=i,f=HT[i].parent;
HC,intn）{//编码
root,intn）{//解码
intmain（void）{//主函数
HuffmanTreeHT;
HuffmanCodeHC;
Treeroot;
int*w,n,i;
char*code;
\t\t设字符集为26个英文字母，其出现频度如下表所示:
\t\t******************************************\n"
\t\t字符|空格|a|b|c|d|e|f|g|h|\n"
\t\t频度|186|64|13|22|32|103|21|15|47|\n"
\t\t字符|i|j|k|l|m|n|o|p|q|\n"
\t\t频度|57|1|5|32|20|57|63|15|1|\n"
\t\t字符|r|s|t|u|v|w|x|y|z|\n"
\t\t频度|48|51|80|23|8|18|1|16|1|\n"
请输入字符集大小n（整型）:
scanf（
升级会员 