1 设计目的
(1)熟悉并且掌握huffman编码算法的流程和实现．
(2)应用huffman算法实现模拟编码器，实现对英文文章中对单词的编码.程序实现对输入的一篇英文文章(以 .txt文件读入)，输出huffman编码(以 .txt文件输出),并试着译码.
2 设计任务
用C语言编写出实现huffman编码算法的各个功能模块，并整合为一个完善的程序，最后以达到压缩文件的目的．
3 设计方法与步骤
3.1 需求分析
我们如何得到使电文总长最短的二进制前缀编码呢?假设每种字符在电文中出现的次数为wi,其编码长度为li,电文中只有n种字符,则电文总长为∑wili.对应到二叉树上,若置wi为叶子结点的权,li恰为从根到叶子的路径长度.则∑wili恰在此时二叉树上带权路径长度.由此可见,设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权,设计一棵huffman树的问题,由此得到的二进制前缀编码便称为huffman编码.
3.2 概要设计
3.2.1 huffman编码程序模块
(1)weight()：此函数将整篇英文文章的各个单词根据空格分开,并分别存入结构体数组中,最后求出各个单词的权值.
结点的存储结构:
typedef struct{
char ch[50];
float w;
}weightnode;
(2)select():此函数的功能是在huffman树中选出两个父结点等于0且权值最小的两个结点.
(3)createhuffmantree():此函数的功能是创建huffman树.
(4)huffmancoding():此函数的功能是从叶子到根逆向求huffman编码.
(5)decoding():此函数的功能是根据编码求译码.
(6)main():主函数.用来打开输入文件,从输入文件获取需要编码的串.然后调用其它函数实现程序功能.
3.3 详细设计
//定义存储结构
typedef struct{
char ch[50];
float w;
}weightnode; /*动态分配数组存储文档中的英语单词*/
typedef struct{
char ch[50];
float weight;
int parent,lchild,rchild;
}htnode,*huffmantree; /*动态分配数组存储赫夫曼树*/
typedef char **huffmancode; /*动态分配数组存储赫夫曼编码表*/
//将方档中的单词存入结构体中,并求出权值
weightnode *weight(char *ccc) /*将文档中的单词分别存入结构体中,并求出权值*/
{
weightnode *c,*mc;
char c2[100][50],*c1;
int i,m=0,number=0,t=0,j=0;
float number2=0.0,x1,x2;
for(i=0;i<100;i++) /*初始化二维数组*/
{
for(j=0;j<50;j++)
{
c2[i][j]='\0';
}
}
c=(weightnode *)malloc(100*sizeof(weightnode));
mc=c;
for(i=0;i<100;i++,c++) {strcpy(&c->ch,nul);c->w=0;}
m=j=0;
c=mc;
for(i=0;i<=strlen(ccc);i++)
{
if(*(ccc+i)>='a'&&*(ccc+i)<='z'||*(ccc+i)>='A'&&*(ccc+i)<='Z')
{
*(*(c2+j)+m)=*(ccc+i);
m++;
}
else
{
*(*(c2+j)+m)='\0';
j++;
m=0;
}
}
