123.cpp

数据库编程数据库编程数据库编程数据库编程

// 课程设计.cpp : Defines the entry point for the console application.
#include "stdafx.h"
#include "stdio.h"
#include "string.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 100
#define STACKINCREEMENT 10

typedef struct vernode
{
	char classname[20];//课程名
	int num;//课程序号，以1开始,即课程按课程数组中的下标排序。
	int schoolscore;//学分
	char classnum[5];//课程序号
	struct arcnode *firstarc;
}vernode;


typedef struct arcnode
{
	char classname[20];//课程名
	int  num;//课程序号，以0开始
	char classnum[5];//课程序号
	struct arcnode *nextadj;
}arcnode;

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

int totalclassnum;
vernode classnode[20];
int indegree[20];
int sort[20];

/*****************初始化栈***********************/
SqStack InitStack(SqStack &S)
{
	S.base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));
	if(!S.base)
		exit(0);
	S.top=S.base;
	S.stacksize=STACK_INIT_SIZE;
	return S;
}

/*****************入栈******************/
void Push(SqStack &S,int e)
{
	if(S.top-S.base>=S.stacksize)
	{
	
		S.base=(int*)realloc(S.base,(S.stacksize+STACKINCREEMENT)*sizeof(int));
		if(!S.base)
			exit(0);
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREEMENT;
	}
	*S.top++=e;
}

/****************出栈******************/ 
int Pop(SqStack &S)
{
	int e;
	if(S.top==S.base)
		printf("错误!");
	e=*--S.top;
	return e;
}

/*****************判断栈是否为空******************/
int StackEmpty(SqStack &S)
{
	if(S.base==S.top)
		return 1;
	else
		return 0;
}

/*****************输入信息******************/
void creatinfo()
{
	int i;
	int num;
	arcnode *pnewarc;
	printf("请输入课程总数：");
	scanf("%d",&totalclassnum);
	for(i=0;i<totalclassnum;i++)
	{
		printf("请输入第%d门课程的课程名：",i+1);
		scanf("%s",classnode[i].classname);
		printf("请输入它的课程号：");
		scanf("%s",classnode[i].classnum);
		printf("请输入它的学分：");
		scanf("%d",&classnode[i].schoolscore);	
		classnode[i].num=i+1;
		classnode[i].firstarc=NULL;
		printf("请输入先修课的编号(以0为结束标志)：");
		scanf("%d",&num);
		getchar();
		while(num!=0)
		{
			pnewarc=new arcnode;
			pnewarc->num=num;
			pnewarc->nextadj=classnode[i].firstarc;
			classnode[i].firstarc=pnewarc;		
			printf("请输入先修课的编号：");
			scanf("%d",&num);
			getchar();
		}
	}
}


/*****************求结点入度******************/
void findindegree()
{
	struct arcnode *pthisarc=NULL;
	int i;
	for(i=0;i<totalclassnum;i++)
	{
		indegree[i]=0;
		pthisarc=classnode[i].firstarc;
		while(pthisarc!=NULL)
		{
			pthisarc=pthisarc->nextadj;
			indegree[i]++;	
		}
	}
	printf("各结点的先修课程数目:");
	for(i=0;i<totalclassnum;i++)
		printf("%5d",indegree[i]);
	printf("\n");
}

/*****************写入文件******************/
void writetable()
{
	FILE *fp;
	int i;
	arcnode *pthisarc;
	if((fp=fopen("D:\\classtable.DAT","wb"))==NULL)
	{
		printf("创建文件失败！");
		exit(0);			
	}
	for(i=0;i<totalclassnum;i++)
	{
		fprintf(fp,"%-10s","verxbegin");
		fprintf(fp,"%-20s%-10s%-5d%-5d",classnode[i].classname,
			classnode[i].classnum,classnode[i].num,classnode[i].schoolscore);
		pthisarc=classnode[i].firstarc;
		while(pthisarc!=NULL)
		{	
			fprintf(fp,"\n%-10s","arcbegin");
			fprintf(fp,"%-20s%-5d\n",pthisarc->classname,pthisarc->num);
			pthisarc=pthisarc->nextadj;
		}
	}
	fclose(fp);
}


/*****************读出文件****************/
void readtable()
{
	FILE *fp;
	int i=-1,inttemp1,inttemp2;
	arcnode *pnewarc;
	char strtemp[20],strtemp1[20],strtemp2[20];
	if((fp=fopen("D:\\classtable.DAT","rb"))==NULL)
	{
		printf("读取文件失败！");
		exit(0);			
	}
	while(!feof(fp))
	{
		fscanf(fp,"%10s",strtemp);
		if(strcmp(strtemp,"verxbegin"))
		{
			i++;
			fscanf(fp,"%20s%10s%5d%5d",strtemp1,strtemp2,&inttemp1,&inttemp2);
			strcpy(classnode[i].classname,strtemp1);
			strcpy(classnode[i].classnum,strtemp2);
			classnode[i].num=i+1;
			classnode[i].schoolscore=inttemp2;
			classnode[i].firstarc=NULL;	
			
		}
		if(strcmp(strtemp,"arcbegin"))
		{
			fscanf(fp,"%20s",strtemp);
			fscanf(fp,"%5d",&inttemp1);
			pnewarc=new arcnode;
			pnewarc->nextadj=classnode[i].firstarc;
			classnode[i].firstarc=pnewarc;
			strcpy(pnewarc->classname,strtemp);
			pnewarc->num=inttemp1;
		}		
	}
	fclose(fp);
}

/************核对信息****************/
void printinfo()
{
	int i;
	char ch='y';
	arcnode *pthisarc;
	printf("以下是你刚刚输入的信息,请仔细核对!\n");
	for(i=0;i<totalclassnum;i++)
	{
		printf("第%d门课程的课程名:",i+1);
		printf("%20s",classnode[i].classname);
		printf("它的课程号:");
		printf("%5s",classnode[i].classnum);
		printf("它的学分:");
		printf("%5d",classnode[i].schoolscore);
		printf("先修课的编号:");
		pthisarc=classnode[i].firstarc;
		while(pthisarc!=NULL)
		{
			printf("%5d",pthisarc->num);
			pthisarc=pthisarc->nextadj;
		}
		printf("\n");
	}
	while(ch=='y')
	{
		printf("\n以上信息输入的正确吗？如果正确，请按Y进入下一步，否则按N重新输入\n");
		scanf("%c",&ch);
		if(ch=='y'||ch=='Y') break;
		else if(ch=='n'||ch=='N')
			creatinfo();
		else
		{
			printf("你的输入有误，请重新选择！");
			scanf("%c",&ch);
		}
	}
}

/*****************拓扑排序**************/
void toposort()
{
	int i,j=0,count=0,k,l=0;
	SqStack S;
	arcnode *pthisarc;
	InitStack(S);
	findindegree();
	for(i=0;i<totalclassnum;i++)
		if(indegree[i]==0)
		{
			indegree[i]=-1;
			Push(S,i);
		}
	while(!StackEmpty(S))
	{
		k=Pop(S);
		sort[j++]=k;
		count++;
		for(l=0;l<totalclassnum;l++)
		{
			if(indegree[l]<0)
				continue;
			pthisarc=classnode[l].firstarc;
			while(pthisarc!=NULL)
			{
				printf("%5d---%-5d",l,pthisarc->num);
				if(pthisarc->num==k+1)
					indegree[l]=indegree[l]-1;				
				if(indegree[l]==0)
				{
					indegree[l]=-1;
					Push(S,l);
				}
				pthisarc=pthisarc->nextadj;
			}
			printf("\n");
		}
	}
	printf("拓扑排序序列：");
	for(i=0;i<totalclassnum;i++)
		printf("%5d",sort[i]);
	printf("\n");
}

/*************判断任意两点是否构成回路**************/
bool iscircle()
{
	int i,j;
	arcnode *pthisarc,*pthatarc;
	for(i=0;i<totalclassnum;i++)
	{
		pthisarc=classnode[i].firstarc;
		while(pthisarc!=NULL)
		{
			j=pthisarc->num-1;
			pthatarc=classnode[j].firstarc;
			while(pthatarc!=NULL)	
			{
				if(pthatarc->num=i+1)
				{
					return true;
					break;
				}
				pthatarc=pthatarc->nextadj;
			}
			pthisarc=pthisarc->nextadj;
		}
	}
	return false;
}

/*****************每学期平均安排课程**********/
void average( )
{
	int totalterm,i,k,j=1,everytermnum;
	printf("请输入总的学期数：");
	scanf("%d",&totalterm);
	if(totalclassnum%totalterm==0)
		everytermnum=totalclassnum/totalterm;
	else 
		everytermnum=totalclassnum/totalterm+1;
	for(i=0;i<totalclassnum;i++)
	{
		if((i+1)%everytermnum==everytermnum-1)
		printf("\n以下是第%d学期的课程:\n",j++);	
		k=sort[i];
		printf("%15s",classnode[k].classname);		
	}
}

/*****************按最大学分自由选课**********/
void maxscore()
{
	int upscore,i,j,k,m=1,sum=0,l=1;
	printf("请输入每学期的最大限制学分：");
	scanf("%d",&upscore);
	printf("\n第%d学期的课程\n:",l);
	for(i=0;i<totalclassnum;i++)
	{
		k=sort[i];
		j=sort[i+1];
		sum+=classnode[k].schoolscore;
		if(sum<=upscore&&sum+classnode[j].schoolscore>upscore)
		{
			printf("\n第%d学期的课程:\n",++l);
			sum=0;
		}
		printf("%15s",classnode[k].classname);
	}
}


void main()
{
	char ch='y';
	int m,n;
	while(ch=='y'||ch=='Y')
	{
		printf("\t\t\t********************\n");
		printf("\t\t\t**欢迎使用排课系统**\n");
		printf("\t\t\t*1.读取文件       **\n");
		printf("\t\t\t*2.输入信息       **\n");
		printf("\t\t\t********************\n");
		printf("\n请选择");
		scanf("%d",&m);
		switch(m)
		{
		case 1:readtable();break;
		case 2:
			{
				creatinfo();
				printinfo();
				writetable();						
				break;
			}
		default:			  
				printf("您的输入有误！");
		}
		if(!iscircle())
			printf("你的输入不能进行安排课程，请检查！");
		else
		{			
			toposort();
			printf("\n");
			printf("\t\t\t++++++++++++++++++++++++++\n");
			printf("\t\t\t+1.每学期均匀选课：      +\n");
			printf("\t\t\t+2.每学期根据最高学分选课+\n");
			printf("\t\t\t++++++++++++++++++++++++++\n");
			printf("请选择1或2：");
			scanf("%d",&m);
			getchar();
			switch(m)
			{
			case 1:
				average();
				break;
			case 2:
				maxscore();
				break;
			}
		}
		getchar();
		printf("\n是否继续？（y/n）请输入：");
		ch=getchar();
		if(ch=='Y'||ch=='y')
			continue;
		else if(ch=='n'||ch=='N')
			break;
		else
		{
			printf("你的输入有误,请重新选择!\n");
			ch=getchar();
		}
	}
}