教学计划编制问题课程设计报告书.doc

任务要求: 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期，试在这样的前提下设计一个教学计划编制程序。 内容摘要: 本程序是一个教学计划的编制的问题，而由任务要求了解到的已知的条件及这次设计的目的。我们在分析问题后决定采用AOV网图来解决。 首先，了解本系统要实现的基本功能，大致划分模块。 其次，由已知条件画出先修关系图，以此来设计邻接表存储结构。 接下来，借助于栈，设计拓扑排序的流程。 最后，对系统开始进行详细的前台界面和后台程序的设计，完善系统。 教师评语: 成绩 签名: 日期: 课程设计报告书 教学计划编制问题 一 设计思想 根据任务要求及对实际情况的了解，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，采用邻接表存储结构，利用栈作辅助结构，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题——输出每学期的课程。 二 系统完成功能及功能框图 图1 系统功能框图 0 C1 1 C2 2 C3 3 C4 4 C5 5 C6 6 C7 ^ 7 C8 ^ 8 C9 9 C10 10 C11 11 C12 ^ 图2：邻接表 图3拓扑排序流程图 图4 课程先修关系图 三 核心算法及说明 （1）采用邻接表存储结构，创建图 int CreateGraph(ALGraph G) { int i, j, k; VertexType va; ArcNode *p; printf(请输入教学计划的课程数: ); scanf(%d,G.vexnum); printf( 请输入各个课程的先修课程的总和(弧总数): ); scanf(%d,G.arcnum); printf( 请输入%d个课程的课程号(最多%d个字符,数字+字母):, G.vexnum,MAX_NAME); for (i = 0;i G.vexnum;++i) { scanf(%s,G.vertices[i].data); G.vertices[i].firstarc = NULL; } printf(请输入%d个课程的学分值:,G.vexnum); for (i = 0;i G.vexnum;++i) { scanf(%d,G.vertices[i].grades); } printf(请输入下列课程的先修课程(无先修课程输入0 结束后也输入0)\n); for (k=0;kG.vexnum;++k) // 构造表结点链表,利用前插法 { printf(%s的先修课程:,G.vertices[k].data); scanf(%s,va); while (va[0]!=0) { i = LocateVex(G, va);//弧头 j = k;??????????????? //弧尾 p = (ArcNode*)malloc(sizeof(ArcNode)); p-adjvex = j; p-nextarc = G.vertices[i].firstarc; // 插在表头 G.vertices[i].firstarc = p; scanf(%s,va); } } return OK; } （2）通过栈实现拓扑排序 FindInDegree(G, indegree);???? // 对各顶点求入度 InitStack(S);????????????????? // 初始化栈 for (i = 0;i G.vexnum;++i)?? //建零入度顶点栈S if (!indegree[i]) Push(S, i);? // 入度为0者进栈 count = 0;???????????????????? // 对输出顶点计数 while (!StackEmpty(S)) { Pop(S, i); printf(%s(%d分),,G.vertices[i].data,G.vertices[i].grades); Temp[j++] = G.vertices[i];? //将当前的拓扑序列保存起来 ++count;??????????????? // 输出i号顶点并计数 for (p =G.vertices[i].firstarc; p; p=p-nextarc)// 对i号顶点的每个邻接点的入度减1 { k = p-adjvex; if (!(--indegree[k])) // 若入度减为0,则入栈 Push(S, k); } } if (