📄 032223-final.cpp

📁 输入学期总数学期的学分上限课程数拓扑排序所形成的课程先修关系的边数课程号及其学分在各学期学期负担尽量均匀和课程集中在前几个学期进行排课两种条件下进行排课
💻 CPP
字号:
#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
#include<string.h>


#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX 30



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

typedef struct VNode{
	char data[5];
	int score;
	ArcNode *firstarc;
}VNode,AdjList[MAX];

typedef struct{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;

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


void InitStack(Stacks &S){
	S.base=(int *)malloc(STACK_INIT_SIZE *sizeof(int));
	if(!S.base)exit(OVERFLOW);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
}

void Push(Stacks &S,int e){
	if(S.top-S.base>=S.stacksize){
		S.base=(int *)realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(int));
		if(!S.base)exit(OVERFLOW);
        S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*S.top++=e;
}

int Pop(Stacks &S,int &e){
if(S.top==S.base)return  ERROR;
e=*--S.top;
return e;
}

int StackEmpty(Stacks S){
	if(S.top==S.base)return 1;
	else return 0;
}

int LocateVex(ALGraph G,char *c){
	int i;
	for(i=0;i<G.vexnum;++i)
		if(strcmp(c,G.vertices[i].data)==0)
			return i;
	return -1;
}  


void FindInDegree(ALGraph G,int *indegree){
	int i;
	ArcNode *p;
	for(i=0;i<G.vexnum;i++)
		indegree[i]=0;
	for(i=0;i<G.vexnum;i++){
		p=G.vertices[i].firstarc;
		while(p){
			indegree[p->adjvex]++;
			p=p->nextarc;
		}
	}
}

void TopologicalSort(ALGraph G,int *c){
	int i,k,count,n=0,indegree[MAX];
	Stacks S;
	ArcNode *p;
	FindInDegree(G,indegree);
//	for(i=0;i<G.vexnum;i++)
//		printf("%d",indegree[i]);
	InitStack(S);
	for(i=0;i<G.vexnum;i++)
		if(!indegree[i])Push(S,i);
	count=0;
	while(!StackEmpty(S)){
		Pop(S,i);printf("\ni=%d,data=%s,score=%d",i+1,G.vertices[i].data,G.vertices[i].score);++count;
		c[n]=i;n++;
		for(p=G.vertices[i].firstarc;p;p=p->nextarc){
			k=p->adjvex;
			if(!(--indegree[k]))Push(S,k);
			}
		}
}


void input(ALGraph &G){
	int i,j,k;
	char v1[5],v2[5];
	ArcNode *p;
	FILE *fp;
	printf("选择--键盘输入<K>___文件输入<F>:");
	switch(getchar()){
		case 'K' :
		case 'k' :
			if((fp=fopen("data.txt","wb+"))==NULL){
				printf("cannot open file\n");
				exit(0);
			}
			printf("请输入课程数:");
			scanf("%d",&G.vexnum);
			fwrite(&G.vexnum,sizeof(int),1,fp);
			printf("请输入拓扑排序所形成的课程先修关系的边数:");
			scanf("%d",&G.arcnum);
			fwrite(&G.arcnum,sizeof(int),1,fp);
			printf("请输入课程号及其学分\n");
			for(i=0;i<G.vexnum;i++){
				printf("No.%d:",i+1);
				scanf("%s %d",&G.vertices[i].data,&G.vertices[i].score);
				G.vertices[i].firstarc=NULL;
				fwrite(&G.vertices[i].data,5*sizeof(char),1,fp);
				fwrite(&G.vertices[i].score,sizeof(int),1,fp);
			}	
			printf("请输入课程之间的关系\n");
			for(i=0;i<G.arcnum;i++){
				scanf("%s %s",v1,v2);
				fwrite(&v1,5*sizeof(int),1,fp);
				fwrite(&v2,5*sizeof(int),1,fp);
				j=LocateVex(G,v1);
				k=LocateVex(G,v2);
				p=(ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex=k;
				p->info=NULL;
				p->nextarc=G.vertices[j].firstarc;
				G.vertices[j].firstarc=p;
			}
			break;
		case 'f' :
		case 'F' :
				if((fp=fopen("data.txt","rb+"))==NULL){
				printf("cannot open file\n");
				exit(0);
			}
			fread(&G.vexnum,sizeof(int),1,fp);
			fread(&G.arcnum,sizeof(int),1,fp);
			for(i=0;i<G.vexnum;i++){
				//	printf("No.%d:",i+1);
				fread(&G.vertices[i].data,5*sizeof(char),1,fp);
				fread(&G.vertices[i].score,sizeof(int),1,fp);
				G.vertices[i].firstarc=NULL;
			}	
			for(i=0;i<G.arcnum;i++){
				fread(&v1,5*sizeof(int),1,fp);
				fread(&v2,5*sizeof(int),1,fp);
				j=LocateVex(G,v1);
				k=LocateVex(G,v2);
				p=(ArcNode*)malloc(sizeof(ArcNode));
				p->adjvex=k;
				p->info=NULL;
				p->nextarc=G.vertices[j].firstarc;
				G.vertices[j].firstarc=p;
			}
			break;
	}
	fclose(fp);
}

void main(){
	ALGraph G;
	int i,j,k,term,scoreup,Sort[MAX]={2,3,4,3,2,3,4,4,7,5,2,3},max;
	FILE *fp;
	printf("请输入学期总数:");
	scanf("%d",&term);
	printf("请输入学期的学分上限:");
	scanf("%d",&scoreup);
	getchar();
	input(G);
	TopologicalSort(G,Sort);
	printf("\n1:各学期学期负担尽量均匀\n2:课程集中在前几个学期\n请选择编排策略:");
	getchar();
	switch(getchar()){
		case '1' :
			if((fp=fopen("result1.txt","wb+"))==NULL){
				printf("cannot open file\n");
				exit(0);
			}
			printf("\n各学期学期负担尽量均匀编排策略:");
			i=0;
			max=0;
			for(k=0;k<term;k++){
				printf("\n第%d学期课程:",k+1);
				fwrite(&k,sizeof(int),1,fp);
				j=0;
				do{
				max+=G.vertices[Sort[i]].score;
				printf("%s ",G.vertices[Sort[i]].data);
				fwrite(&G.vertices[Sort[i]].data,5*sizeof(char),1,fp);
				i++;
				if(i>=G.vexnum){k=term;break;};
				j++;
				}while(j%(G.vexnum/term)!=0&&max+G.vertices[Sort[i]].score<=scoreup);
				max=0;
			}
			for(;i<G.vexnum;i++){
				printf("%s ",G.vertices[Sort[i]].data);
				fwrite(&G.vertices[Sort[i]].data,5*sizeof(char),1,fp);
			}
			fclose(fp);
			putchar('\n');
			break;
		case '2' :
			if((fp=fopen("result2.txt","wb+"))==NULL){
				printf("cannot open file\n");
				exit(0);
			}
			printf("\n课程集中在前几个学期编排策略:");
			i=0;
			max=0;
			for(k=0;k<term;k++){
				printf("\n第%d学期课程:",k+1);
				fwrite(&k,sizeof(int),1,fp);
				j=0;
				do{
				max+=G.vertices[Sort[i]].score;
				printf("%s ",G.vertices[Sort[i]].data);
				fwrite(&G.vertices[Sort[i]].data,5*sizeof(char),1,fp);
				i++;
				if(i>=G.vexnum){k=term;break;};
				j++;
				}while(max+G.vertices[Sort[i]].score<=scoreup);
				max=0;
			}
			for(;i<G.vexnum;i++){
				printf("%s ",G.vertices[Sort[i]].data);
				fwrite(&G.vertices[Sort[i]].data,5*sizeof(char),1,fp);
			}
			fclose(fp);
			putchar('\n');
			break;
	}
	
}

/*
请输入学期总数:6
请输入学期的学分上限:10
选择--键盘输入<K>___文件输入<F>:k
请输入课程数:12
请输入拓扑排序所形成的课程先修关系的边数:16
请输入课程号及其学分
No.1:C01 2
No.2:C02 3
No.3:C03 4
No.4:C04 3
No.5:C05 2
No.6:C06 3
No.7:C07 4
No.8:C08 4
No.9:C09 7
No.10:C10 5
No.11:C11 2
No.12:C12 3
请输入课程之间的关系
C01 C02
C01 C03
C02 C03
C01 C04
C03 C05
C04 C05
C11 C06
C05 C07
C03 C07
C03 C08
C06 C08
C09 C10
C09 C11
C09 C12
C10 C12
C01 C12

i=9,data=C09,score=7
i=10,data=C10,score=5
i=11,data=C11,score=2
i=6,data=C06,score=3
i=1,data=C01,score=2
i=2,data=C02,score=3
i=3,data=C03,score=4
i=8,data=C08,score=4
i=4,data=C04,score=3
i=5,data=C05,score=2
i=7,data=C07,score=4
i=12,data=C12,score=3
1:各学期学期负担尽量均匀
2:课程集中在前几个学期
请选择编排策略:1

各学期学期负担尽量均匀编排策略:
第1学期课程:C09
第2学期课程:C10 C11
第3学期课程:C06 C01
第4学期课程:C02 C03
第5学期课程:C08 C04
第6学期课程:C05 C07 C12 
Press any key to continue


请输入学期总数:6
请输入学期的学分上限:10
选择--键盘输入<K>___文件输入<F>:f

i=9,data=C09,score=7
i=10,data=C10,score=5
i=11,data=C11,score=2
i=6,data=C06,score=3
i=1,data=C01,score=2
i=2,data=C02,score=3
i=3,data=C03,score=4
i=8,data=C08,score=4
i=4,data=C04,score=3
i=5,data=C05,score=2
i=7,data=C07,score=4
i=12,data=C12,score=3
1:各学期学期负担尽量均匀
2:课程集中在前几个学期
请选择编排策略:2

课程集中在前几个学期编排策略:
第1学期课程:C09
第2学期课程:C10 C11 C06
第3学期课程:C01 C02 C03
第4学期课程:C08 C04 C05
第5学期课程:C07 C12 
Press any key to continue
 */
💿 文件大小 3 K
👤 上传用户 a6810121
📂 所属分类数据结构
🏷️ 相关标签

#分 #输入 #上限 #拓扑
⌨️ 快捷键说明

复制代码 Ctrl + C
搜索代码 Ctrl + F
全屏模式 F11
切换主题 Ctrl + Shift + D
显示快捷键 ?
增大字号 Ctrl + =
减小字号 Ctrl + -