数据结构实验报告十-教学计划编制问题

问题描述： 若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个教学计划编制程序，获取一个

问题描述： 若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的 先修关系（如果A课程是B课程的先修课程，那么A到B之间有一条有向边从A 指向B）。试设计一个教学计划编制程序，获取一个不冲突的线性的课程教学流 程。（课程线性排列，每门课上课时其先修课程已经被安排）。 基本要求： （1） 输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直 接先修课的课程号。 （2） 若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用 户指定的文件中。 一、 需求分析： 本程序需要基于图的基本操作来实现 二、概要设计 ： 抽象数据类型 ： 。 为实现上述功能需建立一个结点类，线性表类，图类 算法的基本思想 ： 1、图的构建： 建立一个结点类，类的元素有字符型变量用来存储字母，整形变量用来 存储位置，该类型的指针，指向下一个元素。建立一个线性表类，完成线性 表的构建。建立一个图类，完成图的信息的读取，（如有n个点，则建立n 个线性表，将每个结点与其指向的结点组成一个线性表，并记录线性表的长 度）。 2、Topsort算法： 先计算每个点的入度，保存在数组中。找到第一个入度为0的点，将该 点所连的各点的入度减一。再在这些点中找入度为0 的点。如果找到，重复 上述操作。如果找不到，则跳出while循环，再搜索其他的点，看入度是否 为0。再重复上述操作，如果所有的入度为0的点都被寻找到，但个数少于 输入顶点的个数，说明该图存在环。 程序的流程 程序由三个模块组成： 输入模块： 读入图的信息（顶点和边，用线性表进行存储）。 处理模块：topsort算法。 输出模块：将结果输出。 三、详细设计 算法的具体步骤：