C中的树数据结构 [英] tree data structure in C

问题描述

Hello论坛，



是否可以在纯C中创建树数据结构？

这不是关于二叉树但是每个节点都应该有0-n个孩子。



树在运行时永远不会被更改。由于这是针对嵌入式（Microchip Pic32）项目，因此RAM是一个问题。所以我想把整个东西存储在代码存储器中。通常是const所有内容。



这就是我尝试过的：

Hello forum,

is it possible to create a tree data structure in pure C?
This is not about a binary tree but every node shall have 0-n children.

The tree shall never be changed at runtime. Since this is for an embedded (Microchip Pic32) project, RAM is an issue. So I'd like to store the whole thing in code memory. Usually that's given for everything "const".

This is what I tried:

/* Header */
typedef struct TreeNode TreeNode;

/* Source */
struct TreeNode{
    int id;
    char* text;
    TreeNode* children[]; // List of child nodes
};

void DoSth(void)
{
    static const TreeNode tree = {
        0, "hidden", (TreeNode[3]){
            (TreeNode){1, "child", NULL},           // (1)
            (TreeNode){2, "secondChild", NULL},     // (1)
            (TreeNode){3, "thirdChild", NULL}       // (1)
	}
    };                                              // (2)

    // Code that's actually using the data
}

我确信在结构定义中， children 必须通过指针引用，因为 TreeNode 本身尚未完全定义。



但编译器抱怨（由我编号）

I know for sure that within the struct definition, children has to be referred to by pointers since TreeNode itself is not fully defined at that time.

But Compiler complains (numbering by me)

(1) non-static initialization of a flexible array member
(2) initializer element is not constant

（1）这怎么不是静态的？一切都是为了初始化。



（2）与（1）相同的问题。为什么这不恒定？鉴于嵌入式低RAM环境，这一点尤其重要。

(1) How should that not be static? Everything is given for the initialization.

(2) Same question as (1). Why is that not constant? And this is especially important given the embedded low RAM environment.

推荐答案

您正在尝试混合静态和动态数据，因此编译器不知道要预留多少空间。对于本身没有子节点的子节点，您可能需要不同的结构。你不能像在你的子节点中那样将数组声明为NULL。

You are trying to mix static and dynamic data, so the compiler does not know how much space to reserve. You probably need a different structure for child nodes that do not themselves have children. You cannot declare an array as NULL as you have tried to do in your child nodes.

正如Richard所说，不可能用不完整的类型和变量长度数组来制作你想要的东西，但是...

如果你不喜欢C的黑暗面，有一个解决方法：

As Richard said it is not possible to make what you want with incomplete types and variable lenght arrays, but ...
If you don't dislike the dark side of the C, there is a workaround:

typedef struct _TreeNode{
    int id;
    char* text;
    struct _TreeNode* children[1]; // List of child nodes
} TreeNode;

static TreeNode tree1 = {1, "child",       {0}};
static TreeNode tree2 = {2, "secondChild", {0}};
static TreeNode tree3 = {3, "thirdChild",  {0}};
static TreeNode tree4 = {4, "fourthchild", {0}};

void *FakeTree[] = {
                     (void *)0,
                     (void *)"hidden",
                     (void *)&tree1,
                     (void *)&tree2,
                     (void *)&tree3,
                     (void *)&tree4
                    };

void DoSth(void)
{
	TreeNode *tree = (TreeNode *)&FakeTree;

	// Code that's actually using the data
	// Please remember that you must access the structure always as a
	// pointer to it. I.e.
	for (int i=0; i<4; i++)
	{
		printf("id=%x, name=\"%s\"\n", pTree->children[i]->id, pTree->children[i]->text);
	}
}

唯一的限制是强制表示机器的整数和指针你将使用相同大小的代码。

最后的建议：这可能对你的代码有危险，不要在家里做！ Jocking，这就是你不必制作程序的方法，但如果有必要......

我希望这能解决你的问题;）

The only limit is that it is mandatory that the integers and the pointers of the machine where you'll use the code have the same size.
Last advice: this could be dangerous for your code, don't make it at home! Jocking, this is how you don't have to make programs, but if it is necessary...
I hope this solves your problem ;)

这篇关于C中的树数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！