邻接表创建头插法C语言详细注释

当我们需要存储一个图时，邻接表是一种常用的数据结构。在邻接表中，每个节点代表图中的一个顶点，每个节点包含一个指向该顶点的指针和一个指向与该顶点相邻的所有顶点的指针。邻接表的实现方法有多种，其中头插法是比较常用的一种。下面是关于头插法的C语言代码及其详细注释：

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

#define MAXVEX 100  // 定义图的最大顶点数

// 边表节点结构体
typedef struct EdgeNode {
    int adjvex;  // 邻接点域，存储该顶点对应的下标
    int weight;  // 权值
    struct EdgeNode *next;  // 链域，指向下一个邻接点
} EdgeNode;

// 顶点表结构体
typedef struct VertexNode {
    char data;  // 顶点域，存储顶点信息
    EdgeNode *firstedge;  // 边表头指针
} VertexNode, AdjList[MAXVEX];

// 图结构体
typedef struct {
    AdjList adjList;  // 邻接表
    int numVertexes;  // 图中当前顶点数
    int numEdges;  // 图中当前边数
} GraphAdjList;

// 创建邻接表，采用头插法
void CreateALGraph(GraphAdjList *G) {
    int i, j, k;
    EdgeNode *e;

    printf("请输入顶点数和边数：\n");
    scanf("%d %d", &(G->numVertexes), &(G->numEdges));

    // 读入顶点信息，建立顶点表
    for (i = 0; i < G->numVertexes; i++) {
        printf("请输入第%d个顶点的信息：", i+1);
        scanf(" %c", &(G->adjList[i].data));
        G->adjList[i].firstedge = NULL;  // 将边表置为空表
    }

    // 建立边表
    for (k = 0; k < G->numEdges; k++) {
        printf("请输入边(vi, vj)的下标i, j和权值：\n");
        scanf("%d %d %d", &i, &j, &(e->weight));

        // 生成边表节点e1和e2
        e = (EdgeNode *) malloc(sizeof(EdgeNode));
        e->adjvex = j;
        e->next = G->adjList[i].firstedge;
        G->adjList[i].firstedge = e;

        e = (EdgeNode *) malloc(sizeof(EdgeNode));
        e->adjvex = i;
        e->next = G->adjList[j].firstedge;
        G->adjList[j].firstedge = e;
    }
}

int main() {
    GraphAdjList G;
    CreateALGraph(&G);
    return 0;
}

在上述代码中，我们定义了边表节点结构体EdgeNode，顶点表结构体VertexNode和邻接表结构体GraphAdjList。CreateALGraph函数用于创建邻接表。在该函数中，我们首先读入顶点信息，建立顶点表；然后读入边的信息，依次生成边表节点e1和e2，并采用头插法将它们插入到相应的邻接表中。需要注意的是，由于头插法是将新节点插入到链表的头部，因此在插入新节点之前需要先将该顶点原本的邻接点整体往后移一位。