C语言 难以理解使用链表的图形实现

Question

我正在阅读一本关于Algorithms的书，其中包含以下代码。我很难理解这里的一些台词。

我在以下代码中my doubt lines显示为DOUBT LINE 1和DOUBT LINE 2。我还评论了一行REFERENCE我having difficulty理解的地方。请详细说明DOUBT LINE 1和DOUBT LINE 2。

#define MAXV        100     /* maximum number of vertices */
#define NULL        0       /* null pointer */
/*  DFS edge types      */
#define TREE        0       /* tree edge */
#define BACK        1       /* back edge */
#define CROSS       2       /* cross edge */
#define FORWARD     3       /* forward edge */
typedef struct edgenode {
    int y;              /* adjancency info */
    int weight;         /* edge weight, if any */
    struct edgenode *next;      /* next edge in list */
} edgenode;
typedef struct {
    edgenode *edges[MAXV+1];    /* adjacency info */       //REFERENCE 
    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;

它是 graph.h 标头，在那里它也是读取和插入函数。

read_graph(graph *g, bool directed)
{
    int i;              /* counter */
    int m;              /* number of edges */
    int x, y;           /* vertices in edge (x,y) */
    initialize_graph(g, directed);
    scanf("%d %d",&(g->nvertices),&m);
    for (i=1; i<=m; i++) {
        scanf("%d %d",&x,&y);
        insert_edge(g,x,y,directed);
    }
}
insert_edge(graph *g, int x, int y, bool directed)
{
    edgenode *p;            /* temporary pointer */
    p = malloc(sizeof(edgenode));   /* allocate storage for edgenode */
    p->weight = NULL;
    p->y = y;
    p->next = g->edges[x]; //DOUBT LINE1
    g->edges[x] = p;        /* insert at head of list */ //DOUBT LINE 2
    g->degree[x] ++;        
    if (directed == FALSE)
        insert_edge(g,y,x,TRUE);
    else
        g->nedges ++;
}

Answer 1

每个顶点都包含一组边。 我们可以将集合视为无序的。 在突变器函数之外的任何时候，指针g->edges[i]指向第 i 个顶点上的第一个edgenode事件，否则NULL。 然后，edgenode中的next链接以传递方式指向集合中的其他边。

因此，要添加边，首先创建一个新边，然后将其next指针分配给当前"第一个"节点（疑点行 1），然后为g->edges[i]指针分配新创建的值（疑点行 2）。

请注意，我上面所说的需要存在的条件仍然满足，尽管节点的顺序发生了变化 - "以前"首先是现在第二，新节点是第一个。 没关系，因为我们只是存储一个集合 - 顺序无关紧要。

之前（=>遍历"下一个"链接）：

   // edges[i] == <previous> => <other stuff>...

后：

   //         *             *    These asterisks are above what we set...
   //edges[i] == <new node> => <previous> => <other stuff>

Answer 2

链表表示next是指向以下节点的指针。例：

a {some_data,pointer_to_b}
b {some_data,pointer_to_c}如果要插入节点，必须将前一个节点的指针更改为新节点next并将新节点的next指向下一个节点的地址的指针设置。例：

a {some_data,pointer_to_d/*what is done at doubt line 1*/} d {some_data,pointer_to_b}//插入节点在疑问行 2
处执行的操作 b {some_data,pointer_to_c}

Answer 3

让我们剖析一下，以便您清楚地了解所有内容。

图形的结构

1o-->2o-->#
2o-->3o-->#
3o-->#
4o-->#
5o--.#

这里

 `1o`: The node 1
 `-->`: It denotes a directed edge.
 `#`: denotes `NULL`

现在让我们添加2-->4权重 = 5 的边

步骤1：p = malloc(sizeof(edgenode));

p-------->[ ]   ( This is the allocated node)

步骤2：p->weight = NULL;//应该是边缘的重量 p->y = y;

| wieght = 5 |
| y = 4      |
| next       |

步骤3：p->next = g->edges[x]; g->edges[2] 是指向3o的指针

| wieght = w |
| y = 4      |
| next =------------>3o

现在图片是

1o-->2o--->#
p[]--+
     |
     V
2o-->3o--->#
3o-->#
4o-->#
5o--.#

步骤4：g->edges[2]=p g->edges[2]基本上是2o

1o-->2o--->#
2o-->[] --> 3o--->#
3o-->#
4o-->#
5o-->#

只是

1o-->2o--->#
2o-->4o--->3o--->#
3o-->#
4o-->#
5o-->#

解释：

基本上在这里我们维护一个列表，对于每个节点 x，我们放置 y ， z，如果有边 x->y 和 x->z .

如果我们查看实现，我们将看到节点被添加到前面。

例如。。如果我们添加x->y那么边缘列表将如下所示

x---->y

现在添加 z。

x---->z---->y

就这样。。。一个友好的提示，当你没有得到代码时，得到一支铅笔和纸尝试试运行或它，或者有时只是运行调试器。