主页 / user-15412365

VIAGC's questions

Martin Hope
VIAGC
Asked: 2023-08-27 14:18:10 +0800 CST
  • 10

我正在遵循 Skiena 的算法设计手册 v3。

我看到有几个问题说书中有某些错别字，我不确定这是一个还是只是因为我看不懂。

考虑以下：

typedef struct edgenode {
    int y;                   /* adjacency info */
    int weight;              /* edge weight, if any */
    struct edgenode *next;   /* next edge in list */
} edgenode;

typedef struct {
    edgenode *edges[MAXV+1];  /* adjacency info */
    int degree[MAXV+1];       /* outdegree of each vertex */
    int nvertices;            /* number of vertices in the graph */
    int nedges;               /* number of edges in the graph */
    int directed;             /* is the graph directed? */
} graph;

void insert_edge(graph *g, int x, int y, bool directed) {
    edgenode *p;        /* temporary pointer */

    p = malloc(sizeof(edgenode));    /* allocate edgenode storage */

    p->weight = 0;
    p->y = y;
    p->next = g->edges[x];

    g->edges[x] = p;    /* insert at head of list */

    g->degree[x]++;

    if (!directed) {
        insert_edge(g, y, x, true);
    } else {
        g->nedges++;
    }
}

据我了解，void insert_edge(graph *g, int x, int y, bool directed)连接数组索引处的两个节点x并将y它们添加到edges数组中。

以下片段让我感到困惑：

p->y = y;
p->next = g->edges[x];

g->edges[x] = p;    /* insert at head of list */

这是如何运作的？假设我的输入是x = 3, y = 4，这是第一个输入。

我期望有3 -> 4向图之类的东西。

  1. p->y = y;非常有道理， 的相邻项x是y。
  2. p->next = g->edges[x];但edges数组被初始化为 null。这不会3.next == NULL代替吗3.next == 4？
  3. g->edges[x] = p;什么？edges[x] == x Node，这让我很困惑。

完整的代码可以在graph.c和graph.h中找到。

我认为p.next = y;不知何故，y.next = NULL到目前为止，即第一个插入。也许是我的 C 生锈了，但需要一些帮助。

c