#include<iostream>
#include<string>
#include <stdlib.h>
using namespace std;

#define MAX_TERM_NUM 12
#define MAX_CLASS_NUM 100
#define STACK_SIZE 100

typedef struct ArcNode{
	int adjvex;
	struct ArcNode *nextarc;
}ArcNode;

typedef struct VNode{
	string classorder;       //課程號
	int score;               //學(xué)分
	string preclass[5];      //先修課程數(shù)組
	ArcNode *firstarc;
}VNode,AdjList[MAX_CLASS_NUM];

typedef struct{
	AdjList classvexes;
	int classnum;
}AOV_Graph;

typedef struct{
	int *base;
	int *top;
	int stacksize;
}SqStack;

 //函數(shù)聲明 
void InitGraph(AOV_Graph &AG);              // 初始化AOV網(wǎng)                    
void CreateGraph(AOV_Graph &AG);
void TopologicalSort(AOV_Graph AG,AdjList vertices);       //創(chuàng)建AOV網(wǎng)
int getindex(AdjList classvexes, string classorder);       //獲得當(dāng)前頂點的下標(biāo)
void FindIndegree(AOV_Graph AG, int indegree[]);           //找到每個頂點的如度并存入indegree[]
void InitStack(SqStack *s);                 //初始化棧
bool StackEmpty(SqStack s);                 //判斷棧為空
void Push(SqStack *s, int i);               //棧操作push
int Pop(SqStack *s, int &i);                //棧操作pop
void ArrangeOrder(AOV_Graph AG, int limitescore, int termnum,AdjList vertices);  //對拓?fù)湫蛄羞M行編制

int main(){                        //main函數(shù)

	cout<<"-----------------------------------------------------"<<endl
		<<"本程序處于測試階段，請嚴(yán)格遵守操作規(guī)則！"<<endl<<endl
		<<"任何非法操作都將使程序陷入癱瘓狀態(tài)?。?！"<<endl
		<<"-----------------------------------------------------"<<endl;

	int i=0;
	int termnum=0, limitescore=0, classnum=0;
	AOV_Graph AG;
	AdjList vertices;        //用于存儲拓?fù)湫蛄?	
	cout<<"請輸入學(xué)期總數(shù)的最大值："<<endl;
	cin>>termnum;               //學(xué)期總數(shù)的最大值
	cout<<endl;
	cout<<"請輸入學(xué)期學(xué)分上限："<<endl;
	cin>>limitescore;           //學(xué)期學(xué)分上限
	cout<<endl;
	cout<<"請輸入課程總數(shù)："<<endl;
	cin>>classnum;
	cout<<endl;                  //課程總數(shù)

	AG.classnum=classnum;


	InitGraph(AG);
	CreateGraph(AG);
	TopologicalSort(AG,vertices);
    ArrangeOrder( AG, limitescore,  termnum, vertices);

	return 0;
}
                                         
void InitGraph(AOV_Graph &AG){
	// 初始化AOV網(wǎng) 
	int i=0, j=0;
	for(i=0; i<AG.classnum ;i++){
		AG.classvexes[i].classorder="000";
		AG.classvexes[i].score=0;
		AG.classvexes[i].firstarc=NULL;
		for(j=0;j<5;j++)
			AG.classvexes[i].preclass[j]="000";
	}
}

void CreateGraph(AOV_Graph &AG){
	//創(chuàng)建AOV網(wǎng)
	int i=0, j=0, index=0;
	string *p;           //指向先修課程的指針
	ArcNode *q;          //指向定點的指針

	cout<<"請輸入每門課程的課程號："<<endl;
	for(i=0;i<AG.classnum;i++)
		cin>>AG.classvexes[i].classorder;
	cout<<endl;

	for(i=0; i<AG.classnum; i++){

		cout<<"請輸入"<<AG.classvexes[i].classorder<<"課程的學(xué)分："<<endl;
		cin>>AG.classvexes[i].score ;
		cout<<endl;

		cout<<"請輸入"<<AG.classvexes[i].classorder<<"課程的先修課程的課程號(您需要且最多輸入5門課程，如果沒有先修課程或者不足5門，請輸入000代替課程號："<<endl;
		for(j=0; j<5; j++) 
			cin>>AG.classvexes[i].preclass[j];
        cout<<endl;

		p=(string*)(AG.classvexes[i].preclass);

		while(*p!="000"){                //這部分代碼很重要 ，是創(chuàng)建圖的關(guān)鍵
			index=getindex(AG.classvexes,*p);                   
			q=(ArcNode*)malloc(sizeof(ArcNode));
			q->adjvex=i;
			q->nextarc=AG.classvexes[index].firstarc;
			AG.classvexes[index].firstarc=q;        //插入到頭節(jié)點
			p++;	
		}
	}
}

void TopologicalSort(AOV_Graph AG,AdjList vertices){
	//對AOV網(wǎng)進行拓?fù)渑判虿⒔Y(jié)果存儲在vertices[]中
	int i=0,j=0,k=0,count=0;
	ArcNode *p;
	SqStack s;
	
	int *indegree=new int[AG.classnum];          //存儲頂點如度
	for(i=0;i<AG.classnum;i++)
		indegree[i]=0;

	InitStack(&s);
	FindIndegree(AG, indegree); 

	for(i=0;i<AG.classnum;i++) 
		if(indegree[i]==0)  Push(&s,i);

	while(!StackEmpty(s)){
		Pop(&s,i);

		vertices[count].classorder=AG.classvexes[i].classorder;
		vertices[count].firstarc=AG.classvexes[i].firstarc;
		vertices[count].score=AG.classvexes[i].score;
		for(j=0;j<5;j++)  vertices[count].preclass[j]=AG.classvexes[i].preclass[j];

		count++;

		for(p=AG.classvexes[i].firstarc; p; p=p->nextarc){
			k=p->adjvex;
			if(!(--indegree[k])) Push(&s,k);        //去掉頂點后入度為零的定點入棧
		}
	}


	if(count>AG.classnum)          //出錯信息
		cout<<"程序出現(xiàn)錯誤！??！以下輸出為無效數(shù)據(jù)！?。≌埵謩咏Y(jié)束，重新運行！??！"<<endl;

}


int getindex(AdjList classvexes, string classorder){
	//獲得當(dāng)前頂點的下標(biāo)
	int i=0;
	while(!(classvexes[i].classorder==classorder))  i++;
	return i;
}


void FindIndegree(AOV_Graph AG, int indegree[]){
	//找到每個頂點的如度并存入indegree[]
	int i=0;
	ArcNode *q;
	for(i=0;i<AG.classnum;i++){
		q=AG.classvexes[i].firstarc;
		while(q){
			indegree[q->adjvex]++;
			q=q->nextarc;
		}
	}
}

void InitStack(SqStack *s){
	//初始化棧
	s->base=(int*)malloc(STACK_SIZE*sizeof(int));
	s->stacksize=STACK_SIZE;
	s->top=s->base;
}

bool StackEmpty(SqStack s){
	 //判斷棧為空
	if(s.top==s.base)
		return true;
	else
		return false;
}

void Push(SqStack *s, int i){
	*(s->top)++=i;
}

int Pop(SqStack *s, int &i){
	i=*--(s->top);
	return i;
}
		
void ArrangeOrder(AOV_Graph AG, int limitescore, int termnum,AdjList vertices){
	//對拓?fù)湫蛄羞M行編制
	int i=0, k=0,m=0; 
	int scoresum=0, count=0;

	cout<<"對于教學(xué)計劃進行的拓?fù)渑判蚪Y(jié)果如下："<<endl<<"課程號（學(xué)分）："<<endl<<endl;

	for(m=0;m<AG.classnum;m++) 
		cout<<vertices[m].classorder<<" ( "
		<<vertices[m].score<<" )"<<endl<<endl;

	while(i<AG.classnum){

		while(scoresum<=limitescore&&i<AG.classnum){
			scoresum+=vertices[i].score;
			i++;
		}

		scoresum=vertices[i-1].score;
			
		while(k<i-1){
			cout<<vertices[k].classorder<<"   ( "
				<<vertices[k].score<<" )"<<"   　　";
			k++;
		}
	
		count++;

		cout<<"第"<<count<<"個學(xué)期教學(xué)計劃編制完畢."<<endl;

	}

	cout<<vertices[AG.classnum-1].classorder<<" ( "
		<<vertices[AG.classnum-1].score<<" )"<<"   　　"
		<<"第"<<count+1<<"個學(xué)期教學(xué)計劃編制完畢."<<endl<<endl;

	if(count>termnum)  cout<<"程序出現(xiàn)錯誤?。?！請手動結(jié)束，重新運行?。?！"<<endl;
	else cout<<"教學(xué)計劃配置成功。"<<endl;

}