教学计划编制.doc

(完整word版)教学计划编制
教学计划编制问题
问题描述：
大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学
期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在
开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，
也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。
基本要求：
（1）输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、学分和直接先修课的课程号。
（2）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。
（3）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。
测试数据：
学期总数：6；学分上限：10；该专业共开设12门课，课程号从C01到C12，学分顺序为2,3,4,3,2,3,4,4,7,5,2,3。先修关系如下：
课程编号
课程名称
先决条件
C1
程序设计基础
无
C2
离散数学
C1
C3
数据结构
C1，C2
C4
汇编语言
C1
C5
语言的设计和分析
C3，C4
C6
计算机原理
C11
C7
编译原理
C5，C3
C8
操作系统
C3，C6
C9
高等数学
无
C10
线性代数
C9
C11
普通物理
C9
C12
数值分析
C9，C10，C1
实现提示
可设学期总数不超过12，课程总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中，则作为错误处理。应建立内部课程序号与课程号之间的对应关系。

#include<string.h>
#include<stdio.h>
#include<stdlib.h>

#define null 0
#define MAXNODE 64 //最大课程个数

typedef struct
{
char c[3];
}cid; //课程号

typedef struct Course
{
cid id[3]; //课程号
char name[30]; //课程名
float xf; //学分
}Course; ////////////////////////////////////////////////课程

typedef struct PreCourse
{
int adjvex; //课程在数组中的下标
struct PreCourse *pre; //指向下一先修的课程节点
}PreCourse;/////////////////////////////////////////////////先修的课程节点

typedef struct
{
Course course;//课程
PreCourse *firstnext; //指向第一个先修的课程节点
}CourseNode;////////////////////////////////////////////////////////////课程节点

typedef struct
{
CourseNode courses[MAXNODE]; //邻接表
int xqs;//学期总数
int num; //课程的数目
float xfsx;/////学分上限
}AlGraph;///////////////////////////////////////////////////////////////课程图

typedef struct
{
int data[MAXNODE];//队中元素
int f,r;//队头r 队尾f
}queue;

int IsCricle=0;//判断是否环 1表示是 0表示不是
int jxq;//用于计算学期的
/////////////////////////////////////////////////////////////////////////

void queueinit(queue *q)///////////////队初始化
{
q->f=q->r=0;
}

void queuein(queue *q,int x)//入队
{
if((q->r+1)%MAXNODE==q->f)
{
printf("队满\n");
exit(0);
}
q->r=(q->r+1)%MAXNODE;
q->data[q->r]=x;
}

int queueout(queue *q)//出队
{
if(q->f==q->r)
{
printf("队空\n");
exit(0);
}
q->f=(q->f+1)%MAXNODE;
return q->data[q->f];
}

int queueempty(queue *q)///////////////队判空 1为空
{
if(q->f==q->r)
return 1;
else return 0;
}

void creatpre(AlGraph *CGraph)///////////////建立先修关系
{
system("cls");//用来清屏
int choice;
fflush(stdin);/////////////////////////////////////////////清空输入流
int i,j,n;//////临时变量
PreCourse *p,*q;//////临时变
printf("\n建立先修关系:\n");
printf("\n请输入每一门课程号的编号：");
for(i=0;i<CGraph->num;i++)
{
if(i%4==0)printf("\n");
printf("%d) ",i+1);
printf("%s\t",CGraph->courses[i].course.id);
}
printf("\n请根据以上的编号，输入每一门课程的先修课程（输入0 表示没有或结束）：\n");
for(i=0;i<CGraph->num;i++)
{
printf("%s的先修课程:",CGraph->courses[i].course.id);
scanf("%d",&j);
n=0;
while(j)
{
while(j<1||j>CGraph->num||j==i+1)
{
if(j==i+1)
printf("先修课程号不能是本课程号");
else
printf("输入的先修课程号不在该专业开设的课程序列中");
fflush(stdin);/////////////////////////////////////////////清空输入流
printf("重新输入:");
scanf("%d",&j);
}
p=(PreCourse *)malloc(sizeof(PreCourse));
p->adjvex=j-1;
p->pre=null;
if(n==0)
{
CGraph->courses[i].firstnext=p;
q=CGraph->courses[i].firstnext;
n++;
}
else
{
q->pre=p;
q=p;
n++;
}
scanf("%d",&j);
}
}
printf(" 1)重新建立先修关系 2)确定\n");
printf("请选择:");
scanf("%d",&choice);
if(choice==1)
creatpre(CGraph);
jxq=0;
}

AlGraph input()//////////////////////////////////输入并建立课程图
{
AlGraph CGraph;
int xqzs=0,kczs=0;////////////////学期总数:xqzs 专业共开设课程数:kczs
int i,j;//////临时变量
float xf,xfsx=0;//////临时变量xf 学分上限:xfsx
printf("教学计划编制\n\n");
printf("输入参数:\n");
printf("1、学期总数:");
scanf("%d",&xqzs);
CGraph.xqs=xqzs;
printf("2、专业共开设课程数:");
scanf("%d",&kczs);
CGraph.num=kczs;///////////////////////////////////课程数
printf("3、学分上限(每个学期的学分上限都一样):");
scanf("%f",&xfsx);
CGraph.xfsx=xfsx;
printf("4、每门课的课程号(固定占3位的字母数字串)、课程名、学分:\n");
for(i=0;i<kczs;i++)
{
j=0;
fflush(stdin);/////////////////////////////////////////////清空输入流
printf("课程号:");
scanf("%s",CGraph.courses[i].course.id);
fflush(stdin);/////////////////////////////////////////////清空输入流
printf("课程名:");
scanf("%s",CGraph.courses[i].course.name);
fflush(stdin);/////////////////////////////////////////////清空输入流
printf("学分:");
scanf("%f",&xf);
fflush(stdin);/////////////////////////////////////////////清空输入流
while(xf>xfsx||xf<=0)
{
printf("本课程学分大于学期学分上限或小于等于零，请重新输入学分:");
fflush(stdin);/////////////////////////////////////////////清空输入流
scanf("%f",&xf);
}
CGraph.courses[i].course.xf=xf;
CGraph.courses[i].firstnext=null;
}
creatpre(&CGraph);///////////////建立先修关系
return CGraph;
}

void output(AlGraph CGraph)///////////////输出先修关系
{
int i,j,n;//////临时变量
PreCourse *p;//////临时变量
printf("先修关系如下：\n\n");
printf("课程编号\t课程名称\t\t 先决条件\n");
for(i=0;i<CGraph.num;i++)
{
printf("%s\t\t%s\t\t",CGraph.courses[i].course.id,CGraph.courses[i].course.name);
j=0;
p=CGraph.courses[i].firstnext;
while(p)
{
n=p->adjvex;
printf("%s ",CGraph.courses[n].course.id);
p=p->pre;
j++;
}
if(j==0)printf("无");
printf("\n");
}
}

void findoutdegree(AlGraph *CGraph,int outdegree[])/////////找出度数，即找出每一门课程的先修课数
{
int i;
PreCourse *p;
for(i=0;i<CGraph->num;i++)
{
outdegree[i]=0;
p=CGraph->courses[i].firstnext;
while(p)
{
outdegree[i]++;
p=p->pre;
}
}
}

void judgingcricle(AlGraph *CGraph,queue *q2)////////判断是否有环
{
int outdegree[MAXNODE];/////////出度
int i,m,j,pd=0;
float xf=0;
PreCourse *p;
queue q;
queueinit(&q);///////////////队初始化
findoutdegree(CGraph,outdegree);/////////找出度
for(i=0;i<CGraph->num;i++)
if(outdegree[i]==0&&(xf+CGraph->courses[i].course.xf)<=CGraph->xfsx)/////////出度为零的，并且学分还没达到学分上限的入队，即没有先修课的课程入队
{queuein(&q,i);outdegree[i]--;xf+=CGraph->courses[i].course.xf;}
m=0;xf=0;queuein(&q,-1);jxq++;
while(1)
{
i=queueout(&q);
queuein(q2,i);
if(i!=-1)
{
m++;
for(j=0;j<CGraph->num;j++)
if(j!=i)
{
if(outdegree[j]==0&&(xf+CGraph->courses[j].course.xf)<=CGraph->xfsx)/////////将之前因学分上限受制的出度为零的入队，即没有先修课的课程入队
{queuein(&q,j);outdegree[j]--;xf+=CGraph->courses[j].course.xf;}
else{
p=CGraph->courses[j].firstnext;
while(p)
{
if(p->adjvex==i)
{
outdegree[j]--;
if(outdegree[j]==0&&(xf+CGraph->courses[i].course.xf)<=CGraph->xfsx)/////////出度为零的入队
{queuein(&q,j);outdegree[j]--;pd=1;xf+=CGraph->courses[i].course.xf;}
}
p=p->pre;
}
}
}
}
else
{if(pd){pd=0;queuein(&q,-1);jxq++;xf=0;}else break;}
}
if(jxq>CGraph->xqs){printf("\n错误报告：\n在%d学期内是无法修完这些课程\n",CGraph->xqs);exit(0);}
if(m<CGraph->num)
{
printf("\n错误报告：\n");
for(i=0;i<CGraph->num;i++)
if(outdegree[i]>0)
printf("%s ",CGraph->courses[i].course.id);
printf("存在循环，因此课程安排不了\n");
IsCricle=1;
}
}

void layout1(AlGraph *CGraph,queue *q)////////////////编排1/////
{
printf("\n学生在各学期中的学习负担尽量均匀:\n\n");
int i,j,xq=1,cxq=CGraph->xqs-jxq,ck[20];
float xf,m=CGraph->num/CGraph->xqs*1.0f;//m是每学期要学的课程数
queue q1=*q;////
while(!queueempty(&q1))
{
for(i=0;i<20;i++)ck[i]=-1;
for(i=0;i<m+1;i++)
{
j=queueout(&q1);
if(j==-1)break;
ck[i]=j;
}
if(ck[0]!=-1)
{
printf("\n第%d学期学：",xq++);
xf=0;i=0;
do{
j=ck[i];
printf(" %s ",CGraph->courses[j].course.id);i++;xf+=CGraph->courses[j].course.xf;
}while(ck[i]!=-1);
printf("获得学分是%.2f\n",xf);
}
}
}

void layout2(AlGraph *CGraph,queue *q)////////////////编排2
{
printf("\n课程尽可能地集中在前几个学期中:\n\n");
int i,j,xq=1;float xf;
printf("\n第%d学期学：",xq++);xf=0;
queue q1=*q;////
for(i=0;i<CGraph->num;)
{
j=queueout(&q1);
if(j!=-1)
{printf(" %s ",CGraph->courses[j].course.id);i++;xf+=CGraph->courses[j].course.xf;}
else {printf("获得学分是%.2f\n第%d学期学：",xf,xq++);xf=0;}
}
while(xq<=CGraph->xqs){printf("获得学分是%.2f\n第%d学期学：无\t",xf,xq++);xf=0;}
printf("获得学分是%.2f\n");
}

void main()
{
int choice;
queue q;//用来存放已编排好的课程
queueinit(&q);///////////////队初始化
AlGraph CGraph;//课程图
fflush(stdin);/////////////////////////////////////////////清空输入流
CGraph=input();//输入并建立课程图
system("cls");//用来清屏
output(CGraph);///////////////输出先修关系
printf("\n\n");
fflush(stdin);/////////////////////////////////////////////清空输入流
judgingcricle(&CGraph,&q);////////判断是否有环
if(!IsCricle)
{
printf("请选择编排策略:\n");
printf("1.使学生在各学期中的学习负担尽量均匀;\n");
printf("2.使课程尽可能地集中在前几个学期中。\n");
printf("请选择:");
// scanf("%d",&choice);
// fflush(stdin);/////////////////////////////////////////////清空输入流
// if(choice==1)
layout1(&CGraph,&q);////////////////编排1
// else
layout2(&CGraph,&q);////////////////编排2
}
}