我们看到Google,Firefox一些AJAX页面在用户输入字符时会显示一个可能的项目列表.

有人能给出一个实现自动完成的好算法和数据 struct 吗?

推荐答案

trie是一种数据 struct ,可用于快速查找与前缀匹配的单词.

编辑:下面是一个示例,说明如何使用其中一个来实现自动完成http://rmandvikar.blogspot.com/2008/10/trie-examples.html

这里比较了3种不同的auto-complete implementations(尽管它是用Java而不是C++).

* In-Memory Trie
* In-Memory Relational Database
* Java Set

在查找密钥时,trie比set实现稍微快一些.Trie和Set都比关系数据库解决方案快得多.

该设备的安装成本低于Trie或DB解决方案.你必须决定是频繁构建新的"词集",还是更优先考虑查找速度.

这些结果是在java中,你的里程可能会随C++的解决方案而变化.

C++相关问答推荐

如何将匿名VLA分配给指针?

rSP堆栈指针在返回函数调用的值时有任何用途吗?

为什么这个C程序代码会产生以下结果?

与unions 的未定义行为

什么C代码将确定打开的套接字正在使用的网络适配器?

为什么在C中设置文件的位置并写入文件,填充空字符?

丑陋的三重间接:可扩展的缓冲区管理 struct

在函数中使用复合文字来初始化C语言中的变量

Malloc(sizeof(char[Length]))是否不正确?

如果包含路径不存在,我的编译器可以被配置为出错吗?(GCC、MSVC)

拥有3x3二维数组并访问数组[1][3]等同于数组[2][0]?

在基本OpenGL纹理四边形中的一个三角形中进行渲染

在C++中访问双指针

如何使用_newindex数组我总是得到错误的参数

如何仅使用软件重新初始化STM32微控制器中的USB枚举?

如何用C语言为CLI应用程序编写按键检测系统?

将数字的每一位数平方,并使用C将它们连接为一个数字(程序不能正确处理0)

C 语言中 CORDIC 对数的问题

const struct 成员的 typedef 中的灵活数组大小

将数组返回到链表