用c语言写一个完整的用邻接表存储的拓扑排序

在C语言中，我们可以使用邻接表（Adjacency List）来表示图的数据结构，然后通过拓扑排序算法对有向无环图（DAG，Directed Acyclic Graph）进行排序。以下是一个简单的例子，展示了如何实现这个过程：

首先，我们定义一个节点结构体（Node）和一个链表结点结构体（Edge），用于表示邻接列表：

typedef struct Node {
    int data;
    struct Edge* next; // 指向下一个节点
} Node;

typedef struct Edge {
    Node* node;
    struct Edge* next; // 链表中的下一个边
} Edge;

接下来，我们需要创建邻接表并添加边：

void add_edge(Node** head, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = dest;
    newNode->next = NULL;

    if (*head == NULL) {
        *head = newNode;
    } else {
        Node* temp = *head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

接着，我们编写拓扑排序的函数，这里使用了深度优先搜索（DFS）辅助判断是否有环：

int* topological_sort(Node* head, int n) {
    int count = 0;
    stack<Node*> s;
    Node* temp = head;
    
    while (temp != NULL) {
        if (temp->visited == false) {
            dfs(temp, &s, &count);
        }
        temp = temp->next;
    }

    int* result = (int*)malloc(count * sizeof(int));
    int index = 0;
    while (!s.empty()) {
        result[index++] = s.top()->data;
        s.pop();
    }

    return result;
}

void dfs(Node* node, stack<Node*>* s, int* count) {
    node->visited = true;
    Node* temp = node->next;

    while (temp != NULL) {
        if (temp->visited == false) {
            dfs(temp, s, count);
        }
        temp = temp->next;
    }
    s->push(node);
}

最后，主函数调用上述函数并处理结果：

int main() {
    // 初始化图和边
    Node* head = NULL;
    // 添加边...
    
    int n = ...; // 图的节点数
    int* sortedOrder = topological_sort(head, n);

    printf("Topological sort: ");
    for (int i = 0; i < n; ++i) {
        printf("%d ", sortedOrder[i]);
    }
    free(sortedOrder);
    return 0;
}