jxjh.cpp

数据结构课程设计

#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;               //学分
	string preclass[5];      //先修课程数组
	ArcNode *firstarc;
}VNode,AdjList[MAX_CLASS_NUM];

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

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

 //函数声明 
void InitGraph(AOV_Graph &AG);              // 初始化AOV网                    
void CreateGraph(AOV_Graph &AG);
void TopologicalSort(AOV_Graph AG,AdjList vertices);       //创建AOV网
int getindex(AdjList classvexes, string classorder);       //获得当前顶点的下标
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);  //对拓扑序列进行编制

int main(){                        //main函数

	cout<<"-----------------------------------------------------"<<endl
		<<"本程序处于测试阶段，请严格遵守操作规则！"<<endl<<endl
		<<"任何非法操作都将使程序陷入瘫痪状态！！！"<<endl
		<<"-----------------------------------------------------"<<endl;

	int i=0;
	int termnum=0, limitescore=0, classnum=0;
	AOV_Graph AG;
	AdjList vertices;        //用于存储拓扑序列
	
	cout<<"请输入学期总数的最大值："<<endl;
	cin>>termnum;               //学期总数的最大值
	cout<<endl;
	cout<<"请输入学期学分上限："<<endl;
	cin>>limitescore;           //学期学分上限
	cout<<endl;
	cout<<"请输入课程总数："<<endl;
	cin>>classnum;
	cout<<endl;                  //课程总数

	AG.classnum=classnum;


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

	return 0;
}
                                         
void InitGraph(AOV_Graph &AG){
	// 初始化AOV网 
	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){
	//创建AOV网
	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<<"课程的学分："<<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"){                //这部分代码很重要 ，是创建图的关键
			index=getindex(AG.classvexes,*p);                   
			q=(ArcNode*)malloc(sizeof(ArcNode));
			q->adjvex=i;
			q->nextarc=AG.classvexes[index].firstarc;
			AG.classvexes[index].firstarc=q;        //插入到头节点
			p++;	
		}
	}
}

void TopologicalSort(AOV_Graph AG,AdjList vertices){
	//对AOV网进行拓扑排序并将结果存储在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<<"程序出现错误！！！以下输出为无效数据！！！请手动结束，重新运行！！！"<<endl;

}


int getindex(AdjList classvexes, string classorder){
	//获得当前顶点的下标
	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){
	//对拓扑序列进行编制
	int i=0, k=0,m=0; 
	int scoresum=0, count=0;

	cout<<"对于教学计划进行的拓扑排序结果如下："<<endl<<"课程号（学分）："<<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<<"个学期教学计划编制完毕."<<endl;

	}

	cout<<vertices[AG.classnum-1].classorder<<" ( "
		<<vertices[AG.classnum-1].score<<" )"<<"   　　"
		<<"第"<<count+1<<"个学期教学计划编制完毕."<<endl<<endl;

	if(count>termnum)  cout<<"程序出现错误！！！请手动结束，重新运行！！！"<<endl;
	else cout<<"教学计划配置成功。"<<endl;

}