10.教学计划安排问题

#include <stdio.h>
#include <stdlib.h>
#define MAX_COURSES 100
// 定义课程节点结构
typedef struct Course {
    int id;
    char name[50];
    int prereq_count;
    int prereq[MAX_COURSES];
    int visited; // 用于检测回路
} Course;
Course courses[MAX_COURSES];
int courses_count = 0;
// 添加课程
void addCourse(char* name, int prereq_count, int prereq[]) {
    Course new_course;
    new_course.id = courses_count;
    strcpy(new_course.name, name);
    new_course.prereq_count = prereq_count;
    for (int i = 0; i < prereq_count; i++) {
        new_course.prereq[i] = prereq[i];
    }
    new_course.visited = 0;
    courses[courses_count++] = new_course;
}
// 检测是否存在回路
int hasCycle(int course_id) {
    if (courses[course_id].visited == 1) {
        return 1; // 存在回路
    }
    if (courses[course_id].visited == 2) {
        return 0; // 已经检查过，无回路
    }
    courses[course_id].visited = 1; // 标记为正在访问
    for (int i = 0; i < courses[course_id].prereq_count; i++) {
        if (hasCycle(courses[course_id].prereq[i])) {
            return 1; // 存在回路
        }
    }
    courses[course_id].visited = 2; // 标记为已访问
    return 0; // 无回路
}
// 拓扑排序
void topologicalSort() {
    int indegree[MAX_COURSES] = { 0 };
    for (int i = 0; i < courses_count; i++) {
        for (int j = 0; j < courses[i].prereq_count; j++) {
            indegree[courses[i].prereq[j]]++;
        }
    }
    printf("教学计划:\n");
    for (int i = 0; i < courses_count; i++) {
        int j;
        for (j = 0; j < courses_count; j++) {
            if (indegree[j] == 0) {
                printf("%s\n", courses[j].name);
                indegree[j] = -1;
                for (int k = 0; k < courses[j].prereq_count; k++) {
                    indegree[courses[j].prereq[k]]--;
                }
                break;
            }
        }
        if (j == courses_count) {
            printf("错误：在课程先决条件中检测到循环。\n");
            return;
        }
    }
}
int main() {
    // 输入课程信息
    addCourse("C语言程序设计", 0, NULL);
    addCourse("离散数学", 0, NULL);
    addCourse("数据结构", 2, (int[]) { 0, 1 });
    // 检测是否存在回路
    for (int i = 0; i < courses_count; i++) {
        if (hasCycle(i)) {
            printf("错误：在课程先决条件中检测到循环。\n");
            return 0;
        }
    }
    // 执行拓扑排序并输出教学计划
    topologicalSort();
    return 0;
}