为什么我需要双指针？

Question

我不明白为什么我需要内部双指针'struct graph'。是因为它允许我访问我在函数 makeGraph() 中创建的节点之一吗？

如果我使用一个指针 (struct node *adjList)，那么我无法将节点设置为我在 makeGraph() 中创建的 NULL。

我从 programiz.com 那里得到代码，在解释这段代码的文章中说：不要让 struct node** adjList 淹没你。我们所说的只是我们想要存储一个指向 struct node* 的指针。这是因为我们不知道该图将有多少个顶点，因此我们无法在编译时创建链表数组。

如果我这样做：graph->adjList[1] 是转到第二个节点的地址还是转到节点内部？（我说的是我在 makeGraph() 中创建的节点）

我理解其余代码。如果有人能帮助我，我将不胜感激。

#include <stdlib.h>
#include <stdio.h>

struct node
{
    int vertex;
    struct node *next;
};

struct graph
{
    int numVertices;
    struct node **adjList; // <--- THIS ONE
};

struct graph *makeGraph(int vertices) // Creating a Graph
{
    struct graph *graph = malloc(sizeof(struct graph));
    graph->numVertices = vertices;
    graph->adjList = malloc(sizeof(struct node) * vertices); // creating the nodes

    for (int i = 0; i < vertices; i++)
        graph->adjList[i] = NULL; // Setting all nodes to NULL

    return graph;
}

void addEdge(struct graph *graph, int src, int dest) // Add Edge
{
        struct node *newNode = makeNode(dest);
        newNode->next = graph->adjList[src];
        graph->adjList[src] = newNode;

        struct node *newNode2 = makeNode(src);
        newNode2->next = graph->adjList[dest];
        graph->adjList[dest] = newNode2;
        return;

int main()
{
    struct graph *graph1 = makeGraph(4);
    addEdge(graph1, 0, 1);
    addEdge(graph1, 0, 2);
    addEdge(graph1, 0, 3);
}

Answer 1

邻接表表示为 struct node 的链表。通过指向列表第一个元素的指针访问列表。（当列表为空时，指针将为 NULL。）指针的类型为 struct node *.

该图的顶点数在 struct graph 的 numVertices 成员中设置。每个顶点需要一个邻接表，每个邻接表需要一个struct node *。因此该图需要一个长度为 numVertices 的 struct node * 数组。代码的作者选择动态分配数组作为 adjList 成员指向的单独内存块。 adjList 成员的类型是指向元素类型的指针。元素类型是 struct node * 所以 adjList 成员的类型是 struct node **.

还有另一种方法可以为struct graph 及其邻接表分配内存。通过将 adjList 成员更改为 灵活数组成员 ，可以将它们分配为单个块，如下所示：

#include <stdlib.h>
#include <stddef.h>
#include <stdio.h>

struct node
{
    int vertex;
    struct node *next;
};

struct graph
{
    int numVertices;
    struct node *adjList[]; // <--- FLEXIBLE ARRAY MEMBER
};

struct graph *makeGraph(int vertices) // Creating a Graph
{
    struct graph *graph = malloc(offsetof(struct graph, adjList[vertices]));
    graph->numVertices = vertices;

    for (int i = 0; i < vertices; i++)
        graph->adjList[i] = NULL; // Setting all nodes to NULL

    return graph;
}

offsetof(struct graph, adjList[vertices]) 是从 struct graph 的地址到 adjList[vertices] 数组成员元素的地址的字节偏移量。分配该大小的内存块刚好足以容纳 struct graph 加上指针数组。另一种指定大小的方法是 sizeof(struct graph) + vertices * sizeof(struct node *) 或者 sizeof(struct graph) + vertices * sizeof(graph->adjList[0])，但我认为使用 offsetof 宏是指定大小的更简洁的方法。

为什么我需要双指针？

Why do I need double pointers?

c

pointers

double