5.0.2 字母表
Robert Sedgewick Kevin Wayne
一些应用程序可能会对字符串的字母表作出限制。在这些应用中,可能常常会需要一个 API 如表 5.0.2 所示的 Alphabet 类。
表 5.0.2 字母表的 API
这份 API 定义了一个构造函数,它用一个含有
个字符的字符串参数指定了字母表。API 定义了 toChar() 方法和 toIndex() 方法来在字符和 0 到
之间的整型值进行转换(常数时间)。它还包含了 contains() 方法来检查给定的字符是否存在于字母表中。方法 R() 和 lgR() 用来获取字母表中的字符数以及表示它们所需的比特数。toIndices() 方法和 toChars() 方法能够将由字母表中的字符组成的字符串与 int 数组相互转换。方便起见,下面的表格显示了各种内置的字母表,你可以通过类似 Alphabet.UNICODE16 的方式来访问它们。Alphabet 的实现很简单,我们将它留作练习(请见 5.1.12)。我们会在表 5.0.3 后面的框注“Alphabet 类的典型用例”来展示一个它的用例。
![](https://static001.geekbang.org/files/resource/ebook/100010/image01027.gif)
![](https://static001.geekbang.org/files/resource/ebook/100010/image01624.gif)
表 5.0.3 标准字母表
Alphabet 类的典型用例
字符索引数组。我们使用 Alphabet 类的一个最重要的原因是字符索引的数组能够提高算法的效率。在这个数组中,用字符作为索引来获取与之相关联的信息。如果要使用 Java 的 String 类,那就必须使用一个大小为 65 536 的数组;有了 Alphabet 类,则只需要使用一个字母表大小的数组即可。我们将要学习的一些算法能够产生大量的此类数组。在这种情况下,大小为 65 536 的数组是不可接受的。例如前面框注中的 Count 类,它从命令行接受一个字符串并打印出从标准输入获得的每个字符的出现频率。Count 中用来保存出现频率的 count[] 数组就是一个字符索引数组的示例。你可能会认为数组的计算有些繁琐,但实际上它是 5.1 节介绍的一系列快速排序算法的基础。
公开
同步至部落
取消
完成
0/2000
笔记
复制
AI
- 深入了解
- 翻译
- 解释
- 总结
![](https://static001.geekbang.org/resource/image/d0/e4/d0880927e2a522a038be2d04bf19dfe4.png)
该文章介绍了一个名为“5.0.2 字母表”的 API,它定义了一个名为 <code>Alphabet</code> 的类,用于处理字符串的字母表限制。该类包含了一系列方法,如根据字符串创建新的字母表、字符和整型值之间的转换、检查字符是否存在于字母表中等功能。文章展示了标准字母表的示例,以及一个名为 <code>Count</code> 的典型用例,用于统计字符出现的频率。此外,还介绍了使用 <code>Alphabet</code> 类处理数字的方法,以及基数方法的应用。总的来说,通过介绍 <code>Alphabet</code> 类及其应用场景,为读者提供了一种处理字符串字母表限制的有效工具,尤其适用于处理较小的字母表。文章还提到了在代码中使用常数 R = 256 并在分析中将 <img img src="https://static001.geekbang.org/files/resource/ebook/100010/image01027.gif" alt="R" inline-img="true" /> 作为参数。在适当的时候会讨论通用字母表的性能。
仅可试看部分内容,如需阅读全部内容,请付费购买文章所属专栏
《算法(第 4 版)》
《算法(第 4 版)》
立即购买
登录 后留言
精选留言
由作者筛选后的优质留言将会公开显示,欢迎踊跃留言。
收起评论