数据结构课程设计——教学计划编制

攀枝花学院课程设计论文教学计划编制问题-1-摘要教学计划（课程计划）是课程设置的整体规划，它规定不同课程类型相互结构的方式，也规定了不同课程在管理学习方式的要求及其所占比例，同时，对学校的教学、生产劳动、课外活动等作出全面安排，具体规定了学校应设置的学科、课程开设的顺序及课时分配，并对学期、学年、假期进行划分。根据一定的教育目的和培养目标制定的教学和教育工作的指导文件。它决定着教学内容总的方向和总的结构，并对有关学校的教学、教育活动，生产劳动和课外活动校外活动等各方面作出全面安排，具体规定一定学校的学科设置、各门学科的教学顺序、教学时数以及各种活动等。教学计划、教学大纲和教科书互相联系，共同反映教学内容。近代以来，特别是在实行学科课程的条件下，教学计划主要是学科的计划，或只是学科表。随着社会经济和科学技术的新发展，教育结构不断发生变革，现代教育和教学理论主张对教学计划的结构实行改革。除了教学以外，生产劳动、科技活动、发展体力和增进健康的活动、艺术活动和社会活动等也应列入教学计划。下面就利用对此进行程序设计，已达到预期的目的。关键字：数据结构，教学计划编制，抽象数据类型，程序设计攀枝花学院课程设计论文教学计划编制问题-2-1.需求分析根据课程之间的依赖关系制定课程安排计划，输入课程数及课程之间的关系。需要利用代码实现排序，以及对各个学期课程安排进行排序并输出。1.1问题描述大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。1.2设计思路首先利用拓扑排序对课程先后顺序进行分析，邻接表位主要存储结构，栈为主要辅助结构，给出课程之间的先后关系比如AOV网，然后进行拓扑排序，但当又向图中存在环时，无法查找该图的一个拓扑排序，当图中的所有顶点全部输出，表示对该图排序成功，实现拓扑排序算法时，相应的建立邻接表存储AOV网，为了避免重复检测入度为零的顶点，建立一个栈来对入度为零的顶点进行存放。根据课程的先后关系，对个学期的课程进行排序，输出。1.3设计环境、原理设计环境和器材：硬件：计算机；软件：MicrosoftVisulaC++。设计原理说明：运用图的拓扑排序对课程先修排列的实现，并调用递归完成拓扑排序。1.4实验目的培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高质量的应用软件和系统软件具有关键性作用。通过课程设计的实践，学生可以在程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训练。1.5实验内容针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。攀枝花学院课程设计论文教学计划编制问题-3-2.概要设计：2.1流程图voidFindInDegree(ALGraphG,intindegree[])//求图中各节点的入度（如下左图）voidCreatGraph(ALGraph*G)//构件图（如下右图）。voidTopologicalSort_1(ALGraphG,intnumterm,intuplcredit)//有向图G采用邻接表存储结构(如下左图)；voidTopologicalSort_2(ALGraphG,intnumterm,intuplcredit)//有向图G采用邻接表存储结构（如下右图）。攀枝花学院课程设计论文教学计划编制问题-4-主函数：voidmain()攀枝花学院课程设计论文教学计划编制问题-5-2.2抽象数据类型图的定义ADTGraph{数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R:R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之间存在直接先修关系}基本操作P:voidCreatGraph(ALGraph*);voidFindInDegree(ALGraph,int*);voidTopologicalSort_1(ALGraphG,intnumterm,intmaxcredit);voidTopologicalSort_2(ALGraphG,intnumterm,intmaxcredit);}ADTGraph栈的定义:ADTStack{数据对象:D={ai|ai∈ElemSet,i=1,2,…n,n=0}攀枝花学院课程设计论文教学计划编制问题-6-数据关系:R1={﹤ai-1ai﹥|ai-1,ai∈D,i=2,…,n}基本操作:voidInitStack(SqStack*S);intStackEmpty(SqStackS);voidPush(SqStack*S,int);intPop(SqStack*S,int*e);}ADTStack2.3主程序intmain()//主函数{intnumterm;//学期总数intuplcredit;//一个学期的学分上限intselectway;ALGraphG;printf(请输入学期总数:\n);scanf(%d,&numterm);printf(请输入一个学期的学分上限:\n);scanf(%d,&uplcredit);CreatGraph(&G);printf(请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布\n);scanf(%d,&selectway);if(selectway==1)TopologicalSort_1(G,numterm,uplcredit);if(selectway==2)TopologicalSort_2(G,numterm,uplcredit);system(pause);return0;}2.4本程序只有两个模块,调用关系简单主程序模块→拓扑排序模块攀枝花学院课程设计论文教学计划编制问题-7-4.详细设计4.1头结点、表结点、邻接表的定义#defineMAX_VERTEX_NUM100//最大课程总数typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{charname[24];//课程名intclassid;//课程号intcredit;//课程的学分intindegree;//该结点的入度intstate;//该节点的状态ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VEXTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;邻接表的基本操作：voidCreatGraph(ALGraph*);创建邻接表voidFindInDegree(ALGraph,int*);求一个结点的入度voidTopologicalSort_1(ALGraphG,intnumterm,intmaxcredit);拓扑排序来编排课程voidTopologicalSort_2(ALGraphG,intnumterm,intmaxcredit);拓扑排序来编排课程4.2栈的定义#defineSTACk_INIT_SIZE100//存储空间的初时分配量#defineSTACKINCREMENT10//存储空间的分配增量攀枝花学院课程设计论文教学计划编制问题-8-typedefintElemType;typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;基本操作：voidInitStack(SqStack*S);栈的初始化intStackEmpty(SqStackS);判断栈是否为空voidPush(SqStack*S,int);入栈操作intPop(SqStack*S,int*e);出栈操作4.3主程序和其他算法：#includestring.h#includectype.h#includemalloc.h//malloc()等#includelimits.h//INT_MAX等#includestdio.h//EOF(=^Z或F6),NULL#includestdlib.h//atoi()52#includeio.h//eof()#includemath.h//floor(),ceil(),abs()#includeprocess.h//exit()#includeiostream.h//cout,cin//函数结果状态代码#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OK等typedefintBoolean;//Boolean是布尔类型,其值是TRUE或FALSE攀枝花学院课程设计论文教学计划编制问题-9-#defineMAX_NAME10/*顶点字符串的最大长度*/#defineMAXCLASS100intZ=0;intX=0;intxqzs,q=1,xfsx;typedefintInfoType;typedefcharVertexType[MAX_NAME];/*字符串类型*//*图的邻接表存储表示*/#defineMAX_VERTEX_NUM100typedefenum{DG}GraphKind;/*{有向图,有向网,无向图,无向网}*/typedefstructArcNode{intadjvex;/*该弧所指向的顶点的位置*/structArcNode*nextarc;/*指向下一条弧的指针*/InfoType*info;/*网的权值指针）*/}ArcNode;/*表结点*/typedefstruct{VertexTypedata;/*顶点信息*/ArcNode*firstarc;/*第一个表结点的地址,指向第一条依附该顶点的弧的指针*/}VNode,AdjList[MAX_VERTEX_NUM];/*头结点*/typedefstruct{AdjListvertices,verticestwo;intvexnum,arcnum;/*图的当前顶点数和弧数*/intkind;/*图的种类标志*/}ALGraph;/*图的邻接表存储的基本操作*/intLocateVex(ALGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*//*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/inti;攀枝花学院课程设计论文教学计划编制问题-10-for(i=0;iG.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}StatusCreateGraph(ALGraph*G){/*采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图)*/inti,j,k;VertexTypeva,vb;ArcNode*p;printf(请输入教学计划的课程数:);scanf(%d,&(*G).vexnum);printf(请输入拓扑排序所形成的课程先修关系的边数:);scanf(%d,&(*G).arcnum);printf(请输入%d个课程的代表值(%d个字符):\n,(*G).vexnum,MAX_NAME);for(i=0;i(*G).vexnum;++i)/*构造顶点向量*/{scanf(%s,(*G).vertices[i].data);(*G).vertices[i].firstarc=NULL;}prin