教学计划安排检验程序数据结构课程设计报告

德州学院计算机系2009级数据结构课程设计 -PAGE1-教学计划安排检验程序一、选题背景随着科学技术的发展，计算机技术在世界的每个角落得以运用与推广，其强大的功能已为人们深刻认识，利用计算机进行日常工作的管理也成为国家机关信息化的标志。同时，人们对计算机技术需求的增加，也促进了计算机新技术的发展。现如今，无论是小学、中学还是大学每学期都要面临教学计划安排的问题。然而学校的课程繁多，每所学校的课程也大不相同。给学生们安排课程成了老师的一项繁重而又难免的工作。虽然有软件可以实现课程的安排，但是大都需要购买，而且过程繁琐不好掌握。其实这项工作并没有想象中的那么难做，我们完全可以运用我们所学的知识让计算机来帮我们完成这项工作，体验计算机技术给我带来的高效、和快速。课程安排普遍的要求是：根据课程之间的依赖关系，在满足各学期课程数大致相同的条件下制定出课程安排计划。针对各大院校课程繁多课程安排难的问题，并且避免以往程序的繁琐和不易上手，我们从实际出发，充分运用我们所学的知识，根据不同学校的情况设计出《教学计划安排检验程序》。该程序可以根据用户输入的课程数、学期数、课程间的先后关系数目以及课程间两两间的先后关系，给出学生每学期应学的课程。该教学计划安排程序具有操作简单，功能完善，实用性强等特点，能很好的完成教学计划的检验。二、运行环境（软、硬件环境）软件环境：MicrosoftVisualC++6.0。硬件环境：CPU要求必须是Pentium166或更高的微处理器(或同级兼容处理器),内存至少需要32MB，推荐使用64MB，最高4GB,硬盘需要2GB，自由硬盘空间至少为650MB,一个12倍速成以上的CD-ROM或DVD-ROM驱动器,VGA或更高分辨率的显示器。三、算法设计的思想总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。首先根据课程的先后关系画出AOV网，网中的结点代表课程，有向边表示各学科之间的次序关系。可以采用邻接表作AOV网的存储结构，且在头结点中增加一个存放顶点入度的数组。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。然后根据拓扑排序依次输出应学的课程。编写的程序根据用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，实现输出每学期应学的课程的功能。四、算法的流程图拓扑排序：开始开始输入学期数，课程数，课程代表值，课程相互关系数，课程两两先后关系学期数<=8,课程数<=20拓扑排序输出相应课程结束否是开始开始输入入度，定点数，已输出顶点数已输出定点数<顶点数入度=0顶点入栈栈非空输出顶点顶点数减1顶点入度减1累加已输出顶点数结束是否否是是五、算法设计分析拓扑排序时有向图的一种重要运算。在课表排序中，每门课都有多种关系：、（一）先后关系，即必须在一门课学完后，才能开始学习另一门课；（二）在一类课之间没有次序要求，即两门课可以同时学习，互不影响。将AOV网络中的各个顶点排列成一个线性有序序列，使得所有的要求的前趋、后趋关系都能得到满足。在AOV网络进行拓扑排序的方法：中选择一个没有前趋的顶点，并把它输出；从网络中删去该顶点和从该顶点出发的所有有向边；重复执行上述两步，直到网中所有的顶点都被输出。六、源代码#include"malloc.h"#include"stdio.h"#defineOK1#defineERROR0#defineTRUE1#defineFALSE0#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量#defineMAX_VERTEX_NUM20typedefintStatus;typedefintSElemType;typedefstruct{ SElemType*base;//在栈构造之前和销毁之后,base的值为NULL SElemType*top;//栈顶指针 intstacksize;//当前已分配的存储空间,以元素为单位}SqStack;typedefstructArcNode{ intadjvex;//该弧所指向的顶点的位置 structArcNode*nextarc;//指向第一条依附该顶点的弧的指针}ArcNode;typedefstructVNode{ chardata[10]; ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{ AdjListvertices; intvexnum,arcnum;//图的当前顶点数和弧数}ALGraph;intindegree[20]={0};//存储图的入度的全局变量数组StatusInitStack(SqStack&S){ //构造一个空栈S S.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!S.base) returnERROR;//内存分配失败 S.top=S.base; S.stacksize=STACK_INIT_SIZE; returnOK;}//InitStackStatusPush(SqStack&S,SElemTypee){ //插入元素e为新的栈顶元素 if(S.top-S.base>=S.stacksize) {//栈满,追加存储空间 S.base=(SElemType*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!S.base) returnERROR;//存储分配失败 S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; } *S.top++=e;returnOK;}//PushStatusPop(SqStack&S,SElemType&e){ //若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR if(S.top==S.base) returnERROR; e=*--S.top; returnOK;}//PopStatusStackEmpty(SqStackS){//判断栈是否为空,为空返回TRUE,否则返回FALSE if(S.top==S.base) returnTRUE; elsereturnFALSE;}StatusCreateDG(ALGraph&G){//建立邻接表 inti,l,v,w,vex;printf("请输入学期数目（学期数目必须小于等于8）：");scanf("%d",&l);if(l>8) { printf("请重新输入学期数目（学期数目必须小于等于8）："); scanf("%d",&l); } printf("请输入课程数目(课程数必须小于20)："); scanf("%d",&vex); if(vex>=20) { printf("请重新输入课程数目(课程数必须小于20)："); scanf("%d",&vex); }G.vexnum=vex; printf("请输入课程间的先后关系数："); scanf("%d",&G.arcnum); printf("请输入课程的代表值(课程名的长度小于等于10个字符):"); for(i=0;i<G.vexnum;i++) { scanf("%s",&G.vertices[i].data); G.vertices[i].firstarc=NULL; }//输入顶点信息 printf("请输入课程间两两间的先后关系："); for(i=0;i<G.arcnum;i++){//输入边的信息 scanf("%d,%d",&v,&w);//形式2 ArcNode*p=newArcNode;//建立结点 if(!p)returnERROR; p->adjvex=w-1; p->nextarc=G.vertices[v-1].firstarc;//顶点v的链表 G.vertices[v-1].firstarc=p;//添加到最左边 } returnOK;} voidFindInDegree(ALGraphG){//求图的入度 ArcNode*p; for(inti=0;i<G.vexnum;i++) { p=G.vertices[i].firstarc; while(p) { for(intj=0;j<G.vexnum;j++) if(p->adjvex==j) indegree[j]++; p=p->nextarc; } }}StatusTopologicalSort(ALGraphG){//拓扑排序//有向图G采用邻接表存储结构SqStackS1,S2; ArcNode*p; inti,count,k; FindInDegree(G); InitStack(S1); InitStack(S2); for(i=0;i<G.vexnum;++i) if(!indegree[i]) Push(S1,i);//把入度为0的压入栈S1 count=0;//对输出顶点计数 while(!StackEmpty(S1)) { printf("第%d学期应学的课程:",count+1); while(!StackEmpty(S1)) { Pop(S1,i); printf("%s",G.vertices[i].data);//输出i号顶点 Push(S2,i);//把i号顶点压入栈S2 } printf("\n");count++;//计数 while(!StackEmpty(S2)) { Pop(S2,i); for(p=G.vertices[i].firstarc;p;p=p->nextarc) { k=p->adjvex;//对i号顶点的每个邻接点的入度减1 if(!(--indegree[k]))//若入度减为0,则入栈 Push(S1,k); } } } if(count<G.vexnum)//该有向图有回路 returnERROR; elsereturnOK;}//TopologicalSortintmain(){ALGraphG; CreateDG(G); TopologicalSort(G); return0;}七、运行结果分析1运行程序打开界面如下图，并根据提示，输入学期数目：输入出错时显示如下：2输入正确继续根据提示输入课程数目：输入错误时的显示如下：3输入正确则继续根据界面提示输入课程的代表值：4根据界面提示输入课程间两两间的先后关系：5输入课程间两两间的先后关系后，则输出每学期应学的课程：附*完美输入数据运行结果：八、收获及体会经过一个星期的学习和努力我们小组终于完成了<<教学计划安排检验程序>>的课程设计。从确定题目到算法基本完成，从程序的逐步完善再到设计报告的结束，每一步都是对我们的一种新的挑战。这次训练，让我意识到自己掌握的知识是远远不够的。在这次训练中，有成功有失败，要完全掌握编程技术以后还得多加练习。通过查看相关的资料和书籍，通过仔细的思考，使我们的设计一步步完善起来。我们也切实认识到做设计必然会遇到许许多多新的难题，通过这次课程设计我们小组两个人都受益匪浅。我们形成了一种信念：做设计只要认认真真的用心去做，难点都会一一解决。通过这次课程设计，我们收获的不仅仅是技术，本次程序设计使我不仅深化理解了