数据结构课程设计——教学计划编制.docx

《数据结构课程设计——教学计划编制.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计——教学计划编制.docx（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、攀枝花学院课程设计论文 教学计划编制问题 摘 要 教学计划（课程计划）是课程设置的整体规划，它规定不同课程类型相互结 构的方式，也规定了不同课程在管理学习方式的要求及其所占比例，同时，对学 校的教学、生产劳动、课外活动等作出全面安排，具体规定了学校应设置的学科、 课程开设的顺序及课时分配，并对学期、学年、假期进行划分。 根据一定的教育目的和培养目标制定的教学和教育工作的指导文件。它决定 着教学内容总的方向和总的结构，并对有关学校的教学、教育活动，生产劳动和 课外活动校外活动等各方面作出全面安排，具体规定一定学校的学科设置、各门 学科的教学顺序、教学时数以及各种活动等。教学计划、教学大纲和教科书

2、互相 联系，共同反映教学内容。 近代以来，特别是在实行学科课程的条件下，教学计划主要是学科的计划， 或只是学科表。随着社会经济和科学技术的新发展，教育结构不断发生变革，现 代教育和教学理论主张对教学计划的结构实行改革。除了教学以外，生产劳动、 科技活动、发展体力和增进健康的活动、艺术活动和社会活动等也应列入教学计 划。下面就利用对此进行程序设计，已达到预期的目的。 关键字：数据结构，教学计划编制，抽象数据类型，程序设计 - 1 - 攀枝花学院课程设计论文 教学计划编制问题 1. 需求分析 根据课程之间的依赖关系制定课程安排计划，输入课程数及课程之间的关 系。需要利用代码实现排序，以及对各个学期

3、课程安排进行排序并输出。 1.1问题描述 大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每 学年含两学期，每学期的时间长度和学分上限值均相等，每个专业开设的课程都 是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修 课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这 样的前提下设计一个教学计划编制程序。 1.2设计思路 首先利用拓扑排序对课程先后顺序进行分析，邻接表位主要存储结构，栈为 主要辅助结构，给出课程之间的先后关系比如AOV网，然后进行拓扑排序，但当 又向图中存在环时，无法查找该图的一个拓扑排序，当图中的所有顶点全部输出， 表示

4、对该图排序成功，实现拓扑排序算法时，相应的建立邻接表存储AOV网，为 了避免重复检测入度为零的顶点，建立一个栈来对入度为零的顶点进行存放。根 据课程的先后关系，对个学期的课程进行排序，输出。 1.3设计环境、原理 设计环境和器材： 硬件：计算机；软件：Microsoft Visula C+。 设计原理说明：运用图的拓扑排序对课程先修排列的实现，并调用递归完成拓扑 排序。 1.4实验目的 培养学生用学到的书本知识解决实际问题的能力；培养实际工作所需要的动 手能力；培养学生以科学理论和工程上能力的技术，规范地开发大型、复杂、高 质量的应用软件和系统软件具有关键性作用。通过课程设计的实践，学生可以在

5、 程序设计方法、上机操作等基本技能和科学作风方面受到比较系统和严格的训 练。 1.5实验内容 针对计算机系本科课程，根据课程之间的依赖关系（如离散数学应在数据结 构之前开设）制定课程安排计划，并满足各学期课程数目大致相同。 - 2 - 攀枝花学院课程设计论文 教学计划编制问题 2.概要设计： 2.1流程图 void FindInDegree(ALGraph G, int indegree)/求图中各节点的入度 （如下左图）void CreatGraph(ALGraph *G)/构件图（如下右图）。 void TopologicalSort_1(ALGraph G,int numterm,int

6、 uplcredit) /有向 图G采用邻接表存储结构(如下左图)； void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) /有向 图G采用邻接表存储结构（如下右图）。 - 3 - 攀枝花学院课程设计论文 教学计划编制问题 主函数： void main() - 4 - 攀枝花学院课程设计论文 教学计划编制问题 2.2抽象数据类型图的定义 ADT Graph 数据对象V:V是具有相同特性的数据元素的集合,称为顶点集. 数据关系R: R=VR VR=(v,w)|v,wV,(v,w)表示v和w之间存在直接先修关系 基本操作P: voi

7、d CreatGraph(ALGraph *); 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 - 5 - 攀枝花学院课程设计论文 教学计划编制问题 数据关系:R1=ai-1 ai|ai-1,aiD,i=2,n

8、基本操作: void InitStack (SqStack *S); int StackEmpty(SqStack S); void Push(SqStack *S, int ); int Pop(SqStack *S, int *e); ADT Stack 2.3主程序 int main() /主函数 int numterm; /学期总数 int uplcredit; /一个学期的学分上限 int selectway; ALGraph G; 请输入学期总数 请输入学期总数 请输入一个学期的学分上限 请输入一个学期的学分上限 CreatGraph(&G); 请选择编排策略:1.课程尽可能集中到

9、前几个学期；2.课程尽量均 匀分布 匀分布 if(selectway=1) TopologicalSort_1(G,numterm,uplcredit); if(selectway=2) TopologicalSort_2(G,numterm,uplcredit); return 0; 2.4本程序只有两个模块,调用关系简单 主程序模块拓扑排序模块 - 6 - 攀枝花学院课程设计论文 教学计划编制问题 4.详细设计 4.1头结点、表结点、邻接表的定义 #define MAX_VERTEX_NUM 100 /最大课程总数 typedef struct ArcNode int adjvex; st

10、ruct ArcNode *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 CreatGrap

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

12、枝花学院课程设计论文 教学计划编制问题 typedef int ElemType; typedef struct 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); 出栈操作 4.3主程序和其他算法： #include #include #include / malloc()等

13、#include / INT_MAX等 #include / EOF(=Z或F6),NULL #include / atoi()52 #include / eof() #include / floor(),ceil(),abs() #include / exit() #include / cout,cin/ 函数结果状态代码 #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 typedef int Status; / Status是函数的类型,其值是函数结果状态代码，如 OK等 t

14、ypedef int Boolean; / Boolean是布尔类型,其值是TRUE或FALSE - 8 - 攀枝花学院课程设计论文 教学计划编制问题 #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 enumDGGraph

15、Kind; /* 有向图,有向网,无向图,无向网 */ typedef struct ArcNode int adjvex; /* 该弧所指向的顶点的位置 */ struct ArcNode *nextarc; /* 指向下一条弧的指针 */ InfoType *info; /* 网的权值指针） */ ArcNode; /* 表结点 */ typedef struct VertexType data; /* 顶点信息 */ ArcNode *firstarc; /* 第一个表结点的地址,指向第一条依附该顶点的弧的 指针 */ VNode,AdjListMAX_VERTEX_NUM; /* 头结

16、点 */ 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; - 9 - 攀枝花学院课程设计论文 教学计划编制问题 for(i=0;iG.vexnum;+i) i

17、f(strcmp(u,G.verticesi.data)=0) return i; return -1; Status CreateGraph(ALGraph *G) /* 采用邻接表存储结构,构造没有相关信息的图G(用一个函数构造4种图) */ int i,j,k; VertexType va,vb; ArcNode *p; 请输入教学计划的课程数 ArcNode *p; 请输入教学计划的课程数 请输入教学计划的课程数 请输入教学计划的课程数 请输入拓扑排序所形成的课程先修关系的边数 请输入拓扑排序所形成的课程先修关系的边数 请输入拓扑排序所形成的课程先修关系的边数 请输入拓扑排序所形成的课

18、程先修关系的边数 请输入%d个课程的代表值(%d个字符 个字符 */ for(i=0;i(*G).vexnum;+i) /* 构造顶点向量 */ (*G).verticesi.firstarc=NULL; 个字符 for(i=0;i(*G).vexnum;+i) /* 构造顶点向量 */ 请输入%d个课程的学分值(%d个字符 */ 请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔 以空格作为间隔 */ for(k=0;kadjvex=j; p-info=NULL; /* 图 */ p-nextarc=(*G).verticesi.firstarc; /* 插在表头 */ (*G).verti

19、cesi.firstarc=p; - 10 - 攀枝花学院课程设计论文 教学计划编制问题 return OK; void Display(ALGraph G) /* 输出图的邻接矩阵G */ int i; ArcNode *p; switch(G.kind) 有向图 有向图 个顶点： 个顶点： for(i=0;iG.vexnum;+i) for(i=0;iG.vexnum;+i) for(i=0;iG.vexnum;+i) 条弧(边边 for(i=0;inextarc; void FindInDegree(ALGraph G,int indegree) /* 求顶点的入度，算法调用 */ in

20、t i; ArcNode *p; for(i=0;iG.vexnum;i+) indegreei=0; /* 赋初值 */ for(i=0;iadjvex+; p=p-nextarc; typedef int SElemType; /* 栈类型 */ /*栈的顺序存储表示 */ #define STACK_INIT_SIZE 10 /* 存储空间初始分配量 */ #define STACKINCREMENT 2 /* 存储空间分配增量 */ typedef struct SqStack SElemType *base; /* 在栈构造之前和销毁之后，base的值为NULL */ SElemTy

21、pe *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; ret

22、urn OK; Status StackEmpty(SqStack S) /* 若栈S为空栈，则返回TRUE，否则返回FALSE */ if(S.top=S.base) return TRUE; else return FALSE; Status Pop(SqStack *S,SElemType *e) - 12 - 攀枝花学院课程设计论文 教学计划编制问题 /* 若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回 ERROR */ if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK; Status Push(

23、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; *(

24、*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; SqStack S; pathone a; pathtwo b; ArcNode *p; - 13 - 攀枝花学院课程设计论文 教学计划编制问题 Find

25、InDegree(G,indegree); /* 对各顶点求入度indegree0.vernum-1 */ InitStack(&S); /* 初始化栈 */ for(i=0;inextarc) /* 对i号顶点的每个邻接点的入度减1 */ k=p-adjvex; if(!(-indegreek) /* 若入度减为0,则入栈 */ Push(&S,k); if(countG.vexnum) 此有向图有回路 if(countG.vexnum) 此有向图有回路 return ERROR; else else 为一个拓扑序列。 为一个拓扑序列。 while(q=xqzs) int C=0; if(X

26、=G.arcnum) - 14 - 攀枝花学院课程设计论文 教学计划编制问题 while(C=xfsx) C+=*G.verticestwoZ.data; +Z; 个学期应学课程 第%d个学期应学课程 while(X=Z) while(X=Z) +X; coutendl; q+; else else 课程编制已经完成！ 课程编制已经完成！ return OK; return OK; void main() ALGraph f; 教学计划编制问题的数据模型为拓扑排序AOV-网结构。 ALGraph f; 网结构。 网结构。 以下为教学计划编制问题的求解过程 以下为教学计划编制问题的求解过程 以下

27、为教学计划编制问题的求解过程 请输入学期总数 请输入学期总数 请输入学期总数 请输入学期总数 请输入学期的学分上限 请输入学期的学分上限 请输入学期的学分上限 CreateGraph(&f); Display(f); TopologicalSort(f); - 15 - 攀枝花学院课程设计论文 教学计划编制问题 5.用户使用和说明 使用VC+，打开教学计划编制问题.cpp文件，接着编译，无错误，然后重 建也没有错误，最后执行该文件。显示如下图： 要求输入学期总数、一个学期的学分上限、需要编排课程总数、课程名、课 程号、该课程的学分，按照出现的每一步来输入该课程设计所提供的相关数据。 然后还要输

28、入课程先修课程总数，依据教科书图726，可以算出有16种关系， 分别输出如下图所示。接着程序会根据这些数据，自动生成建立好的邻接表，用 户可以根据系统显示的选择编排策略进行选择，有两种编排策略，最后结果体现 在实验的正确测试结果里（如上图）。 - 16 - 攀枝花学院课程设计论文 教学计划编制问题 6.调试分析 6.1实验过程中出现的问题及解决方法 我们在实验过程中遇到的最大难题是两个课程排序算法的编写。刚开始的时 候没有任何的思路，网上也只有拓扑排序的算法，对于课程设计要求的排序算法 没有任何头绪。经过请教老师和同学以及翻阅了一些相关书籍，并在网上的搜索 有了排序算法的大体思路。经过三天的修

29、改，终于写出了符合要求的排序算法。 6.2测试数据 学期总数：6；学分上限：10；该专业共开设12门课，课程号从01到12， 学分顺序为2，3，4，3，2，3，4，4，7，5，2，3。 6.3测试结果（包含正确和错误的） 正确测试结果： - 17 - 攀枝花学院课程设计论文 教学计划编制问题 错误测试结果： - 18 - 攀枝花学院课程设计论文 教学计划编制问题 6.4测试数据及程序运行情况 输入的内容如下: 课程编号 课程名称 学分 先决条件 01 程序设计基础 2 无 02 离散数学 3 01 03 数据结构 4 01，02 04 汇编语言 3 01 05 语言的设计和分析 2 03，04

30、 06 计算机原理 3 11 07 编译原理 4 05，03 08 操作系统 4 03，06 09 高等数学 7 无 10 线性代数 5 09 11 普通物理 2 09 12 数值分析 3 09，10，01 两种编排方法都输出结果为: 第一学期学的课程有:高等数学 程序设计基础； 第二学期学的课程有:普通物理 线性代数 汇编语言； 第三学期学的课程有:数值分析 计算机原理 离散数学； 第四学期学的课程有:数据结构； - 19 - 攀枝花学院课程设计论文 教学计划编制问题 第五学期学的课程有:操作系统 语言的设计和分析； 第六学期学的课程有:编译原理。 7.实验分工 8.总结 刚开始学的时候确实

31、有很多地方我很不理解，每次上课时老师都会给我们出 不同的设计题目，对于我们一个初学者来说，无疑是一个具大的挑战，撞了几次 壁之后，我决定静下心来，仔细去写程序。老师会给我们需要编程的内容一些讲 解，顺着老师的思路，来完成自己的设计，我们可以开始运行自己的程序，可是 好多处的错误让人看的可怕，还看不出到底是哪里出现了错误，但是程序还是得 继续下去，我多次请教了老师和同学，逐渐能自己找出错误，并加以改正。经过 了这次课程设计，现在已经可以了解很多错误在英文里的提示，这对我来说是一 个突破性的进步，眼看着一个个错误通过自己的努力在我眼前消失，觉得很是开 心。此次的程序设计能够成功，是我和我的同学三个

32、人共同努力作用的结果。在 这一段努力学习的过程中，我们的编程设计有了明显的提高。 其实现在想起来，收获还真是不少，虽然说以前非常不懂这门语言，在它上 面花费了好多心血，觉得它很难，是需用花费了大量的时间编写出来的。现在真 正的明白了一些代码的应用，每个程序都有一些共同点，通用的结构，相似的格 式。同时也对教学编制问题有了进一步的认识。只要努力去学习，就会灵活的去 应用它。 9.参考文献 1数据结构（C语言版），严蔚敏，清华大学出版社，2003。 - 20 - 攀枝花学院课程设计论文 教学计划编制问题 2数据结构题集，严蔚敏，清华大学出版社，2005。 3数据结构（C语言版），刘大有，高等教育出版社，2004。 4Data Structure with C+，William FordWilliam Topp，清华大学 出版社，2003。 - 21 -