数据结构课程设计(教学计划编制问题)报告

中北大学数据结构课程设计说明书学生姓名:张宁学号：1021011524学院:软件学院专业:软件工程题目:教学计划编制问题指导教师何志英2011年12月20日11.设计任务概述1.1问题描述大学的每个专业都要制定教学计划。针对软件工程本专业制定一个教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。1.2需求分析根据问题描述及要求，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题输出每学期的课程。（1）用学分来实现每学期课程数大致相同；（2）根据教学计划中的课程及其关系和学分来定义图的顶点及边的结构体。（3）创建图CreateGraph（）：结合先修关系的AOV网，采用邻接表存储。（4）菜单OUTPUT()：显示代号所对应课程及课程的先修课程。（5）拓扑排序TopoSort(G)：将课程排序后并决定出每学期所学课程。（6）输出图G的信息Display(G)：将图的顶点和弧边输出。1.3本程序包括2个模块：主程序模块和拓扑排序模块。2.本设计所采用的数据结构(1)voidOUTPUT()//显示代号所对应课程及课程的先修课程(2)intLocateVex(ALGraphG,VertexTypeu)//查找图中某个顶点位置(3)intCreateGraph(ALGraphG)//采用邻接表存储结构(4)voidDisplay(ALGraphG)//输出图G的信息(5)voidFindInDegree(ALGraphG,intindegree[])//求顶点的入度(6)voidpuanduan(VertexTypestr,structNamename[],intn)(7)intInitStack(SqStack&S)//栈的初始化(8)intStackEmpty(SqStackS)//判空主程序模块拓扑排序模块2(9)intPop(SqStack&S,SElemType&e)//出栈(10)intPush(SqStack&S,SElemTypee)//入栈(11)intTopoSort(ALGraphG,AdjListTemp,structNamename[])//拓扑排序(12)voidmain()//主函数3.功能模块详细设计3.1详细设计思想3.2核心代码3.21．数据类型定义（1）头结点，表结点，邻接表的定义typedefcharVertexType[MAX_NAME];intTotalTerms;//学期总数intMaxScores;//学分上限typedefstructArcNode{int12main()13411256789103adjvex;//该弧所指向的顶点的位置弧的节点结构structArcNode*nextarc;//指向下一条弧的指针}ArcNode;//表结点typedefstructVNode{VertexTypedata;//顶点信息intgrades;//存储学分信息ArcNode*firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[MAX_VERTEX_NUM];//头结点typedefstructALGraph//邻接表{AdjListvertices;//vertices存储课程名intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;邻接表的基本操作：voidCreatGraph(ALGraph*);创建邻接表voidFindInDegree(ALGraph,int*);求一个结点的入度intTopoSort(ALGraphG,AdjListTemp,structNamename[])//拓扑排序（2）栈的定义：4typedefintSElemType;//栈类型#defineStack_NUM20//存储空间初始分配量#defineStack_MoreNUM5//存储空间分配增量typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;//分配的存储空间}SqStack;基本操作：voidInitStack(SqStack*S);栈的初始化intStackEmpty(SqStackS);判断栈是否为空voidPush(SqStack*S,int);入栈操作intPop(SqStack*S,int*e);出栈操作3.22系统主要子程序详细设计（1）主函数模块设计voidmain(){ALGraphG;AdjListTemp;structNamename[N]={{C1},{C2},{C3},{C4},{C5},{C6},{C7},{C8},{C9},{C10},{C11},{C12}};OUTPUT();printf(**********教学计划编制问题**********\n);5printf(请输入学期总数:);scanf(%d,&TotalTerms);printf(请输入学期的学分上限:);scanf(%d,&MaxScores);CreateGraph(G);Display(G);TopoSort(G,Temp,name);printf(OK\n);scanf(*c);}（2）拓扑排序模块设计intTopoSort(ALGraphG,AdjListTemp,structNamename[]){inti,k,j=0,count,indegree[MAX_VERTEX_NUM];SqStackS;ArcNode*p;FindInDegree(G,indegree);//对各顶点求入度InitStack(S);//初始化栈for(i=0;iG.vexnum;++i)//建零入度顶点栈Sif(!indegree[i])Push(S,i);//入度为0者进栈count=0;//对输出顶点计数while(!StackEmpty(S)){Pop(S,i);printf(%s(%d分),,G.vertices[i].data,G.vertices[i].grades);Temp[j++]=G.vertices[i];//将当前的拓扑序列保存起来++count;//输出i号顶点并计数6for(p=G.vertices[i].firstarc;p;p=p-nextarc)//对i号顶点的每个邻接点的入度减1{k=p-adjvex;if(!(--indegree[k]))//若入度减为0,则入栈Push(S,k);}}if(countG.vexnum){printf(此有向图有回路无法完成拓扑排序);returnERROR;}elseprintf(为一个拓扑序列);printf(\n);intq=1,Z=0;while(q=TotalTerms){intC=Temp[Z].grades;printf(\n第%d个学期应学课程:,q);while(C=MaxScores){C=C+Temp[Z+1].grades;if(ZG.vexnum){puanduan(Temp[Z].data,name,N);++Z;}7}printf(\n);if(q==TotalTerms)printf(\n课程编制完成!);q++;}returnOK;}3.3程序运行结果（1）主界面设计显示课程代号所对应课程及先修课程。（2）输入1-16的任意数回车（3）按要求输入学期数，学分上限，课程数，课程号和各课程的学分：（4）输入各课程先修课程，回车，运行结果：84.课程设计心得、存在问题及解决方法9经过这次这次课程设计，我学到很多。首先是一个总体思想，先确定总体结构。用邻接表把图存储起来，然后用拓扑排序实现先修关系。其中还用到了栈，进栈是要判断栈是否为满，若满则需要再开辟存储空间，如果开辟失败，存储也就失败了。出栈要判断栈是否空，若空，则出栈失败，且返回错误。一开始程序不能运行，后来才找见错误，原来我错加了“&”符号，可见一点疏忽就会导致整个程序无法运行。以后要更加细心的写程序啦！