binary-search-tree c data-structures cots

C 中的通用数据结构

发布于 2024-09-27 03:27:17 字数 377 浏览 6 评论 0原文

我正在考虑创建一个通用的 BST。没有什么特别的，没有 COTS，但我正在尝试确定跟踪 void* 类型的最佳方法。这是节点的接口：

typedef struct
{
   void *data;
   struct TreeNode *left;
   struct TreeNode *right;  
} TreeNode;

但是，当我编写添加/删除操作时，我需要进行比较，因此我需要跟踪“数据”指向的数据类型，对吗？

基本思想是有一个枚举 Node_Type 和一个函数compareTreeNodes，该函数接收两个 TreeNodes 和枚举作为第三个参数。这将允许函数确定将 void* 转换为什么。

还有其他/更好的想法吗？

原文

I'm looking into creating a generic BST. Nothing fancy no COTS, but I'm trying to decide the best way to keep track of the type of the void*. Here's the interface for the nodes:

typedef struct
{
   void *data;
   struct TreeNode *left;
   struct TreeNode *right;  
} TreeNode;

However, when I write add/remove, I'll need to do comparisons, hence I'll need to keep track of the type of data that "data" is pointing to, right?

Basic idea is to have an enum Node_Type and a function compareTreeNodes that receives the two TreeNodes and the enum as a 3rd arg. This would allow the function to determine what to cast the void* to.

Any other/better thoughts?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

匿名。 2024-10-04 03:27:17

但是，当我编写添加/删除时，我需要进行比较，因此我需要跟踪“数据”指向的数据类型，对吗？

看看 qsort() 如何解决这个问题。它也需要处理任意数据类型。基本上，您通过函数指针将比较委托给用户。

回复收藏 0 原文

最美不过初阳 2024-10-04 03:27:17

我假设一个 BST 中只有一种类型的数据。在这种情况下，我将创建一个封装结构，其中包含指向根节点的指针和指向比较函数的指针。 BST 的用户必须在初始化时提供合适的函数。

typedef struct {
    TreeNode *root;
    int (*compar)(const void *, const void *);
} Tree;

顺便说一句，您的第一行可能应该是 typedef struct TreeNode {。您有一个经过 typedef 处理的匿名struct，但引用了内部不存在的标记结构。
这两个版本都可以工作：

typedef struct TreeNode {
    void *data;
    struct TreeNode *left, *right;
} TreeNode;

typedef struct TreeNode TreeNode;
struct TreeNode {
    void *data;
    TreeNode *left, *right;
};

您不能创建自引用匿名结构。

I assume a single BST will have only one type of data in it. In that case I would make a encapsulating struct that contains a pointer to the root node and a pointer to a comparison function. The user of your BST would have to provide a suitable function at initialisation.

typedef struct {
    TreeNode *root;
    int (*compar)(const void *, const void *);
} Tree;

Btw, your first line should probably be typedef struct TreeNode {. You have a typdef'd anonymous struct, but refer to a non-existent tagged struct inside.
These two versions would work:

typedef struct TreeNode {
    void *data;
    struct TreeNode *left, *right;
} TreeNode;

typedef struct TreeNode TreeNode;
struct TreeNode {
    void *data;
    TreeNode *left, *right;
};

You cannot make self-referential anonymous structs.

回复收藏 0 原文

~没有更多了~