哈夫曼树带权路径长度_c 哈夫曼树编码_数据结构哈夫曼树编码(13)

parent=root[parent].rchild;

i++;

}

if(tSize==1) //如果编码表只有一个字符，则根结点即为叶子结点 i++;

d.append(1,HCodeTable[parent].data);//将叶子节点对应的字符追加到解码串中 }

cout<

}

时间复杂度：

设待解码串长度为n，则复杂度为O(n)

8. 计算哈夫曼编码的压缩比(void HuffmanTree::Calculate(string s1,string s2)) 算法伪代码：

1. 获得编码前字符串的长度，即其占用的字节数

2. 获得编码后的字符串的长度，将其除以8然后向上取整，得到其占用的字

节数

3. 压缩比将两个相除

源代码：

void HuffmanTree::Calculate(string s1,string s2)

{

int cal1=s1.length();

int cal2=s2.length();

cal2=ceill((float)cal2/8); //将编码串的比特数转化为字节数 cout<<"编码前的字符串长度："<

cout<<"编码后的字符串长度："<

cout<<"压缩比为："<<((double)cal2/(double)cal1)*100<<"%"<

}

时间复杂度：

O(1)

9. 打印哈夫曼树(void HuffmanTree::PrintTree(int TreeNode,int layer) ) 算法伪代码：

1. 如果待打印结点为空，则返回

2. 递归调用函数打印当前结点的右子树

3. 根据当前结点所在的层次确定其前面要输出多少空格，先输出空格，在打

印当前结点的权值

4. 递归调用函数打印当前结点的左子树

源代码：

void HuffmanTree::PrintTree(int TreeNode,int layer)

{

if(TreeNode==-1) //如果待打印结点为空，则返回 return;

else

{

PrintTree(root[TreeNode].rchild,layer+1); //先打印该结点的右子树，layer记录

的是该结点所在的层次

for(int i=0;i

空格

cout<< ;

cout<

PrintTree(root[TreeNode].lchild,layer+1); //打印该结点的左子树

}

}

时间复杂度：

中序遍历哈夫曼树，复杂度为O(n)

10. 菜单函数(void HuffmanTree::Menu())

算法伪代码：

1. 逐一读取键盘缓存区中的字符，并将它们逐一追加到记录输入字符串的

string变量中，直到读到回车输入符为止

2. 删除string变量末尾的回车输入符

3.利用string变量创建哈夫曼树，初始化编码表。

4. 直观打印哈夫曼树

5. 对输入的字符串进行编码

6. 对编码后的字符串进行解码

7. 计算编码前后的压缩比并输出

源代码：

void HuffmanTree::Menu()

{

cout<<"请输入你要编码的文本,按回车键确定输入"<

string Input;

char letter;

do //将字符逐个读入Input变量中

{

letter=cin.get();

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-35162-13.html