《教学计划编制问题》数据结构课程设计说明书

1、华 北 科 技 学 院 数据结构课程设计说明书 班级 计算 B121 小组成员: 成绩: 小组成员: 成绩: 小组成员: 成绩: 设计题目: 教学计划编制问题 设计时间: 2014.6.23 至 2014.6.27 指导教师: 评 语: 评阅教师: _ 目目 录录 设计总说明.1 第 1 章 绪论.2 第 2 章 教学计划编制问题陈述及需求分析.3 2.1 教学计划编制问题陈述.3 2.2 功能需求分析.3 第 3 章 系统设计.4 3.1 总体设计.4 3.2 主要模块简介.6 第 4 章 详细设计.7 4.1 数据结构.7 4.3 设计说明.9 4.4 算法说明.9 第 5 章 编码与调试

2、.13 5.1 教学计划编制问题实例.13 5.2 程序运行结果.15 第 6 章 总结.19 参考文献.20 附录 源程序.21 教学计划编制问题教学计划编制问题 设计总说明设计总说明 根据任务要求及对实际情况的了解，可知设计中需要定义先修关系的 AOV 网图中的顶 点及弧边的结构体，采用邻接表存储结构，利用栈作辅助结构，在运行结果中将图的信息显 示出来，利用先修关系将课程排序，最后解决问题输出每学期的课程。整个系统从符合 操作简便、界面简洁、灵活、实用、安全的要求出发，完成教学计划编制问题的全过程，包 括创建三个数据结构（邻接表存储结构、栈、拓扑排序） 、数据的处理与计算、数据的分析、 结

3、果的输出。本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说 明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。 关键词：关键词：教学计划编制问题；数据结构；邻接表存储结构；栈；拓扑排序 第第 1 1 章章 绪论绪论 数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机 中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练培 养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。本次课程设计的内 容是教学计划编制问题，邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建 立一个单链表，第 i 个单链表

4、中的结点表示依附于顶点的边。栈是一种限定性的线性表， i v 它只允许在表尾插入元素或删除元素，所以栈具有后进先出的特性。拓扑排序是由某个集合 上的一个偏序得到该集合上的一个全序。而教学计划编制问题就是对排序问题的应用，通过 这个设计事例，我们有理由相信至此以后，我们对邻接表、栈和拓扑排序的理解将会是更上 一层楼。通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设 计、实现较大程序的完整过程，包括系统分析、编码设计以及调试分析，熟练掌握数据结构 的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。 第第 2 2 章章 教学计划编制问题陈述及需求分析教学计划编制问题

5、陈述及需求分析 2.12.1 教学计划编制问题陈述教学计划编制问题陈述 大学中每个专业都有固定的教学计划，任何专业的学习年限是固定的，每年两个学期， 每个专业开设的课程是确定的，而课程之间的开设时间是必须满足先修关系的。每们课可以 有多门先修课，也可以没有。以本科四年为准，要求设计一个教学计划。 输入学期总数，一学期的学分上限，每门课的课程号、学分和直接先修课的课程号。一 是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。输出 教学计划到用户指定的文件中，计划表格格式自行设计，若无结果可报告适当的信息。 2.22.2 功能需求分析功能需求分析 本系统主要实现对大学中每

6、个专业的教学计划进行设计，需要实现以下几个方面的功能： （1）创建存储结构：创建邻接表。 （2）数据的输入：学期总数，课程数，一学期的学分上限，每门课的课程号（固定占 2 位的数字串） 、学分和直接先修课的课程号。 （3）数据的处理：对输入的数据进行计算。 （4）结果的输出：输出各门课程所对应的学分，以及每学期各门课程的安排。 第第 3 3 章章 系统设计系统设计 3.1 总体设计总体设计 允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二 是使课程尽可能地集中在前几个学期中。采用第二种策略，使课程尽可能地集中在前几个学 期中，根据教学计划中的课程及其关系和学分定义图

7、的顶点和边的结构体，创建图，结合先 修关系的 AOV 网，采用邻接链表存储和使用前插法，通过菜单显示代号所对应课程及课程 的先修课程，运用拓扑排序将课程排序后并决定出每学期所学课程，最后输出图 G 的信息， 将图的顶点和弧边输出。具体流程图如图 3.1 所示。 图图 3.13.1 系统功能结构图系统功能结构图 开始 管理员：输入用户名和密码 创建图 CreateGraph（）：结合先修关系的 AOV 网，采用邻接表存储 菜单 OUTPUT()：显示课程代码、课程名称及 先修课程 输出图 G 的信息 Display( )：输出图的顶点和 弧边 拓扑排序 TopoSort( )：将课程排序后，编制

8、出 每学期所学的课程 结束 前插法 使课程尽可能 地集中在前几 个学期中 首先，初始化栈，构造一个空栈 S，判定这个栈是否为空栈，如果是，则进行下一步操 作，否则，返回错误；接下来对各个顶点求入度，将入度为零的顶点存入数组，当所有入度 为零的顶点都存入数组后，执行完毕。具体流程图如图 3.2 所示。 Y N N Y 图图 3.23.2 拓扑排序流程图拓扑排序流程图 初始化栈 InitStack(S) 对各顶点求入度，并存入数组 InDegreei 中（i=0n） 依次将入度为 0 的顶点存入栈中 推出栈顶的一个元素（入度为零的顶点号）至 i，输出 i，计数器加 1（Count+） 对以 i 号

9、顶点为尾弧的每个邻接点的入度减 1， 并将入度减 1 后为零的顶点号压入栈中，输出 i，计数器加 1(Count+) n 个顶点全输 出 Return ERROR Return OK 栈是否为空？ 3.23.2 主要模块简介主要模块简介 1、管理员 要进入管理员界面，首先需要输入用户名和密码。输入正确的用户名和密码后，即可进 入管理员界面；若输入错误，则提示输入正确的用户名或密码。 2、主函数 本程序主要调用两个模块：主程序模块-拓扑排序模块，调用关系简单，通过主函数 主要调用 TopoSort（）输出 G 顶点的拓扑排序， Display（）输出图的邻接矩阵， CreateGraph（） 生

10、成图，用来实现对教学计划的编制。 3、拓扑排序 利用课程之间的先修关系，运用拓扑排序进行学期课程安排（4 个学期） ，每学期都有 学分上限，而每学期应学课程的学分应在学分上限内，超过学分上限后，将移到下一学期课 程安排中。在满足课程先修关系和各学期课程安排的情况下，如果某门课程的学分超过该学 期的学分上限，则系统返回值为 Error，提示错误，需要进行修改，必须保证该学期的各课 程学分不会超过学分上限，这时系统返回值为 OK。 第第 4 4 章章 详细设计详细设计 4.14.1 数据结构数据结构 1、图的数据结构 typedef struct ArcNode /表结点 int adjvex;

11、/该弧所指向的顶点的位置，弧的节点结构 struct ArcNode *nextarc; /指向下一条弧的指针 ArcNode; /链表结点 typedef struct VNode /头结点 VertexType data; /顶点信息 int grades; /存储学分信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM; typedef struct /图的数据结构 AdjList vertices; /vertices 存储课程名 int vexnum,arcnum; /图的当前顶点数和弧数 ALGraph

12、; 2、栈的数据结构 typedef struct SqStack SElemType *base; SElemType *top; int stacksize; /分配的存储空间 SqStack; 4.24.2 抽象数据类型的定义抽象数据类型的定义 1、图的抽象数据类型定义 ADT Graph 数据对象数据对象 V：V 是具有相同特性的数据元素的集合，称为顶点集。 数据关系数据关系 R: R=VR VR=|v,wV 且 P（v,w),表示从 v 到 w 的弧， 谓词 P(v,w)定义了弧的意义或信息 基本操作基本操作 P P： CreateGraph（ AdjList Temp; print

13、f0(); struct Name nameN=1,2,3,4,5,6,7,8,9,10,11,12; OUTPUT(); printf(*教学计划编制系统*nn); printf(请输入学期的总数:); scanf(%d, printf(请输入学期的学分上限:); scanf(%d, CreateGraph(G); Display(G); TopoSort(G,Temp,name); 2、各主要子函数的算法设计 （1）邻接表存储结构 代码： int CreateGraph(ALGraph VertexType va; ArcNode *p; printf(请输入教学计划的课程数:); sca

14、nf(%d, printf(请输入各门课程的先修课程的总和(弧总数):); scanf(%d, printf(请输入%d 门课程的课程代码(最多%d 个字符,数字):,G.vexnum,MAX_NAME); for(i=0;iG.vexnum;+i) /构造头结点 scanf(%s, G.verticesi.firstarc=NULL; for(i=0;iMaxScores|G.verticesi.grades=0) printf(警告!学分必须是在 0 到最大限制%d 之间,请检查后再输入! n,MaxScores); /如果输入的学分大于上限或等于 0，会出现警告 printf(请输入第%

15、d 门课程的学分值:,i+1); scanf(%d, printf(请输入下列课程的先修课程(无先修课程输入 0,结束也输入 0)n); for(k=0;kadjvex=j; p-nextarc=G.verticesi.firstarc; /插在表头 G.verticesi.firstarc=p; scanf(%s,va); system(cls); return OK; （2）拓扑排序 代码： int TopoSort(ALGraph G,AdjList Temp,struct Name name) int i,k,j=0,count,indegreeMAX_VERTEX_NUM; SqSt

16、ack S;ArcNode *p; FindInDegree(G,indegree); /对各顶点求入度 InitStack(S); /初始化栈 for(i=0;inextarc) /对 i 号顶点的每个 邻接点的入度减 1 k=p-adjvex; if(!(-indegreek) /若入度减为 0,则入栈 Push(S,k); if(countG.vexnum) printf(此有向图有回路,无法完成拓扑排序!); return ERROR; else printf(为一个拓扑序列); printf(n); 第第 5 5 章章 编码与调试编码与调试 5.15.1 教学计划编制问题实例教学计划

17、编制问题实例 针对大学各专业本科课程，根据课程之间的依赖关系制定课程安排计划，并满足各学期 课程数尽量排在前几个学期。例如：一个信息与计算科学专业的学生必须学习的一系列基本 课程（如表 5.1 所示） ，其中有些课是基础课，它独立于其他课程，如程序设计基础 ；而 另一些课程必须在学完作为它的基础的先修课程才能开始，如在学习离散数学之前要先 学完它的先修课程程序设计基础 。这些先修课程定义了课程之间的先修关系。 课程编号课程名称先修课程 1 程序设计基础无 2 离散数学 1 3 数据结构1、2 4 汇编语言 1 5 语言的设计和分析3、4 6 计算机原理 11 7 编译原理5、3 8 操作系统3

18、、6 9 高等数学无 10 线性代数 9 11 大学物理 9 12 数值分析9、10、1 表 5.1 信息与计算科学专业的学生必须学习的课程 解答：解答： 某个学生学习了 4 个学期，每个学期的学分上限为 15，教学计划的课程数为 12,12 门 课程对应的学分为 3、4、4、3、2、3、3、2、3、2、4、3，根据上表的先修课程可得： 第一学期应学课程为：高等数学、线性代数、大学物理、计算机原理、程序设计基础； 第二学期应学课程为：离散数学、数据结构、操作系统、汇编语言、语言的设计和分析； 第三学期应学课程为: 编译原理、数值分析； 第四学期应学课程为：无 课程优先关系有向图（如图 5.1

19、所示）： 图图 5.1 课程优先关系有向图课程优先关系有向图 得到一个拓扑有序序列为 （9，10，11，6，1，2，3，8，4，5，7，12） 4 5 1 10 3 7 2 12 11 8 9 6 5.25.2 程序运行结果程序运行结果 1、打开 VC+6.0，输入教学计划编制问题程序，点击运行，首先进入系统主界面，输 入用户名和密码（本系统用户名和密码均为 123）进入管理员界面，如图 5.2 所示。 图图 5.25.2 系统主界面系统主界面 2、在管理员界面，我们可以看到教学计划编制菜单，按 Enter 进行下一步操作，如图 5.3 所示。 图图 5.35.3 管理员界面管理员界面 3、在

20、操作界面里，我们按照系统提示输入某学生的学期课程编制的各类数据，如图 5.4 所示。 图图 5.45.4 学期课程编制数据学期课程编制数据 4、根据该学生的课程编制数据，输出运行结果，如图 5.5 所示。 图图 5.55.5 运行结果运行结果 第第 6 6 章章 总结总结 通过这次课程设计我们学到了很多东西,如程序的模块化设计思想，同时也加深了对数 据结构这门课程的理解和学会了如何在实际中应用数据结构。本次课程设计主要是拓扑排序 的应用，我们根据问题描述给出了数据模型以及能够体现问题本身特点的逻辑结构。 在做程序之前，觉得教学计划编制这个问题，很难解决。在通过我们一次次的画图，推 算结果时，明

21、白了该程序的主要思路。在明白程序的实质后，开始选择数据的存储结构类型， 最开始想到的是数组，但是用数组作为图的存储结构时，邻接矩阵可能是不对称的，没有多 想就放弃了。后来在查阅资料时，发现可以用邻接表作为图的存储结构，在邻接表上容易找 到任一顶点的第一个邻接点和下一个邻接点。确定了图的存储结构后，开始选择一种排序方 法，通过上网查阅资料，发现拓扑排序可以很好的实现我们所需要的排序效果。 以前总是不清楚数据结构它有什么用途。通过这此课程设计，明白我们所学的虽然只是 课本知识，但很多时候，我们可以利用所学的来解决生活中碰到的一些问题。同一个问题往 往可以用不同的方法来解决。 无论我们学习什么课程，

22、概念永远是基础，所有的知识都是建立在基础概念之上的。数 据结构包括线性结构、树形结构、图状结构或网状结构。线性结构包括线性表、栈、队列、 串、数组、广义表等，栈和队列是操作受限的线性表，串的数据对象约束为字符集，数组和 广义表是对线性表的扩展：表中的数据元素本身也是一个数据结构。除了线性表以外，栈是 重点，因为栈和递归紧密相连，递归是程序设计中很重要的一种工具。树状结构中的重点自 然是二叉树和 huffman 树。对于二叉树的很多操作都是基于对二叉树的遍历，掌握了如何遍 历。huffman 编码也有着很广泛的应用。对于图状结构，主要学习图的存储结构及图的遍历。 对算法的学习是学习数据结构的关键

23、。要注重对算法的掌握。对于一个算法，如果我们不是 很理解的话，可以手动将算法走一遍，慢慢理解该算法的思想。学习这门课程的最终目的， 还是要学会如何设计算法，这需要我们长期的练习和思考。 参考文献参考文献 1 严蔚敏，吴伟民.数据结构（c 语言版）.北京：清华大学出版社，1997.4 2 严蔚敏，吴伟民.数据结构题集（c 语言版）.北京：清华大学出版社，2005 3 谭浩强.C 程序设计（第三版）.北京：清华大学出版社，2005 附录附录 源程序源程序 源程序（附注释）： #include #include #include #include #include #include #define

24、TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define MAX_NAME 3 #define MAXCLASS 100 /顶点字符串的最大长度 #define MAX_VERTEX_NUM 100 /最大顶点数 #define N 12 typedef char VertexTypeMAX_NAME; int TotalTerms; /学期总数 int MaxScores; /学分上限 /*-图的邻接表存储表示-*/ typedef struct ArcNode /表结点 int adjvex; /该弧所指向的顶点的位置，弧的节点

25、结构 struct ArcNode *nextarc; /指向下一条弧的指针 ArcNode; /链表结点 typedef struct VNode /头结点 VertexType data; /顶点信息 int grades; /存储学分信息 ArcNode *firstarc; /指向第一条依附该顶点的弧的指针 VNode,AdjListMAX_VERTEX_NUM; typedef struct /图的数据结构 AdjList vertices; /vertices 存储课程名 int vexnum,arcnum; /图的当前顶点数和弧数 ALGraph; void printf0()

26、/ 界面 system(color A); printf(t*n); printf(t n); printf(t 数 据 结 构 课 程 设 计 n); printf(t 课 题 : 教学计划编制问题 n); printf(t 指导老师 : 李强丽 丁智斌 n); printf(t 试 验 者 : 江湖 房超 冯乐乐 n); printf(t 班 级 : 计算 B121 n); printf(t n); printf(t*n); printf(nn); printf(欢迎使用教学计划编制系统:); printf(n); /*-账号和密码设置-*/ char lzhanghao=123,zhan

27、ghao10; char lmima=123,mima10; gets(zhanghao); printf(ttt 用户名:); gets(zhanghao); printf(n); printf(ttt 密码:); int i=0; char c; while(isprint(c=getch() mimai+=c; printf(*); mimai=0; printf(nn); while(strcmp(lzhanghao,zhanghao)!=0|strcmp(lmima,mima)!=0) printf(ttt 账号或密码有误!nn); printf(ttt 请重新输入!nn); pri

28、ntf(ttt 用户名:); gets(zhanghao); printf(n); printf(ttt 密码:); int i=0; char c; while(isprint(c=getch() mimai+=c; printf(*); mimai=0; printf(n); system(cls); /刷新屏幕 void OUTPUT() system(color E); int s; printf(t _教学计划编制菜单_ n); printf(t * n); printf(t 课程代码 | 课程名称 | 先修课程 n); printf(t * n); printf(t * 1 |程序

29、设计基础 | 无 * n); printf(t * 2 |离散数学 | 1 * n); printf(t * 3 |数据结构 | 1, 2 * n); printf(t * 4 |汇编语言 | 1 * n); printf(t * 5 |语言的设计和分析 | 3, 4 * n); printf(t * 6 |计算机原理 | 11 * n); printf(t * 7 |编译原理 | 5, 3 * n); printf(t * 8 |操作系统 | 3, 6 * n); printf(t * 9 |高等数学 | 无 * n); printf(t * 10 |线性代数 | 9 * n); print

30、f(t * 11 |大学物理 | 9 * n); printf(t * 12 |数值分析 | 9,10,1 * n); printf(t * n); printf(n); printf(:); scanf(%c, /scanf(格式控制符, for(i=0;iG.vexnum;+i) if(strcmp(u,G.verticesi.data)=0) return i; return -1; /*采用邻接表存储结构*/ int CreateGraph(ALGraph VertexType va; ArcNode *p; printf(请输入教学计划的课程数:); scanf(%d, printf

31、(请输入各门课程的先修课程的总和(弧总数):); scanf(%d, printf(请输入%d 门课程的课程代码(最多%d 个字符,数字):,G.vexnum,MAX_NAME); for(i=0;iG.vexnum;+i) /构造头结点 scanf(%s, G.verticesi.firstarc=NULL; for(i=0;iMaxScores|G.verticesi.grades=0) printf(警告!学分必须是在 0 到最大限制%d 之间,请检查后再输入!n,MaxScores); /如果输入的学分大于上限或等于 0，会出现警告 printf(请输入第%d 门课程的学分值:,i+1

32、); scanf(%d, printf(请输入下列课程的先修课程(无先修课程输入 0,结束也输入 0)n); for(k=0;kadjvex=j; p-nextarc=G.verticesi.firstarc; /插在表头 G.verticesi.firstarc=p; scanf(%s,va); system(cls); return OK; /*输出图 G 的信息*/ void Display(ALGraph G) system(color B); int i; ArcNode *p; printf(有向图n); printf(%d 个顶点:,G.vexnum); for(i=0;iG.v

33、exnum;+i) printf(%4s,G.verticesi.data); printf(n%d 条弧边:n,G.arcnum); for(i=0;i%sn,G.verticesi.data,G.verticesp-adjvex.data); p=p-nextarc; /*求顶点的入度*/ void FindInDegree(ALGraph G,int indegree) int i; ArcNode *p; for(i=0;iG.vexnum;i+) indegreei=0; for(i=0;iadjvex+; p=p-nextarc; struct Name char c20; nam

34、e; /*栈定义*/ typedef int SElemType; /栈类型 #define Stack_NUM 20 /存储空间初始分配量 #define Stack_MoreNUM 5 /存储空间分配增量 typedef struct SqStack SElemType *base; SElemType *top; int stacksize; /分配的存储空间 SqStack; /*栈的初始化*/ int InitStack(SqStack if(!S.base) exit(-1); S.top=S.base; S.stacksize=Stack_NUM; return OK; /*判空

35、*/ int StackEmpty(SqStack S) if(S.top=S.base) return TRUE; else return FALSE; /*出栈*/ int Pop(SqStack e=*-S.top; return OK; /*入栈*/ int Push(SqStack if(!S.base) exit(-1); S.top=S.base+S.stacksize; S.stacksize+=Stack_MoreNUM; *S.top+=e; return OK; /*拓扑排序*/ int TopoSort(ALGraph G,AdjList Temp,struct Name name) int i,k,j=0,count,indegreeMAX_VERTEX_NUM; SqStack S;ArcNode *p; FindInDegree(G,indegree); /对各顶点求入度 indegree0.vernum-1 InitStack(S); /初始化栈 for(i=