怎样用C语言建立带权有向图的邻接表

建立带权有向图的邻接表可以使用结构体和指针来实现。具体步骤如下：

1. 定义结构体表示每个节点：

struct Node {
    int index; // 节点编号
    int weight; // 权重
    struct Node *next; // 指向下一个节点的指针
};

2. 定义一个指针数组，每个元素指向一个链表，该链表存储与对应节点相连的所有节点：

struct Node **graph;

3. 初始化指针数组，使每个元素都指向空链表：

int n = 10; // 节点数
graph = (struct Node **)malloc(n * sizeof(struct Node *));
for (int i = 0; i < n; i++) {
    graph[i] = NULL;
}

4. 添加一条边，比如从节点 1 到节点 2，权重为 3。首先创建一个新的节点，然后将其插入到节点 1 对应的链表中：

int u = 1, v = 2, w = 3; // u -> v，权重为 w
struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->index = v;
newNode->weight = w;
newNode->next = graph[u];
graph[u] = newNode;

5. 如果需要遍历节点 1 的邻居节点，可以通过遍历链表来实现：

struct Node *cur = graph[1];
while (cur != NULL) {
    printf("%d ", cur->index);
    cur = cur->next;
}

完整代码示例：

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

struct Node {
    int index;
    int weight;
    struct Node *next;
};

struct Node **graph;

void addEdge(int u, int v, int w) {
    struct Node *newNode = (struct Node *)malloc(sizeof(struct Node));
    newNode->index = v;
    newNode->weight = w;
    newNode->next = graph[u];
    graph[u] = newNode;
}

int main() {
    int n = 5;
    graph = (struct Node **)malloc(n * sizeof(struct Node *));
    for (int i = 0; i < n; i++) {
        graph[i] = NULL;
    }

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

    for (int i = 0; i < n; i++) {
        printf("Node %d: ", i);
        struct Node *cur = graph[i];
        while (cur != NULL) {
            printf("(%d, %d) ", cur->index, cur->weight);
            cur = cur->next;
        }
        printf("\n");
    }

    return 0;
}