数据结构实习报告

输出编码：a 0b00c100d00100110 由原始编码的编码规则：r=4

M=26，(1)k=1，k<2r,故将k-1 编成e+1 bit二进制数： a=00000；b=00001，c=00010，d=00011

2.1.2 程序流程图

9

图一、自适应哈弗慢编码的编码过程

10

no 一个个读入比特流，每读入1bit 按照比特流的指示，能否找到一个叶节点？ no yes 再读入1bit 当前节点是否为NYT节点？ yes 读入e bit二进制流 no 译码为找到的叶节点中的字符 对应的十进制数p>r? no 结束 yes p=p+r yes 再读入1bit 是否是最后 找到原始码表中的第一个bit p+1个位置上的字符为 译码结果 图二、自适应哈弗慢编码的解码过程

11

2.1.3 数据结构图

编码的数据结构：

存储结构：以结构体数组形式 逻辑结构：哈弗曼编码树

2.1.4 程序代码

（1）encoding.h #define false 0 #define true 1

//定义全局变量

int ALPH_SIZE=1024,root=1023; unsigned char NYT=255; unsigned char none= 254;

//定义哈弗曼树中的节点类型 typedef struct { unsigned char letter;//节点内容 int count; // 字符频率(字符在文本中出现的次数，可能发生改变)

12