c - C 语言字典

Question

关闭。此题需要 details or clarity 。目前不接受答案。

---

想要改进这个问题吗？通过 editing this post 添加详细信息并澄清问题.

已关闭 3 年前。

Improve this question

我正在尝试用 C 语言实现一个非常简单的字典。我正在考虑使用链表。我在网上看到了这个实现: https://gist.github.com/kgabis/3141664 (我试图在这里发布代码，但它不允许我)。

这看起来有点像我的想法，只是我的值必须是整数。另外，在我自己的“get”函数中，我在返回值后没有使列表指向尾部，我做错了吗？

我的问题是:它被认为是一个很好的字典实现代码吗？我自己的代码有点不同，因为我希望能够打印字典(很难弄清楚应该如何打印我的键值对!)我还希望能够用键数组和值数组制作字典!

我已经坚持了几天了，任何形式的帮助将不胜感激!

Answer 1

I'm trying to implement a pretty simple Dictionary in C. I was thinking about using a linked list. [...] Is it considered a good implementation code for a Dictionary?

不，绝对不是。类似字典的结构的主要目的是提供非常快速的值插入、删除和查找(给定键)，这通常具有恒定的时间复杂度(O(1))。链表具有线性插入和查找时间复杂度，这意味着要访问知道其键的值，需要 O(n) 操作，其中 n 是数字列表中已存在的值。这基本上与简单的未排序数组具有相同的性能，从而抵消了该结构的效用。实现这种结构的事实上的标准方法是使用 hash table ，如果有一个相当好的散列函数和冲突解决策略，它允许在恒定时间内访问数据。

另请参阅:Big O notation .