数据类型的定义
哈夫曼树类型 typedef struct{//构造树 char data;//结点权值 int weight;//权重 int parent;//双亲结点 int lchild;//左孩子 int rchild;//右孩子 }HTNode; HTNode ht[30];
输入
n>=0&&n<=20
哈夫曼编码 译码程序
哈夫曼树的 创建程序
程序
求哈夫曼编 码
创建哈夫曼 树
输出结果
人员分工
收集资料
调试程序 文档编写
徐铭瑶 周弘杰
刘海澍 周弘杰 刘海澍 徐铭瑶
预期结果
输入：键盘输入字符集大小n、
n个字
符和n个权值 输出： 显示每个字符对应的权值 显示所有字符的哈夫曼编码 显示哈夫曼树 显示每个字符对应的编码 将结果输入到文本文件中
乘积
构造赫夫曼树

一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn} 构成n棵二叉树的初始集合F= ｛T1,T2,T3,...,Ti,...,Tn}，其中每棵二叉树Ti中只 有一个权值为Wi的根结点，它的左右子树均为空。

二、在F中选取两棵根结点权值最小的树作为新构造 的二叉树的左右子树，新二叉树的根结点的权值为 其左右子树的根结点的权值之和。 三、从F中删除这两棵树，并把这棵新的二叉树同样 以升序排列加入到集合F中。
赫夫曼编码
计科132 刘海澍 周弘杰 徐铭瑶
目录
哈夫曼树的介绍 选题的意义 实验内容
算法及可行性分析
预期结果
赫夫曼编码是哈夫曼树的 一个应用
路径上的分支数目称作 路径长度 树的带权路径长度为树中所有叶子结点的带 权路径长度之和，通常记作WPL= 树的路径长度 是从树根到每一个结 (W1*L1+W2*L2+W3*L3+...+Wn*Ln ） 点的路径长度之和 N个权值构成一棵有N个叶子结点的二叉树， 每个叶子结点带权为Wi 结点的带权路径长度为从该结点到 相应的叶结点的路径长度为Li(i=1,2,...n)。 树根之间的路径长度与节点上权的 最小的二叉树称作最优二叉树或赫夫曼树
四、重复二和三两步，直到集合F中只有一棵二叉树 为止。这棵树便是赫夫曼树。


选题的意义
“哈夫曼编码”是一种一致性编码法（又称“熵
编码法”），用于数据的无损耗压缩。这一术语 是指使用一张特殊的编码表将源字符（例如某文 件中的一个符号）进行编码。 这张编码表的特殊之处在于，它是根据每一个源 字符出现的估算概率而建立起来的（出现概率高 的字符使用较短的编码，反之出现概率低的则使 用较长的编码，这便使编码之后的字符串的平均 期望长度降低，从而达到无损压缩数据的目的）

求哈夫曼编码类型 typedef struct{ char cd[30];//存放 当前结点的哈弗曼编码 int start;//cd[start]~cd[n] 存放哈弗曼码 }HCode; HCode hcd[30];

程序流程
开始
初始化：键盘输入字符 集大小n n个字符和 和n个权值

算法及可行性分析






主程序部分 void main() { 初始化； 构造哈夫曼树； 求哈夫曼编码； 哈夫曼编码输出； }
哈夫曼树部分
实现哈夫曼树 的抽象数据类型
哈夫曼编码部分
实现求哈夫 曼编码算法的数据类 型
主函数
int main(){ int n; printf("请输入要输入的字符数量n:");//读入字符的个数 while(scanf("%d",&n),n>=0&&n<=20){ //初始化 printf("请输入n个字符和n个权值\n"); CodeInput(n,ht);//输入数据函数，将读入n个字符和权重 CreateHT(ht,n);//构造哈弗曼树 CreateHCode(ht,hcd,n);//哈弗曼编码算法 CodeOutput(n,hcd);}//打印哈弗曼编码，将打印出编码，和 每一个字符述】 设计一个利用哈夫曼 算法的编码和译码系统， 重复地显示并处理以下 项目，直到选择退出为 止。 【选做内容】 (1)显示哈夫曼树； (2)界面设计的优化。

【基本要求】 (1)初始化：键盘输入字 符集大小n、 n个字符和n个权值，建立哈 夫曼树； (2)编码：利用建好的哈 夫曼树生成哈夫曼编码； (3)输出编码； (4)设字符集及频度如下 表： 字符：A B C D E F 频度：4 9 23 2 17 15 字符：G H I J K 频度：1 2 3 3 4