[問題描述]
大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。
[基本要求]
(1) 輸入?yún)?shù)：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(hào)(固定占3位的字母數(shù)字串)、學(xué)分和直接先修課的課程號(hào)。
(2) 允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中。
(3) 若根據(jù)給定的條件問題無解，則報(bào)告適當(dāng)?shù)男畔?；否則將教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式自行設(shè)計(jì)。
[實(shí)現(xiàn)提醒]
可設(shè)學(xué)期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號(hào)不在該專業(yè)開設(shè)的課程序列中，則作為錯(cuò)誤處理。同時(shí)還應(yīng)建立課程號(hào)與課程號(hào)之間的對(duì)應(yīng)關(guān)系。
[測(cè)試數(shù)據(jù)]
學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號(hào)從C01到C12，學(xué)分順序?yàn)?，3，4，3，2，3，4，4，7，5，2，3，先修關(guān)系如下圖。
??????????????????????????????圖13 課程先修關(guān)系
一、邏輯結(jié)構(gòu)設(shè)計(jì)
利用課程之間存在先修關(guān)系，讓所有的課程形成一個(gè)AOV網(wǎng)，各門課程看作AOV網(wǎng)的節(jié)點(diǎn)，滿足課程之間的先修關(guān)系，利用圖的拓?fù)渑判騺磉M(jìn)行學(xué)期之間的課程排序安排，并按照每學(xué)期的課程學(xué)分和學(xué)習(xí)負(fù)擔(dān)來輸出。
二、存儲(chǔ)結(jié)構(gòu)設(shè)計(jì)
課程采用數(shù)組的方式存儲(chǔ)方式，通過棧從AOV網(wǎng)當(dāng)中去獲取，最后通過動(dòng)態(tài)的數(shù)組存儲(chǔ)輸出，AOV網(wǎng)的存儲(chǔ)方式為鄰接表的方式。
三、設(shè)計(jì)思路
四、主要操作設(shè)計(jì)
類圖：
1.Course類，作為課程類，存放和獲取課程的名字和學(xué)分。
2.ArcNode類,主要是圖鄰接表中邊的結(jié)點(diǎn)類，有指向下一條邊的指針域和下一個(gè)結(jié)點(diǎn)的位置。
3.Vnode類，主要圖中點(diǎn)的結(jié)點(diǎn)類，有入度域，數(shù)據(jù)域，指針域，指向第一條邊的相鄰頂點(diǎn)。
4.Graph類，調(diào)用Vnode類建立鄰接表adjList，locateVex()方法用來獲取AOV網(wǎng)中頂點(diǎn)的位置，creatAdj()方法用來創(chuàng)建AOV網(wǎng)，creatConverse()方法創(chuàng)建反向的AOV網(wǎng)，用來后面Test類調(diào)用輸出課程之間的先修關(guān)系。
5.Stack類，重寫棧，調(diào)用Course類建立數(shù)組stackArray來存儲(chǔ)課程信息，并將棧定指針top=-1。重寫其中的push()入棧和pop()出棧方法。
6.Test類，print()方法通過對(duì)AOV網(wǎng)中鄰接表的遍歷，將其課程信息存放到棧中，再調(diào)用前面創(chuàng)建的反向AOV網(wǎng)的鄰接表來輸出課程的先修關(guān)系。最后在main函數(shù)里面調(diào)用該方法輸出課程之間的信息關(guān)系。topSort1()方法用來判斷課程能否順利學(xué)完，若能，輸出一個(gè)正確的學(xué)習(xí)順序通過對(duì)鄰接表的遍歷，將其中入度為0的點(diǎn)壓入棧中，當(dāng)棧中不是空的時(shí)候，就出棧并輸出一個(gè)元素，然后更新與頂點(diǎn)的鄰接點(diǎn)的入度使其為0，接著重復(fù)上面的操作。當(dāng)其中出棧的元素?cái)?shù)量小于頂點(diǎn)表的長(zhǎng)度使就表示有環(huán)路產(chǎn)生，不能學(xué)完所有課程。topSort2()方法用來實(shí)現(xiàn)使課程盡可能的集中在前幾個(gè)學(xué)期中排課，topSort3()方法用來實(shí)現(xiàn)使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻排課
五、技術(shù)難點(diǎn)與解決方法
①怎樣通過拓?fù)渑判驅(qū)崿F(xiàn)將課程盡可能集中在前幾學(xué)期的教學(xué)。
解決方法：通過對(duì)AOV網(wǎng)鄰接表的遍歷，將入度為0的元素入棧，當(dāng)棧不為空時(shí)，就出棧，并將出棧的元素存放到鏈表當(dāng)中，不斷重復(fù)這樣的操作，直到遍歷完畢，接著將鏈表當(dāng)中課程的名字和學(xué)分分別存放到兩個(gè)動(dòng)態(tài)的數(shù)組，在通過for循環(huán)遍歷，滿足每學(xué)期的課程的學(xué)分之和不超過其上限，當(dāng)剩下的課程和剩下的學(xué)期數(shù)相等時(shí)就結(jié)束循環(huán)。再創(chuàng)建兩個(gè)數(shù)組分別存儲(chǔ)課程名字和學(xué)分通過for循環(huán)遍歷將每學(xué)期的課程不超過其學(xué)分上限存儲(chǔ)后，最后輸出剩下學(xué)期的課程。
②怎樣通過拓?fù)渑判驅(qū)崿F(xiàn)使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻排課。
解決方法：將鏈表當(dāng)中課程的名字和學(xué)分分別存儲(chǔ)到兩個(gè)動(dòng)態(tài)的數(shù)組，通過一個(gè)大的for循環(huán)遍歷，在里面寫上一個(gè)小的for循環(huán)，循環(huán)條件j
③怎樣才能夠獲取到AOV網(wǎng)當(dāng)中課程之間的先修關(guān)系。
解決方法：在Graph類中，創(chuàng)建AOV網(wǎng)的同時(shí)，再創(chuàng)建一個(gè)AOV網(wǎng)的反向圖，然后通過for循環(huán)，循環(huán)條件：調(diào)用反向圖當(dāng)中鄰接表的邊的指向下一條邊的指針，當(dāng)該指針不為null，就依次指向下一個(gè)遍歷輸出該鄰接表中的信息。
六、功能模塊圖
七、實(shí)現(xiàn)與展示
??????????????????????圖7.1課程信息展示
?????????????圖7.2課程的學(xué)習(xí)順序可以排課
?????圖7.4當(dāng)存在先修課程不在規(guī)定的課程表當(dāng)中
??????圖7.5均勻排課
圖7.6是課程集中在前幾個(gè)學(xué)期
建立邊結(jié)點(diǎn)類
重慶分公司
重慶分公司
package project4;
//邊結(jié)點(diǎn)
public class ArcNode implements Cloneable{
public int adjVex;//該邊的終點(diǎn)編號(hào)
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;
}
}
建立點(diǎn)結(jié)點(diǎn)類
package project4;
//點(diǎn)節(jié)點(diǎn)
public class Vnode {
//入度域
private int in;
private Course data;//頂點(diǎn)信息
private ArcNode firstArc;//指向第一條邊的相鄰頂點(diǎn)
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;
}
}建立課程類存儲(chǔ)課程信息
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;
}
}重寫棧類用來實(shí)現(xiàn)存入課程類
package project4;
public class Stack {
//用來存儲(chǔ)課程的數(shù)組
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網(wǎng)實(shí)現(xiàn)課程先修網(wǎng)
package project4;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
public class Graph implements Cloneable { //AOV圖（課程）
// 頂點(diǎn)表
public Vnode[] adjList;
//頂點(diǎn)數(shù)
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;
}
//查找頂點(diǎ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 + "先修課程號(hào)不在該專業(yè)開設(shè)的課程序列中");
System.exit(1);
}
int m = Integer.parseInt(str2.substring(1, 3));
if (0 >m || m >12) {
System.out.println(str2 + "先修課程號(hào)不在該專業(yè)開設(shè)的課程序列中");
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 + "先修課程號(hào)不在該專業(yè)開設(shè)的課程序列中");
System.exit(1);
}
int m = Integer.parseInt(str2.substring(1, 3));
if (0 >m || m >12) {
System.out.println(str2 + "先修課程號(hào)不在該專業(yè)開設(shè)的課程序列中");
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);
}
}
}
}實(shí)現(xiàn)教學(xué)安排
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("學(xué)期總數(shù)： 每學(xué)期大學(xué)分： 必須課程數(shù)量：");
int semester = scanner.nextInt();
int score = scanner.nextInt();
int number = scanner.nextInt();
// System.out.println();
System.out.println("-------------------1.查看課程信息---------------------------------");
System.out.println("-------------------2：判斷課程能否順利學(xué)完，若能，輸出一個(gè)正確的學(xué)習(xí)順序----");
System.out.println("-------------------3：使課程盡可能的集中在前幾個(gè)學(xué)期中排課---------------");
System.out.println("-------------------4：使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻排課---------------");
System.out.println("-------------------5：關(guān)閉程序---------------：");
while (true) {
int x = scanner.nextInt();
if (x == 1) {
Graph graph1 = new Graph(number);
//創(chuàng)建AOV無環(huán)網(wǎng)
graph1.creatConverse();
print(graph1, semester, score, number);
} else if (x == 2) {
Graph graph = new Graph(number);
//創(chuàng)建AOV無環(huán)網(wǎng)
graph.creatAdj();
topSort1(graph);
} else if (x == 3) {
Graph graph = new Graph(number);
//創(chuàng)建AOV無環(huán)網(wǎng)
graph.creatAdj();
topSort2(graph, semester, score, number);
} else if (x == 4) {
Graph graph = new Graph(number);
//創(chuàng)建AOV無環(huán)網(wǎng)
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;
//對(duì)鄰接表進(jìn)行遍歷，將其中度為0的點(diǎn)壓入棧中
for (int i = graph.adjList.length - 1; i >= 0; i--) {
stack.push(graph.adjList[i].getData());
}
System.out.print("學(xué)期總數(shù): " + semester + "\t" + "每學(xué)期大學(xué)分: " + score + "\t" + "必修課程的數(shù)量: " + number + "\n");
System.out.println("----------------專業(yè)提供的課程-----------------：");
for (int i = 0; i< number; i++) {
Course course = stack.pop();
System.out.println("----------------------------------------------");
System.out.print("課程號(hào): " + course.getName() + "\t學(xué)分" + 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的點(diǎn)
Stack stack = new Stack();
stack.top = 0;
int count = 0;
//對(duì)鄰接表進(jìn)行遍歷，將其中度為0的點(diǎn)壓入棧中
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("學(xué)習(xí)順序?yàn)椋?);
while (stack.top != 0) {
//出棧并輸出一個(gè)元素
Course course = stack.pop();
System.out.print(course.getName() + ":" + course.getScore());
count++;
//所有與其有關(guān)系的點(diǎn)的入度均減一
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);
//若入度減一后存在頂點(diǎn)的度減少為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("->");
}
}
//出棧的元素?cái)?shù)量小于頂點(diǎn)表的長(zhǎng)度時(shí)，則表明有環(huán)產(chǎn)生
if (count< graph.adjList.length) {
System.out.println("有回路產(chǎn)生，即無法全部學(xué)完所有課程");
}
System.out.println();
}
public static void topSort2(Graph graph, int semester, int score, int number) throws FileNotFoundException {
System.setOut(new PrintStream("盡可能集中在前幾學(xué)期的教學(xué)計(jì)劃表"));
//建立空棧，用于存放入度為0的點(diǎn)
ArrayListlist2 = new ArrayList<>();
ArrayListlist3 = new ArrayList<>();
ArrayListlist4 = new ArrayList<>();
ArrayListlist5 = new ArrayList<>();
Listlist = new ArrayList();
Stack stack = new Stack();
stack.top = 0;
//對(duì)鄰接表進(jìn)行遍歷，將其中度為0的點(diǎn)壓入棧中
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集合來存儲(chǔ)每次棧中的元素
//將所有度為零的元素全部出棧
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();
//所有與其有關(guān)系的點(diǎn)的入度均減一
while (p != null) {
graph.adjList[p.adjVex].setIn(graph.adjList[p.adjVex].getIn() - 1);
//若入度減一后存在頂點(diǎn)的度減少為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) + "學(xué)期的課程");
day++;
while (sum1 + list3.get(c)<= score) {
System.out.print(list2.get(c) + ":" + "學(xué)分：" + 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) + "學(xué)期的課程");
day++;
while (sum + list5.get(i)<= 10) {
System.out.print(list4.get(i) + ":" + "學(xué)分：" + 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("均勻排課的教學(xué)計(jì)劃表"));
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();
//所有與其有關(guān)系的點(diǎn)的入度均減一
while (p != null) {
graph.adjList[p.adjVex].setIn(graph.adjList[p.adjVex].getIn() - 1);
//若入度減一后存在頂點(diǎn)的度減少為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) + "學(xué)期的課程");
for (int j = 0; j< number / semester; j++) {
if (sum + list3.get(n)<= score) {
System.out.print(list2.get(n));
System.out.print(":" + "學(xué)分：" + 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("：學(xué)分：" + list3.get(n) + " ");
sum += list3.get(n);
if (n == number - 1) break;
n++;
}
System.out.println();
}
}
} 你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機(jī)房具備T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級(jí)服務(wù)器適合批量采購(gòu)，新人活動(dòng)首月15元起，快前往官網(wǎng)查看詳情吧
