时间戳

首页 > 解决方案 > 为什么我需要双指针？

c - 为什么我需要双指针？

问题描述

我不明白为什么我需要在“结构图”中使用双指针。是因为它允许我访问我在函数 makeGraph() 中创建的节点之一吗？

如果我使用一个指针（结构节点 *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);
}

标签： cpointersdouble

解决方案

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

该图具有在 的numVertices成员中设置的多个顶点struct graph。每个顶点都需要一个邻接表，每个邻接表都需要一个struct node *. struct node *所以图需要一个长度数组numVertices。代码的作者选择动态分配数组作为成员指向的单独内存块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])是从 astruct graph的地址到adjList[vertices]数组成员元素的地址的偏移量，以字节为单位。分配该大小的内存块刚好足以容纳struct graph指针数组的加号。另一种指定大小的方法是sizeof(struct graph) + vertices * sizeof(struct node *)or sizeof(struct graph) + vertices * sizeof(graph->adjList[0])，但我认为使用offsetof宏是指定大小的更简洁的方法。

推荐阅读