教学计划编制问题课程设计(共28页).doc
精选优质文档-倾情为你奉上信息与电气工程学院课程设计说明书（2015/2016学年第一学期）课程名称 ： 软件算法分析与设计 题 目 ： 教学计划编制 专业班级 ： 计算机1401 学生姓名 ： 李丹丹 学 号： 指导教师 ： 陈丽 设计周数 ： 一周 设计成绩 ： 2016年1月13日专心-专注-专业目录一、课题的主要功能1.1程序的功能大学的每个专业都要制订教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。本程序针对本科的学期内容，通过输入实际的课程及先后关系。结合每学期的学分及课程数，制定好学习计划。在输入相关数据后，程序会安排好每学期的课程。1.2.输入输出的要求输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。输出要求输出各门课程所对应的学分，以及每学期各门课程的安排。1.3运行环境1. WINDOWS 7系统2. Vc+6.0编译环境1.4开发工具 C语言二、概要设计2.1所负责的程序的模块LocateVex（）：图的邻接表存储的基本操作CreateGraph（）：构造生成树Display（）：输出图的邻接矩阵FindInDegree（）：求顶点的入度2.2模块的层次结构及调用关系Main()函数TopologicalSort（）输出G顶点的拓扑排序结果Display（）输出图的邻接矩阵CreateGraph（）生成图2.3模块的主要功能见“详细设计”“主要函数流程图”2.4数据结构和数据库结构储存的数据为结构体类型数组，以及结构体单链表结点类型。1 typedef struct ArcNode弧所指定点位置指向下一条弧的指针网的权值指针intstructInfoType2 typedef struct顶点信息第一个表结点的地址VertexTypeArcNode三主要功能的实现3.1采用C语言定义相关的数据类型。其中包括字符常量，整型，字符型，字符串型，typedef 定义的类型，结构体型，单链表节点类型，结构体数组。3.2主要函数的流程图1.LocateVex（）：图的邻接表存储的基本操作。由初始条件: 图G存在,u和G中顶点有相同特征转而进行判断，若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。int ii=0i<G.vexnumreturn i+ireturn -12.CreateGraph（）：构造生成图。采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图)。int i,j,k;i=0i<(*G).vexnumscanf("%s",(*G).verticesi.data);+iprintf("请输入%d个课程的学分值”)i=0i<(*G).vexnumscanf("%s",(*G).verticestwoi.data);+imulti3.Display（）：输出图的邻接矩阵。采用循环设置输出图的邻接矩阵。int i;G.kind=DGprintf("%d个顶点：n",G.vexnum);i=0i<G vexnum+imulti4.FindInDegree（）：求顶点的入度。int ii=0i<G.vexnumi+i=0i<G.vexnump=G.verticesi.firstarc;pindegreep->adjvex+;i+;所负责的部分程序：/* 图的邻接表存储的基本操作*/ int LocateVex(ALGraph G,VertexType u) /* 初始条件: 图G存在,u和G中顶点有相同特征*/ /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;i<G.vexnum;+i) if(strcmp(u,G.verticesi.data)=0) return i; return -1;Status CreateGraph(ALGraph *G) /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图) */ int i,j,k; VertexType va,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).verticesi.data); (*G).verticesi.firstarc=NULL; printf("请输入%d个课程的学分值(<%d个字符):n",(*G).vexnum,MAX_NAME); for(i=0;i<(*G).vexnum;+i) /* 构造顶点向量*/ scanf("%s",(*G).verticestwoi.data); printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n"); for(k=0;k<(*G).arcnum;+k) /* 构造表结点链表*/ scanf("%s%s",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).verticesi.firstarc=p; return OK; void Display(ALGraph G) /* 输出图的邻接矩阵G */ int i; ArcNode *p; switch(G.kind) case DG: printf("有向图n"); printf("%d个顶点：n",G.vexnum); for(i=0;i<G.vexnum;+i) printf("%s ",G.verticesi.data); printf("n%d条弧(边):n",G.arcnum); for(i=0;i<G.vexnum;i+) p=G.verticesi.firstarc; while(p) printf("%s%s ",G.verticesi.data,G.verticesp->adjvex.data); p=p->nextarc; printf("n"); void FindInDegree(ALGraph G,int indegree) /* 求顶点的入度，算法调用*/ int i; ArcNode *p; for(i=0;i<G.vexnum;i+) indegreei=0; /* 赋初值*/ for(i=0;i<G.vexnum;i+) p=G.verticesi.firstarc; while(p) indegreep->adjvex+; p=p->nextarc; 3.3画出各函数的调用关系图StackEmpty( )ClearStack( )FindInDegree( )Push （ ）StackEmpty（ ）Pop( )FindInDgree( )Push （ ）InitStack( )Tolopogicalsort( )Main函数Display( )CreatGraph( )四、程序调试4.1测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果。数据如下：学期总数：6；学分上限：10；该专业共开设课数：12课程号：从C01到C12；学分顺序：2，3，4，3，2，3，4，4，7，5，2，3。19421221011365788先修顺序(有向图表示)： 4.2使用说明输入学期总数，学分上限，课程数，先修关系边数输入课程代表符号：输入相对学分值：回车，将显示顶点的个数和弧的条数输入完成后执行可得到每个学期的课程计划结果五 总结体会 虽这门课程让我从C语言基础再深入的了解了软件开发的复杂性。对以往模糊的经验，起了总结提升的作用。在学习了这门课程后，我们进行了1个星期的课程设计，来实践我们所学这门课的内容。由于程序十分的复杂，遇到了很多常见的语法错误，及逻辑错误。这需要我们不断的调试分析。符号的格式之类，指针的用法，判断输入输出的条件都是十分容易出错的地方。在逐条排除，向同学老师请教后，程序终于得以完成。这让我明白了，解决问题，要细心认真，集思广益，这样才能把问题解决。六、附录6.1参考书目1 黄同成，黄俊民，董建寅数据结构M北京：中国电力出版社，20082 董建寅，黄俊民，黄同成数据结构实验指导与题解M北京：中国电力出版社，2008 3 严蔚敏，吴伟民. 数据结构（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(=Z或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 / 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如OK等 typedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE #define MAX_NAME 10 /* 顶点字符串的最大长度*/ #define MAXCLASS 100 int Z=0; int X=0; int xqzs,q=1,xfsx; typedef int InfoType; typedef char VertexTypeMAX_NAME; /* 字符串类型*/ /* 图的邻接表存储表示*/ #define MAX_VERTEX_NUM 100 typedef 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; /* 图的种类标志*/ ALGraph;/* 图的邻接表存储的基本操作*/ int LocateVex(ALGraph G,VertexType u) /* 初始条件: 图G存在,u和G中顶点有相同特征*/ /* 操作结果: 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1 */ int i; for(i=0;i<G.vexnum;+i) if(strcmp(u,G.verticesi.data)=0) return i; return -1;Status CreateGraph(ALGraph *G) /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造种图) */ int i,j,k; VertexType va,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).verticesi.data); (*G).verticesi.firstarc=NULL; printf("请输入%d个课程的学分值(<%d个字符):n",(*G).vexnum,MAX_NAME); for(i=0;i<(*G).vexnum;+i) /* 构造顶点向量*/ scanf("%s",(*G).verticestwoi.data); printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):n"); for(k=0;k<(*G).arcnum;+k) /* 构造表结点链表*/ scanf("%s%s",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).verticesi.firstarc=p; return OK; void Display(ALGraph G) /* 输出图的邻接矩阵G */ int i; ArcNode *p; switch(G.kind) case DG: printf("有向图n"); printf("%d个顶点：n",G.vexnum); for(i=0;i<G.vexnum;+i) printf("%s ",G.verticesi.data); printf("n%d条弧(边):n",G.arcnum); for(i=0;i<G.vexnum;i+) p=G.verticesi.firstarc; while(p) printf("%s%s ",G.verticesi.data,G.verticesp->adjvex.data); p=p->nextarc; printf("n"); void FindInDegree(ALGraph G,int indegree) /* 求顶点的入度，算法调用*/ int i; ArcNode *p; for(i=0;i<G.vexnum;i+) indegreei=0; /* 赋初值*/ for(i=0;i<G.vexnum;i+) p=G.verticesi.firstarc; while(p) indegreep->adjvex+; p=p->nextarc; typedef int SElemType; /* 栈类型*/ /*栈的顺序存储表示*/ #define STACK_INIT_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 *)malloc(STACK_INIT_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，否则返回FALSE */ if(S.top=S.base) return TRUE; else return 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 *)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; return OK; typedef int pathoneMAXCLASS;typedef int pathtwoMAXCLASS;Status TopologicalSort(ALGraph G) /* 有向图G采用邻接表存储结构。若G无回路,则输出G的顶点的一个拓扑序列并返回OK, */ /* 否则返回ERROR。*/ int i,k,j=0,count,indegreeMAX_VERTEX_NUM; bool has=false; SqStack S; pathone a; pathtwo b; ArcNode *p; FindInDegree(G,indegree); /* 对各顶点求入度indegree0.vernum-1 */ InitStack(&S); /* 初始化栈*/ for(i=0;i<G.vexnum;+i) /* 建零入度顶点栈S */ if(!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("课程%s学分%s ",G.verticesi.data,G.verticestwoi.data); /* 输出i号顶点并计数*/ +count; for(p=G.verticesi.firstarc;p;p=p->nextarc) /* 对i号顶点的每个邻接点的入度减*/ k=p->adjvex; if(!(-indegreek) /* 若入度减为,则入栈*/ Push(&S,k);/cout<<*G.verticesi.data<<endl; if(count<G.vexnum) printf("此有向图有回路n"); return ERROR; else printf("为一个拓扑序列。n");has=true; FindInDegree(G,indegree); /* 对各顶点求入度indegree0.vernum-1 */ ClearStack(&S); cout<<"=课程计划如下="<<endl; int qq=1; /学期数 int xxf; while(qq<=xqzs) int result20; int rtop=0; int nn=0; /int ccount=0; / 学期学分计算 xxf=0; for(i=0;i<G.vexnum;+i) /* 建零入度顶点栈S */ if(0=indegreei) Push(&S,i); while(!StackEmpty(S) int bb;Pop(&S,&i);bb=atoi(G.verticestwoi.data);xxf=xxf+bb;if(xxf>xfsx)break;indegreei-;for(p=G.verticesi.firstarc;p;p=p->nextarc) /* 对i号顶点的每个邻接点的入度减*/k=p->adjvex;indegreek-;/* if(!(-indegreek) 若入度减为,则入栈Push(&S,k);*/resultrtop=i;rtop+; cout<<"第"<<qq<<"个"<<"学期的课程为："<<endl; for(nn=0;nn<rtop;nn+) cout<<"课程"<<G.verticesresultnn.data<<endl; qq+; return OK;void main() ALGraph f; printf("教学计划编制问题的数据模型为拓扑排序AOV-网结构。n"); printf("以下为教学计划编制问题的求解过程:n"); printf("请输入学期总数:"); scanf("%d",&xqzs); printf("请输入学期的学分上限:"); scanf("%d",&xfsx); CreateGraph(&f); Display(f); TopologicalSort(f); 课程设计评 语课程设计成 绩指导教师（签字） 年 月 日
