北邮信通院数据结构实验报告三哈夫曼编码器.docx

文档介绍：数据结构实验报告
实验名称：实验三树——哈夫曼编/解码器
学生姓名：
班 级：
班内序号：
学 号：
日 期：2014年12月11日
实验要求
利用二叉树结构实现赫夫曼编/解码器。
基本要求：
1、 初始化(Init)：ree[i]. weight 二 HTree[x]. weight+ HTree[y]. weight;
HTree[i]. LChild 二 x;
HTree[i]. RChild 二 y;
HTree[i]. parent = T;
}
}
时间复杂度为0(子)
void Huffman::SelectMin( HNode *hTree, int n, int &il, int &i2 )
(
int i;
//找一个比较值的起始值
for(i=0; i<n; i++) 〃找 il
if(hTree[i]. parent==-l )
il=i;
break;
i++；
for( ; i<n; i++) 〃找 i2
if (hTree [i]. parent=-l )
i2=i;
break;
if(hTree[i1]. weight>hTree[i2]. weight)
//il指向最小的
int j=i2;
i2=il;
il = J；
〃开始找最小的两个
i++；
for( ; i<n; i++)
( if(hTree[i]. parent==-l
&& hTree[i]. weight < hTree[il]. weight )
il = i；
( i2=il;
else if( hTree[i]. parent==-l
&& hTree[i]. weight < hTree[i2]. weight)
( i2=i; }
时间复杂度为0(n)
创建编码表
算法过程：从叶子到根——自底向上
首先定义码表存储空间；
循环对n个叶子结点自底向上回溯到根，记下途径的左右关系，形成编码的逆序串;
将各个叶子结点对应的逆序串反序即可。
void Huffman::CreateCodeTable()
(
HCodeTable = new HCode [n]; 〃生成编码表
for (int i=0;i<n;i++)
{
HCodeTable[i]. data = 1[i];
int child二i; //孩子结点编号
int parent = HTree[i]. parent; //当前结点的父结点编号
int k=0;
while(parent!=~1)
(
if (child==HTree[parent]. LChild) //左孩子标
HCodeTable[i]. code[k] =，O';
else
HCodeTable[i]. code[k]二'1'; 〃右孩子标
k++;
child 二 parent; //迭代
parent = HTree[child]. parent;
HCodeTable[i]. code[k] = ' \0'；
Reverse(HCodeTableEH. code) ; //将编码字符逆置
}
}
时间复杂度为0(n)
生成编码串
将输入的字符串的每一个字符与编码表比较
void Huffman: :Encode (char *d)//编码，d 为编码后的字符串
{
char *s = str;
while(*s!='\0')
{
for (int i=0;i<n;i++)
if (*s == HCodeTable[i]. data )
(
strcat(d, HCodeTable[i]. code);
break;
s++;
时间复杂度为0(n)
解码：
算法过程：从根到叶子-一自顶向下
基于huffman树存储数组，从根结点开始，依据输入待解码串s中码字。或1,分别向左或 右跟踪至叶子结点，叶子结点对应的字符(见码表)，即为解码得到的字符；
只要s串为结束，重复上述过程
void Huffman: :Decode (char* s, char *d) //解码，s为编码串，d为解码后的字符串
(
while(*s!='\0')
{
int parent = 2*n-2; //根结点在HTree中的下标
while (HTree[parent]. LChild!=-l) //如果不是叶子结点
{
if (*s=' O')
parent = HTree[parent]. LChild;
else
parent = HTree[parent]. RChiId;
s++;