排课最新版.cpp

排课表

#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <fstream>
#include <cstring>
#pragma warning(disable : 4786)
using namespace std;

class BadInput{
public:
	BadInput(){}
};

template<class T>//堆栈类
class LinkedStack;
template<class T>
class Node{
friend LinkedStack<T>;
private:
	T data;
	Node<T> *link;
};
template<class T>
class LinkedStack{
public:
	LinkedStack(){top=0;}
	~LinkedStack(){
	//析构函数
		Node<T> *next;
		while(top){
		next=top->link;
		delete top;
		top=next;}
	}

	bool IsEmpty() const{return top==0;}

    T Top() const{
	return top->data;
	}
	LinkedStack<T>& Add(const T& x){
	//添加元素x
		Node<T> *p=new Node<T>;
		p->data=x;
		p->link=top;
		top=p;
		return *this;
	}

	LinkedStack<T>& Delete(T& x){
	//删除栈顶元素，并将其送入x
		if(IsEmpty()) {cout<<"堆栈以空"<<endl;exit(0);}
		x=top->data;
		Node<T> *p=top;
		top=top->link;
		delete p;
		return *this;
	}

private:
	Node<T> *top;//指向栈顶节点
};
template<class T>//函数involve测试向量g中是否包含i,返回一个布尔值
bool involve(vector<T> g,T i){
		for(int d=0;d<g.size();d++){
			if(g[d]==i)
				return true;}
		return false;
	  }

template<class T>//邻接矩阵实现的有向图类
class AdjacencyDigraph{
  public:
	  AdjacencyDigraph(int Vertices,T noEdge);
      template<class T>
      void Delete2DArray(T ** &x,int rows){
	    for(int i=0;i<rows;i++)
			delete [] x[i];
        delete [] x;
		x=0;
	  }
      template<class T>
	  void Make2DArray(T ** &x,int rows,int cols){
	    x=new T * [rows];
	    for(int i=0;i<rows;i++)
			x[i]=new int [cols];
	  }
      ~AdjacencyDigraph(){Delete2DArray(a,n+1);}
      AdjacencyDigraph<T>& Add(int i,int j,const T& wi){//向邻接矩阵中加一条边
        if(i<1||j<1||i>n||j>n||i==j||a[i][j]==1)
          throw BadInput();
        a[i][j]=wi;
        e++;
        return *this;
	  }
      void InitializePos(){pos=new int [n+1];}
      void DeactivatePos(){delete [] pos;}
	  int Begin(int i);//i的第一个邻接至的点
	  int NextVertex(int i);//i的下一个邻接至的点
	  bool Topological(int v[]);//测试是否存在拓扑序列，返回一个布尔值
      void devide(vector<string> vec,ofstream& outstr,int flag){//把可以放到一个学期的课程放到一起
	     //分学期
        vector<int> *term=new vector<int> [n];
        vector<int> g;
        int s=0;
        int *InDegree=new int [n+1];
        for(int f=1;f<=n;f++)
          InDegree[f]=0;
        InitializePos();
        for(int k=1;k<=n;k++){
         int u=Begin(k);
	     while(u){
	     InDegree[u]++;
	     u=NextVertex(k);
		 }
		}
        while(static_cast<int>(g.size())!=n){
		  for(int i=1;i<=n;i++){
			  if((InDegree[i]==0)&&(!involve(g,i))){
			    term[s].push_back(i);
				g.push_back(i);
			  }
		  }
          for(unsigned int s1=0;s1<term[s].size();s1++){
             int u1=Begin(term[s][s1]);
    	     while(u1){
	           InDegree[u1]--;
	           u1=NextVertex(term[s][s1]);
			 }
		  }
		  s++;
		} 
       //输出各个学期课程，这是学期数最少的排法
	    for(int c=0;c<n;c++){
			if(term[c].size()!=0){
			  outstr<<endl;
              outstr<<"第"<<(c+1)<<"个学期课程:\n";
			  if(flag==1)
			    cout<<"第"<<(c+1)<<"个学期课程:\n";
			  for(unsigned int j=0;j<term[c].size();j++){
                if(flag==1)
			      cout<<vec[(term[c][j]-1)]<<"  ";
				outstr<<vec[(term[c][j]-1)]<<"  ";
			  }
              if(flag==1)
                cout<<endl;
			}
		}
        DeactivatePos();
        delete [] InDegree;
		delete [] term;
	  }
  private:
	  T NoEdge;
	  int n;
	  int e;
	  T **a;
	  int *pos;
};

template<class T>
AdjacencyDigraph<T>::AdjacencyDigraph(int Vertices,T 

noEdge){
  n=Vertices;
  e=0;
  NoEdge=noEdge;
  Make2DArray(a,n+1,n+1);
  for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
		 a[i][j]=NoEdge;
}

template<class T>
int AdjacencyDigraph<T>::Begin(int i){
  for(int j=1;j<=n;j++)
	  if(a[i][j]!=NoEdge){
	    pos[i]=j;
        return j;
	  }
  pos[i]=n+1;
  return 0;
}

template<class T>
int AdjacencyDigraph<T>::NextVertex(int i){
  for(int j=pos[i]+1;j<=n;j++)
	  if(a[i][j]!=NoEdge){
	    pos[i]=j;
        return j;
	  }
  pos[i]=n+1;
  return 0;
}

template<class T>
bool AdjacencyDigraph<T>::Topological(int v[]){
  int *InDegree=new int [n+1];
  InitializePos();
  for(int f=1;f<=n;f++)
    InDegree[f]=0;
  for(int r=1;r<=n;r++){
    int u=Begin(r);
	while(u){
	  InDegree[u]++;
	  u=NextVertex(r);
	}
  }
  LinkedStack<int> S;
  for(int i=1;i<=n;i++)
	  if(!InDegree[i]) S.Add(i);

  int t=0;
  while(!S.IsEmpty()){
    int w;
	S.Delete(w);
	v[t++]=w;
	int q=Begin(w);
	while(q){
	  InDegree[q]--;
	  if(!InDegree[q]) S.Add(q);
	  q=NextVertex(w);
	}
  }
  DeactivatePos();
  delete [] InDegree;
  return (t==n);
}

void newline(ifstream& iutstr1)//读取下一行
{
  char symbol;
  do{
    iutstr1.get(symbol);
  }while(symbol!='\n');
}


void new_line()//读取下一行
{
  char symbol;
  do{
    cin.get(symbol);
  }while(symbol!='\n');
}

void redeal(char file[]){//修改已有课程
  vector<string> vec;
  char course[5]="课程",xianxu[5]="先序",kebiao[5]="课表";
  char co[18],xi[18],keb[18];
  strcpy(co,file);  strcpy(xi,file);  strcpy(keb,file);
  strcat(co,course);  strcat(xi,xianxu);  strcat(keb,kebiao);
  ifstream iutstr;
  iutstr.open(co);
  if(iutstr.fail()){
    cout<<"文件打开失败!\n";
	exit(1);
  }
  string next,str("e");
  iutstr>>next;
  while(!next.empty()){
	  if(!involve(vec,next))
	    vec.push_back(next);
	  else
		  cout<<"提示: "<<next<<" 是重复输入，只计算一次。\n";
	  iutstr>>next;
  }
  AdjacencyDigraph<int> course1(static_cast<int>(vec.size()),0);
  if(vec.size()==0)
	  cout<<"没有输入课程!\n";
  ifstream iutstr1;
  iutstr1.open(xi);
  if(iutstr1.fail()){
    cout<<"文件打开失败!\n";
	exit(1);
  }
  string next1,next2;
  for(unsigned int i=0;i<vec.size();i++){
    vector<string> m;
    iutstr1>>next2;
    if(!next2.empty()&&involve(vec,next2)){
      iutstr1>>next1;
      while(next1!=str&&!next1.empty()){
		  if((!involve(m,next1))&&(next1!=vec[i])&&(involve(vec,next1))){
	        m.push_back(next1);
		  }
		  else if(involve(m,next1))
            cout<<"提示: "<<next1<<" 是重复输入，只计算一次。\n";
		  else if(next1==vec[i])
			  cout<<"提示: "<<next1<<" 不能是自己的先行课，将不予计算。\n";
		  else if(!involve(vec,next1))
			  cout<<"提示: "<<next1<<" 不在刚才输入的课程之内，将不予计算。\n";
	      iutstr1>>next1;
	  }
	  for(int w=0;w<m.size();w++){
		  for(unsigned int j=0;j<vec.size();j++){
			  if(m[w]==vec[j]){
				  course1.Add(j+1,i+1,1);}
		  }
	  }
	}
	else if(!involve(vec,next2)){
		cout<<next2<<"不在课程中,不予计算!\n";
        //newline(iutstr1);
	}
  }
  ofstream iutstr2;
  iutstr2.open(keb);
  if(iutstr2.fail()){
    cout<<"文件打开失败!\n";
	exit(1);
  }
  int *v=new int[vec.size()];
  if(course1.Topological(v)){
    course1.devide(vec,iutstr2,0);
    cout<<endl;cout<<endl;
  } 
  else{
    cout<<"先序关系中存在环!无法排课。\n";
	iutstr2<<"先序关系中存在环!无法排课。\n";
	cout<<endl;cout<<endl;
  }
  delete [] v;
  iutstr.close();  iutstr1.close();  iutstr2.close();
}




void deal(char file[]){//处理输入的待排课程
  vector<string> vec;
  cout<<"输入课程清单,结束输入“e”\n";
  string next,str("e");
  cin>>next;
  while(next!=str){
	  if(!involve(vec,next))
	    vec.push_back(next);
	  else
		  cout<<"提示: "<<next<<" 是重复输入，只计算一次。\n";
	  cin>>next;
  }
  char course[5]="课程",xianxu[5]="先序",kebiao[5]="课表";
  char co[18],xi[18],keb[18];
  strcpy(co,file);  strcpy(xi,file);  strcpy(keb,file);
  strcat(co,course);  strcat(xi,xianxu);  strcat(keb,kebiao);
  ofstream outstr;
  outstr.open(co);
  if(outstr.fail()){
    cout<<"文件打开失败!\n";
	exit(1);
  }
  for(unsigned int is=0;is<vec.size();is++){
    outstr<<vec[is]<<"  ";
  }
  new_line();
  AdjacencyDigraph<int> course2(static_cast<int>(vec.size()),0);
  if(vec.size()==0)
	  cout<<"没有输入课程!\n";
  else
    cout<<"输入各个课程的先行课,结束或没有输入“e”\n";
  ofstream outstr1;
  outstr1.open(xi);
  if(outstr1.fail()){
    cout<<"文件打开失败!\n";
	exit(1);
  }
  for(unsigned int i=0;i<vec.size();i++){
    cout<<vec[i]<<" 的先行课: \n";
    outstr1<<vec[i]<<" ";
    vector<string> m;
    string next1;
    cin>>next1;
    while(next1!=str){
		if((!involve(m,next1))&&(next1!=vec[i])&&(involve(vec,next1))){
	      m.push_back(next1);
          outstr1<<next1<<" ";
		}
		else if(involve(m,next1))
          cout<<"提示: "<<next1<<" 是重复输入，只计算一次。\n";
		else if(next1==vec[i])
			cout<<"提示: "<<next1<<" 不能是自己的先行课，将不予计算。\n";
		else if(!involve(vec,next1))
			cout<<"提示: "<<next1<<" 不在刚才输入的课程之内，将不予计算。\n";
	  cin>>next1;
	}
    outstr1<<str<<" ";
    outstr1<<endl;
	new_line();
	for(int w=0;w<m.size();w++){
		for(unsigned int j=0;j<vec.size();j++){
			if(m[w]==vec[j]){
				course2.Add(j+1,i+1,1);}
		}
	}
  }

  ofstream outstr2;
  outstr2.open(keb);
  if(outstr2.fail()){
    cout<<"文件打开失败!\n";
	exit(1);
  }
  int *v=new int[vec.size()];
  if(course2.Topological(v)){
    course2.devide(vec,outstr2,1);
    cout<<endl;cout<<endl;
  } 
  else{
    cout<<"先序关系中存在环!无法排课。\n";
	outstr2<<"先序关系中存在环!无法排课。\n";
	cout<<endl;cout<<endl;
  }

  delete [] v;
  outstr.close();  outstr1.close();  outstr2.close();
}

void liuout(char co[]){
  	 ifstream instr;
     instr.open(co);
     while(instr.fail()){
       cout<<"不是已有组!\n";
       exit(1);
	 }
	 char next;
	 instr.get(next);
	 while(!instr.eof()){
	   cout<<next;
       instr.get(next);
	 }
	 instr.close();cout<<endl;
}

void fileout(char teamname2[]){
  char course[5]="课程",xianxu[5]="先序",kebiao[5]="课表";
  char co[18],xi[18],keb[18];
  strcpy(co,teamname2);  strcpy(xi,teamname2);  strcpy(keb,teamname2);
  strcat(co,course);  strcat(xi,xianxu);  strcat(keb,kebiao);
  cout<<"课程清单:\n";
  liuout(co);
  cout<<"先序关系(每一行后面都是第一个的先行课,e表示没有):\n";
  liuout(xi);
  cout<<"课表:\n";
  liuout(keb);
}

int main(){
  using namespace std;  
  vector<string> team;//读入已有组的组名，以确保可以调用
  ifstream inteam;
  char ru[10]="组名.txt";
  inteam.open(ru);
  if(inteam.fail()){
    cout<<"不存在组文件!\n";
    exit(1);
  }
  string nextt;
  inteam>>nextt;
  while(!nextt.empty()){
    team.push_back(nextt);
    inteam>>nextt;
  }	
  inteam.close();

  bool flag1=true;
  do{
  cout<<endl<<endl<<"1 新建一组   2 调用已有组   3 修改已有组   4 退出\n";
  string num,st1("1"),st2("2"),st3("3"),st4("4"),st("e");
  cin>>num;
  if(num==st1){
     cout<<"输入组名:  退出新建输“e”  ";
	 char teamname[18];
	 cin>>teamname;
     string na(teamname);
     while(involve(team,na)&&na!=st){
	   cout<<"已有这个组!重输:  退出新建输“e”  ";
	   cin>>teamname;
       na=teamname;
	 }
	 if(!involve(team,na)&&na!=st){
       team.push_back(na);
	   ofstream outteam;
	   outteam.open(ru,ios::app);
       if(outteam.fail()){
         cout<<"文件打开失败!\n";
         exit(1);
	   }
	   outteam<<endl<<na<<endl;
	   outteam.close();
	   deal(teamname);cout<<endl;
	 }
  }
  else if(num==st2){
     cout<<"输入组名:  退出调用输“e”  ";
	 char teamname1[18];
	 cin>>teamname1;
	 string sd=teamname1;
     while(!involve(team,sd)&&sd!=st){
	   cout<<"没有这个组!重输:  退出调用输“e”  ";
	   cin>>teamname1;
       sd=teamname1;
	 }
     if(involve(team,sd)&&sd!=st)
       fileout(teamname1);
  }
  else if(num==st3){
     cout<<"输入组名:  退出修改输“e”  ";
	 char teamname2[18];	 
	 cin>>teamname2;
     string na2(teamname2);
     while(!involve(team,na2)&&na2!=st){
	   cout<<"没有这个组!重输:  退出修改输“e”  ";
	   cin>>teamname2;
       na2=teamname2;
	 }
	 if(involve(team,na2)&&na2!=st){
       team.push_back(na2);
       cout<<"请在当前目录中的 "<<na2<<"课程 和 "<<na2<<"先序 文件修改并保存。\n确定已修改输入‘e’\n";
	   string ah,ss("e");
	   cin>>ah;
	   while(ah!=ss){
	     cout<<"确定已修改输入‘e’:";
	     cin>>ah;
	   }
	   if(ah==ss){
	     redeal(teamname2);
         fileout(teamname2);
	   }
	 }
  }
  else if(num==st4)
    flag1=false;
  else
	  cout<<"输入错误!重输:\n";
}while(flag1==true);
  return 0;
}