天天都是一个出发点,每天都有一点提高,每天都有一点收成!
一、需求分析
目前
进行快速远距离通信的主要手段是电报
即将需传送的文字转化成由二级制的字符组成的字符串
例如
假设需传送的电文为"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); //译码
三、详细设计
(一)、建立哈夫曼树
(二)、对哈夫曼树进行编码
主要代码实现:
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';
}
}
(三)、输出对应字符的码
字符编码a110b111c10d0
(四)、译码过程
主要代码实现:
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