c - 数据结构和算法的API设计

Question

我最近实现了二叉搜索树、链表等作为学习练习。我实现了几个API，如插入、删除等。例如，插入节点 API 看起来像

 void insertNode(Node** root, Node* node)

应用程序将为要插入的节点分配内存。即节点并分配值/键并传递给此函数。

1)我的问题是，这总体上是否是正确的方法？或者应用程序只需要将值/键传递给 insertNode 函数，然后该函数分配内存？

  i.e void insertNode(Node** root, int key)
      {
            malloc for node here
      }

2) 什么是好的设计实践 - 应用程序处理分配内存和释放 APi 的库？

谢谢

Answer 1

一般原则:

1. 分配内存的人也应该有责任删除它。
2. 让客户的工作尽可能简单
3. 考虑线程安全

因此，不要让客户端分配由树管理的内存。然而，我们需要仔细考虑查找或搜索应该返回什么。

您可以查看示例代码来了解其他人对集合 API 采取的策略。对于 example .

顺便说一句，你不需要双指针作为你的根。

如果某人的 root 指向一个对象 { left -> ..., right -> ...} 那么如果您将 root 作为 Node* 传递，您的代码可以编写

 root->left = newValue;

您正在修改根指向的内容，而不是根本身。通过传递双指针，您可以完全重新定位结构，因为有人可以编写:

 *root = completelyNewTree

我怀疑你的意图。

现在，对于插入，我建议传递新值，但让集合分配空间并复制它。该集合现在可以完全控制它所保存的数据，并且它返回的任何内容都应该被复制。我们不希望客户端直接弄乱树(线程安全)。

这意味着对于查找结果，调用者必须预先分配缓冲区，或者我们必须清楚地记录集合正在返回调用者必须删除的已分配副本。

是的，使用任何垃圾收集语言都容易更容易!