适合快速查找和简单增删改查的C数据结构

Question

如题头所述，我需要一种适合快速高效搜索的数据结构。数据结构还应该能够向/从数据结构内的任何位置添加/删除元素。

目前我正在使用链表。但问题是我应该遍历列表以找到所需的元素。一般搜索算法(二分搜索、跳转搜索等)不能直接用于链表，因为无法随机访问列表元素。对这些算法所需的列表元素进行排序也是一个问题。另一方面，我不能使用数组，因为很难向/从任何所需的索引添加/删除元素。

我在链表中​​寻找搜索算法，然后我来到了“跳表”。现在想问问有没有更好的数据结构适合我的情况，或者链表有没有更好的搜索算法。

Answer 1

我会使用 AVL 二叉搜索树

有关二叉搜索树的示例，您可以查看 https://www.geeksforgeeks.org/avl-tree-set-1-insertion/和 https://www.geeksforgeeks.org/avl-tree-set-2-deletion/

很详细，有C代码和schema。

它的搜索效率很高，并且允许您添加和删除值。它适用于数值和某些字符实现(例如 dictionnay)。