文档介绍：数据结构试验四试验汇报
试验名称: 哈弗曼编码
姓名: 黄州龙班级: 08级软件工程A班学号:
需求分析
本试验包含算法思想是最优二叉树构建, 而该算法思想实际应用广泛, 哈弗曼编码就是这一算法应用, 经过本试验练****能够加深学生对二叉树了解, 学****怎样将算法学以致用, 并为以后应用中有所突破奠定基础;
试验程序是经过用户输入哈弗曼编码频度表文件（.txt）路径, 从硬盘中读取数据, 并深入使用哈弗曼编码算法进行哈弗曼树构建, 最终输出编码结果给用户, 也能够选择将哈弗曼树存入文件保留起来;
试验程序能够实现对已知频度码值进行编码功效, 含有一定使用价值, 编写函数算法是完全能够被用在其它软件程序中, 含有很好代码复用性;
存放编码频度表文件结构:
首行是一个正整数N, 表示有N个码
第二行是N个以空格隔开字符, 即N个码码值, 第三行是N个用空格隔开非负整数, 对应N个码值频度;
测试数据;

文件内容:
8
A B C D E F G H
12 50 52 60 34 80 21 4

文件内容:
6
V P K L Y M
20 10 30 40 60 40

文件内容:
26
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

文件内容:
9
I A M Z E P H Y R
9 8 7 6 5 4 3 2 1
概要设计
1、二叉链结点定义
struct TreeNode
{
char data;//数据域, 具体应用时可能是别类型
int visit;//目前访问状态
TreeNode * l;//左树域
TreeNode * r;//右树域
};//end of definition to TreeNode
2、创建森林和创建哈弗曼树模块
Status createForest(vector<TreeNode *> &forest,string filename)
初始条件: filename所指示文件路径有效且文件内容符合格式要求
参数: 第一个参数传入用来存放每个码结点地址向量, 第二个参数传入编码频度表文件路径字符串
操作结果:从文件中读取数据并构建出码值二叉森林, 为哈弗曼编码算法做准备
Status createHuffman(vector<TreeNode *> &forest)
初始条件: 传入码值森林已经初始化
参数: 第一个参数传入码值森林所初始化向量
操作结果: 码值森林只剩一个结点, 该结点是哈弗曼树根结点
3、输出哈弗曼编码和输出哈弗曼树模块
void printHuffmanCode(TreeNode * root)
初始条件: 传入树根结点是有效树根结点
参数: 第一个参数传入哈弗曼树根结点
操作结果: 输出每个码值对应哈弗曼编码
printTree(TreeNode * tn,int depth)
初始条件: 传入二叉树根是有效, 传入二叉树深度和二叉树相对应
参数: 第一个参数传入要进行树形输出二叉树根结点
第二个根结点传入二叉树深度
操作结果;将二叉树以树状进行输出, 比较直观
具体设计
1、创建森林和创建哈弗曼树模块
Status createForest(vector<TreeNode *> &forest,string filename)
{
ifstream is(());//从路径字符串初始化文//件流
cout<<"从文件中读取编码频度表......\n";//提醒以开始//读取
int codenum=0;
TreeNode *code=NULL;
is>>codenum;//读取码数
cout<<"有"<<codenum<<"个编码.\n";
for(int i=0;i<codenum;i++)//依据结点数一次读入码值数//据并以此创建结点森林
{
code=new TreeNode;
if(!code)//创建结点, 若失败则返回错误
return ERROR;