学期授课计划编制教材

1、学期授课计划编制”实验报告 实验目的 1. 题目：学期授课计划编制 2. 问题描述 大学每个学期的课程授课有学分及授课门数上限的规定。课程之间有先行课 的限制。设计编制学期授课计划，使得总的教学时长为最短的拓扑集合划分 程序。 3. 实验要求 设计大学四年制授课计划编制的模拟程序。 （1）采用邻接表或邻接矩阵存储结构。 （2）使用栈或队列等作为拓扑排序的辅助数据结构。 （3）可以尝试采用深度优先遍历求解问题。 需求分析 1. 根据我的调查及生活经验， 学期授课计划的编制需要以下几个方面的信息汇总才可以实 现 （ 1） 确定学期数，以及一个学期的最大学分上限和最大的课程数目上限。 （ 2） 确定

2、一共需要上几门课，一级每门课的学分。 （ 3） 确定课程的先行关系。 （ 4） 综合以上信息采用拓扑排序制定出总的教学时长最短的教学授课计划。 2. 模块流程图 主程序模块 栈模块 排序模块 3. 性能需求 本程序在运行期间， 为了避免在运行大量数据时不会出错， 并且能够在很短的时间内将 运行结果稳定输出，就需要系统达到安全性能好， 可靠性高，稳定性强，处理数据迅速 等特点。 三、程序实现 本程序采取数据结构模块化编程， 很好的实现了实验所要求的各项功能， 本程序分为三个主 要模块：主程序模块、栈模块、排序模块。 1. 主程序模块 int main() printf( 学期授课计划编制 n);

3、 printf( /AOV-网:顶点表示活动，弧表示活动间优先关系的有向图； int CONTINUE = 1; while(CONTINUE != 0) printf(n); ALGraph f; / 图的邻接表存储； printf( 请输入学期总数 :); scanf(%d, printf( 请输入每学期的学分上限 :); scanf(%d, CreateGraph(f); Display(f); TopologicalSort(f); printf(n 按 1 继续，按 0 结束 :); scanf(%d, return 0; 2. 栈模块 typedef enumDGGraphKind

4、; / 有向图 ,有向网 ,无向图 ,无向网 ; typedef struct ArcNode/ 弧结构； int adjvex; / 该弧所指向的顶点的位置 ; struct ArcNode * nextarc; / 指向下一条弧的指针 ; InfoType * info; / 网的权值指针 ; ArcNode; / 表结点 ; typedef struct VertexType data; / 顶点信息 ; ArcNode *firstarc; / 第一个表结点的地址 ,指向第一条依附该顶点的弧的指针 ; VNode, AdjListMAX_VERTEX_NUM; typedef stru

5、ct AdjList vertices,vertices2; / 分别存课程名和学分； int vexnum,arcnum; int kind; ALGraph; int LocateVex(ALGraph G,VertexType u) int i; for(i=0;iG.vexnum;+i) if(strcmp(u, G.verticesi.data)=0) return i; return -1; Status CreateGraph(ALGraph VertexType v1,v2; / 顶点信息； ArcNode * p; / 指向第一条依附某顶点的弧的指针； printf( 请输入

6、教学计划的课程数 : ); scanf(%d, printf( 请输入课程先修关系数(弧的数目): ); scanf(%d, printf( 请输入 %d 个课程的代表值 (如 :c01):n,G.vexnum); for(i=0;iG.vexnum;+i) scanf(%s,G.verticesi.data); G.verticesi.firstarc=NULL; printf( 请输入 %d 个课程的学分值 :n,(G).vexnum); for(i=0;iG.vexnum;+i) scanf(%s,G.vertices2i.data); printf( 请顺序输入每条弧的弧尾和弧头 (以

7、空格作为间隔 ):n); for(k=0;kadjvex = j; p-info = NULL; p-nextarc = G.verticesi.firstarc; G.verticesi.firstarc = p; return OK; void Display(ALGraph G) int i; ArcNode * p; switch(G.kind) case DG: printf(有向图 n); printf(%d 个顶点： n,G.vexnum); for(i=0;iG.vexnum;+i) printf(%s ,G.verticesi.data); printf(n%d 条弧 :n,

8、G.arcnum); for(i=0;iG.vexnum;i+) p=G.verticesi.firstarc; printf(n); void FindInDegree(ALGraph G,int indegree) int i; ArcNode *p; for(i=0;iG.vexnum;i+) indegreei=0; for(i=0;iadjvex+; p=p-nextarc; typedef int SElemType; #define STACK_INIT_SIZE 10 #define STACKINCREMENT 2 typedef struct SqStack SElemTy

9、pe *base; SElemType *top; int stacksize; SqStack; Status InitStack(SqStack *S) (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; void ClearStack(SqStack *S) /清空栈的操作 S-top=S-base; Status Stack

10、Empty(SqStack S) if(S.top=S.base) return TRUE; else return FALSE; 3. 排序模块 Status Pop(SqStack *S,SElemType *e) if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK; Status Push(SqStack *S,SElemType e) if(*S).top-(*S).base=(*S).stacksize) (*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+

11、STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return OK; Status zxf(ALGraph G) int z=0; for(int i=0; i G.vexnum; i+) z += atoi(G.vertices2i.data); return z; typedef int pathoneMAX_CLASS_NUM; typedef

12、 int pathtwoMAX_CLASS_NUM; Status TopologicalSort(ALGraph G) int i,k,count,indegreeMAX_VERTEX_NUM; bool has = false; SqStack S; pathone a; pathtwo b; ArcNode * p; FindInDegree(G,indegree); InitStack( for(i=0;inextarc) k=p-adjvex; if(!(-indegreek) Push( if(countG.vexnum) printf( 此有向图有回路 n); return ER

13、ROR; else printf( 为一个拓扑序列。 nn); has=true; int pattern=2; FindInDegree(G,indegree); / 对各顶点求入度 indegree0.vernum-1 ; ClearStack( printf(=n); printf( 教学计划如下： n); int xq = 1; / 学期数 ; int xfh; / 学分和； int now=0; int top = G.vexnum / term_num ; / 平均每学期课程数； int pjxf = zxf(G) / term_num ; / 每学期平均学分； while(xq

14、= term_num + 1) int result20; / 某个学期的课程； int m = 0; xfh = 0; now=0; / 当前学期课程数 ； for(i=0;iG.vexnum;+i) if(0 = indegreei) Push( if(xq = term_num+1 while(!StackEmpty(S) break; if(pattern = 1) if(xq!=term_num/ 2 now = 0; break; if(pattern = 2) if(xq!=1 now = 0; break; indegreei-; / 减为 -1,避免被再次计入； for(p=

15、G.verticesi.firstarc; p; p=p-nextarc) k=p-adjvex; indegreek-; if(indegreek=0) Push( resultm=i; m+; if(xq = term_num) printf( 第%d 个学期的课程为： ,xq); for(int j=0; jm; j+) printf( 课程 %s ,G.verticesresultj.data); printf(n); xq+; ClearStack( printf(=n); return OK; 四、程序运行截图 程序开始运行界面 测试数据：学期一共为 2 个学期，每个学期上限 10

16、学分，总共教学计划安排 5 门课，分别 为 c1 课 2 学分， c2 课 6 学分， c3 课 4 学分， c4 课 6 学分， c5 课 2 学分。必须先上 c1 课再 上 c2 课，先上 c3课再上 c4 课，根据总教学时间最少的要求排课，输出的排课结果为：第 一学期 c5、c3，第二学期 c4、 c1。还有 c2 没有安排，所以无法排课，排课失败。 测试数据：学期一共为 1 个学期，每个学期上限 10 学分，总共教学计划安排 3 门课，分别 为 c1 课 2 学分， c2 课 2 学分， c3 课 2 学分。必须先上 c1 课再上 c3 课，根据总教学时间最 少的要求排课，输出的排课结

17、果为：第一学期c2、 c1、c3。排课成功。 五、调试总结 1. 由于对于指针的操作掌握的不是很熟练， 导致越界访问现象频频发生， 因此， 今后自己 应该加强对指针的掌握和使用，以便可以更加顺利的编程。 2. 各操作时空复杂性比较合理，时空复杂度均为 O（ n），O（1）。 3. 本程序作业采用数据结构抽象的程序设计方法， 使得设计时思路清晰， 实现时调试顺利， 各模块具有较好的可重复性，确实得到了一次良好的程序设计训练。 六、参考文献 1 严蔚敏、吴伟民 编著. 数据结构题集（C 语言版）. 北京：清华大学出 版社. 1999 2 严蔚敏、吴伟民 编著.数据结构（C语言版）. 北京：清华大学

18、出版社 . 2007 七、程序清单 #include #include #include #include #include / floor（）,ceil（）,abs（） #include using namespace std; #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; / Status 是函数的返回类型； typedef int Boolean; #define MAX_NAME 10/ 顶点字符串的最大长度 ; #define

19、MAX_CLASS_NUM 100 int Z=0; int X=0; int term_num,credit_lim,q=1; typedef int InfoType; typedef char VertexTypeMAX_NAME; / 字符串类型 ; #define MAX_VERTEX_NUM 100 typedef enumDGGraphKind;/ 有向图 ,有向网 ,无向图 ,无向网 ; typedef struct ArcNode / 弧结构； int adjvex; / 该弧所指向的顶点的位置 ; struct ArcNode * nextarc;/ 指向下一条弧的指针 ;

20、 InfoType * info;/ 网的权值指针 ; ArcNode; / 表结点 ; typedef struct VertexType data; / 顶点信息 ; ArcNode *firstarc; / 第一个表结点的地址 ,指向第一条依附该顶点的弧的指针 VNode, AdjListMAX_VERTEX_NUM; typedef struct AdjList vertices,vertices2;/ 分别存课程名和学分； int vexnum,arcnum; int kind; ALGraph; int LocateVex(ALGraph G,VertexType u) int i

21、; for(i=0;iG.vexnum;+i) if(strcmp(u, G.verticesi.data)=0) return i; return -1; Status CreateGraph(ALGraph VertexType v1,v2; / 顶点信息； ArcNode * p;/ 指向第一条依附某顶点的弧的指针； printf( 请输入教学计划的课程数 : ); scanf(%d, printf( 请输入课程先修关系数(弧的数目): ); scanf(%d, printf( 请输入 %d 个课程的代表值 ( 如 :c01):n,G.vexnum); for(i=0;iG.vexnum

22、;+i) scanf(%s,G.verticesi.data); G.verticesi.firstarc=NULL; printf( 请输入 %d 个课程的学分值 :n,(G).vexnum); for(i=0;iG.vexnum;+i) scanf(%s,G.vertices2i.data); printf( 请顺序输入每条弧的弧尾和弧头 (以空格作为间隔 ):n); for(k=0;kadjvex = j; p-info = NULL; p-nextarc = G.verticesi.firstarc; G.verticesi.firstarc = p; return OK; void

23、Display(ALGraph G) int i; ArcNode * p; switch(G.kind) case DG: printf( 有向图 n); printf(%d 个顶点： n,G.vexnum); for(i=0;iG.vexnum;+i) printf(%s ,G.verticesi.data); printf(n%d 条弧 :n,G.arcnum); for(i=0;iadjvex.data); p=p-nextarc; printf(n); void FindInDegree(ALGraph G,int indegree) int i; ArcNode *p; for(i

24、=0;iG.vexnum;i+) indegreei=0; for(i=0;iadjvex+; p=p-nextarc; typedef int SElemType; #define STACK_INIT_SIZE 10 #define STACKINCREMENT 2 typedef struct SqStack SElemType *base; SElemType *top; int stacksize; SqStack; Status InitStack(SqStack *S) (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SE

25、lemType); if(!(*S).base) exit(OVERFLOW); (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK; void ClearStack(SqStack *S) /清空栈的操作 S-top=S-base; Status StackEmpty(SqStack S) if(S.top=S.base) return TRUE; else return FALSE; Status Push(SqStack *S,SElemType e) if(*S).top-(*S).base=(*S).stacks

26、ize) (*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return OK; Status zxf(ALGraph G) int z=0; for(int i=0; i G.vexnum; i+) z += atoi(G.vertices2

27、i.data); return z; typedef int pathoneMAX_CLASS_NUM; typedef int pathtwoMAX_CLASS_NUM; Status TopologicalSort(ALGraph G) int i,k,count,indegreeMAX_VERTEX_NUM; bool has = false; SqStack S; pathone a; pathtwo b; ArcNode * p; FindInDegree(G,indegree); InitStack( for(i=0;inextarc) k=p-adjvex; if(!(-indegreek) Push( if(countG.vexnum) printf( 此有向图有回路 n); return ERROR; else printf( 为一个拓扑序列。 nn); has=true; int pattern=2; FindInDegree(G,indegree); / 对各顶点求入度 indegree0.vernum-1 ; ClearStack( printf(=n); printf( 教学计划如下： n); int xq = 1; / 学期数 ; int xfh; / 学分和； int