[问题描述]
大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
[基本要求]
(1) 输入参数：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。
(2) 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
(3) 若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
[实现提醒]
可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。同时还应建立课程号与课程号之间的对应关系。
[测试数据]
学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3，先修关系如下图。
图13 课程先修关系
一、逻辑结构设计
利用课程之间存在先修关系，让所有的课程形成一个AOV网，各门课程看作AOV网的节点，满足课程之间的先修关系，利用图的拓扑排序来进行学期之间的课程排序安排，并按照每学期的课程学分和学习负担来输出。
二、存储结构设计
课程采用数组的方式存储方式，通过栈从AOV网当中去获取，最后通过动态的数组存储输出，AOV网的存储方式为邻接表的方式。
三、设计思路
四、主要操作设计
类图：
1.Course类，作为课程类，存放和获取课程的名字和学分。
2.ArcNode类,主要是图邻接表中边的结点类，有指向下一条边的指针域和下一个结点的位置。
3.Vnode类，主要图中点的结点类，有入度域，数据域，指针域，指向第一条边的相邻顶点。
4.Graph类，调用Vnode类建立邻接表adjList，locateVex()方法用来获取AOV网中顶点的位置，creatAdj()方法用来创建AOV网，creatConverse()方法创建反向的AOV网，用来后面Test类调用输出课程之间的先修关系。
5.Stack类，重写栈，调用Course类建立数组stackArray来存储课程信息，并将栈定指针top=-1。重写其中的push()入栈和pop()出栈方法。
6.Test类，print()方法通过对AOV网中邻接表的遍历，将其课程信息存放到栈中，再调用前面创建的反向AOV网的邻接表来输出课程的先修关系。最后在main函数里面调用该方法输出课程之间的信息关系。topSort1()方法用来判断课程能否顺利学完，若能，输出一个正确的学习顺序通过对邻接表的遍历，将其中入度为0的点压入栈中，当栈中不是空的时候，就出栈并输出一个元素，然后更新与顶点的邻接点的入度使其为0，接着重复上面的操作。当其中出栈的元素数量小于顶点表的长度使就表示有环路产生，不能学完所有课程。topSort2()方法用来实现使课程尽可能的集中在前几个学期中排课，topSort3()方法用来实现使学生在各学期中的学习负担尽量均匀排课
五、技术难点与解决方法
①怎样通过拓扑排序实现将课程尽可能集中在前几学期的教学。
解决方法：通过对AOV网邻接表的遍历，将入度为0的元素入栈，当栈不为空时，就出栈，并将出栈的元素存放到链表当中，不断重复这样的操作，直到遍历完毕，接着将链表当中课程的名字和学分分别存放到两个动态的数组，在通过for循环遍历，满足每学期的课程的学分之和不超过其上限，当剩下的课程和剩下的学期数相等时就结束循环。再创建两个数组分别存储课程名字和学分通过for循环遍历将每学期的课程不超过其学分上限存储后，最后输出剩下学期的课程。
②怎样通过拓扑排序实现使学生在各学期中的学习负担尽量均匀排课。
解决方法：将链表当中课程的名字和学分分别存储到两个动态的数组，通过一个大的for循环遍历，在里面写上一个小的for循环，循环条件j< number / semester，再通过每学期课程不超过其学分上限的条件循环输出，当I< number % semester时输出该学期的课程。
③怎样才能够获取到AOV网当中课程之间的先修关系。
解决方法：在Graph类中，创建AOV网的同时，再创建一个AOV网的反向图，然后通过for循环，循环条件：调用反向图当中邻接表的边的指向下一条边的指针，当该指针不为null，就依次指向下一个遍历输出该邻接表中的信息。
六、功能模块图
七、实现与展示
图7.1课程信息展示
图7.2课程的学习顺序可以排课
图7.4当存在先修课程不在规定的课程表当中
图7.5均匀排课
图7.6是课程集中在前几个学期
建立边结点类
package project4;
//边结点
public class ArcNode implements Cloneable{
public int adjVex;//该边的终点编号
public ArcNode nextArc;//指向下一条边的指针
@Override
public Object clone(){
ArcNode arcNode = null;
try {
arcNode = (ArcNode) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
arcNode.nextArc = (ArcNode) nextArc.clone();
return arcNode;
}
public ArcNode() {
adjVex = -1;
nextArc = null;
}
}
建立点结点类
package project4;
//点节点
public class Vnode {
//入度域
private int in;
private Course data;//顶点信息
private ArcNode firstArc;//指向第一条边的相邻顶点
public Vnode() {
in = -1;
data = null;
firstArc = null;
}
@Override
public Object clone() throws CloneNotSupportedException {
Vnode vnode = null;
try {
vnode = (Vnode) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
vnode.in = ((Vnode) vnode.clone()).getIn();
vnode.data = (Course) data.clone();
vnode.firstArc = (ArcNode) firstArc.clone();
return vnode;
}
public int getIn() {
return in;
}
public void setIn(int in) {
this.in = in;
}
public Course getData() {
return data;
}
public void setData(Course data) {
this.data = data;
}
public ArcNode getFirstArc() {
return firstArc;
}
public void setFirstArc(ArcNode firstArc) {
this.firstArc = firstArc;
}
}建立课程类存储课程信息
package project4;
//课程信息
public class Course implements Cloneable {
private String name;
private int score;
public Course() {
}
@Override
public Object clone() throws CloneNotSupportedException {
Course course = null;
try {
course = (Course) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
return course;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public int getScore() {
return score;
}
public void setScore(int score) {
this.score = score;
}
}重写栈类用来实现存入课程类
package project4;
public class Stack {
//用来存储课程的数组
public Course[] stackArray;
public int top;//栈顶指针
public Stack() {
top = -1;
stackArray = new Course[100];
}
public Stack(int n){
top = -1;
stackArray = new Course[n];
}
public void push(Course course){
if (top == stackArray.length-1){
Course[] p = new Course[top*2+2];
for (int i = 0; i<= top; i++) {
p[i] = stackArray[i];
}
stackArray = p;
}
top++;
stackArray[top] = course;
}
public Course pop(){
if (top == -1){
System.out.println("栈已空，无法再删除元素！");
return null;
}
top--;
return stackArray[top+1];
}
}建立AOV网实现课程先修网
package project4;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Graph implements Cloneable { //AOV图（课程）
// 顶点表
public Vnode[] adjList;
//顶点数
private int n;
public Graph(int number) {
adjList = new Vnode[number];
n = number;
}
@Override
public Object clone() {
Graph graph = null;
try {
graph = (Graph) super.clone();
} catch (CloneNotSupportedException e) {
e.printStackTrace();
}
graph.adjList = (Vnode[]) adjList.clone();
return graph;
}
public void setN(int n) {
this.n = n;
}
//查找顶点位置
public int locateVex(Course c) {
for (int i = 0; i< n; i++) {
if (adjList[i].getData().getName().equals(c.getName())) {
return i;
}
}
return -1;
}
// 建立有向图的邻接表
public void creatAdj() throws FileNotFoundException {
System.setIn(new FileInputStream("课程"));
Scanner scanner = new Scanner(System.in);
for (int i = 0; i< n; i++) {
String name = scanner.next();
int score = scanner.nextInt();
Course c = new Course();
c.setName(name);
c.setScore(score);
adjList[i] = new Vnode();
adjList[i].setIn(0);
adjList[i].setData(c);
adjList[i].setFirstArc(null);
}
while (true) {
String str1 = scanner.next();
if (str1.equals("end")){
break;
}
String str2 = scanner.next();
int k = Integer.parseInt(str1.substring(1, 3));
if (0 >k || k >12) {
System.out.println(str1 + "先修课程号不在该专业开设的课程序列中");
System.exit(1);
}
int m = Integer.parseInt(str2.substring(1, 3));
if (0 >m || m >12) {
System.out.println(str2 + "先修课程号不在该专业开设的课程序列中");
System.exit(1);
}
Course c1 = new Course();
Course c2 = new Course();
c1.setName(str1);
c2.setName(str2);
int a = locateVex(c1);
int b = locateVex(c2);
if (a >= 0 && b >= 0) {
ArcNode s = new ArcNode();
s.adjVex = b;
s.nextArc = adjList[a].getFirstArc();
adjList[a].setFirstArc(s);
adjList[b].setIn(adjList[b].getIn() + 1);
}
}
}
public void creatConverse() throws FileNotFoundException {
System.setIn(new FileInputStream("课程"));
Scanner scanner = new Scanner(System.in);
for (int i = 0; i< n; i++) {
String name = scanner.next();
int score = scanner.nextInt();
Course c = new Course();
c.setName(name);
c.setScore(score);
adjList[i] = new Vnode();
adjList[i].setIn(0);
adjList[i].setData(c);
adjList[i].setFirstArc(null);
}
while (true) {
String str1 = scanner.next();
if (str1.equals("end")){
break;
}
String str2 = scanner.next();
int k = Integer.parseInt(str1.substring(1, 3));
if (0 >k || k >12) {
System.out.println(str1 + "先修课程号不在该专业开设的课程序列中");
System.exit(1);
}
int m = Integer.parseInt(str2.substring(1, 3));
if (0 >m || m >12) {
System.out.println(str2 + "先修课程号不在该专业开设的课程序列中");
System.exit(1);
}
Course c1 = new Course();
Course c2 = new Course();
c1.setName(str2);
c2.setName(str1);
int a = locateVex(c1);
int b = locateVex(c2);
if (a >= 0 && b >= 0) {
ArcNode s = new ArcNode();
s.adjVex = b;
s.nextArc = adjList[a].getFirstArc();
adjList[a].setFirstArc(s);
adjList[b].setIn(adjList[b].getIn() + 1);
}
}
}
}实现教学安排
package project4;
import java.io.FileNotFoundException;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Test {
public static void main(String[] args) throws FileNotFoundException {
Scanner scanner = new Scanner(System.in);
System.out.println("学期总数： 每学期大学分： 必须课程数量：");
int semester = scanner.nextInt();
int score = scanner.nextInt();
int number = scanner.nextInt();
// System.out.println();
System.out.println("-------------------1.查看课程信息---------------------------------");
System.out.println("-------------------2：判断课程能否顺利学完，若能，输出一个正确的学习顺序----");
System.out.println("-------------------3：使课程尽可能的集中在前几个学期中排课---------------");
System.out.println("-------------------4：使学生在各学期中的学习负担尽量均匀排课---------------");
System.out.println("-------------------5：关闭程序---------------：");
while (true) {
int x = scanner.nextInt();
if (x == 1) {
Graph graph1 = new Graph(number);
//创建AOV无环网
graph1.creatConverse();
print(graph1, semester, score, number);
} else if (x == 2) {
Graph graph = new Graph(number);
//创建AOV无环网
graph.creatAdj();
topSort1(graph);
} else if (x == 3) {
Graph graph = new Graph(number);
//创建AOV无环网
graph.creatAdj();
topSort2(graph, semester, score, number);
} else if (x == 4) {
Graph graph = new Graph(number);
//创建AOV无环网
graph.creatAdj();
topSort3(graph, semester, score, number);
} else {
break;
}
}
scanner.close();
}
public static void print(Graph graph, int semester, int score, int number) {
Stack stack = new Stack();
stack.top = 0;
//对邻接表进行遍历，将其中度为0的点压入栈中
for (int i = graph.adjList.length - 1; i >= 0; i--) {
stack.push(graph.adjList[i].getData());
}
System.out.print("学期总数: " + semester + "\t" + "每学期大学分: " + score + "\t" + "必修课程的数量: " + number + "\n");
System.out.println("----------------专业提供的课程-----------------：");
for (int i = 0; i< number; i++) {
Course course = stack.pop();
System.out.println("----------------------------------------------");
System.out.print("课程号: " + course.getName() + "\t学分" + course.getScore() + "\t先修课程");
ArcNode p1 = new ArcNode();
for (p1 = graph.adjList[i].getFirstArc(); p1 != null; p1 = p1.nextArc) {
System.out.print(" " + graph.adjList[p1.adjVex].getData().getName());
}
System.out.println();
}
}
public static void topSort1(Graph graph) {
//建立空栈，用于存放入度为0的点
Stack stack = new Stack();
stack.top = 0;
int count = 0;
//对邻接表进行遍历，将其中度为0的点压入栈中
for (int i = 0; i< graph.adjList.length - 1; i++) {
if (graph.adjList[i].getIn() == 0) {
stack.push(graph.adjList[i].getData());
}
}
System.out.println("学习顺序为：");
while (stack.top != 0) {
//出栈并输出一个元素
Course course = stack.pop();
System.out.print(course.getName() + ":" + course.getScore());
count++;
//所有与其有关系的点的入度均减一
ArcNode p = graph.adjList[graph.locateVex(course)].getFirstArc();
while (p != null) {
int in = graph.adjList[p.adjVex].getIn() - 1;
graph.adjList[p.adjVex].setIn(in);
//若入度减一后存在顶点的度减少为0，便将其入栈
if (graph.adjList[p.adjVex].getIn() == 0) {
stack.push(graph.adjList[p.adjVex].getData());
}
p = p.nextArc;
}
if (count != graph.adjList.length) {
System.out.print("->");
}
}
//出栈的元素数量小于顶点表的长度时，则表明有环产生
if (count< graph.adjList.length) {
System.out.println("有回路产生，即无法全部学完所有课程");
}
System.out.println();
}
public static void topSort2(Graph graph, int semester, int score, int number) throws FileNotFoundException {
System.setOut(new PrintStream("尽可能集中在前几学期的教学计划表"));
//建立空栈，用于存放入度为0的点
ArrayListlist2 = new ArrayList<>();
ArrayListlist3 = new ArrayList<>();
ArrayListlist4 = new ArrayList<>();
ArrayListlist5 = new ArrayList<>();
Listlist = new ArrayList();
Stack stack = new Stack();
stack.top = 0;
//对邻接表进行遍历，将其中度为0的点压入栈中
for (int i = 0; i< graph.adjList.length - 1; i++) {
if (graph.adjList[i].getIn() == 0) {
stack.push(graph.adjList[i].getData());
}
}
while (stack.top != 0) {
//使用ArrayList集合来存储每次栈中的元素
//将所有度为零的元素全部出栈
while (stack.top != 0) {
Course course = stack.pop();
list.add(course);
}
for (int i = 0; i< list.size(); i++) {
ArcNode p = graph.adjList[graph.locateVex(list.get(i))].getFirstArc();
//所有与其有关系的点的入度均减一
while (p != null) {
graph.adjList[p.adjVex].setIn(graph.adjList[p.adjVex].getIn() - 1);
//若入度减一后存在顶点的度减少为0，便将其入栈
if (graph.adjList[p.adjVex].getIn() == 0) {
stack.push(graph.adjList[p.adjVex].getData());
}
p = p.nextArc;
}
}
}
for (Course c : list) {
list2.add(c.getName());
list3.add(c.getScore());
}
int c = 0;
int day = 0;
for (int i = 0; i< semester - 1; i++) {
int sum1 = 0;
System.out.println("第" + (i + 1) + "学期的课程");
day++;
while (sum1 + list3.get(c)<= score) {
System.out.print(list2.get(c) + ":" + "学分：" + list3.get(c) + " ");
sum1 += list3.get(c);
if (number - 1 - c == semester - 1 - i) break;
c++;
}
System.out.println();
}
int n = 0;
for (int i = 0; i< semester - 1; i++) {
int sum = 0;
while (sum + list3.get(n)<= score) {
list4.add(list2.get(n));
list5.add(list3.get(n));
sum += list3.get(n);
if (n == number - 1) break;
n++;
}
}
for (int i = c + 1; i< number; i++) {
int sum = 0;
System.out.println("第" + (day + 1) + "学期的课程");
day++;
while (sum + list5.get(i)<= 10) {
System.out.print(list4.get(i) + ":" + "学分：" + list5.get(i));
sum += list5.get(i);
if (i == number - 1) break;
}
}
}
public static void topSort3(Graph graph, int semester, int score, int number) throws FileNotFoundException {
System.setOut(new PrintStream("均匀排课的教学计划表"));
Stack stack = new Stack();
ArrayListlist2 = new ArrayList<>();
ArrayListlist3 = new ArrayList<>();
Listlist = new ArrayList<>();
stack.top = 0;
for (int i = 0; i< graph.adjList.length - 1; i++) {
if (graph.adjList[i].getIn() == 0) {
stack.push(graph.adjList[i].getData());
}
}
while (stack.top != 0) {
while (stack.top != 0) {
Course course = stack.pop();
list.add(course);
}
for (int i = 0; i< list.size(); i++) {
ArcNode p = graph.adjList[graph.locateVex(list.get(i))].getFirstArc();
//所有与其有关系的点的入度均减一
while (p != null) {
graph.adjList[p.adjVex].setIn(graph.adjList[p.adjVex].getIn() - 1);
//若入度减一后存在顶点的度减少为0，便将其入栈
if (graph.adjList[p.adjVex].getIn() == 0) {
stack.push(graph.adjList[p.adjVex].getData());
}
p = p.nextArc;
}
}
}
for (Course c : list) {
list2.add(c.getName());
list3.add(c.getScore());
}
int n = 0;
for (int i = 0; i< semester; i++) {
int sum = 0;
System.out.println("第" + (i + 1) + "学期的课程");
for (int j = 0; j< number / semester; j++) {
if (sum + list3.get(n)<= score) {
System.out.print(list2.get(n));
System.out.print(":" + "学分：" + list3.get(n) + " ");
sum += list3.get(n);
if (n == number - 1) break;
n++;
}
}
if (i< number % semester) {
System.out.print(list2.get(n));
System.out.print("：学分：" + list3.get(n) + " ");
sum += list3.get(n);
if (n == number - 1) break;
n++;
}
System.out.println();
}
}
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧