range_course_system.java

排课程序

		    }
		    if(m==0){//若某一课程入度为零，则以-1存入Input[][]
		    	Input[n]=new int[1];
		    	Input[n][0]=-1;
		    }
		}
		
		 for(n=0;n<i;n++)
			for(j=0;j<10;j++)  next[n][j]=-1; //将没有保存课程邻接点的数组元素统一保存-1   
		for(n=0;n<i;n++){
			   p=0;
		    for(m=0;m<i;m++){//将每门课程的邻接点保存到next[][]
		    	for(k=0;k<Input[m].length;k++){
		    	    	if(m==n||Input[m][k]==-1) break;
		    	    	if(n==Input[m][k]){
		    	    		 next[n][p]=m;
		    	    		  p++; 
		    	    		 break;
		    	    	}
		    	    }
		    	  
		    }
		    	
		}
	  	 p=0;
	  	 for(n=0;n<i;n++){//计算每门课程的出度
			for(j=0;next[n][j]!=-1;j++)  p++;
			if(p!=0) outdeg[n]=p;
			else     outdeg[n]=1;
			p=0;
		}
   	  
	}	      
	

	class Range_Course{//排列课程
	     public Range_Course(){
		
	}
	
		public void set_per_TermNum(){//初步设定每学期安排的课程数目
	       int per_Term,remain;
	       int totalSub=20;//课程总数
	       int k,i;
	       if(time!=0&&termNum==10){//当学期数为10且进行第2，3方案排课时假定每学期的课数
	       	  per_Term=1;
	       	  remain=10;
	       } 
	       
	       else{
	       	    per_Term=totalSub/termNum;
	   	        remain=totalSub%termNum;	
	       } 
	       	
		for(k=0;k<termNum;k++){
			num[k]=per_Term;
		} 
		if(remain!=0){
			if(remain==10){//只有当学期数为10且进行第2，3方案排课时才存在这种情况
				for(i=0;i<7;i++) num[i]+=1;
				remain=3;
			}
			for(k=0;k<remain;k++){
				i=(int)(Math.random()*termNum);
				num[i]=num[i]+1;
			}
		}
	}
	

   public void distribute_course(){//初步分配每学期的课程
   		int k=0;
   		int i,j;
		for(i=0;i<termNum;i++){
			for(j=0;j<10;j++){
					if(j<num[i]) {
						 subject[i][j]=order[k];
						 k++;
						 }
		           	else          subject[i][j]=-1;
		    
			}
		
		}
   }
   
   
   public int start_arrange_course(){
   	   	int i,j,h,k,m,n=0,a,b,leg;
		int sig=0;//记录本学期内需要调整的课程数目
   	   for(i=0;i<termNum;i++){//检查每个学期是否存在互斥的课程，如果存在则将为前提的课程后移
			for(j=0;j<num[i];j++){
		 	  for(k=0;k<num[i];k++){
		 	     	m=subject[i][k];
		 		 for(h=0;h<outdeg[m];h++){
		 		    if(subject[i][j]==next[m][h]){//如果为某一课程的出度则互斥
		 			middle[sig]=subject[i][j];//保存要移动的课程编号
		 			location[sig]=j;//保存要移动的课程在数组中的位置
		 			n++;
		 			sig++;
		 			break;//如果与一门课的任一邻接点相等无须再比较
		 	    	}
		 		}
		 		
		 		if(n!=0){
		 		  n=0;
		 		  break;	
		 		} 
		 		//如果与本学期内的任一门课有关联，则无须再比较
		 	}
		 }
		   for(h=0;h<sig;h++){//将需要调整的课程编号设为-1
		   	  k=location[h];
		   	  subject[i][k]=-1;//将原来保存移动的课程编号的数组元素置为-1
		   }
		   
		    for(leg=num[i+1],a=0;a<sig;a++){//将课程移动到下一学期
		 		subject[i+1][leg]=middle[a];
		 		middle[a]=-1;
		 		leg++;
		 	}		 	   		 	  
		    num[i+1]=num[i+1]+sig;//改变原来按排每学期课程数目
		    n=0;
		    sig=0;
		}
		return num[i];//返回一次排课后还剩余的课程
   }	
   	
   
	public void ArrangeCourse(){			
		int i,j,h,k,m,n=0,a,b,leg;
		int sig=0;//记录本学期内需要调整的课程数目
		int p;	  	 			 				
	if(termNum!=20){//如果termNum=20,则无须执行以下代码
		  set_per_TermNum();		
		for(k=0;k<termNum;k++){//备份初步设定每学期安排的课程数目，用于以后需要重新每学期安排的课程数目
			num2[k]=num[k];
		}

		for(i=0;i<20;i++) new_order[i]=indegree[i];//////////////////source of mistake		
		change_Order();//将课程编号按入度小到大的顺序排序
	    distribute_course();//将课程分配到各学期		
			num[termNum]=start_arrange_course();//返回一次排课后还剩余的课程
		  for(k=0;k<termNum;k++) num[k]=num2[k];//还原每个学期原来设定的课程数目
			for(;num[termNum]!=0;){//如果还有剩余课程，重新再排课
		 	     num[termNum]=0;				 		
		 	     num[0]+=1;//在上一次按排每个学期的课程数的基础上，将第一学期课程数加1，最后一个学期课程数减肥
		    	if((num[termNum-1]-1)>0)  num[termNum-1]-=1;
		        if((num[termNum-1]<=0)&&num[termNum-2]>0) num[termNum-2]-=1;
		        if((num[termNum-2]<=0)&&num[termNum-3]>0) num[termNum-3]-=1;
		        if((num[termNum-3]<=0)&&num[termNum-4]>0) num[termNum-4]-=1;
		        if((num[termNum-4]<=0)&&num[termNum-5]>0) num[termNum-5]-=1;
		     for(k=0;k<termNum;k++) num2[k]=num[k];//备份重新按排的每个学期课程数目
		    	distribute_course();//重新分配各学期的课程	
		    	num[termNum]=start_arrange_course();//重新再排课
		    for(k=0;k<termNum;k++) num[k]=num2[k];//恢复重新按排的每个学期课程数目		
     	}
     					
	}  			    
		 	
   if(termNum==20){
   	for(i=0;i<20;i++)
   	   for(j=0;j<10;j++){
   	   	   if(j==0) subject[i][j]=course_num[i];
   	   	   else     subject[i][j]=-1;
   	   }
   }
	 
	 	time++;
       range.multiply_Proposal(time);
		 	  	  			 
}
	
    public int compare_Proposal(int t){//比较重新排出的课程与原来的课程方案是否相同，如相同则重新排列至不同，如不同则保存到相应的数组中
    	int i=0,j=0,k=0,sign=0,token=0,signal=0;
    	 if(t==2){//方案二
    	 	for(i=0;i<20;i++){//比较新排列出的方案与原方案各学期的课程数目
    			for(j=0;j<10;j++){
    				if(subject[i][j]!=-1)    sign++;
    				if(proposal1[i][j]!=-1)  token++;   			   	 
    			   } 
    			   if(sign!=token){//如果存在一个学期的课程数目不相等，则说明两方案不同
    			   	  sign=0;
    			   	  token=0;
    			   	  signal++;
    			   	  break;
    			   }
    			   sign=0;
    			   token=0;  	
    			} 
    			   		   
    	   if(signal==0){//////如果各学期的课程数目相等，再比较--如果新方案与原方案的其中一个学期有不相同的课程，则说明两方案不同
    	   	  for(i=0;i<20;i++){/////5
    	   	  	  for(j=0;j<10;j++){////4
    	   	      	if(subject[i][j]!=-1){///3
    	   	      	    for(k=0;k<10;k++){//2
    	   	      	    	if(proposal1[i][k]!=-1)
    	   	      	    	    if(subject[i][j]==proposal1[i][k]){///
    	   	      	    	    	signal++;
    	   	      	    	    	break;
    	   	      	    	    }///
    	   	      	    }//2
    	   	      	    if(signal==0){
    	   	      	    	token++;
    	   	      	    	break;
    	   	      	    } 
      	   	      	    else      signal=0;
    	   	      }///3
    	   	  }////4
    	   	    if(token!=0){
    	   	    	token=0;
    	   	    	signal++;
    	   	    	break;
    	   	    }
    	   }/////5
    	  }//////
    	   if(time==2)       	       
    		 if(signal!=0){//确定为方案二
    		   for(i=0;i<20;i++)
    	           for(j=0;j<10;j++) proposal2[i][j]=subject[i][j];		
    		 } 
    		if(signal==0) time=time-1;   
    	 } 
        
        if(t==3){//方案三
            	   	       	       
    		for(i=0;i<20;i++){
    			for(j=0;j<10;j++){
    				if(subject[i][j]!=-1)    sign++;//本学期课程数
    				if(proposal2[i][j]!=-1)  token++;   			   	 
    			   } 
    			   if(sign!=token){
    			   	  sign=0;
    			   	  token=0;
    			   	  signal++;
    			   	  break;
    			   }
    			   sign=0;
    			   token=0;  	
    			} 
    			
    		if(signal==0){//////6
    	   	  for(i=0;i<20;i++){/////5
    	   	  	  for(j=0;j<10;j++){////4
    	   	      	if(subject[i][j]!=-1){///3
    	   	      	    for(k=0;k<10;k++){//2
    	   	      	    	if(proposal2[i][k]!=-1)
    	   	      	    	    if(subject[i][j]==proposal2[i][k]){///
    	   	      	    	    	signal++;
    	   	      	    	    	break;
    	   	      	    	    }///
    	   	      	    }//2
    	   	      	    if(signal==0){
    	   	      	    	token++;
    	   	      	    	break;
    	   	      	    } 
      	   	      	    else      signal=0;
    	   	      }///3
    	   	  }////4
    	   	    if(token!=0){
    	   	    	token=0;
    	   	    	signal++;
    	   	    	break;
    	   	    }
    	   }/////5
    	  }//////6
    	   	       	      		  	
    	if(signal!=0){//确定为方案三
       			for(i=0;i<20;i++)
    	           for(j=0;j<10;j++) proposal3[i][j]=subject[i][j];	
       		}
       	if(signal==0) time=time-1;    			
      }
      
      return signal;
    
    }
    
    
    public void multiply_Proposal(int t){//进行多方案排课
    	int i,j,signal=0,m=-2,sign=0,token=0,k=0;
    	if(t==1){//保存方案一
    	   for(i=0;i<20;i++)
    	       for(j=0;j<10;j++) proposal1[i][j]=subject[i][j];	
    	} 
    	
    	if(t==2){//比较新排出的方案二是否与原方案一相同
    		signal=compare_Proposal(t);   		
        }
    	
    	if(t==3){//比较新排出的方案三是否与原方案一，二相同
    		signal=compare_Proposal(2);
    		if(signal!=0) signal=compare_Proposal(t);
    	}       
        
        if(termNum!=5&&termNum!=20){
        	if(signal==0||time<3){//如果新方案与原方案相同或未排到3个方案，则继续排
        	  for(i=0;i<20;i++) indegree[i]=indegree_Copy[i];
        	  ArrangeCourse();
            } 
            else  time=0;
        }    
        else time=0;  
        
    }
    
    
    public void print_result(int sig){//输出排课结果
    	int i,j,m=-2,t;
    	display.setText("");
    if(termNum!=20){
    	if(sig==1){//输出方案一
    	   for(i=0;i<termNum;i++){
    	       t=i+1;
    		display.append("第"+t+"学期课程："+"\n");
    		display.append("         ");
    		for(j=0;j<10;j++){
		   	  m=proposal1[i][j];
		   	  if(m!=-1) display.append("    "+course[m]+"  ");
		 	}	
		 	display.append("\n");
    	}	
      }
      if(sig==2){//输出方案二
    	   for(i=0;i<termNum;i++){
    	       t=i+1;
    		display.append("第"+t+"学期课程："+"\n");
    		display.append("         ");
    		for(j=0;j<10;j++){
		   	  m=proposal2[i][j];
		   	  if(m!=-1) display.append("    "+course[m]+"  ");
		 	}	
		 	display.append("\n");
    	}	
      }
      if(sig==3){//输出方案三
    	   for(i=0;i<termNum;i++){
    	       t=i+1;
    		display.append("第"+t+"学期课程："+"\n");
    		display.append("         ");
    		for(j=0;j<10;j++){
		   	  m=proposal3[i][j];
		   	  if(m!=-1) display.append("    "+course[m]+"  ");
		 	}	
		 	display.append("\n");
    	}	
      }
    }
    	
    else for(i=0;i<termNum;i++){
    	      t=i+1;
    	     display.append("第"+t+"学期课程："+"  ");
    	     display.append(course[course_num[i]]+"\n");
    }

	 	
    }
    
    
    	
	public void change_Order(){//将课程编号按入度小到大的顺序排序保存到order[]中
		int s,i,j,n;
		for(i=0;i<20;i++){
			 for(j=i+1,n=1;n<20-i;j++,n++){
		  	if(new_order[i]>new_order[j]){
		  		s=new_order[i];
		  		new_order[i]=new_order[j];
		  		new_order[j]=s;
                 }
		  }
		}
		 for(i=0;i<20;i++)
		  for(j=0;j<20;j++){
		  	if(new_order[i]==indegree[j]){
		  		order[i]=j;
		  		indegree_Copy[j]=indegree[j];
		  		indegree[j]=-1;//////////////////////////////
		  		break;
		  	}
		  }
	}
	
	
	
}
	
	VNode[] vertices=new VNode[20];//创建实例对象保存顶点信息,使用前要再实例化
	VNode p=new VNode();
	Stack stack=new Stack();//建立栈的实例对象
	JTextArea display;
	Range_Course range;
	int vexnum=20;//顶点数（即需要排的课程数目）
	int kind;
	int termNum=0;//学期数
	int time=0;//表示排课的方案数
	int[]   order=new int[20];//保存课程编号
	int[][]  subject=new int[20][10];//用保存排好课后的各学期课程编号，其中第N行保存第N+1个学期的课程编号
    int[]  middle=new int[10];//暂存学期间调换课程
    int[]  num=new int[20];//保存输入学期数后暂时确定每个学期安排的课程数
	int[]  location=new int[10];//记录本学期内需要调整课程在数组中的位置
	int[]  new_order=new int[20];
	int[]  num2=new int[20];
	String[][] str=new String[20][];
	String[]   str1=new String[20];
	String[]   str2=new String[20];
	String str3;//保存pop()的返回值
	String[]   course=new String[20];//保存课程名
	int[]      course_num=new int[20];//保存课程编号
	int[][]      Input=new int[20][];//第n行保存编号为n+1课程的前提课程编号
	int[][]      next=new int[20][10];//next[][]第n行保存第n个结点邻接点
	int[]      outdeg=new int[20];//保存各结点的出度
	int[]   indegree=new int[20];//保存各结点的入度
	int[] indegree_Copy=new int[20];
    int[][] proposal1=new int[20][10];
    int[][] proposal2=new int[20][10];
    int[][] proposal3=new int[20][10];	
}

//以类代替结构体存储顶点
class ArcNode{//表结点
	public ArcNode(){
		
	}
	
	int adjvex;//该弧所指向的顶点的位置
	int info;//该弧相关信息
}


class VNode{//头结点
	public VNode(){
		
	}
	
	String data;//顶点信息
	ArcNode[] firstarc=new ArcNode[20];
}