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

拓扑排序是对有向无环图(DAG)的所有节点进行排序，使得对于每一条有向边(u,v)，在排序后的节点序列中，节点u都排在节点v的前面。下面是用C语言实现基于邻接表存储有向图的拓扑排序的代码：

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

#define MAXV 1000  // 最大顶点数

typedef struct node{
    int v;  // 存储的顶点
    struct node *next;  // 指向下一个节点的指针
}node;

node *G[MAXV];  // 存储图的邻接表
int inDegree[MAXV];  // 存储各个顶点的入度
int V, E;  // 顶点数和边数

// 向邻接表中添加一条边
void addEdge(int u, int v){
    node *newNode = (node*)malloc(sizeof(node));
    newNode->v = v;
    newNode->next = G[u];
    G[u] = newNode;
}

// 用拓扑排序对DAG进行排序
void topologicalSort(){
    int i, j;
    int queue[MAXV], front = 0, rear = -1;  // 队列实现
    int cnt = 0;  // 记录已经输出的顶点数

    // 将入度为0的顶点入队
    for(i = 0; i < V; i++){
        if(inDegree[i] == 0){
            queue[++rear] = i;
        }
    }

    while(front <= rear){
        int u = queue[front++];  // 取出队首元素
        printf("%d ", u);
        cnt++;

        // 将所有u指向的顶点的入度减1
        for(node *p = G[u]; p != NULL; p = p->next){
            int v = p->v;
            inDegree[v]--;
            // 如果v的入度为0，将v入队
            if(inDegree[v] == 0){
                queue[++rear] = v;
            }
        }
    }

    // 如果输出的顶点数小于V，说明图中有环
    if(cnt < V){
        printf("Error: Graph contains cycle!\n");
    }
}

int main(){
    int i, u, v;

    scanf("%d%d", &V, &E);  // 输入顶点数和边数

    // 初始化邻接表和入度数组
    for(i = 0; i < V; i++){
        G[i] = NULL;
        inDegree[i] = 0;
    }

    // 读入边，建立邻接表和入度数组
    for(i = 0; i < E; i++){
        scanf("%d%d", &u, &v);
        addEdge(u, v);
        inDegree[v]++;
    }

    topologicalSort();  // 拓扑排序

    return 0;
}

在这个程序中，我们使用了邻接表存储图，并且记录了每个顶点的入度。在拓扑排序时，我们使用了队列实现。我们先将入度为0的顶点入队，然后不断从队列中取出元素，输出该元素，并将所有该元素指向的顶点的入度减1。如果减1后该顶点的入度变为0，就将该顶点入队。当队列为空时，如果输出的顶点数小于总顶点数，说明图中存在环。