[问题描述]

成都创新互联公司，专注为中小企业提供官网建设、营销型网站制作、成都响应式网站建设公司、展示型网站设计、做网站等服务，帮助中小企业通过网站体现价值、有效益。帮助企业快速建站、解决网站建设与网站营销推广问题。

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

[基本要求]

(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元起，快前往官网查看详情吧

新闻标题：数据结构课设教学计划编制问题Java-创新互联
链接分享：http://chengdu.cdxwcx.cn/article/iooog.html