Trie数据结构插入代码中key[i] - 'a'语句的含义疑问
Trie代码中
key[i] - 'a'语句的作用说明 - C++的
char类型本质是存储ASCII编码的整数,小写英文字母的ASCII值是连续的:'a'对应97,'b'对应98,依次递增到'z'对应122。 - 这段Trie代码默认处理的是仅包含小写英文字母的字符串,节点中定义的
child数组长度为26,合法下标范围是0 ~ 25,每个下标对应一个英文字母的子节点。 - 如果直接把字符的ASCII值作为
child数组的下标,97~122的数值远超过数组的合法下标范围,会触发数组越界,导致非法内存访问甚至程序崩溃。 key[i] - 'a'就是做字符到数组下标的映射:'a'减'a'得到0,'b'减'a'得到1,以此类推,'z'减'a'得到25,刚好完美匹配child数组的下标范围,每个位置就对应了对应字母的子节点存储位置。
注意:这个写法的前提是插入的字符串仅包含小写英文字母,如果需要支持大写、数字等其他字符,需要对应调整映射规则和
child数组的长度。
内容的提问来源于stack exchange,提问作者Sway the Destroyer 'STD'
相关产品推荐
相关产品推荐

