一、需求分析
目前,进行快速远距离通信的主要手段是电报,即将需传送的文字转化成由二级制的字符组成的字符串。例如,假设需传送的电文为“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); //译码
三、 详细设计
(一)、建立哈夫曼树
a b c d
1 2 3 4 5 * * * 6 7 a b * c *
a
b
*
c *
d * 序号: 字符: 权值: 1 2 3 4 3 6 10 a b * 1 2 1 2 3 3 1 2 3 3 6 4 10
3 6 图3-1 图3-2 图3-3
(二)、对哈夫曼树进行编码 主要代码实现:
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'; } }
(三)、输出对应字符的码
字符 编码 a 110 b 111 c 10 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;
}
else {
c=p[c].rchild; //右孩子 }
}
a
b
* c
* d
*
1 1 0 1 0 图3-4
表3-1
从叶子到根逆向求编码
a b
*
c *
d *
0 1 1 1 从跟到叶子顺向求字符 图3-5
四、 调试分析
(一)、数字的输入判断
(二)、字母的输入判断
(三)、程序是否继续进行的
判断
五、 用户手册