数据结构之教学计划编制问题.doc

1、课程设计说明书题目： 教学计划编制问题（A类） 院 系： 计算机科学系 专业班级： 06网络工程 学 号： 学生姓名： 指导教师： 一. 需求分析（1）实验内容和实验目的：1.大学的每个专业都要编制教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限都相等。每个专业开设的课程都是确定的，而且课程的开设时间的安排必须满足先修关系。每个课程的先修关系都是确定的，可以有任意多门，也可以没有。每一门课程恰好一个学期。试在这样的情况下设置一个教学计划编制程序。2.在大学的某个专业中选取几个课程作为顶点,通过各门课的先修关系来构建个图,该图用邻接表来存储,邻接表的头结点存储

2、每门课的信息.3.本程序的目的是为用户编排课程,根据用户输入的信息来编排出每学期要学的课程.（2）测试数据：学期总数：6；学分上限：10；该专业共开设12门课，课程号从01到12，学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。先修关系见教科书图726。（3）测试结果（包含正确和错误的）：正确测试结果：错误测试结果：二. 概要设计1. 抽象数据类型图的定义如下: ADT Graph数据对象V:V是具有相同特性的数据元素的集合,称为顶点集.数据关系R: R=VR VR=(v,w)|v,wV,(v,w)表示v和w之间存在直接先修关系基本操作P:void CreatGraph(ALGrap

3、h *);void FindInDegree(ALGraph , int * );void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);ADT Graph栈的定义:ADT Stack数据对象:D=ai|aiElemSet,i=1,2,n,n=0 数据关系:R1=ai-1 ai|ai-1,aiD,i=2,n基本操作:void InitStack (SqStack *S);int StackEmpty(SqStac

4、k S);void Push(SqStack *S, int );int Pop(SqStack *S, int *e);ADT Stack2. 主程序 int main() /主函数 int numterm; /学期总数 int uplcredit; /一个学期的学分上限 int selectway; ALGraph G; printf(请输入学期总数:n); scanf(%d,&numterm); printf(请输入一个学期的学分上限:n); scanf(%d,&uplcredit); CreatGraph(&G); printf(请选择编排策略:1.课程尽可能集中到前几个学期；2.课程

5、尽量均匀分布n);scanf(%d,&selectway); if(selectway=1) TopologicalSort_1(G,numterm,uplcredit); if(selectway=2) TopologicalSort_2(G,numterm,uplcredit); system(pause); return 0;3. 本程序只有两个模块,调用关系简单. 主程序模块 拓扑排序模块三详细设计1头结点，表结点，邻接表的定义#define MAX_VERTEX_NUM 100 /最大课程总数typedef struct ArcNode int adjvex; struct ArcN

6、ode *nextarc; ArcNode;typedef struct VNode char name24; /课程名 int classid; /课程号 int credit; /课程的学分 int indegree; /该结点的入度 int state; /该节点的状态 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VEXTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; ALGraph;邻接表的基本操作：void CreatGraph(ALGraph *);

7、创建邻接表void FindInDegree(ALGraph , int * );求一个结点的入度void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);拓扑排序来编排课程void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);拓扑排序来编排课程2栈的定义：#define STACk_INIT_SIZE 100 /存储空间的初时分配量#define STACKINCREMENT 10 /存储空间的分配增量typedef int ElemType;typedef str

8、uct AdjList vertices; int vexnum, arcnum; ALGraph;基本操作：void InitStack (SqStack *S);栈的初始化int StackEmpty(SqStack S);判断栈是否为空void Push(SqStack *S, int );入栈操作int Pop(SqStack *S, int *e);出栈操作3主程序和其他算法int main() /主函数 int numterm; /学期总数 int uplcredit; /一个学期的学分上限 int selectway; ALGraph G; printf(请输入学期总数:n);

9、scanf(%d,&numterm); printf(请输入一个学期的学分上限:n); scanf(%d,&uplcredit);CreatGraph(&G);printf(请选择编排策略:1.课程尽可能集中到前几个学期；2.课程尽量均匀分布n); scanf(%d,&selectway); if(selectway=1) TopologicalSort_1(G,numterm,uplcredit); if(selectway=2) TopologicalSort_2(G,numterm,uplcredit); system(pause); return 0;void CreatGraph(A

10、LGraph *G)/构件图int i, m, n; ArcNode *p; printf(请输入需要编排课程总数:n); scanf(%d,&G-vexnum); for( i=1;ivexnum;i+) printf(请输入课程名n); scanf(%s,&G-verticesi.name); printf(请输入课程号n); scanf(%d,&G-verticesi.classid); printf(请输入该课程的学分n); scanf(%d,&G-verticesi.credit); G-verticesi.indegree=0; G-vertices i.state=NOTSTUD

11、Y; G-verticesi.firstarc=NULL; printf(请输入课程先修关系总数：); scanf(%d,&G-arcnum); printf(请顺序输入每个课程先修关系(先修课程在前并以逗号作为间隔):n); for (i = 1; i arcnum; i+) printf(n请输入存在先修关系的两个课程的序号:); scanf(%d,%d,&n,&m); while (n G-vexnum | m G-vexnum) printf(输入的顶点序号不正确 请重新输入:); scanf(%d,%d,&n,&m); p = (ArcNode*)malloc(sizeof(ArcN

12、ode); if (p = NULL) printf(memory allocation failed,goodbey); exit(1); p-adjvex = m; p-nextarc = G-verticesn.firstarc; G-verticesn.firstarc = p; printf(n建立的邻接表为:n); /输出建立好的邻接表 for(i=1;ivexnum;i+) printf(%d:-,G-verticesi.classid); for(p=G-verticesi.firstarc;p!=NULL;p=p-nextarc) printf(%d-,p-adjvex);

13、printf(NULL); printf(n); void InitStack(SqStack *S) S-base=(int *)malloc(STACK_INIT_SIZE *sizeof(int); if (!S-base) printf(ERROR); exit(1); S-top=S-base; S-stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack *S) if(S-top=S-base) return OK; else return ERROR;void Push(SqStack *S,int e) if(S-top - S-base

14、 = S-stacksize) S-base = (int *) realloc (S-base , (S-stacksize + STACKINCREMENT) * sizeof(int); if(!S-base) printf(ERROR); exit(1); S-top = S-base + S-stacksize; S-stacksize += STACKINCREMENT; *S-top+ = e;int Pop(SqStack *S, int *e) if(S-top = S-base) exit(1); *e = * -S-top; return 0;void FindInDeg

15、ree(ALGraph G, int indegree)/求图中各节点的入度 int i; for (i = 1; i = G.vexnum; i+) indegreei = 0; for (i = 1; i adjvex+; G.verticesi.firstarc = G.verticesi.firstarc-nextarc; void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) FILE *fp; fp=fopen(bianpai.txt,w); ArcNode *p; SqStack S; int indegreeM;/

16、存放各节点的入度 int i,j, k, m,n; int count; /课程编排数目计数器 int sumcredit;/每个学期的课程学分累加器 FindInDegree(G, indegree); for (i = 1; i = G.vexnum; i+) G.verticesi.indegree=indegreei; InitStack(&S); count=0; k=0; while(count!=G.vexnum & k=numterm) sumcredit=0; for(i=1;i=G.vexnum;i+) /入度为零的节点入栈，即无先修的课程入栈 if(G.verticesi

17、.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY;/避免入度为零节点重复入栈 if(!StackEmpty(&S)&(sumcredit=uplcredit) k= k+1; printf(n); printf(第%d个学期学得课程有:n,k); sumcredit = 0; for(i=1;i=G.vexnum;i+)/入度为零的节点入栈，即无先修的课程入栈 if(G.verticesi.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S

18、,i); while(!StackEmpty(&S)&(sumcredituplcredit)/栈非空&学分总数小于学分上限 Pop(&S,&j); sumcredit = sumcredit + G.verticesj.credit; if(sumcredit nextarc)/对j号顶点每个邻接点的入度减一 G.verticesp-adjvex.indegree-; else Push(&S,j);/将未输出的节点重新压入栈 fprintf(fp,n); printf(n); if(countG.vexnum) printf(n课程编排出错n); else printf(n课程编排成功n)

19、; fclose(fp);void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) FILE *fp; fp=fopen(bianpai.txt,w); ArcNode *p; SqStack S; int indegreeM; int i,j, k, m,n; int maxnum; int sumnum; int count; /课程编排数目计数器 int sumcredit;/每个学期的课程学分累加器 FindInDegree(G, indegree); for (i = 1; i = G.vexnum; i+) G.vert

20、icesi.indegree = indegreei; InitStack(&S); count=0; k=0; maxnum = G.vexnum/numterm+1; sumnum = 0; while(count!=G.vexnum & k=numterm) for(i=1;i=G.vexnum;i+) /入度为零的节点入栈，即无先修的课程入栈 if(G.verticesi.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY; if(!StackEmpty(&S)&(sumcredi

21、t=uplcredit)&(sumnum=maxnum) k= k+1; printf(n); printf(第%d个学期学得课程有:,k); sumcredit = 0; sumnum = 0; for(i=1;i=G.vexnum;i+)/入度为零的节点入栈，即无先修的课程入栈 if(G.verticesi.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(!StackEmpty(&S)&(sumcredituplcredit)&(sumnummaxnum) /栈非空&学分总数小于学分上限&学期课程数目小于学期最大数目 P

22、op(&S,&j);/出栈 sumcredit = sumcredit + G.verticesj.credit; sumnum = sumnum+1; if(sumcredit = uplcredit)&(sumnum nextarc)/对j号顶点每个邻接点的入度减一 G.verticesp-adjvex.indegree-; else Push(&S,j); fprintf(fp,n); printf(n); if(countG.vexnum) printf(课程编排出错n); else printf(课程编排成功n); fclose(fp);流程图如下所示：void FindInDegr

23、ee(ALGraph G, int indegree)/求图中各节点的入度（如下左图）void CreatGraph(ALGraph *G)/构件图（如下右图） void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) /有向图G采用邻接表存储结构(如下左图)void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) /有向图G采用邻接表存储结构（如下右图）主函数：void main()四调试分析：（1）实验过程中出现的问题及解决方法我们在实验过程中遇到的最大难题是两个课程

24、排序算法的编写。刚开始的时候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索有了排序算法的大体思路。经过三天的修改，终于写出了符合要求的排序算法。（2）实验体会:经过此次课程设计，我们认识到了理论与实践结合的重要性，仅仅只是从课本上学到算法原理是远远不够的。在实践中，我们总会出现许多错误。这就要求我们以一个脚踏实地的态度来处理问题。我们深刻地认识到自己写程序的不足，使我们学到了好多有用的知识，让我们明白了C语言的语句用法。五用户使用和说明：使用VC+，打开教学计划编制问题.cpp文件，接着编译，无错误，然

25、后重建也没有错误，最后执行该文件。显示如下图：要求输入学期总数、一个学期的学分上限、需要编排课程总数、课程名、课程号、该课程的学分，按照出现的每一步来输入该课程设计所提供的相关数据。然后还要输入课程先修课程总数，依据教科书图726，可以算出有16种关系，分别输出如下图所示。接着程序会根据这些数据，自动生成建立好的邻接表，用户可以根据系统显示的选择编排策略进行选择，有两种编排策略，最后结果体现在实验的正确测试结果里（如上图）。六.测试数据及程序运行情况:输入的内容如下:课程编号 课程名称 学分 先决条件 01 程序设计基础 2 无 02 离散数学 3 01 03 数据结构 4 01，02 04

26、汇编语言 3 01 05 语言的设计和分析 2 03，04 06 计算机原理 3 11 07 编译原理 4 05，03 08 操作系统 4 03，06 09 高等数学 7 无 10 线性代数 5 09 11 普通物理 2 09 12 数值分析 3 09，10，01两种编排方法都输出结果为:第一学期学的课程有:高等数学 程序设计基础 第二学期学的课程有:普通物理 线性代数 汇编语言第三学期学的课程有:数值分析 计算机原理 离散数学第四学期学的课程有:数据结构第五学期学的课程有:操作系统 语言的设计和分析第六学期学的课程有:编译原理七.参考文献:数据结构、C程序设计、百度八、实验分工姓名分工黄玲报

27、告书综合整理和程序测试吴明敏制作流程图和一些资料查找陈娟资料查找及任务书的整理汤小玲程序查找和调试及资料整合闽江学院课程设计（论文）任务书 计算机科学 院系 软件 教研室学 号120061101412120061101419120061101420120061101425学生姓名黄玲吴明敏陈娟汤小玲专业（班级）网络工程4班设计题目教学计划编制问题（A类）设计技术参数1 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。2 要求每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。3 可设学期总数不超过12，课程

28、总数不超过100。如果输入的先修课程号不在该专业开设的课程序列中测作为错误处理。应建立内部课程序号与课程号之间的对应关系。设计要求（ 1 ）输入参数包括：学期总数，一学期的学分上限，每门课的课程号（固定占3位的字母数字串）、学分和直接先修课的课程号。（ 2 ）允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。（ 3 ）若根据给定的条件问题无解，则报告适当的信息；否则将教学计划输出到用户指定的文件中。计划的表格格式自行设计。工作量课程设计报告（不附源程序），不得少于10页，源程序不等小于300行工作计划整体设计和详细设计 2天编代码 1天调试和测试 1天设计论文书写 半天演示软件和答辩 半天 参考资料百度数据结构C程序设计指导教师签字教研室主任签字 2008年 6 月 17日