c - 创建具有未知链接数的结构节点

Question

我研究过链表、二叉树，我们已经知道一个节点可以拥有的链接数量。例如，一个双向链表有 2 作为二叉树。但是当涉及到 Graphs 时，一个节点可以被 n 个其他节点所喜欢，所以我的问题是如何为具有未知数量链接的节点声明一个结构。

二叉树结构

struct node{
    node* left;
    node* right;
    int data;
}

单链表

struct node{
    node* link;
    int data;
}

在此图中，节点“2”有两个链接，而节点“4”有三个。

我是 C 的新手，所以请容忍我对这些主题缺乏了解，在此先感谢。

标签： cgraphstructure

Answer 1

如何为具有未知数量链接的节点声明结构。

创建指向动态分配的指向节点的指针数组的指针。

struct node {
    /// array of pointers to nodes we link to
    node **link;
    /// count of links
    size_t link_cnt;

    int data;
};

然后link指向一个动态分配的指向节点的指针数组——它是一个“链接”数组。可link_cnt用于跟踪链接数组中的链接计数。

// example of linking two nodes in one direction.
void node_link_to_node(struct node *this, struct node *other) {
   void *p = realloc(this->link, sizeof(*this->link) * (this->link_cnt + 1));
   if (p == NULL) abort();
   this->link = p;
   this->link[this->link_cnt] = other;
   this->link_cnt++;
}

我用 C 语言编写了这段代码。