c - 指向节点的双指针

Question

我的疑问仅与指针有关，这里 head 是指向 Queue 的双指针，如果我们使用 *head 而不是访问内部的位置(或传递的地址) main 但当我们简单地使用 head 时，我们只在当前函数中使用 heading ，当我们执行此 时，它将保存指向 Queue 的指针的地址head=&(*head)->next 因为 (*head)->next 本身就是一个地址，当我们在此之前使用 & 时，一个单独的 block 将内存块将被创建并保存 (*head)->next 的地址，我们将该地址分配给 head我有这个疑问，因为它就像一个两步过程，我们不能直接将 (*head)->next 放在 head 里面的东西，我们需要传递地址的地址，因为我们需要一个额外的 block 什么时候循环会执行 n 次，而不是有 n 个中间 block ？请告诉我我是否正确并告诉正确的逻辑谢谢

void queue_push(Queue **head, int d, int p)
{
    Queue *q = queue_new(d, p);

    while (*head && (*head)->priority < p) {
        head = &(*head)->next;
    }

    q->next = *head;
    *head = q;
}

完整程序是

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

    typedef struct Queue Queue;

    struct Queue {
        int data;
        int priority;
        Queue *next;
    };

    Queue *queue_new(int d, int p)
    {
        Queue *n = malloc(sizeof(*n));

        n->data = d;
        n->priority = p;
        n->next = NULL;

        return n;
    }

    int queue_pop(Queue **head)
    {
        assert(*head);

        Queue *old = *head;
        int res = old->data;

        *head = (*head)->next;
        free(old);

        return res;
    }

    void queue_remove(Queue **head, int data)
    {
        while (*head && (*head)->data != data) {
            head = &(*head)->next;
        }

        if (*head) queue_pop(head);
    }

    void queue_push(Queue **head, int d, int p)
    {
        Queue *q = queue_new(d, p);

        while (*head && (*head)->priority < p) {
            head = &(*head)->next;
        }

        q->next = *head;
        *head = q;
    }


    int queue_empty(Queue *head)
    {
        return (head == NULL);
    }

    void queue_print(const Queue *q)
    {
        while (q) {
            printf("%d[%d] ", q->data, q->priority);
            q = q->next;
        }

        puts("$");
    }

    typedef struct Graph Graph;
    typedef struct Edge Edge;

    struct Edge {
        int vertex;
        int weight;
        Edge *next;
    };

    struct Graph {
        int v;
        Edge **edge;
        int *dist;
        int *path;
    };

    Graph *graph_new(int v)
    {
        Graph *G = malloc(sizeof(*G));

        G->v = v;
        G->edge = calloc(v, sizeof(*G->edge));
        G->dist = calloc(v, sizeof(*G->dist));
        G->path = calloc(v, sizeof(*G->path));

        return G;
    }

    void graph_delete(Graph *G)
    {
        if (G) {
            for (int i = 0; i < G->v; i++) {
                Edge *e = G->edge[i];

                while (e) {
                    Edge *old = e;

                    e = e->next;
                    free(old);
                }
            }

            free(G->edge);
            free(G->dist);
            free(G->path);
            free(G);
        }
    }

    Edge *edge_new(int vertex, int weight, Edge *next)
    {
        Edge *e = malloc(sizeof(*e));

        e->vertex = vertex;
        e->weight = weight;
        e->next = next;

        return e;
    }

    void graph_edge(Graph *G, int u, int v, int w)
    {
        G->edge[u] = edge_new(v, w, G->edge[u]);
        G->edge[v] = edge_new(u, w, G->edge[v]);
    }

    void dijkstra(const Graph *G, int s)
    {
        Queue *queue = NULL;

        for (int i = 0; i < G->v; i++) G->dist[i] = -1;
        G->dist[s] = 0;

        queue_push(&queue, s, 0);

        while (!queue_empty(queue)) {
            int v = queue_pop(&queue);
            Edge *e = G->edge[v];

            while (e) {
                int w = e->vertex;
                int d = G->dist[v] + e->weight;

                if (G->dist[w] == -1) {
                    G->dist[w] = d;
                    G->path[w] = v;

                    queue_push(&queue, w, d);
                }

                if (G->dist[w] > d) {
                    G->dist[w] = d;
                    G->path[w] = v;

                    queue_remove(&queue, w);
                    queue_push(&queue, w, d);
                }

                e = e->next;
            }
        }
    }

    int main()
    {
        int t;

        scanf("%d", &t);

        while (t--) {
            Graph *G;
            int v, e, s;

            scanf("%d %d", &v, &e);

            G = graph_new(v);

            for (int i = 0; i < e; i++) {
                int u, v, w;

                scanf("%d %d %d", &u, &v, &w);
                graph_edge(G, u - 1, v - 1, w);
            }

            scanf("%d", &s);
            dijkstra(G, s - 1);

            for (int i = 0; i < G->v; i++) {
                if (i != s - 1) {
                    printf("%d ", G->dist[i]);
                }
            }

            puts("");
            graph_delete(G);
        }

        return 0;
    }

Answer 1

queue_push() 未能正确插入新节点。

只有一个节点的.next被更新。通常有 2 个节点需要更新它们的 .next 成员。一个在原始列表中(在新节点位置之前)和一个新的。

---

我发现在列表 superhead 之前创建一个临时节点可以简化代码。

void queue_push(Queue **head, int d, int p) {
  Queue *q = queue_new(d, p);

  Queue superhead; // Only superhead.next member important.
  superhead.next = *head;  
  Queue *previous = &superhead;

  while (previous->next && previous->next->priority < p) {
    previous = previous->next;
  }

  q->next = previous->next;
  previous->next = q;
  *head = superhead.next;
}