教学计划安排检验程序正文

i目录1实验目的...................................................................................................................12问题描述...................................................................................................................13需求分析...................................................................................................................14概要设计...................................................................................................................24.1设计思想..................................................................................................24.2设计流程图..............................................................................................24.3数据库设计.............................................................................................34.4函数及功能要求......................................................................................34.5模块调用关系..........................................................................................45详细设计....................................................................................................................45.1制定课程计划伪码..................................................................................46测试分析...................................................................................................................87使用说明.................................................................................................................118总结.........................................................................................................................129参考文献.................................................................................................................1310附录.......................................................................................................................14德州学院计算机系2011网络工程数据结构课程设计1教学计划安排检验（德州学院计算机系，山东德州253023）1实验目的本次数据结构课程设计的主要目的是检验和巩固专业知识，提高综合素质和能力。并在实际操作中掌握：1．邻接表的存储结构。2．栈的基本操作。3．拓扑排序的思想。通过实习，可以将我们课堂上掌握的理论知识与处理数据的业务相结合，以检验我们掌握知识的宽度、深度及对知识的综合运用能力。2问题描述针对学院的计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划，并满足各学期课程数大致相同。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程。3需求分析该程序的工作是制定课程安排计划，并满足各学期课程数大致相同。此程序规定：1、输入的形式和输入值的范围：输入间用空格隔开。要求用户输入的课程数小于20，学期数小于或是等于8，课程名的长度小于等于10个字符。2、程序所能达到的功能：按照用户的输入，给出每学期应学的课程。3、测试数据：输入：学期数：５，课程数：12，课程间的先后关系数：16，课程的代表值：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。课程间两两间的先后关系：v1v2,v1v3,v1v4,v1v12,v2v3,v3v5,v3v7,v3v8,v4v5,v5v7,v6v8,v9v10,v9v11,v9v12,v10v12,v11v6输出：第1学期应学的课程：v1v9第2学期应学的课程：v2v4v10v11第3学期应学的课程：v3v6v12德州学院计算机系2011网络工程数据结构课程设计2第4学期应学的课程：v5v8第5学期应学的课程：v74概要设计4.1设计思想总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。首先根据课程的先后关系画出AOV网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作AOV网的存储结构，且在头结点中增加一个存放顶点入度的数组。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。4.2设计流程图图1流程图开始输入学期数，课程数，课程代表值，课程相互关系数，课程两两先后关系学期数=8课程数=20拓扑排序输出相应课程结束不符德州学院计算机系2011网络工程数据结构课程设计34.3数据库设计ADTGraph｛数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据系统用到的抽象数据类型定义：1．关系R：R=｛VR｝VR=｛v,w|v,w∈V且P(v,w),v,w表示从v到w的弧，谓词P(v,w)定义了弧v,w的意义和信息｝基本操作：（1）StatusCreateDG(ALGraph&G)；（2）voidFindInDegree(ALGraphG)；（3）StatusTopologicalSort(ALGraphG)；｝ADTGraph2.ADTStack｛数据对象：D={ai|ai∈ElemSet，i=1,2,…,n,n≥0}数据关系：R1=｛ai-1，ai|ai-1，ai∈D,i=2,…，n｝约定an端为栈顶，a1端为栈底。基本操作：（1）StatusInitStack(SqStack&S)；（2）StatusPush(SqStack&S,SElemTypee)；（3）StatusPop(SqStack&S,SElemType&e)；（4）StatusStackEmpty(SqStackS)；｝ADTStack4.4函数及功能要求（1）StatusInitStack(SqStack&S)：构造一个空栈。（2）StatusPush(SqStack&S,SElemTypee)：插入元素e为新的栈顶元素。（3）StatusPop(SqStack&S,SElemType&e)：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。（4）StatusStackEmpty(SqStackS)：判断栈是否为空,为空返回TRUE,否德州学院计算机系2011网络工程数据结构课程设计4则返回FALSE。（5）StatusCreateDG(ALGraph&G)：建立邻接表。（6）voidFindInDegree(ALGraphG)：求图的入度。（7）voidprint(intn[],ALGraphG)：排序输出顶点数据。（8）StatusTopologicalSort(ALGraphG)：拓扑排序，有向图G采用邻接表存储结构。4.5模块调用关系各程序模块之间的调用关系（子程序编号见上）：主函数可调用子程序5，8。子程序8可调用子程序1，2，3，4，6，7。5详细设计5.1制定课程计划伪码制定课程计划算法的伪码描述如下：StatusCreateDG(ALGraph&G){//建立邻接表提示请输入学期数目（学期数目必须小于等于8）：;scanf(%d,&学期数目);if(学期数目8){提示请重新输入学期数目（学期数目必须小于等于8）：;scanf(%d,&学期数目);}提示请输入课程数目(课程数必须小于20)：;scanf(%d,&课程数目);if(课程数目=20){提示请重新输入课程数目(课程数必须小于20)：;scanf(%d,&课程数目);}德州学院计算机系2011网络工程数据结构课程设计5图G的顶点数=课程数目;提示请输入课程间的先后关系数：;scanf(%d,&图G的顶点数);提示请输入课程的代表值(课程名的长度小于等于10个字符):;for(i=0;i图G的顶点数;i++){scanf(%s,&图G的第i个顶点的数据);图G的第i个顶点指向的第一条弧=NULL;}//输入顶点信息提示请输入课程间两两间的先后关系：;for(i=0;i图G的弧数;i++){//输入弧的信息scanf(%d,%d,&弧尾v,&弧头w);ArcNode*p=newArcNode;//建立结点if(p为空)returnERROR;p所指向的顶点（p-adjvex）=w-1;p所指向的下一条弧（p-nextarc）=G.vertices[v-1].firstarc;//顶点v的链表G.vertices[v-1].firstarc=p;//添加到最左边}returnOK;}voidFindInDegree(ALGraphG){//求图各顶点的入度ArcNode*p;for(inti=0;i图G的顶点数;i++){p=G.vertices[i].firstarc;while(p不为空){德州学院计算机系2011网络工程数据结构课程设计6for(intj=0;j图G的顶点数;j++)if(p所指向的顶点位置（p-adjvex）==j)第j个顶点的入度+1;p=p-nextarc;}}}voidprint(intn[],ALGraphG)//对刚出s1栈的数据进行排序然后输出{for(i=0;n[i]!=-1;i++)for(j=i+1;n[j]!=-1;j++)if(n[i]n[j]){n[i]与n[j]交换;}for(i=0;n[i]!=-1;i++)输出“G.vertices[n[i]].data”;}StatusTopologicalSort(ALGraphG){//拓扑排序//有向图G采用邻接表存储结构SqStackS1,S2;ArcNode*p;inti,count,k,m,n[20];FindInDegree(G);InitStack(S1);InitStack(S2);for(i=0;i20;i++)n[i]=-1