哈夫曼编码译码器数据结构C语言.docx
《哈夫曼编码译码器数据结构C语言.docx》由会员分享，可在线阅读，更多相关《哈夫曼编码译码器数据结构C语言.docx（16页珍藏版）》请在冰点文库上搜索。
哈夫曼编码译码器数据结构C语言
哈夫曼编码译码器数据结构C语言
一、需求分析
目前，进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二级制的字符组成的字符串。
例如，假设需传送的电文为“ABACCDA”，它只有4种字符，只需两个字符的串，便可以分辨。
假设A、B、C、D、的编码分别为00,01,10和11，则上述7个字符的电文便为“00010010101100”，总长14位，对方接受时，可按二位一分进行译码。
当然，在传送电文时，希望总长尽可能地短。
如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送电文的总长便可减少。
如果设计A、B、C、D的编码分别为0,00,1,01，则上述7个字符的电文可转换成总长为9的字符串“000011010”。
但是，这样的电文无法翻译，例如传送过去的字符串中前4个字符的字串“0000”就可以有很多种译法，或是“AAAA”或者“BB”，或者“ABA”等。
因此，若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。
然而，如何进行前缀编码就是利用哈夫曼树来做，也就有了现在的哈夫曼编码和译码。
二、概要设计
利用哈夫曼树编/译码
（一）、建立哈夫曼树
（二）、对哈夫曼树进行编码
（三）、输出对应字符的编码
（四）、译码过程
主要代码实现：
structcode//结构体的定义
{
chara;
intw;
intparent;
intlchild;
intrchild;
};
voidcreation（code*p,intn,intm）;//建立哈夫曼树
voidcoding（code*p,intn）;//编码
voiddisplay（code*p,intn,intm）;//输出函数
voidtranslate（char**hc,code*p,intn）;//译码
三、详细设计
（1）
、建立哈夫曼树
（2）
从叶子到根逆向求编码
、对哈夫曼树进行编码
主要代码实现：
for（c=i,f=p[i].parent;f!
=0;c=f,f=p[f].parent）
{
if（p[f].lchild==c）//左孩子编码为'0'
{
cd[--start]='0';
}
else//右孩子编码为'1'
{
图3-4
cd[--start]='1';
}
}
（3）、输出对应字符的码
字符
编码
a
110
b
111
c
10
d
表3-1
0
（4）、译码过程
主要代码实现：
if（strcmp（a,hc[i]）==0）//比较两个字符串是否相等，相等则输出0
{
for（c=2*n-1,j=0;a[j]!
='\0';j++）//从根出发，按字符'0'或'1'确定找左孩子或右孩子
从跟到叶子顺向求字符
{
if（a[j]=='0'）//左孩子
{
c=p[c].lchild;
}
else
{
c=p[c].rchild;//右孩子
}
图3-5
}
四、调试分析
（一）、数字的输入判断
（二）、字母的输入判断
（三）、程序是否继续进行的
判断
图4-3
五、用户手册
（1）、首先根据提示输入初始化数据，提示输入一个数字，请输入一个数a，0（2）在某一界面结束后，会有“请按回车继续下面操作”提示，请按提示进行操作，如输入其他数字则无效，知道输入回车符界面才会跳转。
（3）对界面的操作可以自行选择，在询问是否译码的时候，请按要求进行选择，在一次译码结束后会询问是否继续译码，如需要则输入y或者Y，输入其他字符则退出程序。
六、测试结果
（一）、初始化
（二）、建立哈夫曼树
（三）、哈夫曼编码
（四）、哈夫曼译码
（五）、错误判定
附录：
源代码：
#include
#include
#include
#include
structcode//结构体的定义
{
chara;
intw;
intparent;
intlchild;
intrchild;
};
voidcreation（code*p,intn,intm）;//建立哈夫曼树
voidcoding（code*p,intn）;//编码
voidtranslate（char**hc,code*p,intn）;//译码
voiddisplay（code*p,intn,intm）;//输出函数
//主函数
voidmain（）
{
inti,n,m;
code*ht;
printf（"字符的数量:
\n（请输入一个大于0的数字,输入多个数字则按第一个数字运行）\n"）;
while（scanf（"%d",&n）!
=1||n<0||n>9999）
{
printf（"重新输入：
\n"）;
fflush（stdin）;
}
m=2*n-1;//哈夫曼树中没有度为1的结点，故含有m=2n-1个结点
ht=（code*）malloc（（m+1）*sizeof（code））;//动态申请内存
for（i=1;i<=n;i++）//对1~n的数进行初始化
{
printf（"输入编码中的字符（请输入一个字母）:
\n"）;
fflush（stdin）;
scanf（"%c",&ht[i].a）;
while（!
（ht[i].a>'a'||ht[i].a<'z'||ht[i].a>'A'||ht[i].a<'Z'））
{
printf（"重新输入：
\n"）;
fflush（stdin）;
scanf（"%c",&ht[i].a）;//清空输入缓冲区，往往是确保不影响后面数据的读取
}
printf（"输入字符的权值（请输入一个数字）:
\n"）;
while（scanf（"%d",&ht[i].w）!
=1||ht[i].w<0||ht[i].w>9999）
{
printf（"重新输入：
\n"）;
fflush（stdin）;//清空输入缓冲区，往往是确保不影响后面数据的读取
}
ht[i].lchild=0;
ht[i].rchild=0;
ht[i].parent=0;
}
for（i=n+1;i<=m;i++）//对n+1~2n-1的数进行初始化
{
ht[i].a='*';
ht[i].w=0;
ht[i].lchild=0;
ht[i].rchild=0;
ht[i].parent=0;
}
creation（ht,n,m）;
printf（"请按回车进入哈夫曼树对应界面\n"）;
getchar（）;
getchar（）;
system（"cls"）;
display（ht,n,m）;
printf（"请按回车进入编码对应界面\n"）;
getchar（）;
system（"cls"）;
coding（ht,n）;
getchar（）;
}
voidcreation（code*ht,intn,intm）
{
inti,j,m1,m2,t1,t2;
for（i=n+1;i<=m;i++）
{
j=1;//找到第一个最小值（双亲不为0）
while（ht[j].parent!
=0）//找到表中第一个没有双亲的结点
{
j++;
}
t1=ht[j].w;
m1=j;
for（j=m1+1;j<=m;j++）
{
if（ht[j].parent==0&&ht[j].w!
=0）//条件（ht[j].w!
=0）是因为n~2n-1的权值初始值为0
{
if（ht[j].w{
t1=ht[j].w;
m1=j;
}
}
}
ht[m1].parent=i;//第一个值的双亲为ht[i]
ht[i].lchild=m1;//h[i]的的左孩子是最小值的序号
j=1;//剩余中找到第二个最小值（双亲不为0）
while（ht[j].parent!
=0）
{
j++;
}
t2=ht[j].w;
m2=j;
for（j=m2+1;j<=m;j++）
{
if（ht[j].parent==0&&ht[j].w!
=0）
{
if（ht[j].w{
t2=ht[j].w;
m2=j;
}
}
}
ht[m2].parent=i;//第二个值的双亲为ht[i]
ht[i].rchild=m2;//h[i]的的左孩子是最小值的序号
ht[i].w=t1+t2;//h[i]的权值是找到的两个值的权值之和
}
}
voidcoding（code*p,intn）
{
inti,c,f;
char**hc;//指针的指针
char*cd;
charch;
intstart;
hc=（char**）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（c=i,f=p[i].parent;f!
=0;c=f,f=p[f].parent）//从叶子到根逆向求编码
{
if（p[f].lchild==c）//左孩子编码为'0'
{
cd[--start]='0';
}
else//右孩子编码为'1'
{
cd[--start]='1';
}
}
hc[i]=（char*）malloc（（n-start）*sizeof（char））;//为第i个字符编码分配空间
strcpy（hc[i],&cd[start]）;//从cd复制编码（串）到hc,&是取地址符，即取首地址，从start位置到'\0'的编码为止。
}
free（cd）;//释放工作空间
printf（"\n输出编码后的结果：
\n"）;
printf（"符号数码\n"）;
for（i=1;i<=n;i++）
{
printf（"\n%c%s\n",p[i].a,hc[i]）;
}
printf（"是否进行译码操作，是则译码，否则退出程序！
\n是（输入y/Y）否（输入其他字符）\n"）;
scanf（"%d",&ch）;
if（ch=='y'||ch=='Y'）
{
translate（hc,p,n）;
}
else
exit（0）;
}
voidtranslate（char**hc,code*p,intn）
{
chara[10],ch;
inti,j,c;
do
{
printf（"\n\n\n请输入编码：
\n"）;
scanf（"%s",a）;//回车之后会自动生成'\0'
for（i=1;i<=n;i++）
{
if（strcmp（a,hc[i]）==0）//比较两个字符串是否相等，相等则输出0
{
for（c=2*n-1,j=0;a[j]!
='\0';j++）//从根出发，按字符'0'或'1'确定找左孩子或右孩子
{
if（a[j]=='0'）//左孩子
{
c=p[c].lchild;
}
else
{
c=p[c].rchild;//右孩子
}
}
printf（"字符是：
\n"）;
printf（"%c\n",p[c].a）;
break;
}
}
if（i>n）
{
printf（"编码不存在对应的字符！
\n"）;
}
printf（"是否继续输入?
是（输入y或者Y）否（其他）\n"）;
fflush（stdin）;
scanf（"%c",&ch）;
}while（ch=='y'||ch=='Y'）;
}
voiddisplay（code*p,intn,intm）
{
inti;
printf（"\n序号码值权值双亲左孩子右孩子\n"）;
for（i=1;i<=m;i++）
{
printf（"%d%c%d%d%d%d\n",i,p[i].a,p[i].w,p[i].parent,p[i].lchild,p[i].rchild）;
}
}
设计体会
通过这个课程设计，让我对数据结构这门课程有了更深一步的了解，对以后的深造奠定了基础。
本次课程设计的课题是：
哈夫曼编码以及译码的实现。
本程序的特色是：
结构清晰，内容全面，输入的错误提醒。
在输入的错误的提醒方面，做了很大的改进。
不过在这方面仍存在些许的不足，就是在输入一个字母的时候，如果输入的数据是"ab"，不会提示错误，只会按第一个'a'有效。
在初始化的时候，输入'a3'这种数据，则不会提示错误，而是执行了下一条scanf语句输入的数字。
学习是一个无止境的过境，我们要善于使用资源，书籍，网络等等，努力地提升自己，为今后的发展做更大的努力。
升级会员 