北邮数据结构实验3哈夫曼编码

4. 重复以上步骤，直到所有待编码串中的字符都编码完毕 5. 输出编码后的字符串 时间复杂度O(n)

（7）.解码函数（void Huffman::Decode()） 算法伪代码：

1. 得到指向哈夫曼树的根结点的指针和指向待解码串中的第1个字符的指针 2. 逐个读取待解码串中的字符，若为0，则指向哈夫曼树当前结点的指针指向

当前结点的左孩子，若为1，则指向当前结点的右孩子

3. 指向待解码串的指针指向解码串中的下一个字符，直到指向哈夫曼树结点

的指针的孩子结点为空

4. 如果哈夫曼树只有一个叶子结点，直接将待解码串中的编码转换为对应的

字符

5. 如果指向哈夫曼树结点的指针的孩子结点已经为空，则将叶子结点下标对

应的字符追加到解码串中。 6. 输出解码串

时间复杂度O(n)

3. 程序运行结果

1.主函数流程图

5

6

main.cpp

#include\void main() {

Huffman H;

do {

cout<<\请选择功能（输入编译字符串2输出编码表3输出字符串编码及压缩比4解码5退出）int i;

char str1[100]={'\\0'}; string d; int count=0;

\

7

int n; cin>>n; char ch='a'; cin.get(ch); switch(n) { case 1:

{

cout<<\请输入\ cin.getline(str1,100);

}

cout<<\请选择（继续运行 0 退出）\

break; break;

cout<<\请输入正确序号\break; case 5: default:

}

int m=0; while(str1[m++])

count++;

break;

case 2:

{ } break; { } break; { }

cout<<\请输入解码数据\char s[200]={'\\0'}; char d[100]={'\\0'}; cin.getline(s,200,'\\n'); H.Decode(s,d);

cout<<\解码数据为：\H.Encode(str1,&d);

H.differ(str1,count);

H.CreateCodeTable(H.str2,H.dif);

case 3:

case 4:

8