发布时间 : 星期五 文章北邮数据结构实验报告更新完毕开始阅读897193b19a89680203d8ce2f0066f5335b81676f
cout parent=root.lchild; else //编码为1则寻找右孩子 parent=root.rchild; i++; }
if(tSize==1) //如果编码表只有一个字符，则根结点即为叶子结点 i++;
(1,HCodeTable.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=(); int cal2=();
cal2=ceill((float)cal2/8); //将编码串的比特数转化为字节数 cout cout cout } 时间复杂度： 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.rchild,layer+1); //先打印该结点的右子树，layer记录 的是该结点所在的层次 for(int i=0;i 空格
cout cout PrintTree(root.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=(); (1,letter);
}while(letter!=' ');
(()-1,1); //去掉Input末尾的回车符
Init(Input); //根据输入的字符串创建哈夫曼树及其编码表 cout PrintTree(2*tSize-1-1,1); //打印哈夫曼树
cout string d1,d2;
cout Encode(Input,d1); //编码并打印编码串 cout Decode(d1,d2); //解码并打印解码串 cout Calculate(Input,d1); //计算编码前后的压缩比 } 其他
1.由于题目要求能输入任意长的字符串，所以本程序采用了string变量来记录输入
的字符串，并采用string类的类成员函数来完成各项任务
2.打印哈夫曼树时采用了递归函数，且采用了凹凸表的形式打印哈夫曼树。
3.为了输入空格，输入时采取逐个字符输入的方式 3. 程序运行结果 主函数流程图： 运行结果：
各函数运行正常，没有出现bug 4. 总结
经过这次实验，我了解了哈夫曼树的创建过程，了解了一种不等长编码的方法，用设断点调试的方法更加熟练，同时熟悉了STL中string类型的用法，对C++更加熟悉