拓扑排序课程设计

课程设计报告课程名称数据结构课题名称1.拓扑排序2.成绩管理专业计算机科学与技术班级计算机1181学号201113030128姓名蔡彪指导教师刘铁武2013年6月30日湖南工程学院课程设计任务书课程名称数据结构课题1.拓扑排序2.成绩管理专业班级计算机1181学生姓名蔡彪学号201113030128指导老师刘铁武审批任务书下达日期2013年6月17日任务完成日期2013年6月30日一．设计内容：问题1：拓扑排序大学期间各专业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的，而有的则有先修后修的限定。试设计相应的课程设置程序，实现对某专业各学期的课程的排布，其中每门课需一定的课时，而各学期的总课时不能超过上限。测试数据学期课时上限数：350各课程所需学时：48课程先、后修关系如图：问题3：成绩管理编制一应用软件实现对班级成绩管理。基本功能有学生信息的增删（转入或退学）、查找（从当前点向前或向后双向的）、录入、统计（如总分，及格率等）。建议用双链表实现。194212101136578二．设计要求：课程设计报告内容说明1)需求分析程序的功能；输入输出的要求。2)概要设计程序的模块构成以及模块之间的层次结构、各模块的调用关系；每个模块的功能；课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计采用C语言定义相关的数据类型；写出各模块的类C码算法；画出各函数的调用关系图、主要函数的流程图。4)调试分析以及设计体会测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果；程序调试中遇到的问题以及解决问题的方法；课程设计过程经验教训、心得体会。5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式见附带说明。7)附录参考书目；源程序清单（带注释）成绩评定：指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分：①平时出勤（占10%）②系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%）③程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%）④设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。⑤独立完成情况（占10%）。①运行所设计的系统。三.进度安排第17周星期一星期二星期三星期四星期五星期六星期日上午8：00~12：008:30~11:308:30~11:30下午13：30~17：3013:00~16:00第18周星期一星期二星期三星期四星期五星期六星期日上午8：00~12：008:30~11:30下午13：30~17：3013:00~16:0013:00~16:00参考书籍1.《C＋＋程序设计课程设计》刘振安编著TP312C5632.《C++Builder和Delphi课程设计与系统开发案例》伍俊良清华大学出版社7-302-06072-X3.VisualC++课程设计案例精编严华峰中国水利水电出版社7-5084-2007-120044.VisualC++课程设计与系统开发案例伍俊良清华大学出版社7-302-05968-320025.VisualC++语言课程设计:案例精选与编程指导陈清华朱红东南大学出版社7-81089-275-420036.VisualC++课程设计案例精编中国水利水电出版社7-5084-1004-120027.数据结构课程设计案例精编:用C/C++描述李建学李光元吴春芳清华大学出版社7-302-14536-92007（编程平台不限，vc++,c++Builder等等。）目录课题1第一章拓扑排序…………………………………………（一）目的与要求……………………………………(二)设计方法与原理………………………………(三)需求分析………………………………第二章总体设计………………………………………………………（一）系统流程图………………………………………………（二）详细设计…………………………………………………第三章系统调试………………………………………………………（一）系统调试…………………………………………………（二）结果分析…………………………………………………第四章总结………………………………………………………………附录：源程序………………………………………………………课题2第一章成绩管理…………………………………………（一）目的与要求……………………………………(二)设计方法与原理………………………………(三)需求分析………………………………第二章总体设计………………………………………………………（一）系统流程图………………………………………………（二）详细设计…………………………………………………第三章系统调试………………………………………………………（一）系统调试…………………………………………………（二）结果分析…………………………………………………第四章总结………………………………………………………………附录：源程序………………………………………………………课题1第一章：拓扑排序（1）目的与要求：目的：（1）要求学生达到熟练掌握语言的基本知识和技能；（2）基本掌握面向对象程序设计的基本思路和方法；（3）能够利用所学的基本知识和技能，解决简单的程序设计问题。要求：（1）选择合适的存储结构，建立有向无环图，并输出该图；（2）实现拓扑排序算法；（3）运用拓扑排序实现对教学计划安排的检验。（2）设计方法与原理在AOV网中为了更好地完成工程，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划。（3）需求分析程序的功能：该程序的功能主要是根据图的拓扑排序算法，依某专业的课程先、后修关系图，实现该专业课程的排布。其中，每门课程需设定课时，而各学期的总课时不能超过上限。输入输出要求：首先，创建课程先、后关系图。其中，需要输入该关系图的结点数(课程数)、结点信息及弧的信息等；然后，输入该专业课程的学期数，并在拓扑排序过程中，依次输入某学期的课程安排。所以，最终输出为各个学期所安排的课程结果，并且，课程安排符合课程先、后关系图的一个拓扑排序。第二章：总体设计（1）系统流程图1.1.1模块功能流程图程序调用关系及模块功能运行流程如下：123图1.1程序调用关系及模块功能流程图1.1.2数据结构及数据类型图的存储结构有邻接矩阵和邻接表。在该程序中采用了邻接表来存储有向图。在邻接表中，需要定义头结点的结构体数据类型，用以存储图的结点信息，并且在每个头结点后连接一个单链表，用以存储以该头结点为弧尾，链表中结点为弧头的弧。所以还需定义表结点的结构体数据类型，用以存储图中弧的信息。最后，定义有向图的结构体数据类型，其中的数据项包含一个指向头结点首地址的指针和顶点数、弧数的整型数据类型。开始主函数main()分支选择处理创建图拓扑排序退出系统结束1.1.3拓扑排序算法拓扑排序算法描述如下：(1)在有向图中选一个没有前驱的顶点且输出之。即入度为零的结点。(2)从图中删除该顶点和所有以它为尾的弧。即以该结点为弧尾的弧的弧头结点的入度值减一。(3)重复上述两步，直至全部结点均已输出，或者当前结点中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环，拓扑排序失败。然而，在此课题中是为了依拓扑排序算法而设计课程的安排序列。显然，在同一学期里的课程是相互独立的，不存在先、后修关系。由此，对于某个学期课程的安排，其安排的课程范围是有向图中某次拓扑排序中所有没有前驱顶点结点的集合，则该学期课程的安排可以在该集合中选择，并且选择结果满足的总课时没有超过上限。同时，由此次选择结果，可以产生下个学期课程安排的范围。重复上述操作，直至所有课程都选择完。另外，还应设计一个能够检测所有课程是否在规定的学期内修完。若检测到在规定学期内课程没有修完，则需重新设定学期数或者重新进行课程安排。（2）详细设计1.2.1采用C语言定义结构体数据类型1.2.1.1头结点的顶点信息结构体数据类型typedefstructVertexType{charname[20];//顶点编号，即课程编号charsbname[20];//课程名称intOutdegree;//顶点的出度intIndegree;//顶点的入度intweight;//课时boolmark;//在拓扑排序时，标记该结点是否已访问intid;//确定该课程属于哪个学期}VertexType;1.2.1.2头结点结构体数据类型typedefstructVNode{VertexTypedata;//顶点信息ArcNode*first;//指向第一条依附该结点的弧的指针}VNode;1.2.1.3表结点结构体数据类型typedefstructArcNode{intadjvex;//该弧所指向的顶点的位置structArcNode*next;//指向下一条弧的指针}ArcNode;1.2.1.4图的结构体数据类型typedefstructGraph{VNode*head;//指向头结点首地址的指针intvexnum,arcnum;//图的定点数和弧数}Graph;1.2.1.5学期课程结构体数据类型TypedefstructSubject{intcount;//某学期所安排的课程数int*head;//某学期所安排课程对应结点在图中的存储置}Subject,*PSubject;1.2.2各模块的类C码算法1.2.2.1创建有向图的类C码算法：StatusGCreate(Graph&G){scanf(%d,G.vexnum);if(!(G.head=(VNode*)malloc(G.vexnum*sizeof(VNode))))exit(OVERFLOW);for(i=0;iG.vexnum;i++)scanf(%s%s%d,&G.head[i].data.name,&G.head[i].data.sbname,&G.Head[i].data.weight);//输入结点信息，各头结点的入度、出度、学期编号id均初始化为零//访问标记mark初始化为false,并给指针域first分配内存空间j=0;while(1){//输入弧，并以输入字符#结束scanf(%s%s,ch1,ch2);if(strcmp(ch1,#)==0)break;n=GLocateVex(G,ch1);//获取弧尾结点存储位置m=GLocateVex(G,ch2);//获取弧头结点存储位置if(n!=-1&&m!=-1){//输入的弧存在j++;ptr1=G.head[n].first;while(ptr1-next!=NULL)ptr1=ptr1-next;if(!(ptr2=(ArcNode*)malloc(sizeof(ArcNode))))exit(OVERFLOW);ptr2-adjvex=m;ptr1-next=ptr2;Ptr2-next=NULL;G.head[n].data.Outdegree++;G.head[m].data.Indegree++;}}returnOK;}1.2.2.2拓扑排序的类C码算法：StatusGSort(GraphG,intMAX){scanf(%d,&n);//输入学期数PSubjectp;//对p分配连续的n个空间，并对p进行初始化//其中，count初始化为零，指针head分配连续的G.vexnum个空间k=0;i=0;while(k=n){while(iG.vexnum){max=0;x=0;ma