我正在遵循 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向图之类的东西。
p->y = y;非常有道理， 的相邻项x是y。p->next = g->edges[x];但edges数组被初始化为 null。这不会3.next == NULL代替吗3.next == 4？g->edges[x] = p;什么？edges[x] == x Node，这让我很困惑。
我认为p.next = y;不知何故，y.next = NULL到目前为止，即第一个插入。也许是我的 C 生锈了，但需要一些帮助。
我不会将此称为“添加到
edges数组”，因为edges数组具有固定长度，并且每个节点都有一个条目（而不是每个边）。的索引
edges标识一条边的“起始”顶点，而yan 的字段edgenode标识该同一边的相应“至”顶点。对于每个顶点
x，此代码维护一个边链接列表（不是edges，而是edges[x]），该列表最初为空。让我们对示例图执行此操作：
...初始化后，其边缘填充如下：
让我们看看它是如何填充
graph数据结构的。我们从这个状态开始g（我假设MAXV这个表示是 4）：连字符代表
nullpointer值。我假设所有这些都已正确初始化。然后
insert_edge(g, 0, 1, true)将创建一个p节点，该节点的分配和初始化如下：值得注意的是该
next字段是nullptr，因为这是在 处找到的值g->edges[0]。然后下一条语句
g->edges[x] = p进行链接，并且在两个计数器递增后，该函数完成其工作：现在我们来看看更有趣的一个：
insert_edge(g, 0, 2, true);。再次p是指向一个新的edgenode，但是这次g->edges[0]不是nullptr，所以p->next会指向先前添加的edgenode。完成后insert_edge我们得到这个：对于其他边也是如此：每次将新边
edgenode添加到链表之前，该链表的头指针存储在数组中edges。我们有 5 个链表：每个顶点一个。这是上面示例的最终结果：
希望这能澄清这一点。