基于拓扑集合划分的教务课程编排模拟程序课程设计报告.doc

东北大学计算机科学与工程学院数据结构课程设计报告题目 教务课程计划安排课题组长 课题组成员 专业名称 计算机科学与技术班级 指导教师 2016 年 1月课程设计任务书题目：教务课程计划安排问题描述：拓扑集合的划分可以解决教务课程计划安排问题。高校每学年含两学期，每学期的教学周数和学分均有上限。在教学计划一定的情况下，开设的课程必须满足次序关系。拓扑集合的划分与拓扑排序的算法类似。设计要求：设计基于拓扑集合划分的教务课程编排模拟程序。（1）采用图邻接表、栈等数据结构。（2）可以随机、文件及人工输入数据。（3）计算课程安排的最优划分，尽量使学期最短。（4）可以统计数据并满足必要的约束条件。（5）可以查询和更新数据。（6）其他完善性或拓展性功能。指导教师签字：年月日目录1 课题概述1 1.1 课题任务1 1.2 课题原理1 1.3 相关知识32 需求分析4 2.1 课题调研4 2.2 用户需求分析53 方案设计7 3.1 总体功能设计7 3.2 数据结构设计8 3.3 函数原型设计10 3.4 主算法设计12 3.5 用户界面设计13 3.6 输入输出设计144 方案实现15 4.1 开发环境与工具15 4.2 程序设计关键技术16 4.3 个人设计实现（按组员分工）16 4.3.1 *设计实现17 4.3.2 *设计实现185 测试与调试23 5.1 个人测试（按组员分工）23 5.1.1*测试23 5.1.2*测试24 5.2 组装与系统测试33 5.3 系统运行366 课题总结39 6.1 课题评价39 6.2 团队协作40 6.3 个人设计小结（按组员分工）42 6.3.1*设计小结42 6.3.1*设计小结427 附录50 A 课题任务分工50 A-1 课题程序设计分工50 A-2 课题报告分工51 B 课题设计文档（光盘）52 B-1课程设计报告（电子版）52 B-2源程序代码（*.H，*.CPP）52 B-3工程与可执行文件52 B-4屏幕演示录像文件（可选）52 C 使用手册（可选）53 C.1 运行环境说明53 C.2 操作说明541 课题概述1.1 课题任务 拓扑集合的划分可以解决教务课程计划安排问题。高校每学年含两学期，每学期的教学周数和学分均有上限。在教学计划一定的情况下，开设的课程必须满足次序关系。拓扑集合的划分与拓扑排序的算法类似。 设计基于拓扑集合划分的教务课程编排模拟程序。 （1）采用图邻接表、栈等数据结构。（2）可以随机、文件及人工输入数据。（3）计算课程安排的最优划分，尽量使学期最短。（4）可以统计数据并满足必要的约束条件。（5）可以查询和更新数据。（6）其他完善性或拓展性功能。1.2 课题原理教务课程安排可以用拓扑集合的划分来解决，而拓扑集合的划分类似拓扑排序的算法。可以通过拓扑排序的知识结合教务课程计划安排的实际情况来安排课程解决问题。依教务课程设计的课程图叫做AOV网，不应该在AOV网中出现环，因为环意味着该课程以及为先决条件也就是在学习该课程之前要先学习完成该课程，这是荒谬的。进行拓扑排序的方法如下：首先在有向图中选一个没有前驱结点的顶点输出之；然后从图中删去该顶点和所有以它为尾的弧；重复上述两部，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。后一种说明有向图中存在环。而进行课程安排的算法类似拓扑排序，需结合约束条件比如周数上限和学分上限。在安排一门课程之前必须要先将其前面所需先完成的课程学习完毕。直至安排完所有课程，输出安排结果和所需学期数。1.3 相关知识 AOV网（是一个有向无环图（Directed Acycline Graph，DAG图）AOV网中，如果顶点Vi表示的活动在和顶点Vj表示的活动之前进行，则称Vi是Vj的前驱顶点，Vj是Vi后继顶点。拓扑排序就是将有向无环图中的各个顶点排成一个序列，使得所有的前去后继关系都得到满足。对于相互之间没有次序关系的顶点，在拓扑排序的序列中可以处在任意的位置。因此，拓扑排序的结果往往是不唯一的。2 需求分析2.1 课题调研高校教务课程设计的安排需要根据每学期的教学周数上限和每位学生每学期修的学分上限来安排课程。在待安排的课程信息中，可以得到每门课程的完成学习的周数和学完该门课程修得的学分；并且根据实际情况创建有向无环图，然后根据有向无环图编排课程计划。编排课程计划时，要考虑实际情况，比如计算机专业的学生，要学习一系列课程，其中有些课程是基础课，独立于其他课程，如高等数学；而另一些课程必须在学完作为他的基础的先修课程才能开始。如在学习程序设计基础和离散数学学完之前就不能开始学习数据结构。这些先决条件定义了课程之间的优先关系。有向边表示先决条件，若课程i是课程j的先决条件，则图中有弧。 2.2 用户需求分析此课题是针对安排课程人员和学生；安排课程人员在安排课程时会输入课程信息，创建课程信息图（有向无环图），可以在使用系统时人工输入这些课程信息，也可以通过文件输入快捷创建课程信息图。另外，也可以更新安排好的课表，比如课程名字，但是不允许更改已编排好的课程的学分和周数，因为更改周数和学分会使已编排好的课程失去作用。系统还提供统计功能，便于统计每学期的课程修得的学分。学生可以通过系统查询已编排好的课表，在查询功能可以根据学期序号查询，也可以根据课程名字查询还可以查询所有的课程。学生想要查到所查课程的对应的学期序号和课程学分。3 方案设计3.1 总体功能设计1、 编排课程表 (1)-人工创建课程图 (2)-文件创建课程图 (3)-拓扑编排课程表2、查询课程表 (1)-依课程名字查询 (2)-依学期序号查询 (3)-查询全部课程3、更新课程表4、统计课程表3.2 数据结构设计1、 课程图以有向图的邻接表存储结构实现表 3.2.1 邻接表数据结构设计表struct ArcNode /表节点 int adjvex; /该弧所指向的顶点的位置 struct ArcNode *nextarc; /指向下一条弧的指针 struct VertexType /顶点数据类型 int Num; /课程序号char Name20; /课程名字float Point; /学分int Weeks; /周数bool marks; /访问标记int term; /学期序号int Indegree; /入度 int Outdegree; /出度struct VNode /头结点 VertexType data; /顶点信息ArcNode *firstarc; /指向第一条依附该顶点的弧的指针typedef struct ALGraph /图结构 VNode AdjListMAX_VERTEX_NUM; /顶点表int vexnum; /图的当前顶点数int arcnum; /边数void GhPrint(ALGraph G) /输出邻接表图顶点信息void GhArc(ALGraph G) /输出边的关系int GLocateVex(ALGraph G,int x) /判断给定点是否存在，若存在则返回1，否则返回02、 借助队列实现拓扑排序算法设计表 3.2.2 队列数据结构设计表struct Queue /队列结构定义 int Top,Tail; /队头，队尾VNode *a20; /队列数据类型 VNode *Front(); /取队首元素 void Clear(); /清空队列void Pop(); /删除队首元素void Push(VNode *e); /队尾插入元素bool Empty(); /判空函数3.3 函数原型设计表 3.3.1 函数原型设计表函数原型参数功能void Menu()无功能菜单void FileCreate(ALGraph &G)ALGraph &G文件方式创建课程图void CreateALGraph(ALGraph &G)ALGraph &G 人工方式创建课程图void CourseSort(ALGraph G)ALGraph G拓扑编排课程void SearchCourse()无查询课程void Tongji()无统计课表信息void Update()无更新课表信息3.4 主算法设计 1、创建课程图（以邻接表结构实现） 1-人工输入：输入课程编号、名字、周数和学分；输入课程的优先关系； 2-文件输入：从存储在.txt文档文件里面读取课程信息，包括课程编号、名字、周数和学分；然后手动输入课程的优先关系； 2、拓扑编排课程 1-输入每学期的周数和学分上限； 2-将图中入度为零的顶点入队列，并记录本次入队的节点个数m； 3-队列不空的时候，取队首元素，然后将其所指向的顶点入度减一，然后安排该课程，并同时设一变量n,每安排一门课程n+,当nm时，表示接下来要安排的课程与当前安排的课程有优先关系，将该课程的周数与学分与上述剩余周数和剩余学分比较，在同事满足的条件下可以安排在本学期，剩余周数和剩余学分为减去当前课程的周数和学分；否则，安排在下一学期，剩余周数和学分为周数上限和学分上限减去当前周数和学分； 4-重复2、3步骤，直到图中没有零入度顶点； 3、更新功能 输入课程名字，将文件中已编排好的课程读取到数组中，通过比较课程名字找到要更新的课程，然后可以更改课程名字；更新可以连续进行；更新完毕将更新后的课程表存放到文件中保存；4、统计功能 类似更新算法的前面的步骤，激情课程表读取出来，根据学期序号，统计周数和学分总和；3.5 用户界面设计3.6 输入输出设计 1、输入设计：人工输入：分行输入课程编号、名称、周数和学期；空格作为间隔。输入周数学分上限，输入弧关系，空格间隔；文件输入：读取.txt文件中的课程编号、名称、周数和学期信息，收入弧的关系，空格间隔； 2、输出设计： 输出格式如下图：4 方案实现4.1开发环境与工具开发工具为：Code：Blocks 13.124.2 程序设计关键技术 本程序设计的关键技术为基于拓扑集合划分的教务课程计划安排；4.3 个人设计实现4.3.1张刘涛设计实现部分/队列定义struct Queueint Top,Tail;VNode *a20;VNode *Front();void Clear();void Pop();void Push(VNode *e);bool Empty();/入队列void Queue:Push(VNode *e)aTail+=e;return ;/清空队列void Queue:Clear()Top=Tail=0;return ;/出队列void Queue:Pop()Top+;return ;/取队列首元素VNode *Queue:Front()return aTop;/判断队列是否为空bool Queue:Empty()return Top=Tail;/边节点struct ArcNodeint adjvex;struct ArcNode *nextarc;/顶点信息struct VertexTypeint Num;char Name20;float Point;int Weeks;bool marks;int term;int Indegree;int Outdegree;/头结点typedef struct VNodeVertexType data;ArcNode *firstarc;VNode;/图的结构设计typedef struct ALGraph VNode AdjListMAX_VERTEX_NUM;int vexnum;int arcnum;ALGraph;/判断图中是否存在顶点x，若存在则返回x的位置，否则-1int GLocateVex(ALGraph G,int x)int i,j=-1;for(i=0;iG.vexnum;i+)if(G.AdjListi.data.Num=x) j=i; break; return j;/打印课程图弧的关系void GhArc(ALGraph G)int i;ArcNode *q;printf(ttt所创建课程图的课程关系如下(编号代替课程表示)n);for(i=0;i%dn,G.AdjListi.data.Num,G.AdjListq-adjvex.data.Num); q=q-nextarc;/输出课程图信息void GhPrint(ALGraph G)int i;printf(tttt 课程信息如下:nnttt课程编号 课程名称 学分 周数n);for(i=0;iG.vexnum;i+)printf(nttt%dt%10st%.1ft%dnn,G.AdjListi.data.Num,G.AdjListi.data.Name,G.AdjListi.data.Point,G.AdjListi.data.Weeks);/判断课程图中是否存在入度为0的顶点，若存在返回1，否则返回0bool Find(ALGraph G)int j=0;for(int i=0;iG.vexnum;i+)if(G.AdjListi.data.marks=0)j=1; break;return j;/以文件读取形式创建课程图void FileCreate(ALGraph &G)FILE *fp;int i=0;int m,n,k,s1,s2;ArcNode *s;fp=fopen(entering.txt,a+);if(fp=fopen(entering.txt,a+)=NULL)printf(.打开文件失败!);exit(0);elsewhile(!feof(fp)fscanf(fp,%d%s%f%d,&G.AdjListi.data.Num,&G.AdjListi.data.Name,&G.AdjListi.data.Point,&G.AdjListi.data.Weeks);G.AdjListi.firstarc=NULL;G.AdjListi.data.marks=0;G.AdjListi.data.term=0;G.AdjListi.data.Outdegree=0;G.AdjListi.data.Indegree=0;i+;fclose(fp);G.vexnum=i;printf(tttt读取课程信息成功！nn);GhPrint(G);printf(ttt请输入课程图的边数：);scanf(%d,&G.arcnum);printf(nttt请输入顶点关系:(课程编号(弧尾) 课程编号(弧头)n);for(int j=1;jadjvex=n; s-nextarc=G.AdjListm.firstarc; G.AdjListm.firstarc=s;G.AdjListm.data.Outdegree+; G.AdjListn.data.Indegree+; /人工输入创建课程图void CreateALGraph(ALGraph &G)int i,j,m,n,k,s1,s2; ArcNode *s;printf(请输入所创建课程图的顶点个数和边数：);scanf(%d %d,&i,&j);G.vexnum=i;G.arcnum=j;printf(n请输入顶点的信息顺序如下:n);printf(n课程编号 课程名称 学分 周数n);for(i=0;iG.vexnum;i+)scanf(%d%s%f%d,&G.AdjListi.data.Num,&G.AdjListi.data.Name,&G.AdjListi.data.Point,&G.AdjListi.data.Weeks);G.AdjListi.firstarc=NULL;G.AdjListi.data.marks=0;G.AdjListi.data.term=0;G.AdjListi.data.Outdegree=0;G.AdjListi.data.Indegree=0;printf(n请输入顶点关系:(课程编号(弧尾) 课程编号(弧头)n);for(j=1;jadjvex=n; s-nextarc=G.AdjListm.firstarc; G.AdjListm.firstarc=s;G.AdjListm.data.Outdegree+; G.AdjListn.data.Indegree+; /printf(创建成功!n);/拓扑编排课程表void CourseSort(ALGraph G)int i,m,n,k=0,s=0,a=0;int Term=1;FILE *fp1;float t=0;/学期剩余学分VNode *v;VNode Sort50;ArcNode *p;int Maxweeks;float Maxpoints;printf(ttt请输入每学期的周数和学分上限n);printf(nttt周数上限:);scanf(%d,&Maxweeks);printf(nttt学分上限:);scanf(%f,&Maxpoints);s=Maxweeks;t=Maxpoints;system(cls);Queue Q;Q.Clear();while(Find(G) a=0;m=0,n=0;for(i=0;ifirstarc; while(p) G.AdjListp-adjvex.data.Indegree-;/入度减一p=p-nextarc; if(v-data.Pointdata.Weeksdata.term=Term;Sortk+=*v; else Term+;/学期数加一t=Maxpoints;v-data.term=Term;Sortk+=*v; if(n=m) for(int j=0;j=(Maxweeks-Sortj.data.Weeks)s=Maxweeks-Sortj.data.Weeks;t=t-v-data.Point; else s=Maxweeks; t=t-v-data.Point; printf(经最优划分使学期最短的情况下安排这些课程的最少学期数是: %dntttt课程表如下n,Term);for(int j=1;j=Term;j+)printf(ntttt第%d学期的课程如下nn,j);printf(ttt课程编号 课程名称 学分 周数 学期数n);for(int m=0;mk;m+)if(Sortm.data.term=j)printf(nttt%dt%10st%.2ft%dt%dtn,Sortm.data.Num,Sortm.data.Name,Sortm.data.Point,Sortm.data.Weeks,Sortm.data.term);fp1=fopen(beifen,w+);if(fp1=fopen(beifen.txt,w+)=NULL)printf(打开文件失败!);exit(0);else for(int d=0;dk;d+)fprintf(fp1,%dt%10st%.2ft%dt%dtn,Sortd.data.Num,Sortd.data.Name,Sortd.data.Point,Sortd.data.Weeks,Sortd.data.term);fclose(fp1);/查询已编排课程表void SearchCourse()VNode S50;char s20;int d=0,j=0,m=1,n,Term=0;FILE *fp2;fp2=fopen(beifen.txt,a+);if(fp2=fopen(beifen.txt,a+)=NULL)printf(打开文件失败!);exit(0);elsewhile(!feof(fp2)fscanf(fp2,%d%s%f%d%d,&Sd.data.Num,&Sd.data.Name,&Sd.data.Point,&Sd.data.Weeks,&Sd.data.term);d+;fclose(fp2);for(int s=0;s=Term)Term=Ss.data.term;while(m)system(cls);printf(ntttt1-依课程名字查询nntttt2-依学期序号查询nntttt3-查询全部课程nntttt输入:); scanf(%d,&n);switch(n)case 1:system(cls);j=0; printf(n请输入你要查询的课程名字：); scanf(%s,s); system(cls); for(int i=0;id;i+) if(strcmp(Si.data.Name,s)=0) printf(ntttt您所查的课程信息为：n); printf(nttt课程编号 课程名称 学分 周数 学期数n); printf(nttt%dt%10st%.2ft%dt%dtn,Si.data.Num,Si.data.Name,Si.data.Point,Si.data.Weeks,Si.data.term); j=1; break; if(j=0) printf(nttt.未查找到你所要查找的课程信息!n); break;case 2:system(cls);int t;printf(n请输入您要查询的学期号：);scanf(%d,&t);system(cls);if(t=Term)printf(ntttt第%d学期的课程如下nn,t);printf(ttt课程编号 课程名称 学分 周数 学期数nn);for(int i=0;id;i+)if(Si.data.term=t) printf(nttt%dt%10st%.2ft%dt%dtn,Si.data.Num,Si.data.Name,Si.data.Point,Si.data.Weeks,Si.data.term); elseprintf(nttt.输入学期序号过大，该学期不存在!n);break;case 3:system(cls);for(int i=1;i=Term;i+) printf(ntttt 第%d学期的课程如下nn,i); printf(ttt课程编号 课程名称 学分 周数 学期数n); for(int k=0;kd;k+) if(Sk.data.term=i) printf(nttt%dt%10st%.2ft%dt%dtn,Sk.data.Num,Sk.data.Name,Sk.data.Point,Sk.data.Weeks,Sk.data.term); break;default:printf(ntttt.输入错误!n);printf(nnttt是否继续查询？t(是-输入1，否-输入0)nnttt输入：);scanf(%d,&m);/创建课程图输入设计函数void func1(ALGraph G)int i;printf(ntttt请选择创建课程图的方式：n);printf(ntttt1-人工输入n);printf(ntttt2-文件输入nntttt输入：);scanf(%d,&i);switch(i)case 1:system(cls);CreateALGraph(G);break;case 2:system(cls);FileCreate(G);break;default:printf(输入错误!);exit(0);system(cls);GhArc(G);GhPrint(G);CourseSort(G);printf(nnttt教务课程计划安排成功!n);/菜单函数void Menu()int n;ALGraph G;while(n)system(cls);int i;printf(tttt欢迎使用课程设计系统n);printf(ntttt1-新建课程表n);printf(ntttt2-查询已排课程n);printf(ntttt3-更新课程表n);printf(ntttt4-统计信息nntttt输入：);scanf(%d,&i);switch(i)case 1:system(cls);func1(G);break;case 2:system(cls);SearchCourse();system(cls);break;case 3:system(cls);Update();system(cls);break;case 4:system(cls);Tongji();break;default:printf(输入错误!);exit(0);system(cls);printf(nnttt是否返回主菜单？(1-返回主菜单，0-退出系统)nnttt输入：);scanf(%d,&n);system(cls);printf(nntttt谢谢使用课程设计系统!nn);4.3.2 梁思宇设计实现部分/统计功能实现void Tongji() VNode S50;int d=0,Term=0,p1=0; float p2=0;FILE *fp2;fp2=fopen(beifen.txt,a+);if(fp2=fopen(beifen.txt,a+)=NULL)printf(打开文件失败!);exit(0);elsewhile(!feof(fp2)fscanf(fp2,%d%s%f%d%d,&Sd.data.Num,&Sd.data.Name,&Sd.data.Point,&Sd.data.Weeks,&Sd.data.term);d+;fclose(fp2);for(int i=0;i=Term)Term=Si.data.term;for(int j=1;j=Term;j+)p1=0;p2=0;for(int k=0;kd;k+)if(Sk.data.term=j)p1+;p2=p2+Sk.data.Point;printf(nttt第%d学期共需学习%d门课程，修得%.2f学分!n,j,p1,p2); /更新功能实现 void Update() char n20; VNode S50; int i,s,d=0,j=0; FILE *fp3,*fp4;fp3=fopen(beifen.txt,a+);if(fp3=fopen(beifen.txt,a+)=NULL)printf(打开文件失败!);exit(0);elsewhile(!feof(fp3)fscanf(fp3,%d%s%f%d%d,&Sd.data.Num,&Sd.data.Name,&Sd.data.Point,&Sd.data.Weeks,&Sd.data.term);d+;fclose(fp3);while(s)system(cls);j=0; printf(输入你要更新的课程的名字：); scanf(%s,n); for(i=0;id-1;i+)if(strcmp(Si.data.Name,n)=0)printf(n您所要更新的课程信息为：n); printf(n课程编号 课程名称 学分 周数 学期数n) printf(n%dt%10st%.2ft%dt%dtn,Si.data.Num,Si.data.Name,Si.data.Point,Si.data.Weeks,Si.data.term); j+; break;if(j=0)printf(n未查找您要更新的课程!n);else printf(n%s 更新为： ,Si.data.Name); scanf(%s,Si.data.Name); system(cls); printf(n更新后的信息为：n); printf(n课程编号 课程名称 学分 周数 学期数n); printf(n%dt%10st%.2ft%dt%dtn,Si.data.Num,Si.data.Name,Si.data.Point,Si.data.Weeks,Si.data.term); fp4=fopen(beifen.txt,w+); if(fp4=fopen(beifen.txt,w+)=NULL) printf(打开文件失败!); exit(0); else for(int k=0;kd-1;k+) fprintf(fp4,%dt%10st%.2ft%dt%dtn,Sk.data.Num,Sk.data.Name,Sk.data.Point,Sk.data.Weeks,Sk.data.term); fclose(fp4); printf(n更新成功!n);printf(n是否继续更新？t(是-输入1，否-输入0)nn输入：); scanf(%d,&s);5 测试与调试5.1 个人测试 5.1.1测试 1-人工输入测试2-文件输入测试3-查询课程测试查询全部课程5.1.2测试 1-更新测试2-统计测试5.2 组装与系统测试 各部分组装起来之后系统运行正常，没有出现冲突或者错误的地方；5.3 系统运行系统运行采用从文件读取的方式输入测试：查询全部课程： 更新课程：统计课程：6 课题总结6.1 课题评价我们组的这个课题比较实际化，但在开始分析的时候还是有点不太理解；经过询问老师、上网查询和组内讨论拟定了方案；本课题围绕拓扑排序的原理以及方法制定方案，由于以前没有练习过拓扑排序类的题目，此次我们首先对拓扑排序的知识做了一番透彻的理解，并掌握了拓扑排序的原理方法。由于高校每学年有两个学期，每学期有学分和周数上限，安排的课程之间有的存在优先级关系，这类课程就必须满足其给定的优先级关系，实现先后安排存在这样关系的两门课程，此时又要