c语言 有向图创建邻接表

C语言是一种面向过程的编程语言，它是一种通用的高级程序设计语言，由Dennis Ritchie于1972年在贝尔实验室开发。C语言是系统编程语言的首选，因为它允许直接访问内存地址和硬件寄存器，可以实现高效的操作系统、网络和驱动程序等。

邻接表是一种常见的图的表示方法，它用一个数组和若干链表来表示一个有向图。具体地说，数组的每个元素表示一个顶点，该元素指向一个链表，链表中存储了该顶点所指向的所有顶点。

创建邻接表的步骤如下：
1. 定义一个结构体来表示链表节点，其中包含一个指向下一个节点的指针和一个表示该节点所连接的顶点的编号。
2. 定义一个结构体来表示整个邻接表，其中包含一个数组和一个表示图中顶点数的整数。
3. 初始化邻接表，即为每个顶点创建一个链表头节点。
4. 遍历有向图中每条边，将每条边的起点添加到对应终点的链表中。

以下是一个C语言示例代码，用于创建邻接表：

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

// 定义链表节点结构体
struct ListNode {
    int vertex;             // 该节点所连接的顶点编号
    struct ListNode* next;  // 指向下一个节点的指针
};

// 定义邻接表结构体
struct AdjList {
    int numVertices;        // 图中顶点数
    struct ListNode** adjLists; // 指向链表头节点数组的指针
};

// 创建链表节点
struct ListNode* createNode(int v) {
    struct ListNode* newNode = malloc(sizeof(struct ListNode));
    newNode->vertex = v;
    newNode->next = NULL;
    return newNode;
}

// 创建邻接表
struct AdjList* createAdjList(int vertices) {
    struct AdjList* adjList = malloc(sizeof(struct AdjList));
    adjList->numVertices = vertices;
    adjList->adjLists = malloc(vertices * sizeof(struct ListNode*));

    for (int i = 0; i < vertices; i++) {
        adjList->adjLists[i] = NULL;    // 初始化链表头节点为NULL
    }

    return adjList;
}

// 添加边到邻接表中
void addEdge(struct AdjList* adjList, int src, int dest) {
    // 添加到src顶点的链表中
    struct ListNode* newNode = createNode(dest);
    newNode->next = adjList->adjLists[src];
    adjList->adjLists[src] = newNode;
}

// 打印邻接表
void printAdjList(struct AdjList* adjList) {
    for (int i = 0; i < adjList->numVertices; i++) {
        printf("顶点 %d 的邻接表：\n", i);
        struct ListNode* temp = adjList->adjLists[i];
        while (temp) {
            printf("%d -> ", temp->vertex);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int vertices, edges;
    printf("请输入图中顶点数和边数：");
    scanf("%d %d", &vertices, &edges);

    struct AdjList* adjList = createAdjList(vertices);

    printf("请输入%d条有向边（起点和终点编号）：\n", edges);
    for (int i = 0; i < edges; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(adjList, src, dest);
    }

    printAdjList(adjList);

    return 0;
}