又称单词查找树,是一种树形结构,是一种哈希树的变种。 典型应用: 1.统计 2.排序 3.保持大量字符串(不仅限于字符串) 经常被搜索引擎用于文本词频统计 优点: 利用字符串的公共前缀来减少查询时间,最大限度地减少无谓字符串的比较,查询效率比哈希树高算法思路:
1.创建存储儿子节点的数组son[][26]
由于存储字母,最多只有26钟可能,故列为26
2.创建记录单词出现次数的数组cnt[]
每次字符串遍历到最后一个字母时,累加一次
#核心代码 import numpy as np def main(): idx = 0 # 每一个字母都有唯一的索引号 son = np.zeros((10,26),dtype=int) #存放当前节点的子节点 cnt = [0]*1000 # 记录单词数 str_ = input("请输入字符串:") insert(str_) # 插入单词操作 query(str_) #查询单词数量操作 def insert(str_): global idx global son global cnt p = 0 # 行标记 for item in str_: u = ord(item)-ord('a') if son[p][u] == 0: idx += 1 son[p][u] = idx p = son[p][u] cnt[p] += 1 def query(str_): p = 0 for item in str_: u = ord(item)-ord('a') if son[p][u] == 0: return p = son[p][u] return cnt[p]