数据结构实习报告

步骤一：

初始状态，仅有唯一的NYT节点，NYT节点的权重为0

步骤二：输入字符a，由于在编码树中找不到与字符a有关的叶节点，故输出NYT引导的比特流（无）和a对应的原始码字：用a表示

更新原NYT节点的权值

步骤三：输入b，在编码树中找不到与字符b有关的叶节点，故输出NYT引导的码流和b的原始编码即0b 更新编码树：

更新原NYT节点权值

5

当前节点指向原NYT节点，判断当前节点是否为根节点，不是，当前节点指向原NYT节点的双亲节点，当前节点是block中最大编号的节点，权值加1

当前节点是根节点，结束

步骤四：读入c，c是第一次出现，输出00c 更新编码树：

6

步骤5：读入字符d 输出：100d

步骤五：读入字符d 输出：001

字符d在编码树中已出现过，

7

步骤六：读入字符b 输出001

步骤七：读入字符b，输出：10

8