c - 适合快速搜索和简单添加/删除的 C 数据结构

Question

正如问题标题中所述，我需要一个适合快速高效搜索的数据结构。数据结构还应该能够在数据结构内的任何地方添加/删除元素。

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

我一直在寻找链接列表中的搜索算法，然后我来到了“跳过列表”。现在我在这里询问是否有更好的数据结构适合我的情况，或者是否有更好的链表搜索算法。

标签： csearchdata-structureslinked-listrandom-access

Answer 1

我会使用 AVL 二叉搜索树

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

它非常详细，有 C 代码和架构。

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