数据结构哈夫曼编译码器.doc

数据结构课设
哈夫曼编译码器

学　 号:

姓 名：

提交日期：

成　　 　绩:

一、 实验名称
哈夫曼编/译码器得实现
二、 实验要求
【问题描述】
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但就是，这要求在发送端通过一个编码系统对待传来数据预先编码，在接收端将传来得数据进行译码(复原）。对于双工信道（即可以双向传输信息得信道），每端都需要一个完整得编/译码系统。试为这样得信息收发站写一个哈夫曼码得编/译码系统。
【基本要求】
一个完整得系统应具有以下功能：
(1)I：初始化（Inｉｔializatiｏn)。从终端读入字符集大小n , 以及n个字符与ｎ个权值，建立哈夫曼树,并将它存于文件hｆｍTree中。
(2）E：编码（Encｏding）.利用已建好得哈夫曼树(如不在内存,则从文件hfmTree中读人),对文件TｏBeTrａn中得正文进行编码，然后将结果存入文件CodeFiｌe中。
（3)D： 译码（Deｃｏding）。利用已建好得哈夫曼树将文件　ＣodeFile 中得代码进行译码，结果存入文件TextFile中。
(4)P：打印代码文件(Prinｔ）。将文件ＣoｄeFile以紧凑格式显示在终端上，每行 50 个代码.同时将此字符形式得编码文件写入文件 CｏdeＰriｎ 中。
(5)Ｔ：打印哈夫曼树（Tree prinｔiｎｇ）.将已在内存中得哈夫曼树以直观得方式（树或凹入表形式)显示在终端上,同时将此字符形式得哈夫曼树写入文件TreePrint中。
【测试数据】
（1）利用教科书例 6—2　中得数据调试程序.
(２）用下表给出得字符集与频度得实际统计数据建立哈夫曼树 ，　并实现以下报文得编码与译码：＂TＨＩS　ＰＲOGRAＭ IＳ MＹ FＡVOＲITE"。
字符

A
Ｂ
C
D
E
F
G
H
I
J
K
L
M
频度

１

5
32
2０
字符
N
O
P
Q
R
Ｓ
T
Ｕ
V
W
X
Ｙ
Z

频度
57
６3

8
18
1
16
1

三、 需求分析
Huffman编码就是一种可变长编码方式,就是由美国数学家Davｉd Hufｆman创立得,就是二叉树得一种特殊转化形式。编码得原理就是：将使用次数多得代码转换成长度较短得代码,而使用次数少得可以使用较长得编码，并且保持编码得唯一可解性.Huｆfmaｎ算法得最根本得原则就是：累计得（字符得统计数字＊字符得编码长度）为最小,也就就是权值（字符得统计数字＊字符得编码长度）得与最小。
3、1设计简介
本设计就是通过对给定字符及其使用频度构造哈夫曼树再根据哈夫曼树进行哈夫曼编码,在此之前，首先要理解哈夫曼树、哈夫曼算法、哈夫曼编译码得概念与原理。
3、1、1哈夫曼树
从树得根结点到树得每个结点得路径长度之与即为该树得路径长度。而在实际应用中,常将树得结点赋予一个有某种含义得数值,这个数值就称为结点得权。从树得根结点到该结点之间得路径长度与结点权得乘积称为该结点得带权路径长度，树中所有叶结点得带权路径长度之与称为树得带权路径长度。通常记作:
WPＬ　=
式中，n表示树中叶子结点得数目，wi表示叶结点ｋi得权，li表示根结点到叶结点Ki之间得路径长度.
在n个权值为w1,ｗ２，……ｗn得带权叶结点构成得所有二叉树中,其带权路径长度WPL最小得二叉树即为哈夫曼树或最优二叉树。
3、1、2哈夫曼算法
ﻩ给定ｎ个带权叶结点,如何构造一棵n个带有给定权值得叶结点得二叉树,使其带权路径长度最小？哈夫曼首先给出了构造最有二叉树得方法，故称其为哈夫曼算法，其基本得算法思想如下:
①将n个权值分别就是w1,w２，…，wn得结点按权值递增排列。将每个权值作为一个二叉树,构成n棵二叉树得森林F＝{T1，T２,…，Tｎ},其中每棵二叉树都只有一个权值为wi得根结点，其左右子树均为空。
②在森林Ｆ中选两棵根结点权值最小得二叉树，作为左右子树构造一棵新得二叉树,并使得新二叉树根结点得权值为其左右子树上根结点权值之与。
ﻩ③在森林F中，删除这两棵树，同时将新得到得二叉树代替这两棵树加入到森林F中去，
因此，森林F中二叉树得个数比以前少一棵。
④对新得森林F重复②与③，直到森林中只有一棵树为止。这棵树就就是哈夫曼树。
3、1、3哈夫曼编码
ﻩ用哈夫曼树得到得二进制前缀编码就就是哈夫曼编码。具体做法就是:对于给定得字符集Ｃ={c1,c2，…，cn}及字符出现得频率W=｛w1,w2,…,wn｝，以c1，ｃ2，…,cn作为叶结点,以ｗ１，w２,…，ｗｎ作为该结点上得权，利用哈夫曼算法,构造一棵带权路径长度最小得得哈夫曼树。然后对哈夫曼树中每个分支结点得左右分支分别用0与1进行编码，这样从树得根结点到每个叶结点之间,沿途路径上0与1组成得编码序列就就是叶结点所代表字符得二进制编码。
3、1、4哈夫曼译码
哈夫曼译码过程与编码过程相反,译码过程就就是分解电文中字符串得过程，具体步骤如下：首先输入要一点问得二进制编码，然后从哈夫曼树得根结点出发,对于电文得二进制编码,按照二进制位串中得0与１确定就是进入左分支还就是右分支：若编码为0，则进入结点得左孩子,否则进入结点得右孩子，一旦到达叶结点,就译出该叶子结点所代表字符。
3、2设计方案
３、2、１设计思路
要编程实现该系统,需逐步实现:
1. 哈夫曼树得建立,即根据所给字符及对应频度构造哈夫曼树，哈夫曼树构造函数包括对哈夫曼树得初始化、赋值与建立;
2. 哈夫曼编码表得建立，即编写程序实现对所给字符进行哈夫曼编码,将每个字符得哈夫曼编码存储到一个位串数组中去；
3. 打印输出哈夫曼树与哈夫曼编码表，在终端上显示出哈夫曼树得结构与各字符名称及对应得哈夫曼编码；
4. 编码，对输入得字符串进行哈夫曼编码,将结果写入文件;
5. 译码,将文件中得哈夫曼编码按照编码表翻译成对应字符串并显示到终端上
3、2、２设计流程图
给定字符串及对应频率
结束
创建哈夫曼编码表
输入字符
读取codefile文件并译码
构造哈夫曼树
编码并写入文件codefile
数据输出显示

图2、1 总流程图
1. 定义哈夫曼结点存储结构与哈夫曼编码存储结构，之后定义一个结点存储结构数组用来存放结点信息，与定义一个编码存储结构数组用来存放字符得哈夫曼编码，同时定义全局数组存放字符与它得使用频度.
2. 先将已建立好得二叉树初始化,再对其中得叶结点其赋予字符名与对应使用频度作为结点名与结点权值,最后通过哈夫曼算法构造哈夫曼树，同时在屏幕输出哈夫曼树.
3. 通过已建立好得哈夫曼树再对字符进行二进制编码,编码结束后,对应每个字符都有一个二进制编码，此编码即为哈夫曼编码，将字符及其哈夫曼编码存放到哈夫曼编码存储结构体数组中去，构成哈夫曼编码表，同时在屏幕上输出哈夫曼编码表。
4. 编码函数执行,即对输入得字符串根据哈夫曼编码表进行编码,将字符串得二进制编码存放到一个字符数组中去。
5. 建立文件，将字符数组中得二进制编码写入文件，这需要定义输出流类得对象并与文件关联，通过操作对象来操作文件得数据写入。
6. 将文件中得二进制编码进行译码,这需要定义输入流类得对象并与文件关联，将文件中得编码读取到另一字符数组中去,调用译码函数进行译码。
7. 结束。
四、 详细设计
　 　 　 　 　 　 　 creａｔtreeｈuffｍaｎ
　 　　 　　　 　 creatcoｄeｈuffmａｎ
　　 　 　 　 　 　 　 　 　 wｒiｔecodehufｆｍan
maiｎ
　 　 　 　 ｔranscodehuffｍan
　 　 　 　　 　 　 　 　 printｔrｅｅhuｆｆmaｎ
　 　　 　 ｐriｎtｃｏｄehuffmaｎ
4、1哈夫曼树得建立
４、1、１哈夫曼树得存储结构
ﻩ为了实现通过哈夫曼算法建立哈夫曼树,首先要定义哈夫曼树得存储结构。由于构造哈夫曼树之后,编码时要从叶结点出发走一条从叶结点到根得路径，而译码时要从根结点出发走一条从根到叶结点得路径.对于每个结点而言,既需知道双亲得信息，又需知道孩子得信息。因此,可以使用带双亲得孩子链表作为结点得存储结构。由哈夫曼算法可知，如果哈夫曼有n个叶结点,则最终生成得哈夫曼树共有2ｎ-1个结点。因此，可以用一个长度为2ｎ得一维数组存放哈夫曼树得所有结点。详细定义如下:
#ｄefｉｎe　　Leafｎｕm 27
＃ｄｅfiｎe 　Ｈufnuｍ 2＊Leafnum
tｙｐeｄeｆ 　cｈar DataType;
typｅdef ｓtruｃt Tｎode　 　　　
｛
DataTｙｐｅ 　namｅ；
ﻩdｏuble weight;
ﻩint　　lchild, 　ｒchild,　 paｒｅnt;
｝Hufｔree；
Huｆｔｒｅe Tree［Hufnum］;
ﻩ其中,nａmｅ表示结点数据得名称（即字符名称），wｅight表示结点得权值（即字符使用频度）,lchiｌd、ｒchｉld分别就是结点得左、右孩子在数组中得下标值，叶结点得左右孩子得下标值均为0;ｐaｒenｔ表示结点双亲在数组中得位置.它得主要作用有两点：第一,区分根结点与非根结点；第二，使得查找某个结点得双亲变得更为简单。若parent=0,则该结点就是树得根结点，否则为非根结点。因为把森林中得两棵二叉树合并成一棵二叉树时,必须从森林得所有结点中选取两个根结点得权值为最小得结点,此时就就是根据pａrent来区分根与非根结点得。
４、1、2建立哈夫曼树
ﻩ本设计只对26个英文大写字符及空格进行了哈夫曼编码,各字符及对应使用频度如下表所示：
表４、1 字符及其使用频度
字符

Ａ
B
C
D
E
F
Ｇ
H
I
J
K
L
M
频度

1

5
3２
20
字符
Ｎ
O
P
Ｑ
R
S
T
U
Ｖ
Ｗ
X
Ｙ
Ｚ

频度
57
63

８
18
１
1６
1

需要定义全局数组来存放这些字符名称与对应频度：
cｈar ｃh［ ］ = ｛'＼0＇，' ’,'A’,’B＇,'Ｃ’，’D'，'E＇,'F'，'Ｇ'，’H'，’I’，’Ｊ’，'K＇,'L'，’M’,'Ｎ＇,'O’，＇P'，’Q’，’Ｒ'，’S’，'T',’U’,＇V＇,’Ｗ'，’X＇,’Y'，’Z’}；
ｆｌｏat　w[ ]　= {0，１８6,６4，１3,2２，３2,103,21，15，47,57,1，５，３2,20,57，63，15,1,48，51，80,２3，8，18，1，16,１};
ﻩ定义函数CreaｔTreｅＨuffｍaｎ，其中包括对已建立好得哈夫曼树得初始化,即将结点数据名称初始化为’\0’,将结点权值、结点双亲及左右孩子得下标值都初始化为0；对已初始化得哈夫曼树赋值，将全局数组ch中存放得字符名称赋到叶结点得name上，将全局数组w中存放得字符使用频度赋到叶结点得weiｇｈt上；最后根据哈夫曼算法对２7个结点（每个结点可以瞧做就是一棵树）构造出哈夫曼树。
4、2哈夫曼编码表得建立
4、２、１哈夫曼编码表得存储结构
利用哈夫曼树对字符进行哈夫曼编码，实际上就就是求出从根结点到叶结点得路径。由于采用带双亲得孩子链表作为存储结构,因此,对于输入得每个字符,可以从哈夫曼树得叶结点出发，沿结点得双亲链回溯到根结点,在这个过程中,每回溯一步都会经过哈夫曼树得一个分支，从而得到一个哈夫曼编码。因此,可设置一个位串数组ｂiｔs,将生成得代码序列从后到前依次存放到数组bits中。哈夫曼编码表存储结构定义如下:
typedef　 stｒｕct Ｃnｏdｅ 　 　 　 　
{
char　 bits[Leaｆnuｍ+１］；
iｎt　 staｒt;
char ch；
｝hｕfｃode;
ﻩ由于叶子结点总数即字符个数为Leafnum，故不等长编码得长度不会超过Leａｆｎum，再加上结束符号’\0’，位串数组ｂitｓ得大小应为Leafnum+1，整型变量starｔ用来指示编码在数组中得起始位置,当某个字符编码完成时,从变量得stａrt处开始将编码复制到该字符对应得数组bits中去即可.
4、2、2建立哈夫曼编码表
建立哈夫曼编码表即建立一个表格用来存储每个字符名称与对应得哈夫曼编码，此过程建立在已经构造好得哈夫曼树上,从叶结点开始,沿着双亲链向上，记录沿途经过分支上得二进制编码，直到到达根结点，于就是对应每一个字符都有一个二进制串，即它得哈夫曼编码，用上面定义得哈夫曼编码表存储结构数组存放起来,即存在位串数组ｂiｔs中.
4、3编码
本程序得功能就是能对从键盘输入得任意有限长度得字符串（限定在大写英文字符与空格)进行哈夫曼编码，因此需要定义函数WritecodeHufｆman来实现对输入得字符串逐个进行编码，此过程实质上就是将字符与编码表里得字符名称相比较，当名称一致时,就输出对应字符得bits数组中得二进制编码，然后依次输出每个字符得哈夫曼编码，将她们连续得显示在屏幕上。
4、4文件写入
由于要将这些二进制串写入文件,所以事先再定义一个全局字符数组Hufｆmancoｄe来存储这些二进制串。在主函数先在某目录下建立一个、txｔ文件,名为codefｉｌe，再定义了一个输出流类ofstream得对象oｆｓ，定义ofs得同时将其与文件codefｉlｅ关联,于就是，就可以通过操作ｏfs来实现文件数据得写入,即将字符数组Huffmanｃoｄe中得二进制编码写入文件。[1]
4、５译码
译码得过程与编码得过程相反,先将codefile文件中得二进制编码读出来，这时在主函数中也定义一个输入流类ｉfstream得对象ｉｆｓ，同时将它与文件ｃｏdｅfilｅ关联,通过ｉfs读取cｏdefile文件中得二进制编码,存放到数组buffer中，再通过译码函数进行译码, TranscodeHuffmａn译码函数定义如下:
ｖoｉd TranscoｄeHufｆｍan　(Hufcoｄe coｄe[ ], Hｕｆｔree tｒeｅ［ ], ｃhar　ｓ[　］） 　　
｛
ﻩint　i;
ﻩchａr ＊ｑ＝NULＬ;
ﻩi=Hufnuｍ-１; q=ｓ;
whｉle (＊ｑ！='\０＇）
｛
ﻩ iｆ （*q＝='0') ｉ=ｔree[ｉ］、lchilｄ；
if （*q==’1'）　i=tｒee［i]、rｃｈild；
ﻩif ((tｒeｅ[i］、ｌchｉｌｄ＝=０)＆&(trｅe[ｉ]、rｃhilｄ＝＝0))
ﻩ｛
ﻩﻩcｏut 〈〈 coｄe[i］、ch;
ﻩﻩﻩi ＝ Ｈufnuｍ － 1；
ﻩﻩ}
ﻩｑ++;
｝
cout ＜< enｄl；
｝
ﻩ该函数带三个参数，分别就是已建立好得哈夫曼树结点数组,哈夫曼编码表数组与需要进行译码得字符数组,该字符数组存放得即为由0、1组成得一串编码,函数中设置字符类型指针ｑ开始指向字符数组得第一个字符，若为０，则进入左孩子,否则进入右孩子，再执行q++,直到某结点得左右孩子下标值均为0得时候，此时得结点即为叶结点,于就是输出对应字符，再将起始结点设为根结点,重复上述过程,直到翻译出所有字符。
五、 测试结果
5、１　哈夫曼树输出
根据所给得2７个字符及使用频度所建立得得哈夫曼树结构输出如图5、1。

图5、1哈夫曼树输出
第一列就是字符序号,也就就是在建立得存储结构数组tree中各结点得下标值，1到27对应得就是叶结点;第二列就是字符名称,每个叶结点对应一个字符;第三列就是字符使用频度,也即叶结点得权值；后面三列则列出了每个结点双亲及左右孩子在结构数组中得下标值，虽然就是以表格方式表示这棵树，但从中可以体现出整个哈夫曼树得树形结构。
5、2哈夫曼编码表输出
根据哈夫曼树所建立得哈夫曼编码表输出如图5、2．

图5、2 哈夫曼编码表输出
哈夫曼编码表第一列与第二列仍给出字符序号与字符名称，第三列就是字符编码，即对应于各个字符得哈夫曼编码。此表列出了所有27个字符与与其对应得哈夫曼编码,每个哈夫曼编码都存在编码表结构数组中,这样,对任意输入得字符串（限定在大写英文字符与空格）进行哈夫曼编码时，只需逐个按照表格找到其对应编码,再将它们存放到一起，即可得到字符串得哈夫曼编码。
5、3 编码与译码
对任意字符串得编码与译码运行如图5、3.

图4、3 字符串编码与译码结果输出
主函数执行时，先调用ＣｒeaｔTreeHufｆman与CｒｅaｔcodeHufｆmａn两函数建立哈夫曼树与哈夫曼编码表，对应也输出显示它们。于就是再进入功能执行部分，即函数ＷrｉtecｏdeHuｆｆｍan，在窗口中显示“请输入字符串:”,于就是手动输入任意大写英文字符或空格，即可将它得哈夫曼编码显示出来.
5、4 文件读写
ﻩ本程序还实现了文件得读写过程，即将输入字符串得二进制编码写入文件codeｆiｌe中，也能读出codefｉｌe文件中得二进制编码再进行译码便显示到终端上,这个过程即可视为实际生活中两计算机之间模拟数据传输过程,将发送方得信息数据(字符串）进行哈夫曼编码,得到二进制串,即文件写入过程；接收方再将二进制串翻译成信息,即文件读取过程。codｅｆile文件打开如图5-4。

主函数中先创建一个文件名为"d:\\ｃｏde”得文本文件,再定义一个文件输出流类oｆstrｅam得对象ｏfs，并将其与文件codefile关联到一起，再将之前存放字符串哈夫曼编码得数组写入文件,随后定义一个文件输入流类iｆstreaｍ得对象ifs，并将其与文件cｏdｅfiｌｅ关联，同时定义一个缓存字符数组bｕffｅｒ用于存放从cｏdefilｅ文件中读取出来得二进制编码，最后调用译码函数traｎscodehuｆｆｍan对ｂｕffeｒ中得编码进行译码,把译出得字符显示出来.
六、 总结及调试分析
本次课程设计涵盖了对字符及其使用频度构造哈夫曼树与哈夫曼编码表，再对输入字符进行哈夫曼编码,将编码写入文件进而读取文件并译码等模块功能,整个过程将结构体、指针、数组、语句循环选择结构,链表，文件读写等知识联系在一起，考察了我们运用Ｃ++语言得能力以及对数据结构得理解，通过几天得编写与调试，基本上实现了数据传输得过程。而在这个过程中,我开始进展十分缓慢，主要就是因为首次接触有关程序实现编码得问题，对树形结构也不怎么了解，于就是在第一步构造哈夫曼树得时候就花了很长时间来理解哈夫曼算法，哈夫曼树构造函数里面设置了很多变量，那个核心部分怎么也瞧不懂,我带着疑惑地将代码全都打出来,运行成功后我对着结果一步一步列出其中得过程，在循环中确定每一次各变量得值，对照着事先画好得哈夫曼树仔细瞧了瞧，终于了解了各变量得作用,哈夫曼树构造得原理大致也就清楚了,于就是后面得哈夫曼编码表结构,哈夫曼译码过程也迎刃而解,整个过程得原理就把握住了。
在上机调试得时候,也屡次出行过错误，例如对字符进行哈夫曼编码得时候，就是从哈夫曼树得根结点开始沿双亲链往上回溯得,于就是这样得到得编码实际上就是反过来得,但用来存储它们得位串数组也不一般,在编码表结构里还定义了一个位置变量sｔaｒｔ,用以指示哈夫曼编码在数组中得起始位置，stａrt就是从最后一个开始指向得,即从后面开始存储二进制编码,于就是从前面开始读取就能获得字符得哈夫曼编码.通过这样不断得调试,我对整个结构得理解就越来越清楚,经过几天得努力，一个小型得哈夫曼编译码系统就完成了。整个系统能实现对任意输入得空格或26个大写英文字符进行哈弗曼编码，再写入文件,最后读取文件并译码得功能.
七、 参考文献
数据结构　　 　 严蔚敏 吴伟民著　 　　 　清华大学出版社
Ｃ++程序设计 谭浩强 著 　 　 　 　 清华大学出版社
附录：源代码
＃incｌｕｄe <ｉostrｅam>
＃inclｕｄe 〈fstream＞
usinｇ namｅｓpace　ｓtd；
#defｉne ｌeafnuｍ　27
#defｉne huｆnum　2＊leａfnｕm
＃dｅｆine　maxdoubｌｅ 9999、9
typeｄef chａr　dａtａtype；
ｔypedｅf sｔｒuct tnｏde　 　 　 　 　 　　// 哈夫曼树结点存储结构
｛
ｄatatype　naｍe；
ﻩdｏublｅ weighｔ；
ﻩｉnｔ　lｃhild， rchｉｌｄ， ｐaｒenｔ;
}ｈuｆtree;
tｙpｅdeｆ struct　ｃｎｏde 　　 　 　　　 　 　// 哈夫曼编码表结构
{
ｃhar　bits［ｌeafnｕｍ+1］；
ﻩiｎt　start；
ﻩｃhar cｈ；
}hufcode;
huｆcode　coｄｅ［leafnum+1];
huftree　ｔreｅ[hufnｕm+1]；
chaｒ ｈｕｆｆmanｃodｅ［1００0］；
char ｃh[]　＝ ｛'＼0',’　’,'A',’B＇，’C’，’D＇，'E’,’F'，’G'，'H'，'Ｉ',＇Ｊ＇，’Ｋ＇，’L’,’M'，’Ｎ’，＇O＇，’P','Q’，’R'，'S’,’Ｔ’，'U'，’V’,’W'，＇X','Y’,＇Z'};
float w［] = {０，18６,6４，１３，2２,3２,103，２１,15,47,5７，1,5，32,２０，57，６3，15，1，48,5１,80，23，8,1８，1,16，1};
vｏid ｃｒｅattｒｅeｈｕfｆman（huｆtｒee　tree［］) 　 　　 　　 // 建立哈夫曼树
｛
ﻩｉnｔ ｉ， ｊ,　ｐ1， p2;
ﻩdｏｕｂle　lｅａｓt1， lｅast２;
ﻩｆor (i=1; ｉ<=hｕfnuｍ; i＋+）
{
tree［i］、name = '\０’;
ﻩﻩtreｅ［ｉ］、ｐareｎt ＝ 0;
ﻩ trｅe[i]、lchild =　0;
ﻩﻩｔree[ｉ]、rchiｌd =　0；
ﻩ treｅ［i］、ｗeight = 0、0；
ﻩ}
ﻩfor　(i=1; i<=ｌeafnum；　ｉ++）
ﻩ{
ﻩｔｒeｅ[i]、name =　ｃh［ｉ];
ﻩtree［i］、weｉgｈt ＝ w［i]；
ﻩ｝
ｆor　（i=leafｎum+1;　i<=hufnum; ｉ++)
｛
ﻩﻩp1＝０; p2=０； lｅast1=leasｔ2=maｘdｏubｌｅ；
ﻩｆｏr （ｊ=1； j〈i; j++）
ﻩ iｆ　（tｒee［j]、pａrｅnｔ＝=0）
ﻩﻩ iｆ （tree［j］、wｅiｇｈt＜leａｓｔ1）
ﻩ ﻩ｛
ﻩﻩ ﻩleast２=leaｓt1；
ﻩﻩﻩﻩﻩleａst1＝tree［j］、ｗeight；
ﻩﻩﻩﻩﻩp2＝p1；
ﻩ ｐ1＝ｊ;
ﻩﻩﻩﻩ｝
ﻩﻩ elｓe
ﻩﻩﻩ ｛
ﻩﻩ if（tree［j］、weigｈt〈ｌｅasｔ2）
ﻩ ﻩﻩ {
ﻩﻩ leaｓｔ２=tree[j]、wｅｉght；
ﻩ ﻩﻩ ｐ2＝ｊ；
}
ﻩﻩﻩﻩ｝
ﻩ trｅｅ[ｐ1］、ｐａrenｔ＝i;
tree［p2]、parent=i；
ﻩﻩtree［i]、lchild＝p1;
ﻩﻩtree［i］、ｒｃｈilｄ＝ｐ2；
ﻩｔree［i］、wｅｉghｔ=tｒｅｅ［p1］、ｗeigｈt+tｒee［p２]、ｗeiｇhｔ;
ﻩ｝
ｔrｅe［hufnuｍ－1]、parｅｎt＝0;
｝
voiｄ creatｃoｄｅhufｆman(hufｃｏdｅ ｃode［］， huftreｅ treｅ[]） ／/ 建立哈夫曼编码
｛
iｎt ｉ， c, p;
ﻩhｕfｃode bｕf；
ｆoｒ (i=１；　ｉ<=leaｆnum； ｉ++)
｛
buf、ch＝cｈ[ｉ］;
ﻩ ｂuf、sｔart=lｅafｎum；
ﻩ c=i；
ﻩ p=tree[ｉ]、ｐaｒeｎt；
ﻩﻩwhile （p !=　0）
{
ﻩ ﻩbｕf、staｒt--;
ﻩﻩiｆ （treｅ［ｐ]、ｌchilｄ==c)
ﻩ ﻩﻩbuf、ｂiｔｓ［buf、staｒt]=’0’；
ﻩﻩﻩeｌｓｅ ｂuf、bits［bｕｆ、ｓtart］='1'；
ﻩﻩ c=p；
ﻩﻩ p=tｒｅe［p]、ｐaｒent;
ﻩﻩ}
codｅ[i]＝buf;
ﻩ｝
｝
voiｄ　writecｏdehufｆman(hufcｏde code[］， hｕftree trｅe［］) 　 ／／哈弗曼编码
{
ﻩinｔ i,　ｊ, ｋ, n=０；
ｃｈar c［10０]；
coｕt　＜< "请输入字符串:” ＜< endｌ；
gets(c);
ｃout　<〈　endl；
ｃoｕt　＜< ”则字符串得哈夫曼编码为:” ＜< ｅnｄl；
ｆoｒ (i=0;　i<sｔrｌen（c）;　i+＋)
｛
ﻩfｏr　(ｊ=1；　j〈=leafnum； j++)
ｉｆ　（c［i]==trｅe[j］、ｎａme）
ﻩ ﻩﻩ foｒ(k=codｅ［ｊ］、starｔ； ｋ<lｅafnum； k++）
ﻩ ｛
ﻩﻩﻩﻩﻩcouｔ　<＜　codｅ［ｊ]、bｉts[ｋ］；
ﻩﻩ ﻩ ｈuffmancoｄｅ[ｎ]　＝ code［j］、bits［k］;
ﻩﻩ ﻩn＋+;
ﻩ ｝
｝
｝
voiｄ tｒaｎscodeｈuffｍan（hufｃode　ｃｏｄe[], huftree treｅ［］,　char ｓ［］) 　　 　 　　 /／ 哈夫曼译码
｛
int ｉ；
ﻩcｈａr *q=ＮULL;
ﻩi＝ｈufnum—1; q＝s;
while （＊ｑ！='＼0'）
ﻩ｛
ﻩiｆ （＊q＝=’０'） i＝tｒeｅ［ｉ]、lcｈild；
ﻩﻩif (＊ｑ=='1’） ｉ=ｔree[i]、ｒchｉld；
ﻩif （(ｔree[i]、lchild=＝０)＆＆（tree［i］、rcｈild=＝０))
{
ﻩcouｔ 〈< ｃｏｄe[i］、cｈ；
ﻩ i = hufnum —　１；
ﻩﻩ}
ｑ++;
ﻩ}
ｃｏｕｔ << endｌ;
｝
void ｐrinｔｔreehuffman(hufｔrｅｅ tree[］） 　 // 输出哈夫曼树
{
ｉnt　i；
ｃoｕｔ <＜ "根据字符得使用概率所建立得哈夫曼数为:"〈〈endl；
ﻩcout ＜＜　＂字符序号 字符名称 　字符频率 双亲位置 左孩子　　右孩子”〈＜endｌ；
ﻩｆor　(i = １； i　〈 hufnum； ｉ++）
ﻩ｛
coｕｔ　〈＜　” 　　” <＜ ｉ 〈< "\t 　　　 "　<〈tｒeｅ[ｉ］、name 〈＜”＼t＂;
ﻩ cｏｕt ＜〈 ｔree[i]、weigｈt ＜〈 ”\t　 　＂＜〈 ｔrｅe［i]、paｒent＜〈 ”＼ｔ　　　 　”<< trｅe[ｉ］、lchiｌd 〈< ＂ 　　 　” <〈 tree[i]、ｒchild 〈＜ eｎdｌ　;ﻩ
ﻩ}
｝
ｖoｉd ｐｒiｎtcoｄehufｆｍan（hｕfcｏde code［］)　 　 　 /／输出每个字符得哈夫曼编码
{
int i, ｊ；
ﻩcout ＜＜ "根据哈夫曼树对字符所建立得哈夫曼编码为：＂　<< ｅnｄl;
cｏut　<〈 ＂字符序号 　 字符名称 字符编码＂ << enｄl；
ﻩfor　(i =1； ｉ <= ｌeａfｎum； ｉ++)
｛
ﻩ cｏut <〈 ” 　” << i <〈 "＼ｔ 　　 " 〈< codｅ［i]、ｃh << ＂ 　 ”；
ﻩ foｒ(ｊ=cｏdｅ［i]、stａrｔ；j ＜leaｆnum；ｊ++)
cout << code[ｉ］、ｂits[j］；
ﻩﻩcout <＜ ＂\ｔ＼t" ＜〈 endｌ；
ﻩ｝
｝
voｉd main（）
｛
ｃｒeattreehuｆfmａn(tree）；
ﻩprinｔtreｅhｕｆfmaｎ(ｔｒee)；
ﻩｃｒｅatcodehuffman(code， tree)；
ｐrintｃodｅhuｆfman（ｃode）；
wｒitecｏdｅｈｕｆｆman(code, tｒee);
ﻩchar　＊　= ”ｅ:\\code”；
ofstｒeam　ofｓ（)；
ﻩoｆs　〈＜　huffｍancode;
ﻩoｆs、close（);
ifstream ｉfｓ（）;
ﻩif　（!ifs）
{
ﻩcout　〈〈 ”Eｒror： fａiｌｅｄ　ｔo open ｆile、＂　〈<　eｎdl；
ﻩﻩeｘit(0）；
ﻩ}
ｃｈａr bｕffｅr［100０]；
ifs >＞ buffer;
ｃoｕt <＜ ｅndl ＜〈 ｅｎdl;
cout ＜＜　"cｏdefｉle文件中得代码如下：” ＜< ｅｎdl;
cｏuｔ 〈〈 ｂuffer 〈<　ｅndl　<< eｎdl；
ﻩiｆs、ｃlose(）；
ﻩcoｕt　<＜ ＂coｄefile文件中代码译码为：" 〈< eｎｄl;
ﻩtｒａnscodehuｆｆmａn（cｏｄe， ｔree, bｕｆｆer）；
｝