编程实现邻接表生成逆邻接表，用c语言实现

以下是用 C 语言实现邻接表生成逆邻接表的代码：

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

// 定义邻接表结构体
typedef struct node {
    int vertex;             // 存储顶点号
    struct node* next;      // 指向下一个邻接点
} Node;

// 定义邻接表头结点结构体
typedef struct {
    Node* head;             // 指向第一个邻接点
} HeadNode;

// 定义邻接表结构体
typedef struct {
    int num_vertices;       // 顶点数
    HeadNode* array;        // 存储邻接表头结点数组
} AdjList;

// 创建新的邻接表头结点
HeadNode* newHeadNode() {
    HeadNode* new_head = (HeadNode*) malloc(sizeof(HeadNode));
    new_head->head = NULL;
    return new_head;
}

// 创建新的邻接点
Node* newNode(int vertex) {
    Node* new_node = (Node*) malloc(sizeof(Node));
    new_node->vertex = vertex;
    new_node->next = NULL;
    return new_node;
}

// 添加边
void addEdge(AdjList* adj_list, int src, int dest) {
    Node* new_node = newNode(dest);
    new_node->next = adj_list->array[src].head;
    adj_list->array[src].head = new_node;
}

// 邻接表生成逆邻接表
AdjList* reverseGraph(AdjList* adj_list) {
    AdjList* rev_adj_list = (AdjList*) malloc(sizeof(AdjList));
    rev_adj_list->num_vertices = adj_list->num_vertices;
    rev_adj_list->array = (HeadNode*) malloc((adj_list->num_vertices + 1) * sizeof(HeadNode));

    int i;
    for (i = 1; i <= adj_list->num_vertices; i++) {
        rev_adj_list->array[i].head = NULL;
    }

    for (i = 1; i <= adj_list->num_vertices; i++) {
        Node* tmp = adj_list->array[i].head;
        while (tmp != NULL) {
            addEdge(rev_adj_list, tmp->vertex, i);
            tmp = tmp->next;
        }
    }

    return rev_adj_list;
}

// 主函数
int main() {
    int num_vertices = 5;
    AdjList* adj_list = (AdjList*) malloc(sizeof(AdjList));
    adj_list->num_vertices = num_vertices;
    adj_list->array = (HeadNode*) malloc((num_vertices + 1) * sizeof(HeadNode));

    int i;
    for (i = 1; i <= num_vertices; i++) {
        adj_list->array[i].head = NULL;
    }

    addEdge(adj_list, 1, 2);
    addEdge(adj_list, 1, 4);
    addEdge(adj_list, 2, 3);
    addEdge(adj_list, 2, 5);
    addEdge(adj_list, 3, 1);
    addEdge(adj_list, 3, 4);

    AdjList* rev_adj_list = reverseGraph(adj_list);

    for (i = 1; i <= rev_adj_list->num_vertices; i++) {
        printf("Vertex %d: ", i);
        Node* tmp = rev_adj_list->array[i].head;
        while (tmp != NULL) {
            printf("%d ", tmp->vertex);
            tmp = tmp->next;
        }
        printf("\n");
    }

    return 0;
}

这个程序定义了邻接表结构体 `AdjList`，其中包含了顶点数和一个邻接表头结点数组。邻接表头结点结构体 `HeadNode` 包含了指向第一个邻接点的指针。邻接点结构体 `Node` 包含了存储顶点号和指向下一个邻接点的指针。

程序中的 `newHeadNode()` 和 `newNode()` 函数分别用于创建新的邻接表头结点和新的邻接点。`addEdge()` 函数用于添加边。`reverseGraph()` 函数用于生成逆邻接表。

在主函数中，我们首先创建了一个邻接表，然后调用 `reverseGraph()` 函数生成逆邻接表。最后，我们遍历逆邻接表并输出结果。