1 

一

、

需求分析

目前

,

进行快速远距离通信的主要手段是电报，即将需传送的文字转化成由二级制的字符组成的

字符串

.

例如

,

假设需传送的电文为“

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); 

//

译码

三、

详细设计

（一）、建立哈夫曼树