课程设计-教学计划编制问题.docx

合肥手浣行靠机科学与技木系课程设计报告20122013学年第2学期C01C01C01C01C09C09C09C02C04C03C03C03 ellC06C04C02C03C12 c12C10 ellC03C05C05C07C08C06C08遥建昭'一学分7课程cl。 学分2课程c04： f :：f学分4课程c 08：- 鬃不率曲短率赢嬴; 谟程C09 添程C01：*2个学期应学课程为: 谟程C12 谟程ell谟程c10课程C04事3个学期应学课程为: 谍电C06 倬起C02学分5课程cl8 学分3课程c 02： f :第4个学期应学课程为： 课程C03亲号个学期应学课程为: 谍程C08课程c07谟程c05； 学分2课程c06： 6 /.学分3课程c03： f 学分4课程c0S：学分4课程cl2： f学分3为一个拓小序列。 课程计划如下=学分3课程f：f 学分2课程c07234323447523请顺序输入每条弧边的弧尾和弧头 以空格作为间隔：以个顶点：c01 c02 c03 c04 c05 c06 c07 c08 c09 cl0 ell cl214条弧边：c01->cl2c01>c03c01>c02c01>c04c02->c03¥=图12输入完成后执行可得到每个学期的课程结果如图13C09->cl0 c09f cl2 cllf C06图13五、参考资料1王昆仑李红2严蔚敏吴伟明3谭浩强数据结构与算法数据结构C程序设计4.3程序调试中遇到的问题以及解决问题的方法。由于程序十分的复杂，遇到了很多常见的语法错误，及逻辑错误。这需要我们不断的调 试分析。符号的格式之类，指针的用法，判断输入输出的条件都是十分容易出错的地方。 在逐条排除，向同学老师请教后，程序终于得以完成。这让我明白了，解决问题，要细心认 真，集思广益，这样才能把问题解决。北京中国铁道出版社2007. 6北京清华大学出版社2002. 9北京清华大学出版社2010.6七、附录源程序：#include<string.h>#include<malloc.h>#include<stdio.h>#include<stdlib.h>#include<math.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE-1typedef int Status; / Status是函数的类型淇值是函数结果状态代码#define MAX_NAME 10/顶点字符串的最大长度#define MAXCLASS 100int Z=0;int X=0;int xqzs,q=l,xfsx;typedef int InfoType;typedef char VertexTypeMAX_NAME; / 字符串类型/图的邻接表存储表示#define MAX_VERTEX_NUM 100typedef enumDGGraphKind; / 有向图，有向网,无向图，无向网typedef struct ArcNode(int adjvex; /该弧所指向的顶点的位置struct ArcNode *nextarc; / 指向下一条弧的指针InfoType *info; 网的权值指针) ArcNode; / 表结点 typedef struct(VertexType data; / 顶点信息ArcNode firstarc; /第一个表结点的地址，指向第一条依附该顶点的弧的指针VNode,AdjListMAX_VERTEX_NUM; / 头结点 typedef struct (AdjList vertices,verticestwo;int vexnum,arcnum; /图的当前顶点数和弧数int kind; 图的种类标志JALGraph;/图的邻接表存储的基本操作int LocateVex(ALGraph G,VertexType u) /初始条件：图G存在,u和G中顶点有相同特征/操作结果：假设G中存在顶点u,那么返回该顶点在图中位置;否那么返回-1int i;for(i=0;i<G.vexnum;+i)if(strcmp(u,G. vertices i.data)=0) return i;return -1;)Status CreateGraph(ALGraph *G) 采用邻接表存储结构，构造没有相关信息的图G(用一个函数构造种图)int i,j,k;VertexType va,vb;ArcNode *p;printf(”请输入教学计划的课程数:n) scanf("%d”,&(*G).vexnum);printf(”请输入拓扑排序所形成的课程先修关系的边数:n) scanf(M%dH,&(*G).arcnum);printff 请输入d 个课程的代表值(<%d 个字符):n(*G).vexnum,MAX_NAME);for(i=0;iv(*G).vexnum;+i) / 构造顶点向量 scanf(n%sn,(：HG).vertices|i.data);(*G).verticesi.firstarc=NULL;)printf("请输入d 个课程的学分值(<%d 个字符):n(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;+i) 构造顶点向量 scanf(n%sn,(*G).verticestwoi.data);)printff请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n) for(k=0;k<(*G).arcnum;+4-k) / 构造表结点链表 scanf(n%s%sn,va,vb);i=LocateVex(*G,va); 弧尾j=LocateVex(*G,vb); / 弧头p=(ArcNode*)malloc(sizeof( ArcNode);p->adjvex=j;p->info=NULL; / 图p->nextarc=(*G).verticesi.firstarc; / 插在表头(*G).vcrticcsi.firstarc=p;return OK;)void Display(ALGraph G)/输出图的邻接矩阵Gint i;ArcNode *p;/ switch(Gkind)/ case DG: printf("有向图rT);/)printf(n%d 个顶点：n”,Gvexnum);for(i=0;i<G.vexnum;+i)printf(H%s Hverticesi.data);printf(nn%d 条弧(边):n”,G.arcnum);for(i=0;i<G.vexnum;i+4-)(p=G.verticesi.firstarc;while(p)printf(,%s->%s ",G.verticesi.data,G.verticesp->adjvex.data); p=p->nextarc;printf(nnn);) ) void FindInDegree(ALGraph G,int indegree)/求顶点的入度，算法调用int i;ArcNode *p;for(i=0;ivG.vexnum;i+)indegreei=O; / 赋初值for(i=0;i<G.vexnum;i+)(p=G vertices i.firstarc;while(p) indegreep->adjvex+; p=p->nextarc;) ) typedef int SElemType; /栈类型 栈的顺序存储表示#define STACKJNIT_SIZE 10/存储空间初始分配量#define STACKINCREMENT 2 /存储空间分配增量 typedef struct SqStack(SElemType *base; 在栈构造之前和销毁之后，base的值为NULL SElemType *top; 栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack; / 顺序栈/顺序栈的基本操作Status InitStack(SqStack *S) /构造一个空栈S(*S).base=(SElemType *)manoc(STACKNIT_SIZE*sizeof(SElemType);if(!(*S).base)exit(OVERFLOW); /存储分配失败(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;return OK;void ClearStack(SqStack *S) 清空栈的操作 (S->top=S->base;Status StackEmpty(SqStack S)假设栈S为空栈，那么返回TRUE,否那么返回FALSEif(S.top=S.base)return TRUE;elsereturn FALSE;Status Pop(SqStack *S,SElemType *e)假设栈不空，那么删除S的栈顶元素，用e返回其值，并返回OK；否那么返回ERROR if(*S).top=(*S).base)return ERROR;*e=*-(*S).top;return OK;Status Push(SqStack *S,SElemType e)/插入元素e为新的栈顶元素if(*S).top-(*S).base>=(*S).stacksize) / 栈满,追加存储空间(*S).base=(SElemType *)reaHoc(*S).base,(*S).Stacksize+STACKINCREMENT)*sizeof(SElemType);if(!(*S).base)exit(OVERFLOW); /存储分配失败(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+二STACKINCREMENT;*(*S).top)+=e;return OK;)typedef int pathoneMAXCLASS;typedef int pathtwoMAXCLASS;Status TopologicalSort(ALGraph G) 有向图G采用邻接表存储结构。假设G无回路，那么输出G的顶点的一个拓扑序列并返回 OK/否那么返回ERRORoint i,k,j=O,count,indegreeMAX_VERTEX_NUM;bool has=false;SqStack S;pathone a;pathtwo b;ArcNode *p;FindInDegree(G,indegree); / 对各顶点求入度 indegree0.vernum-1InitStack(&S); / 初始化栈for(i=0;i<G.vexnum;+i) / 建零入度顶点栈 Sif(!indegreei) Push(&S,i);/cout«*G.verticesi.data«endl;)/入度为者进栈count=0; /对输出顶点计数while(! StackEmpty(S) /栈不空Pop(&S,&i);ai=*G.verticesi.data;bi=*G.verticestwoi.data;printf("课程5： f 学分s”,G.verticesi.data,Gverticestwoi.data);输出i号顶点并计数+count;for(p=G.verticesi.firstarc;p;p=p->nextarc) 对i号顶点的每个邻接点的入度减k=p->adjvex;if(!(-indegreek) /假设入度减为,那么入栈Push(&S,k);/cout«RG.vcrticcsi.data«cndl;)if(count<G.vexnum)printf("此有向图有回路n”)；return ERROR;)elseprintf("为一个拓扑序列。nn);has=true;)输出内容=FindInDegree(G,indegree); 11 对各顶点求入度 indegreeO.vernum-lCIearStack(&S);printf("= 课 程 计 划 如 下=、/)；int xqs=l; /学期数int xqxf;while(xqs<=xqzs)(int result! 20;int top=0;int num=0;/学期学分计算xqxf=0;for(i=0;i<G.vexnum;+i) / 建零入度顶点栈 S if(O=indegreei) ( Push(&S,i);) while(! StackEmpty(S) ( Pop(&S,&i);xqxf=xqxf+atoi(Gverticestwo| i .data);if(xqxf>xfsx) break;/indegreei;for(p=G.verticesi.firstarc;p;p=p->nextarc)对i号顶点的每个邻接点的入度减1k=p->adjvex; indcgrcck-; ) resulttop+=i; ) printf("第d个学期应学课程为:n",xqs); for(num=0;num<top;num4-+)printf(n iM® %snH,G. verticesl result| num | |.data); ) xqs+;return OK;)void main() ALGraph f; a / V I *£*1* *1#*1* *1* *1* *1* *1* *£* *£*1* *1* *1* *1* *X* *X* *£*1* *1* xt* *1*1* *£* *1* *1* *1* *1*1 *1* *£*1*1* *1* *1* *1*£*1* *1* *1* *1*5* *1* *1* *1* *1*i* *X*nn”)printf(nprintf(nprintf(ny* ->- f *1* *1* *T* <T><i* <T*ri* rx* ri* ri* *T*ri* rT* rT* *Jwevw erw erw*Tw *Tw *iwri* ri* ri*<iw *Tw <Tw数据结构课程设计nn”）；课 题：教学计划编制nn”）；试 验者：合肥学院 网络工程1班nn”）; » /QIKf> kIx kV> k1> k1*9 vf> k!> kT> k)> *2 Kf> k!>4!*k£* k£*1# *3* k£*vl* k1k1kI> K(> k2> vlk!> k1> k1> *3*十十, rT* *7* r1* ri* ri* *T* *1* r5> <7> r1* rT* ri* ri* *T* <T* r?* r?* rr» rlw riw *T* rT* ri*T* el* rj* rj* ri* <i* <i* <T* <T>*1* *1* *7*<i* ri* *7* rj* <i* *1* *Tw *i* *7* r?w *?* *T* *T* *T* *5 rr* r?* rT*nW”)printf(”请输入学期总数:n")；scanf(n%dn,&xqzs);printf(”请输入学期的学分上限:n)scanf(H%dn,&xfsx);CreateGraph(&f);/ system("cls");Display(f)；TopologicalSort(f);11网工一班单东亚2013年6月16日教学计划编制问题实验设计报告一、问题分析和任务定义名称：教学计划编制问题内容：大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年 含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而 且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以 有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计 划编制程序。要求：a.输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位 的字母数字串）、学分和直接先修课的课程号。b.允许用户指定以下两种编排策略之一：一是使学生在各学期中的学习负担尽量 均匀；二是使课程尽可能地集中在前几个学期中。c.假设根据给定的条件问题无解，那么报告适当的信息；否那么，将教学计划输出 到用户指定的文件中。计划的表格格式自行设计。二、数据结构的选择和概要设计2.1测试数据及实验分析（1）测试数据学期总数:6；学分上限：10；该专业共开设课数：12课程号：从C01到C12；学分顺序：2, 3, 4, 3, 2, 3, 4, 4, 7, 5, 2, 3。（2） .实验分析可设学期总数不超过6,课程总数不超过12o如果输入的先修课程号不在该专业开设的 课程序列中，那么作为错误处理。应建立内部课程号与课程号之间的对应关系。2. 2输入输出的要求输入参数包括：学期总数，一学期的学分上限，每门课的课程号(固定占3位的字母数字串)、 学分和直接先修课的课程号。输出要求输出各门课程所对应的学分，以及每学期各门课程的安排。2. 3课题的功能模块的划分(1)程序的模块组成LocateVex ()：图的邻接表存储的基本操作CreateGraph ()：构造生成树Display ()：输出图的邻接矩阵FindlnDegree ()：求顶点的入度InitStack ()：构造一个空栈ClearStack ()：清空栈StackEmpty ()：判断是否为空栈Pop ()：出栈Push ()：入栈TopologicalSort ()：输出G顶点的拓扑排序结果(2)模块的层次结构及调用关系Main。函数TopologicalSDisplay ()输出CreateGraphort()输出G 图的邻接矩阵()生成图顶点的拓扑排序结果图2模块层次结构2.4模块的主要功能1. CreateGraph ()：构造生成图。采用邻接表存储结构，构造没有相关信息的图G(用一个函 数构造种图)2. Display ()：输出图的邻接矩阵。采用循环设置输出图的邻接矩阵。3. TopologicalSort ()：输出G顶点的拓扑排序结果。有向图G采用邻接表存储结构。假设G无回路,那么输出G的顶点的一个拓扑序列并返回0K,否那么返回ERRORo具体设计见“详细设计”-“主要函数流程图”。2. 5数据结构和数据库结构储存的数据为结构体类型数组，以及结构体单链表结点类型。表 1： struct ArcNode弧所指定点位置指向下一条弧的指针网的权值指针intstructInfoType表 2： typedef struct顶点信息第一个表结点的地址VertexTypeArcNode三.详细设计2.1 采用C语言定义相关的数据类型。其中包括字符常量，整型，字符型，字符串型，typedef定义的类型，结构体型，单链 表节点类型，结构体数组。3. 2主要函数的流程图l.LocateVex ()：图的邻接表存储的基本操作。由初始条件：图G存在,u和G中顶点有相同特征转而进行判断，假设G同特征转而进行判断，假设G中存在顶点u,那么返回该顶点在图中位置；否那么返回如图图 3 Locate Vex ()图 4 CreateGraph ()图 5 Display ()2. CreateGraph ()：构造生成图。采用邻接表存储结构，构造没有相关信息的图G(用一个函 数构造种图)。如图4Display ()：输出图的邻接矩阵，采用循环设置输出图的邻接矩阵，如图5。.FindlnDegree ()：求顶点的入度，如图6.图 6 FindlnDegree ()图 7 nitStack ()InitStack ()：构造一个空栈,如图6。5. ClearStack ()：清空栈。6. StackEmpty ()：判断栈是否为空。假设栈S为空栈，那么返回TRUE,否那么返回FALSE,如图7oT图 8 push ()图 8 push ()图 9,TopologicalSort()7. Push ()：入栈。插入元素e为新的栈顶元素。如图8lO.TopologicalSort ()：输出G顶点的拓扑排序结果。有向图G采用邻接表存储结构。假设 G无回路，那么输出G的顶点的一个拓扑序列并返回0K,否那么返回ERROR,如图9。3. 3画出各函数的调用关系图图10 .各函数的调用关系四.程序调试4.1 测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出 结果。准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出 结果。数据如下：学期总数：6；学分上限：10；该专业共开设课数：12课程号：从C01到C12；学分顺序：2, 3, 4, 3, 2, 3, 4, 4, 7, 5, 2, 3。先修顺序：4.2 使用说明及调试过程输入学期总数，学分上限，课程数，先修关系边数，课程代表符号，相对 学分值：数据结课 题试验者构课程设计:教学计划编制=合肥学院 网络工程1班 请输入学期总数：;青输入学期的学分上限：售输入教学计划的课程数：善输入拓扑排序所形成的课程先修关系的边数：14请输入12个课程的代表值10个字符 =c01 c02 c03 c04 c05 c06 c07 c08 c09 cl0 ell cl2请输入12个课程的学分值10个字符:234323447523请顺序输入每条弧边的弧尾和弧头（以空格作为间隔）:c01 C04图11