java教学计划编制的全部代码.doc

package curriculumProject;/非连通图的深度优先搜索遍历和广度优先搜索遍历import linearList.Queue.SeqQueue; /顺序循环队列类public abstract class AbstractGraph implements GGraph/抽象图类 public abstract int vertexCount(); /返回顶点数，方法由子类实现 public abstract E get(int i); /返回顶点vi的数据域 public abstract int getFirstNeighbor(int i); /返回顶点vi的第一个邻接顶点的序号 public abstract int getNextNeighbor(int i, int j); /返回vi在vj后的下一个邻接顶点的序号 / public abstract AbstractGraph prim(); public void DFSTraverse(int v) /从顶点v出发对非连通图的一次深度优先搜索遍历 boolean visited = new booleanvertexCount(); /访问标记数组，元素初值为false，表示未被访问 int i=v; do if (!visitedi) /若顶点vi未被访问 System.out.print( ); depthfs(i, visited); /从顶点vi出发的一次深度优先搜索遍历 System.out.print( ); i = (i+1) % vertexCount(); /在其他连通分量中寻找未被访问顶点 while (i!=v); System.out.println(); private void depthfs(int v, boolean visited) /从顶点v开始发的一次深度优先搜索遍历 /遍历一个连通分量 System.out.print(this.get(v)+ ); /访问该顶点 visitedv = true; /置已访问标记 int w = getFirstNeighbor(v); /获得第一个邻接顶点 while (w!=-1) /若存在邻接顶点 if(!visitedw) /若邻接顶点w未被访问 depthfs(w, visited); /从w出发的深度优先搜索遍历，递归调用 w = getNextNeighbor(v, w); /返回v在w后的下一个邻接顶点的序号 public void BFSTraverse(int v) /从顶点v出发对非连通图进行一次广度优先搜索遍历 boolean visited = new booleanvertexCount(); /访问标记数组 int i=v; do if (!visitedi) /若顶点vi未被访问 System.out.print( ); breadthfs(i, visited); /从顶点vi出发的广度优先搜索遍历 System.out.print( ); i = (i+1) % vertexCount(); /在其他连通分量中寻找未被访问顶点 while (i!=v); System.out.println(); private void breadthfs(int v, boolean visited) /从顶点v出发的广度优先搜索遍历 /遍历一个连通分量 System.out.print(this.get(v)+ ); visitedv = true; SeqQueue que = new SeqQueue(vertexCount(); /创建顺序队列 que.enqueue(new Integer(v); /访问过的顶点v的序号入队 while (!que.isEmpty() /当队列不空时循环 v = que.dequeue().intValue(); /出队 int w = getFirstNeighbor(v); /获得顶点v的第一个邻接顶点序号 while (w!=-1) /当邻接顶点存在时循环 if (!visitedw) /若该顶点未访问过 System.out.print(this.get(w)+ ); /访问顶点 visitedw = true; que.enqueue(new Integer(w); /访问过的顶点w的序号入队 w = getNextNeighbor(v, w); /返回v在w后的下一个邻接顶点的序号 package curriculumProject;/图的邻接表import dataStructure.linearList.SeqList; /顺序表类import linearList.linkedList.SortedHSLinkedList; /排序的带头结点的单链表类/public class AdjListGraph implements GGraph /邻接表表示的图类 public class AdjListGraph extends AbstractGraph implements GGraph /邻接表表示的图类 protected SeqListVertex vertexlist; /顶点表 public AdjListGraph(int n) /构造方法，n指定顶点数 this.vertexlist = new SeqListVertex(n); public AdjListGraph(E vertices, Edge edges) /以顶点集合和边集合构造一个图 this(vertices.length); for (int i=0; ivertices.length; i+) insertVertex(verticesi); /插入一个顶点 for (int j=0; jedges.length; j+) insertEdge(edgesj); /插入一条边 public int vertexCount() /返回顶点数 return this.vertexlist.length(); public E get(int i) /返回顶点vi的数据元素 return this.vertexlist.get(i).data; public boolean insertVertex(E vertex) /插入一个顶点，若插入成功，返回true return this.vertexlist.add(new Vertex(vertex); /在顺序表最后插入一个元素 public boolean insertEdge(int i, int j) /插入一条权值为weight的边vi,vj if (i=0 & i=0 & jvertexCount() & i!=j) /SortedHSLinkedList slink = new SortedHSLinkedList(); SortedHSLinkedList slink = this.vertexlist.get(i).adjlink;/ slink = this.vertexlist.get(i).adjlink;/ System.out.println(this.vertexlist.get(i); return slink.add(new Edge(i,j);/在第i条单链表最后增加边结点 return false; public boolean insertEdge(Edge edge) /插入一条边 if (edge!=null) return insertEdge(edge.start, edge.dest); return false; public String toString() /获得图的顶点集合和邻接表 String str= 顶点集合：+vertexlist.toString()+n; str += 出边表：n ; /+edgeCount+条边 n; for (int i=0; i=0 & i=0 & j=0 & vn) SortedHSLinkedList slink = this.vertexlist.get(v).adjlink; /获得欲删除的第v条边单链表 int i=0; Edge edge = slink.get(i); while (edge!=null) this.removeEdge(edge.dest, edge.start); /删除对称的边 i+; edge = slink.get(i); this.vertexlist.remove(v); /删除顺序表的第i个元素，顶点数已减一 for (i=0; iv) edge.start-; /顶点序号减一 if (edge.destv) edge.dest-; j+; edge = slink.get(j); return true; return false; public int getFirstNeighbor(int v) /返回顶点v的第一个邻接顶点的序号 /若不存在第一个邻接顶点，则返回-1 return getNextNeighbor(v, -1); public int getNextNeighbor(int v, int w) /返回v在w后的下一个邻接顶点的序号 /若不存在下一个邻接顶点，则返回-1 if (v=0 & v=-1 & wvertexCount() SortedHSLinkedList slink = this.vertexlist.get(v).adjlink; /获得第v条边单链表 Edge edge = slink.get(0); /返回单链表的第一个结点表示的边 int i=0; while (edge!=null) /寻找下一个邻接顶点 if (edge.destw) return edge.dest; /返回下一个邻接顶点的序号 i+; edge = slink.get(i); /返回单链表的第一个结点表示的边 return -1; package curriculumProject;/带权图的边类public class Edge implements Comparable /带权值的边类 public int start; /边的起点序号 public int dest; /边的终点序号 /public int weight; /边的权值 public Edge(int start, int dest) this.start = start; this.dest = dest; /this.weight = weight; public String toString() return (+start+,+dest+); public int compareTo(Edge e) /约定两条边比较大小的规则 if (this.start!=e.start) return this.start - e.start; else return this.dest - e.dest; package curriculumProject;/图接口public interface GGraph /图接口 int vertexCount(); /返回顶点数 E get(int i); /返回顶点vi的数据元素 boolean insertVertex(E vertex); /插入一个顶点 boolean insertEdge(int i, int j); /插入一条权值为weight的边vi,vj boolean removeVertex(int v); /删除序号为v的顶点及其关联的边 boolean removeEdge(int i, int j); /删除边vi,vj int getFirstNeighbor(int v); /返回顶点v的第一个邻接顶点的序号 int getNextNeighbor(int v, int w); /返回v在w后的下一个邻接顶点的序号 package curriculumProject;import java.util.*;import linearList.Queue.SeqQueue;public class Graph_Main2 /* * param args */int bian;/ 定义边数HashSet array = new HashSet();/ 定义一个集合保存顶点的值ArrayList list2 = new ArrayList();/ 保存优先关系顶点的值ArrayList listrudu = new ArrayList();/ 保存顶点的入度ArrayList result = new ArrayList();/ 保存拓扑排序的结果ArrayList credit2 = new ArrayList();/ 保存学分信息ArrayList credit3 = new ArrayList();/ 保存学分信息int relation;/ 保存输入优先关系的所有值int c_relation;Scanner scanner = new Scanner(System.in);public void input() System.out.println(请输入课程总数,按回车确认);Scanner reader=new Scanner(System.in);int Input=reader.nextInt();System.out.println(请依次输入各个课程的学分:);int credit = new intInput;for(int i = 0; i Input; i+)crediti = reader.nextInt();credit2.add(crediti);String vertices = new StringInput;for (int n = 0; n Input; n+) if (n 9) verticesn = C0 + (n + 1); else verticesn = C + (n + 1);Scanner reader2=new Scanner(System.in);System.out.println(请输入课程之间的关系总和，即有多少条边？,按回车确认);bian = reader2.nextInt();relation = new intbian2;List list = new ArrayList();System.out.println(比如：C01是C02的先修课，则输入 01 02);for (int i = 0; i bian; i+) System.out.print(请输入第 + (i + 1) + 条边的优先关系);for (int j = 0; j 2; j+) relationij = reader.nextInt();list.add(new Edge(relationi0,relationi1); Edge edges = list.toArray(new Edge0); AdjListGraph graph = new AdjListGraph(vertices,edges);System.out.println(带权有向图，+graph.toString();System.out.println(深度优先搜索遍历);for(int i=0;igraph.vertexCount();i+)graph.DFSTraverse(i);System.out.println(广度优先搜索遍历);for(int i=0;igraph.vertexCount();i+)graph.BFSTraverse(i);public void sort() for (int i = 0; i bian; i+) for (int j = 0; j 2; j+) array.add(relationij);Iterator iter = array.iterator();while (iter.hasNext() Object s = iter.next();list2.add(s);/ 将各顶点的值保存在list里，方便后面查找入度时使用int count = 0;/ 定义一个记入度的计数器for (int i = 0; i list2.size(); i+) for (int j = 0; j bian; j+) if (list2.get(i).equals(relationj1) count+;listrudu.add(list2.get(i);listrudu.add(count);count = 0;System.out.println();boolean flag = true;while (flag) int check = 0;/ 检查有没有入度为0for (int i = 0; i listrudu.size(); i = i + 2) if (listrudu.get(i + 1).equals(0) result.add(listrudu.get(i);/for(int j=0;jresult.size();j+)/credit3.add(credit2.get(j);/credit3.add(credit2.get(i);for (int j = 0; j list2.size(); j+) if (listrudu.get(i).equals(list2.get(j) for (int j2 = 0; j2 bian; j2+) if (list2.get(j).equals(relationj20) relationj21 = -9999;/ 如果这个前驱是要被删除的话，那么把他的后继改值list2.remove(j); else check+;if (check = listrudu.size()/2) System.out.println(课程关系输入错误，有环,无法排序);flag = false;int count1 = 0;/ 定义一个记入度的计数器for (int i = 0; i list2.size(); i+) for (int j = 0; j = 0; i-) for (int j = 0; j i; j+) if (result.get(j).equals(result.get(i) result.remove(j);for (int i = 0; i );System.out.println();System.out.println();System.out.println(请输入你的总学期数);Scanner reader3=new Scanner(System.in);int term = reader3.nextInt();System.out.println(请输入学期学分上线);int sum_credit = reader3.nextInt();System.out.println(如果要使课程均匀分布在各个学期，则为：);int sum=0;int sum2=0;for (int i = 0; i result.size(); i+) for(int j=0;jresult.size();j=j+2) Object res2 = result.get(j); Integer r2 = Integer.parseInt(res2.toString(); Object obj = credit2.get(r2-1);Integer a = Integer.parseInt(obj.toString();sum += a;j=j+2;break;double value = (double)credit2.size()/(double)term;int value2=0;if(value);System.out.println();elseif(sum=sum_credit)for(int j3=0;j3result.size();j3=j3+2)Object res = result.get(j3);Integer r = Integer.parseInt(res.toString();Object obj2 = credit2.get(r-1);Integer a2 = Integer.parseInt(obj2.toString();sum += a2;break;if(sum);/System.out.print(result.get(i) + -);elsesum = 0;System.out.print(result.get(i) + -);elseSystem.out.println();sum = 0;System.out.print(result.get(i) + -);System.out.println();System.out.println();System.out.println(如果要使课程分布在前几个学期，则为：);int j_=0;int j=0;for (int i = 0; i result.size(); i+) /for(int j=0;jresult.size();j=j+2)Object res4 = result.get(j);Integer r4 = Integer.parseInt(res4.toString();Object obj4 = credit2.get(r4-1);Integer a4 = Integer.parseInt(obj4.to