教学计划编制问题课程设计

信息与电气工程学院课程设计说明书（2015/2016学年第一学期）课程名称：软件算法分析与设计题目：教学计划编制专业班级：计算机1401学生姓名：李丹丹学号：140210132指导教师：陈丽设计周数：一周设计成绩：2016年1月13日目录一、课题的主要功能..................................................................31.1程序的功能.................................................................31.2.输入输出的要求.............................................................31.3运行环境...................................................................31.4开发工具...................................................................3二、概要设计........................................................................42.1程序的模块组成..............................................................42.2模块的层次结构及调用关系....................................................42.3模块的主要功能..............................................................42.4数据结构和数据库结构........................................................5三．主要功能的实现..................................................................53.1采用C语言定义相关的数据类型。..............................................53.2主要函数的流程图............................................................53.3画出各函数的调用关系图.....................................................12四、程序调试.......................................................................134.1测试数据：................................................................134.2使用说明..................................................................14五．心得体会.......................................................................17六、附录...........................................................................156.1参考书目..................................................................156.2源程序清单（带注释）.......................................................16第3页一、课题的主要功能1.1程序的功能大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。本程序针对本科的学期内容，通过输入实际的课程及先后关系。结合每学期的学分及课程数，制定好学习计划。在输入相关数据后，程序会安排好每学期的课程。1.2.输入输出的要求输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。输出要求输出各门课程所对应的学分，以及每学期各门课程的安排。1.3运行环境1.WINDOWS7系统2.Vc++6.0编译环境1.4开发工具C语言第4页二、概要设计2.1所负责的程序的模块LocateVex（）：图的邻接表存储的基本操作CreateGraph（）：构造生成树Display（）：输出图的邻接矩阵FindInDegree（）：求顶点的入度2.2模块的层次结构及调用关系2.3模块的主要功能见“详细设计”－“主要函数流程图”Main()函数TopologicalSort（）输出G顶点的拓扑排序结果Display（）输出图的邻接矩阵CreateGraph（）生成图第5页2.4数据结构和数据库结构储存的数据为结构体类型数组，以及结构体单链表结点类型。1typedefstructArcNode弧所指定点位置指向下一条弧的指针网的权值指针intstructInfoType2typedefstruct顶点信息第一个表结点的地址VertexTypeArcNode三．主要功能的实现3.1采用C语言定义相关的数据类型。其中包括字符常量，整型，字符型，字符串型，typedef定义的类型，结构体型，单链表节点类型，结构体数组。3.2主要函数的流程图1.LocateVex（）：图的邻接表存储的基本操作。由初始条件:图G存在,u和G中顶点有相同特征转而进行判断，若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。第6页2.CreateGraph（）：构造生成图。采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)。intii=0returni++ireturn-1iG.vexnum第7页3.Display（）：输出图的邻接矩阵。采用循环设置输出图的邻接矩阵。i(*G).vexnumscanf(%s,(*G).vertices[i].data);++iprintf(请输入%d个课程的学分值”)i=0i(*G).vexnumscanf(%s,(*G).verticestwo[i].data);++imultiinti,j,k;i=0第8页4.FindInDegree（）：求顶点的入度。inti;G.kind=DGprintf(%d个顶点：\n,G.vexnum);i=0iGvexnum++imulti第9页所负责的部分程序：/*图的邻接表存储的基本操作*/intLocateVex(ALGraphG,VertexTypeu){/*初始条件:图G存在,u和G中顶点有相同特征*/intii=0iG.vexnumi++i=0iG.vexnump=G.vertices[i].firstarc;pindegree[p-adjvex]++;i++;第10页/*操作结果:若G中存在顶点u,则返回该顶点在图中位置;否则返回-1*/inti;for(i=0;iG.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}StatusCreateGraph(ALGraph*G){/*采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)*/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;}printf(请输入%d个课程的学分值(%d个字符):\n,(*G).vexnum,MAX_NAME);for(i=0;i(*G).vexnum;++i)/*构造顶点向量*/{scanf(%s,(*G).verticestwo[i].data);}printf(请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n);for(k=0;k(*G).arcnum;++k)/*构造表结点链表*/{scanf(%s%s,va,vb);i=LocateVex(*G,va);/*弧尾*/第11页j=LocateVex(*G,vb);/*弧头*/p=(ArcNode*)malloc(sizeof(ArcNode));p-adjvex=j;p-info=NULL;/*图*/p-nextarc=(*G).vertices[i].firstarc;/*插在表头*/(*G).vertices[i].firstarc=p;}returnOK;}voidDisplay(ALGraphG){/*输出图的邻接矩阵G*/inti;ArcNode*p;switch(G.kind){caseDG:printf(有向图\n);}printf(%d个顶点：\n,G.vexnum);for(i=0;iG.vexnum;++i)printf(%s,G.vertices[i].data);printf(\n%d条弧(边):\n,G.arcnum);for(i=0;iG.vexnum;i++){p=G.vertices[i].firstarc;while(p){printf(%s→%s,G.vertices[i].data,G.vertices[p-adjvex].data);p=p-nextarc;}printf(\n);}第12页}voidFindInDegree(ALGraphG,intindegree[]){/*求顶点的入度，算法调用*/inti;ArcNode*p;for(i=0;iG.vexnum;i++)indegree[i]=0;/*赋初值*/for(i=0;iG.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p-adjvex]++;p=p-nextarc;}}}3.3画出各函数的调用关系图Main函数CreatGraph()Display()Tolopogicalsort()FindInDgree()InitStack()Push（）StackEmpty（）第13页19421221011365788四、程序调试4.1测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。数据如下：学期总数：6；学分上限：10；该专业共开设课数：12课程号：从C01到C12；学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。先修顺序(有向图表示)：第14页4.2使用说明输入学期总数，学分上限，课程数，先修关系边数第15页输入课程代表符号：输入相对学分值：第16页回车，将显示顶点的个数和弧的条数输入完成后执行可得到每个学期的课程计划结果第17页五．总结体会虽这门课程让我从C语言基础再深入的了解了软件开发的复杂性。对以往模糊的经验，起了总结提升的作用。在学习了这门课程后，我