} static int k=0; int bb[1000]; static int x; static int y; int min=1000;
for(int jj=0;jj<n;jj++) //创建第n+1个节点 {
if(HTree[jj].weight<min) { min=HTree[jj].weight;
2009级数据结构实验报告
实验名称： 实验3——哈夫曼树
学生姓名： 陈家斌
班 级： 2009211121
班内序号： 16
学 号： 09210619
日 期： 2010年12月3日
1．实验要求
【实验目的】
通过选择下面两个题目之一进行实现，掌握如下内容： 掌握二叉树基本操作的实现方法 了解赫夫曼树的思想和相关概念 学习使用二叉树解决实际问题的能力
2. 程序分析
【算法实现】
程序第一遍统计原数据中各字符出现的频率，利用得到的频率值 创建哈夫曼树，并把树的信息保存起来，以便解压时创建同样的哈夫曼 树进行解压；第二遍，根据第一遍扫描得到的哈夫曼树进行编码，并把 编码后的码字存储。
哈弗曼树的c++描述如下：
class Huffman {
public: HNode*HTree; //哈夫曼树 HCode*HCodeTable; //哈弗曼编码表
study data Structure. 提示： 1、用户界面可以设计为“菜单”方式：能够进行交互。
2、根据输入的字符串中每个字符出现的次数统计频度，对没有 出现的 字符一律不用编码。
【代码要求】 1、必须要有异常处理，比如删除空链表时需要抛出异
常； 2、保持良好的编程的风格： 代码段与段之间要有空行和缩近 标识符名称应该与其代表的意义一致 函数名之前应该添加注释说明该函数的功能 关键代码应说明其功能 3、递归程序注意调用的过程，防止栈溢出
【题目】
利用二叉树结构实现赫夫曼编/解码器。 【基本要求】
1、 初始化(Init)：能够对输入的任意长度的字符串s进 行统计，统计每个字符的频度，并建立赫夫曼树
2、 建立编码表(CreateTable)：利用已经建好的赫夫曼 树进行编码，并将每个字符的编码输出。
3、 编码(Encoding)：根据编码表对输入的字符串进行 编码，并将编码后的字符串输出。
kk=k+2; } if(kk==k) {
if(HTree[jjj].weight>=HTree[x].weight)
{ if(HTree[jjj].weight<_min) { _min=HTree[jjj].weight; y=jjj;
} } } } bb[k]=y; k++; HTree[x].parent=HTree[y].parent=ii; HTree[ii].weight=HTree[x].weight+HTree[y].weight; HTree[ii].lchild=x; HTree[ii].rchild=y; HTree[ii].parent=-1; } }
【存储算法】
对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立 赫夫曼树
void Huffman::CreateHTree(int a[],int n) {
HTree=new HNode [2*n-1]; for(int i=0;i<n;i++) {
HTree[i].weight=a[i]; HTree[i].lchild=-1; HTree[i].rchild=-1; HTree[i].parent=-1;
if(HTree[jjj].weight<_min) {
_min=HTree[jjj].weight; y=jjj;
}
} } } bb[k]=y; k++; HTree[x].parent=HTree[y].parent=n; HTree[n].weight=HTree[x].weight+HTree[y].weight; HTree[n].lchild=x; HTree[n].rchild=y; HTree[n].parent=-1; for(int ii=n+1;ii<2*n-1;ii++) //开始创建哈夫曼树， {
if(HTree[jj].weight<min) {
min=HTree[jj].weight; x=jj;
} } } } bb[k]=x; k++; int _min=1000; for(int jjj=0;jjj<ii;jjj++) { int kk; for( kk=0;kk<k;kk++) { if(jjj==bb[kk])
x=jj;
}
} ห้องสมุดไป่ตู้b[k]=x;
k++; int _min=1000; for(int jjj=0;jjj<n;jjj++) {
int kk; for( kk=0;kk<k;kk++) {
if(jjj==bb[kk]) kk=k+2;
} if(kk==k) {
if(HTree[jjj].weight>=HTree[x].weight) {
min=1000;
for(int jj=0;jj<ii;jj++) {
int kk; for( kk=0;kk<k;kk++) {
if(jj==bb[kk]) kk=k+2;
} if(kk==k) {
if(HTree[jj].weight>=HTree[y].weight )// may wrong {
4、 译码(Decoding)：利用已经建好的赫夫曼树对编码 后的字符串进行译码，并输出译码结果。
5、 打印(Print)：以直观的方式打印赫夫曼树（选作）
6、 计算输入的字符串编码前和编码后的长度，并进行 分析，讨论赫夫曼编码的压缩效果。
【测试数据】 I love data Structure, I love Computer。I will try my best to
void CreateHTree(int a[],int n);//创建哈夫曼树 void CreateTable(char b[],int n);//创建编码表 void Encoding (char*s,int n);//编码 void Decoding (char*s,char*d,int n);//解码 void DestroyTree(int n); };