题3

题3

题目

【2020 统考真题】若任意一个字符的编码都不是其他字符编码的前缀, 则称这种编码具有前缀特性。现有某字符集 (字符个数 ) 的不等长编码,每个字符的编码均为二进制的 0、1 序列,最长为 位,且具有前缀特性。请回答下列问题:

1. 哪种数据结构适宜保存上述具有前缀特性的不等长编码?
2. 基于你所设计的数据结构, 简述从 串到字符串的译码过程。
3. 简述判定某字符集的不等长编码是否具有前缀特性的过程。

分析

解

1. 使用一棵二叉树保存字符集中各字符的编码, 每个编码对应于从根开始到达某叶结点的一条路径, 路径长度等于编码位数, 路径到达的叶结点中保存该编码对应的字符。

2. 从左至右依次扫描 串中的各位。从根开始,根据串中当前位沿当前结点的左子指针或右子指针下移, 直到移动到叶结点时为止。输出叶结点中保存的字符。然后从根开始重复这个过程, 直到扫描到 0/1 串结束, 译码完成。

3. 二叉树既可用于保存各字符的编码, 又可用于检测编码是否具有前缀特性。判定编码是否具有前缀特性的过程, 也是构建二叉树的过程。初始时, 二叉树中仅含有根结点, 其左子指针和右子指针均为空。

依次读入每个编码 ,建立/寻找从根开始对应于该编码的一条路径,过程如下:

对每个编码,从左至右扫描 的各位,根据 的当前位 ( 0 或 1 ) 沿结点的指针 (左子指针或右子指针) 向下移动。当遇到空指针时, 创建新结点, 让空指针指向该新结点并继续移动。沿指针移动的过程中, 可能遇到三种情况:

① 若遇到了叶结点 (非根), 则表明不具有前缀特性, 返回。

② 若在处理 的所有位的过程中,均没有创建新结点,则表明不具有前缀特性,返回。

③ 若在处理 的最后一个编码位时创建了新结点,则继续验证下一个编码。

若所有编码均通过验证, 则编码具有前缀特性。