哈夫曼编码译码器数据结构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”等。因此，若要设计长短不等的编码，则必须是任一字符的编码都不是另一个字符的编码的前缀，这种编码称作前缀编码。
然而，如何进行前缀编码就是利用哈夫曼树来做，也就有了现在的哈夫曼编码和译码。 二、概要设计
利用哈夫曼树编/译码
(一)、建立哈夫曼树
(二)、对哈夫曼树进行编码
(三)、输出对应字符的编码
(四)、译码过程
主要代码实现:
struct code //结构体的定义
{
char a;
int w;
int parent;
int lchild;
int rchild;
};
void creation(code *p,int n,int m); //建立哈夫曼树
void coding(code *p,int n); //编码
void display(code *p,int n,int m); //输出函数
void translate(char **hc,code *p,int n); //译码
三、 详细设计
(一)、建立哈夫曼树
10 序号: 3 4 5 2 6 7 1 * 字符: c * * * a b d 4 6 6 权值: 1 2 3 4 3 6 10 d * * 3 3 3 3 3 c * c * * 1 2 2 1 2 1 a b a b 图3-3 图3-1 a b 图3-2
1
(二)、对哈夫曼树进行编码
主要代码实现: 从叶子到根逆向求编码 for(c=i,f=p[i].parent;f!=0;c=f,f=p[f].parent) { *
if(p[f].lchild==c) //左孩子编码为'0' 1
{ d * cd[--start]='0'; 0 1
} c *
1 else //右孩子编码为'1' 0
{ a b
cd[--start]='1';
图3-4 }
}
(三)、输出对应字符的码
字符 编码
a 110
b 111
c 10
0 表3-1 d
(四)、译码过程
主要代码实现:
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; 1 0 }
d * else 1 0 { c * c=p[c].rchild; //右孩子 1 0
} a b }
图3-5
2
四、 调试分析
(一)、数字的输入判断
图4-1
(二)、字母的输入判断
图4-2
(三)、程序是否继续进行的
判断
图4-3
五、 用户手册
(一)、首先根据提示输入初始化数据，提示输入一个数字，请输入一个数a，0
#include
#include
#include
struct code //结构体的定义
{
char a;
int w;
int parent;
int lchild;
int rchild;
};
void creation(code *p,int n,int m); //建立哈夫曼树
void coding(code *p,int n); //编码
void translate(char **hc,code *p,int n);//译码
void display(code *p,int n,int m); //输出函数
//主函数
void main()
{
int i,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);//清空输入缓冲区，往往是确保不影响后面数据的读取
}
5
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();
}
void creation(code *ht,int n,int m)
{
int i,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
6
{
if(ht[j].wn)
{
printf("编码不存在对应的字符～\n");
}
printf("是否继续输入?是(输入y或者Y)否(其他)\n");
fflush(stdin);
scanf("%c",&ch);
}while(ch=='y'||ch=='Y');
}
void display(code *p,int n,int m) {
int i;
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语句输入的数字。学习是一个无止境的过境，我们要善于使用资源，书籍，网络等等，努力地提升自己，为今后的发展做更大的努力。
9
浙公网安备 33021202002483