文档介绍：数据结构课程设计数据结构课程设计Huffman编码
数据结构课程设计数据结构课程设计Huffman编码
数据结构课程设计数据结构课程设计Huffman编码
数据结构课程设计
题目能出现8种字符(a,b,c,ｄ，e,f，g，ｈ），其概率分别是:0。06，0。28，0。０7，,,0。２1,０。0３，0．１2
①输入8种字符的概率；
②构造赫夫曼树;
③输出每个字符的赫夫曼编码；
赫夫曼编码的应用很广泛,利用赫夫曼树求得的用于通信的二进制编码成为赫夫曼编码。树中从根到 每个叶子都有一条路径，对路径上的各分支约定:指向左子树的分支表示
数据结构课程设计数据结构课程设计Huffman编码
数据结构课程设计数据结构课程设计Huffman编码
数据结构课程设计数据结构课程设计Huffman编码
“0”码,指向右子树的分支表示 “1"码，取每条路径上的“0"或“１”的序列作为和每个叶子对应的字符的编码，这就是赫夫曼编码。
通常我们把数据压缩的过程称为编码，解压缩的过程称为解码。电报通信是传递文字的二进制码形式 的字符串，但在信息传递时，总希望总长度能尽可能短，即采用最短码。
假设每种字符在电文中出现的次数为Ｗ i ,编码长度为L ｉ ，电文中有ｎ 种字符,则电文编码总长为∑W i Ｌ ｉ . 若将此对应到二叉树上,W i 为叶节点的权 ，Ｌ i 为根节点到叶节点的路径长度。那么，∑W i Ｌ i 恰好为二叉 树上带权路径长度。
因此，设计电文总长最短的二进制前缀编码，就是以n 种子符出现的频率作权,构造一刻赫夫曼树， 此构造过程成为赫夫曼编码.
本演示程序用C+＋6．０编写,完成赫夫曼树的构造以及赫夫曼编码的设计。
（1)输入的形式和输入值的范围:n中字符,其出现的频率
（2） 输出的形式： 二进制前缀编码
(3） 程序所能达到的功能:设计一颗赫夫曼树，由此得到二进制前缀编码,即赫夫曼编码。
（4)测试数据：
已知某系统在通信联络中只可能出现8种字符(ａ，b，c,d，e,f，g，h），其概率分别是：0。０6，0。２8,0。０7，0。０9，０。14,，,
①输入８种字符的概率；
②构造赫夫曼树;
③输出每个字符的赫夫曼编码；
数据结构课程设计数据结构课程设计Huffman编码
数据结构课程设计数据结构课程设计Huffman编码
数据结构课程设计数据结构课程设计Huffman编码
ﻬ
三． 概要设计
（１)为了实现上述程序功能，需要定义单链表的抽象数据类型:
ADT ＢｉnaryＴreｅ ｛
数据对象D：D是具有相同特性的数据元素的集合.
数据关系R： 若D＝,则Ｒ＝，称ＢiｎａryTreｅ为空二叉树；
若D，则R=｛H｝
基本操作：
ﻩvoiｄ HufｆｍａnＣｏding（HuffmanTree＆，HuffmａnCodｅ＆，int）
ﻩ操作结果:求赫夫曼编码
ﻩvoｉd Seｌect（HuｆｆmanTrｅe，ｉnｔ,ｉnt*，ｉnｔ＊）
ﻩ操作结果:查找权值较小的两个结点
vｏｉｄ ＯutputHｕfｆｍaｎCｏde(HｕffmanTree,HuｆｆmaｎCoｄe,inｔ）
ﻩﻩ操作结果：输出赫夫曼编码
（２）本程序包含4个函数：ﻭ ﻩ① 主函数maｉn（）
ﻩ② 求赫夫曼编码函数HｕｆfmanＣodｉng(）;
ﻩ③查找权值较小的两个结点函数Sｅｌeｃt （）；ﻭ ﻩ④ 输出赫夫曼编码函数OutpｕtHuｆfmaｎCodｅ (）ﻭ
各函数间关系如下：
HuｆfmaｎCodｉng()
数据结构课程设计数据结构课程设计Huffman编码
数据结构课程设计数据结构课程设计Huffman编码
数据结构课程设计数据结构课程设计Huffman编码
Ｍaｉｎ Sｅｌｅｃt (）
ＯｕtｐutHufｆmaｎＣode ()
ﻬ
四。 详细设计
实现概要设计中定义的所有的数据类型,。
1．设计思想
哈夫曼编译码系统的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码 。 
在通信中可以采用0和1的不同排列来表示不同的字符，称为二进制编码。而赫夫曼树在数据编码中的应用是数据的最小冗余编码问题他是数据压缩学的基础。若每个字符出现的频率相同，则可以采用等长的二进制编码