用C语言编写程序实现拓扑排序:例如:C0是C2和C6的前序课程,而在选修C8之前,必须已经选修过C3和C7。要求存储该拓扑结构图,当用户从键盘输入任意课程的编号时,可打印出该课程的所有的先序课程。要求用户输入课程已经程序之间的指向关系,注意是先序而不是前驱课程。
时间: 2024-11-09 17:28:35 浏览: 21
在C语言中,我们可以使用邻接表数据结构来存储拓扑排序的问题。首先,我们需要定义一个结构体来表示课程,包含课程编号以及指向其他依赖课程的数组。然后,我们创建一个函数来读取用户的输入,并使用深度优先搜索(DFS)算法来执行拓扑排序。
```c
#include <stdio.h>
#include <stdlib.h>
// 定义课程结构体
typedef struct Course {
int id;
struct Course* prerequisites; // 存储课程依赖
} Course;
// 添加课程依赖
void add_dependency(Course** courses, int course_id, int dependency_id) {
Course* new_course = malloc(sizeof(struct Course));
new_course->id = course_id;
if (*courses[dependency_id] == NULL) {
*courses[dependency_id] = new_course;
} else {
Course* temp = *courses[dependency_id];
while (temp->prerequisites != NULL) {
temp = temp->prerequisites;
}
temp->prerequisites = new_course;
}
}
// 深度优先搜索进行拓扑排序
void topological_sort(Course** courses, int num_courses, void (*visit)(int)) {
for (int i = 0; i < num_courses; i++) {
if (courses[i] == NULL) {
continue;
}
visit(i);
for (Course* c = courses[i]; c != NULL; c = c->prerequisites) {
topological_sort(courses, num_courses, visit);
}
}
}
// 打印先序课程
void print_preorder(int id) {
printf("先序课程: %d ", id);
Course* course = courses[id];
while (course != NULL) {
printf("%d ", course->id);
course = course->prerequisites;
}
printf("\n");
}
int main() {
int num_courses, course_id, dependency_id;
printf("请输入课程总数:");
scanf("%d", &num_courses);
// 初始化课程数组
Course** courses = malloc(num_courses * sizeof(Course*));
for (int i = 0; i < num_courses; i++) {
courses[i] = NULL;
}
// 用户输入课程之间的依赖关系
printf("请输入每门课程及其依赖的课程编号(输入0结束):\n");
while (scanf("%d %d", &course_id, &dependency_id) == 2 && dependency_id != 0) {
add_dependency(courses, course_id, dependency_id - 1); // 减一转换为索引
}
// 拓扑排序并打印先序课程
topological_sort(courses, num_courses, print_preorder);
free(courses);
return 0;
}
```
当你运行这个程序时,它会提示你输入课程的数量以及它们之间的依赖关系。你可以按照题目描述的顺序输入课程和它们的先序课程。程序会在完成输入后对所有课程进行拓扑排序,并按顺序打印每个课程的先序课程。
阅读全文