邻接表生成逆邻接表用C语言实现

下面是一个使用C语言实现邻接表生成逆邻接表的示例代码：

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

#define MAX_NODE_NUM 100  // 最大节点数

// 邻接表节点结构体
typedef struct AdjListNode {
    int dest;  // 邻接节点编号
    struct AdjListNode* next;  // 指向下一个邻接节点的指针
} AdjListNode;

// 邻接表结构体
typedef struct AdjList {
    AdjListNode* head;  // 邻接表头指针
} AdjList;

// 图结构体
typedef struct Graph {
    int num_vertices;  // 节点数
    AdjList* adj_lists;  // 邻接表数组
} Graph;

// 创建邻接节点
AdjListNode* createAdjListNode(int dest) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    newNode->dest = dest;
    newNode->next = NULL;
    return newNode;
}

// 创建图
Graph* createGraph(int num_vertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->num_vertices = num_vertices;
    graph->adj_lists = (AdjList*)malloc(num_vertices * sizeof(AdjList));
    for (int i = 0; i < num_vertices; i++) {
        graph->adj_lists[i].head = NULL;
    }
    return graph;
}

// 添加边
void addEdge(Graph* graph, int src, int dest) {
    AdjListNode* newNode = createAdjListNode(dest);
    newNode->next = graph->adj_lists[src].head;
    graph->adj_lists[src].head = newNode;
}

// 生成逆邻接表
Graph* getReverseGraph(Graph* graph) {
    Graph* reverseGraph = createGraph(graph->num_vertices);
    for (int i = 0; i < graph->num_vertices; i++) {
        AdjListNode* curr = graph->adj_lists[i].head;
        while (curr != NULL) {
            addEdge(reverseGraph, curr->dest, i);
            curr = curr->next;
        }
    }
    return reverseGraph;
}

// 打印邻接表
void printGraph(Graph* graph) {
    for (int i = 0; i < graph->num_vertices; i++) {
        AdjListNode* curr = graph->adj_lists[i].head;
        printf("节点 %d 的邻接节点：", i);
        while (curr != NULL) {
            printf("%d ", curr->dest);
            curr = curr->next;
        }
        printf("\n");
    }
}

int main() {
    Graph* graph = createGraph(5);
    addEdge(graph, 0, 1);
    addEdge(graph, 0, 2);
    addEdge(graph, 1, 3);
    addEdge(graph, 2, 3);
    addEdge(graph, 3, 4);
    printGraph(graph);
    Graph* reverseGraph = getReverseGraph(graph);
    printf("逆邻接表：\n");
    printGraph(reverseGraph);
    return 0;
}

在上面的示例代码中，我们首先定义了邻接表节点结构体和邻接表结构体，并使用它们创建了一个图结构体。接着，我们实现了创建邻接节点、创建图、添加边、打印邻接表等相关函数，其中 `addEdge` 函数用于向图中添加边，`getReverseGraph` 函数用于生成逆邻接表。

最后，在 `main` 函数中，我们创建了一个包含 5 个节点的图，并向其中添加边。然后，我们打印出图的邻接表，并生成其对应的逆邻接表并打印出来。