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

目录一、课题的主要功..................................................................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

一、课题的主要功1.1程序的功每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序制定好学习计划。在输入相关数据后，程序会安排好每学期的课程1.2.输入输出的要求输入参数包括学期总数一学期的学分上限每门课的课程（固定占3位的字母数字串学分和直接先修课的课程号输出要求输出各门课程所对应的学分，以及每学期各门课程的安排1.3运行环境1.WINDOWS7系2.Vc++6.0编译环境1.4开发工具C 第3页

二、概要设2.1所负责的程序的模块LocateVe（：图的邻接表存储的基本操CreateGraph（：构造生成Display（：输出图的邻接矩FindInDegree：求顶点的入2.2模块的层次结构及调用关系函TopologicalSor2.3模块的主要功能y出图的邻接阵CreateGrap生成图见“详细设计”－“主要函数流程图 第4页

2.4数据结构和数据库结构储存的数据为结构体类型数组，以及结构体单链表结点类型1typedefstructArcNode弧所指定点位置 指向下一条弧的指针 网的权值指针int struct InfoType2typedefstruct顶点信息 第一个表结点的地址VertexType ArcNode三．主要功能的实3.1采用C语言定义相关的数据类型。其中包括字符常量，整型，字符型，字符串型，typedef定义的类型，结构体型，单链表节点类型，结构体数组3.2主要函数的流程图1.LocateVex（：图的邻接表存储的基本操作。由初始条件:图G存在u和G转而进行判断，若G中存在顶点u,则返回该顶点在图中位置否则返回1 第5页

i=0.vexnum++i2.CreateGrap（构造生成图采用邻接表存储结构,构造没有相关信息的图种图 第6页

i=0

++i

++i请输%d个课程的学分值”)i=0++i3.Displa（：输出图的邻接矩阵。采用循环设置输出图的邻接矩阵 第7页

.kind=DG.kind=DG.kind=DG个顶点： i=0i<Gvexnum++i4.FindInDegre（：求顶点的入度 第8页

i=0.vexnumi++i=0.vexnump=p所负责的部分程序/*图的邻接表存储的基本操*/intLocateVex(ALGraphG,VertexTypeu){/*初始条件图在u和G中顶点有相同特征*/ 第9页

操作结:G中存在顶点u,则返回该顶点在图中位置否则返回-1*/inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}StatusCreateGraph(ALGraph*G){/*采用邻接表存储结构,构造没有相关信息的G(用一个函数构造种图)*/inti,j,k;VertexTypeva,vb;ArcNode*p;请输入d个课程的代表请输入d个课程的代表*/for(i=0;i<(*G).vexnum;++i)/*构造顶点向*/*/(*G).vertices[i].firstarc=NULL;}for(i=0;i<(*G).vexnum;++i)/*构造顶点向for(i=0;i<(*G).vexnum;++i)/*构造顶点向*/*/}请顺序输入每条弧边)的弧尾和弧头请顺序输入每条弧边)的弧尾和弧头*/for(k=0;k<(*G).arcnum;++k)/*构造表结点链表*/*/i=LocateVex(*G,va);/*弧尾

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)switch(G.kind)switch(G.kind)}for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)弧(for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p)while(p)while(p)p=p->nextarc;}}

voidFindInDegree(ALGraphG,intindegree[]){/*求顶点的入度，算法调*/inti;ArcNode*p;for(i=0;i<G.vexnum;i++)indegree[i]=0;/*赋初值*/for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}3.3画出各函数的调用关系图Main函数（ （

四、程序调4.1测试数据：准备典型的测试数据和测试方案数据如下：学期总数：学分上限：10该专业共开设课数12课程号：从C01到C12学分顺序2，，，3，3，，，75，，先修顺序有向图表示)10136578

明输入学期总数，学分上限，课程数，先修关系边

输入课程代表符号输入相对学分值

回车，将显示顶点的个数和弧的条输入完成后执行可得到每个学期的课程计划结

．会虽这门课程让我从C总结提升的作用。在学习了这门课程后，我们进行课的内容。由于程序十分的复杂，遇到了很多常见的语法错误，及逻辑错误。这需要我们不断的调试分析。符号的格式之类，指针的用法，判断输入输出的条件都是十分容易出错的地方。在逐条排除，向同学老师请教后，程序终于得以完成。这让我明白了，解决问题，要细心认真，集思广益，这样才能把问题解决六、附录6.1参考书目1黄同成，黄俊民，董建寅．数据结构[M]．北京：中国电力出版社，20082董建寅，黄俊民，黄同成．数据结构实验指导与题解[M]．北京：中国电力出版社，20083严蔚敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，20024唐策善，李龙澍，黄刘生．数据结构—用C语言描述[M]．北京：高等教育出版社，20016.2源程序清单（带注释）#include<string.h>#include<ctype.h>#include<malloc.h>//malloc()#include<limits.h>//INT_MAX#include<stdio.h>//EOF(=^或F6),NULL#include<stdlib.h>//atoi()52#include<io.h>//eof()#include<math.h>//floor(),ceil(),abs()#include<process.h>//exit()

#include<iostream.h>//cout,cin//函数结果状态代#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;//Status是函数的类型,其值是函数结果状态代码，如OKtypedefintBoolean;//Boolea是布尔类型,其值是TRUEFALSE#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){/*初始条件图在u和G中顶点有相同特征*//*操作结:G中存在顶点u,则返回该顶点在图中位置否则返回-1*/inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}StatusCreateGraph(ALGraph*G){/*采用邻接表存储结构,构造没有相关信息的G(用一个函数构造种图)*/inti,j,k;VertexTypeva,vb;ArcNode*p;请输入d个课程的代表请输入d个课程的代表for(i=0;i<(*G).vexnum;++i)/*构造顶点向*/

(*G).vertices[i].firstarc=NULL;}for(i=0;i<(*G).vexnum;++i)/*构造顶点向for(i=0;i<(*G).vexnum;++i)/*构造顶点向*/*/}请顺序输入每条弧请顺序输入每条弧边)的弧尾和弧头*/for(k=0;k<(*G).arcnum;++k)/*构造表结点链表*/i=LocateVex(*G,va);/*弧尾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)switch(G.kind)switch(G.kind)}for(i=0;i<G.vexnum;++i)

弧(for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p)while(p)while(p)p=p->nextarc;}}}voidFindInDegree(ALGraphG,intindegree[]){/*求顶点的入度，算法调*/inti;ArcNode*p;for(i=0;i<G.vexnum;i++)indegree[i]=0;/*赋初值*/for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}typedefintSElemType;/*栈类*//*栈的顺序存储表示*/#defineSTACK_INIT_SIZE10/*存储空间初始分配量*/

#defineSTACKINCREMENT2/*存储空间分配增*/typedefstructSqStack{SElemType*base;/*在栈构造之前和销毁之后，base的值为NULL*/SElemType*top;/*栈顶指针*/intstacksize;/*当前已分配的存储空间，以元素为单*/}SqStack;/*顺序栈*//*顺序栈的基本操作*/StatusInitStack(SqStack*S){/*构造一个空S*/(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);/*存储分配失败(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}voidClearStack(SqStack*S)//清空栈的操{ S->top=S->base;}StatusStackEmpty(SqStackS){/*若栈S为空栈，则返回TRUE，否则返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;

StatusPop(SqStack*S,SElemType*e){/*若栈不空，则删的栈顶元素，e返回其值，并返回OK；否则返回ERROR*/if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}StatusPush(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)exit(OVERFLOW);/*存储分配失败*/(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*((*S).top)++=e;returnOK;}typedefintpathone[MAXCLASS];typedefintpathtwo[MAXCLASS];

StatusTopologicalSort(ALGraphG){/*有向图采用邻接表存储结构。若无回路,则输出的顶点的一个拓扑序列并返回OK,*//*否则返ERROR。inti,k,j=0,count,indegree[MAX_VERTEX_NUM];boolhas=false;SqStackS;pathonea;pathtwob;ArcNode*p;FindInDegree(G,indegree);/*对各顶点求入indegree[0..vernum-1]*/InitStack(&S);/*初始化*/for(i=0;i<G.vexnum;++i)/*建零入度顶点栈S*/if(!indegree[i]) {Push(&S,i); //cout<<*G.vertices[i].data<<endl; } /*入度为者进栈*/count=0;/*对输出顶点计*/while(!StackEmpty(S)){/*栈不*/Pop(&S,&i);a[i]=*G.vertices[i].data;b[i]=*G.verticestwo[i].data;b[i]=*G.verticestwo[i].data;b[i]=*G.verticestwo[i].data;课程s分出号顶点并计数*/++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){/*对号顶点的每个邻接点的入度减*/k=p->adjvex;

if(!(--indegree[k]))/*若入度减,栈*/ {Push(&S,k); //cout<<*G.vertices[i].data<<endl; }}}if(count<G.vexnum)if(count<G.vexnum)returnERROR;}elseelseelse为一个拓扑序列。 has=tru