文档介绍：word
word
1 / 13
word
数据结构实验报告
实验名称：实验三哈夫曼树
学生：
班 级：
班序号：
学 号：
日 期：
程序分析：
存储结构：二叉树
程序流程：
template <class T>
class BiTree
{
public:
BiTree(); //构造函数，其前序序列由键盘输入
~BiTree(void); //析构函数
BiNode<T>* Getroot(); //获得指向根结点的指针
protected:
BiNode<T> *root; //指向根结点的头指针
};
//声明类BiTree及定义结构BiNode
Data：
二叉树是由一个根结点和两棵互不相交的左右子树构成
word
word
2 / 13
word
二叉树中的结点具有相同数据类型及层次关系
示意图： root
lchild parent rchild
哈夫曼树类的数据域，继承节点类型为int的二叉树
class HuffmanTree:public BiTree<int>
data:
HCode* HCodeTable;//编码表
int tSize; //编码表中的总字符数
二叉树的节点结构
template <class T>
struct BiNode //二叉树的结点结构
{
T data; //记录数据
T lchild; //左孩子
T rchild; //右孩子
T parent; //双亲
};
示意图：
T data
T lchild
T rchild
T parent
编码表的节点结构
struct HCode
{
char data; //编码表中的字符
char code[100]; //该字符对应的编码
};
示意图：
char data
char code[100]
待编码字符串由键盘输入，输入时用链表存储，链表节点为
struct Node
{
char character; //输入的字符
word
word
3 / 13
word
unsigned int count;//该字符的权值
bool used; //建立树的时候该字符是否使用过
Node* next; //保存下一个节点的地址
};
Node* next
bool used
unsigned int count
char character
示意图：
关键算法分析：
（void HuffmanTree::Init(string Input)）
算法伪代码：
，并将其插入到链表尾部,n=1(n记录的是链表中字符的个数)
，逐个取出字符串中的字符
将当前取出的字符与链表中已经存在的字符逐个比较，如果当前取出的字符与链表中已经存在的某个字符相同，则链表中该字符的权值加1。
如果当前取出的字符与链表中已经存在的字符都不相同，则将其加入到链表尾部，同时n++
=n(tSize记录链表中字符总数，即哈夫曼树中叶子节点总数)
源代码：
void HuffmanTree::Init(string Input)
{
Node *front=new Node; //初始化链表的头结点
if(!front)
throw exception("堆空间用尽");
front->next=NULL;
front->character=NULL;
front->count=0;
Node *pfront=front;
char ch=Input[0]; //获得第一个字符
Node* New1=new Node;
if(!New1)
throw exception("堆空间用尽");
New1->characte