数据结构用队列实现拓扑排序、逆拓扑排序C语言代码

以下使用队列实现拓扑排序和逆拓扑排序的示例代码（C语言）：

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

#define MAX_VERTICES 100

typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct Graph {
    int numVertices;
    int* indegree;
    Node** adjLists;
} Graph;

typedef struct Queue {
    int front;
    int rear;
    int size;
    int capacity;
    int* elements;
} Queue;

Graph* createGraph(int numVertices) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->numVertices = numVertices;

    graph->indegree = (int*)malloc(numVertices * sizeof(int));
    for (int i = 0; i < numVertices; i++) {
        graph->indegree[i] = 0;
    }

    graph->adjLists = (Node**)malloc(numVertices * sizeof(Node*));
    for (int i = 0; i < numVertices; i++) {
        graph->adjLists[i] = NULL;
    }

    return graph;
}

void addEdge(Graph* graph, int src, int dest) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->vertex = dest;
    newNode->next = graph->adjLists[src];
    graph->adjLists[src] = newNode;

    graph->indegree[dest]++;
}

Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->front = 0;
    queue->rear = -1;
    queue->size = 0;
    queue->capacity = capacity;
    queue->elements = (int*)malloc(capacity * sizeof(int));
    
    return queue;
}

int isEmpty(Queue* queue) {
    return queue->size == 0;
}

int isFull(Queue* queue) {
    return queue->size == queue->capacity;
}

void enqueue(Queue* queue, int item) {
    if (isFull(queue)) {
        printf("Queue is full.\n");
        return;
    }
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->elements[queue->rear] = item;
    queue->size++;
}

int dequeue(Queue* queue) {
    if (isEmpty(queue)) {
        printf("Queue is empty.\n");
        return -1;
    }
    int item = queue->elements[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size--;

    return item;
}

void topologicalSort(Graph* graph) {
    int* result = (int*)malloc(graph->numVertices * sizeof(int));
    int index = 0;

    Queue* queue = createQueue(graph->numVertices);

    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->indegree[i] == 0) {
            enqueue(queue, i);
        }
    }

    while (!isEmpty(queue)) {
        int vertex = dequeue(queue);
        result[index++] = vertex;

        Node* temp = graph->adjLists[vertex];
        while (temp != NULL) {
            int adjVertex = temp->vertex;
            graph->indegree[adjVertex]--;
            if (graph->indegree[adjVertex] == 0) {
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }

    if (index != graph->numVertices) {
        printf("Graph contains a cycle, topological sorting not possible.\n");
        return;
    }

    printf("Topological Sort: ");
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(result);
}

void reverseTopologicalSort(Graph* graph) {
    int* result = (int*)malloc(graph->numVertices * sizeof(int));
    int index = graph->numVertices - 1;

    Queue* queue = createQueue(graph->numVertices);

    for (int i = 0; i < graph->numVertices; i++) {
        if (graph->indegree[i] == 0) {
            enqueue(queue, i);
        }
    }

    while (!isEmpty(queue)) {
        int vertex = dequeue(queue);
        result[index--] = vertex;

        Node* temp = graph->adjLists[vertex];
        while (temp != NULL) {
            int adjVertex = temp->vertex;
            graph->indegree[adjVertex]--;
            if (graph->indegree[adjVertex] == 0) {
                enqueue(queue, adjVertex);
            }
            temp = temp->next;
        }
    }

    if (index != -1) {
        printf("Graph contains a cycle, reverse topological sorting not possible.\n");
        return;
    }

    printf("Reverse Topological Sort: ");
    for (int i = 0; i < graph->numVertices; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(result);
}

int main() {
    int numVertices, numEdges;
    printf("Enter the number of vertices and edges: ");
    scanf("%d %d", &numVertices, &numEdges);

    Graph* graph = createGraph(numVertices);

    printf("Enter the edges (source vertex and destination vertex):\n");
    for (int i = 0; i < numEdges; i++) {
        int src, dest;
        scanf("%d %d", &src, &dest);
        addEdge(graph, src, dest);
    }

    topologicalSort(graph);
    reverseTopologicalSort(graph);

    return 0;
}

在这段代码中，我们首先定义了 `Node` 结构体表示图的顶点，并使用邻接表的形式存储图的边关系。然后定义了 `Graph` 结构体表示图的基本属性，包括顶点个数、入度数组和邻接表数组。接下来，定义了 `Queue` 结构体表示队列，并实现了相关的队列操作函数。最后，实现了拓扑排序和逆拓扑排序的函数，并在 `main` 函数中进行测试。

希望这段代码对你有帮助！如果还有其他问题，请随时提问。