数据结构与算法：用C语言实现基于邻接表存储有向图并用栈进行进行输入输出的拓扑排序

好的，以下是实现的步骤：

1. 首先定义有向图的邻接表结构体，包括每个节点的入度、出度及指向下一个节点的指针数组。

typedef struct node{
    int val; //顶点值
    int in_degree; //入度
    int out_degree; //出度
    struct node *next; //指向下一个节点的指针数组
}Node;

typedef struct graph{
    int v_num; //节点数目
    Node **adj_list; //邻接表
}Graph;

2. 定义栈结构体和相关操作函数，用于进行拓扑排序时的存储和输出。

typedef struct stack{
    int top;
    int *data;
}Stack;

Stack* create_stack(int size){
    Stack *s = (Stack*)malloc(sizeof(Stack));
    s->top = -1;
    s->data = (int*)malloc(sizeof(int)*size);
    return s;
}

void push(Stack *s, int val){
    s->data[++s->top] = val;
}

int pop(Stack *s){
    return s->data[s->top--];
}

int is_empty(Stack *s){
    return s->top == -1;
}

3. 实现有向图的创建函数，根据输入的节点数目和每个节点的出度建立邻接表。

Graph* create_graph(int v_num){
    Graph *g = (Graph*)malloc(sizeof(Graph));
    g->v_num = v_num;
    g->adj_list = (Node**)malloc(sizeof(Node*)*v_num);
    for(int i=0; i<v_num; i++){
        g->adj_list[i] = (Node*)malloc(sizeof(Node));
        g->adj_list[i]->val = i;
        g->adj_list[i]->in_degree = 0;
        g->adj_list[i]->out_degree = 0;
        g->adj_list[i]->next = NULL;
    }

    for(int i=0; i<v_num; i++){
        int out;
        printf("Enter out degree of vertex %d: ", i);
        scanf("%d", &out);
        for(int j=0; j<out; j++){
            int to;
            printf("Enter vertex pointed by vertex %d: ", i);
            scanf("%d", &to);

            Node* new_node = (Node*)malloc(sizeof(Node));
            new_node->val = to;
            new_node->in_degree++;
            new_node->next = g->adj_list[i]->next;
            g->adj_list[i]->next = new_node;
            g->adj_list[i]->out_degree++;
        }
    }

    return g;
}

4. 实现拓扑排序函数，依次遍历邻接表中的每个节点，将入度为0的节点入栈，然后将其指向的节点的入度减1，若其入度变为0，则入栈。直到栈为空。

void topological_sort(Graph *g){
    Stack *s = create_stack(g->v_num);
    for(int i=0; i<g->v_num; i++){
        if(g->adj_list[i]->in_degree == 0){
            push(s, i);
        }
    }

    while(!is_empty(s)){
        int node = pop(s);
        printf("%d ", node);
        Node *p = g->adj_list[node]->next;
        while(p){
            if(--g->adj_list[p->val]->in_degree == 0){
                push(s, p->val);
            }
            p = p->next;
        }
    }
}

5. 在主函数中调用以上函数进行测试。

int main(){
    int v_num;
    printf("Enter number of vertices in graph: ");
    scanf("%d", &v_num);

    Graph *g = create_graph(v_num);
    printf("Topological order of graph: ");
    topological_sort(g);

    return 0;
}

完整代码如下：