《教学计划编制问题》数据结构课程设计说明书(共31页).doc

精选优质文档-倾情为你奉上华 北 科 技 学 院数据结构课程设计说明书班级 计算B121 小组成员: 成绩: 小组成员: 成绩: 小组成员: 成绩: 设计题目: 教学计划编制问题 设计时间: 2014.6.23 至 2014.6.27 指导教师: 评 语: 评阅教师: _ 专心-专注-专业目 录教学计划编制问题设计总说明根据任务要求及对实际情况的了解，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体，采用邻接表存储结构，利用栈作辅助结构，在运行结果中将图的信息显示出来，利用先修关系将课程排序，最后解决问题输出每学期的课程。整个系统从符合操作简便、界面简洁、灵活、实用、安全的要求出发，完成教学计划编制问题的全过程，包括创建三个数据结构（邻接表存储结构、栈、拓扑排序）、数据的处理与计算、数据的分析、结果的输出。本课程主要介绍了本课题的开发背景，所要完成的功能和开发的过程。重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法。 关键词：教学计划编制问题；数据结构；邻接表存储结构；栈；拓扑排序 第1章 绪论数据结构是研究数据元素之间的逻辑关系的一门课程，以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。该课程设计的目的是通过课程设计的综合训练培养分析和编程等实际动手能力，系统掌握数据结构这门课程的主要内容。本次课程设计的内容是教学计划编制问题，邻接表是图的一种链式存储结构。在邻接表中，对图中每个顶点建立一个单链表，第i个单链表中的结点表示依附于顶点的边。栈是一种限定性的线性表，它只允许在表尾插入元素或删除元素，所以栈具有后进先出的特性。拓扑排序是由某个集合上的一个偏序得到该集合上的一个全序。而教学计划编制问题就是对排序问题的应用，通过这个设计事例，我们有理由相信至此以后，我们对邻接表、栈和拓扑排序的理解将会是更上一层楼。通过该课程设计，能运用所学知识，能上机解决一些实际问题，了解并初步掌握设计、实现较大程序的完整过程，包括系统分析、编码设计以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。第2章 教学计划编制问题陈述及需求分析2.1 教学计划编制问题陈述大学中每个专业都有固定的教学计划，任何专业的学习年限是固定的，每年两个学期，每个专业开设的课程是确定的，而课程之间的开设时间是必须满足先修关系的。每们课可以有多门先修课，也可以没有。以本科四年为准，要求设计一个教学计划。输入学期总数，一学期的学分上限，每门课的课程号、学分和直接先修课的课程号。一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。输出教学计划到用户指定的文件中，计划表格格式自行设计，若无结果可报告适当的信息。2.2 功能需求分析 本系统主要实现对大学中每个专业的教学计划进行设计，需要实现以下几个方面的功能： （1）创建存储结构：创建邻接表。 （2）数据的输入：学期总数，课程数，一学期的学分上限，每门课的课程号（固定占2位的数字串）、学分和直接先修课的课程号。 （3）数据的处理：对输入的数据进行计算。 （4）结果的输出：输出各门课程所对应的学分，以及每学期各门课程的安排。第3章 系统设计3.1 总体设计允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负担尽量均匀；二是使课程尽可能地集中在前几个学期中。采用第二种策略，使课程尽可能地集中在前几个学期中，根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体，创建图，结合先修关系的AOV网，采用邻接链表存储和使用前插法，通过菜单显示代号所对应课程及课程的先修课程，运用拓扑排序将课程排序后并决定出每学期所学课程，最后输出图G的信息，将图的顶点和弧边输出。具体流程图如图3.1所示。开始管理员：输入用户名和密码菜单OUTPUT()：显示课程代码、课程名称及先修课程前插法创建图CreateGraph（）：结合先修关系的AOV网，采用邻接表存储输出图G的信息Display( )：输出图的顶点和弧边使课程尽可能地集中在前几个学期中拓扑排序TopoSort( )：将课程排序后，编制出每学期所学的课程结束图 3.1 系统功能结构图 首先，初始化栈，构造一个空栈S，判定这个栈是否为空栈，如果是，则进行下一步操作，否则，返回错误；接下来对各个顶点求入度，将入度为零的顶点存入数组，当所有入度为零的顶点都存入数组后，执行完毕。具体流程图如图3.2所示。初始化栈InitStack(S)对各顶点求入度，并存入数组InDegreei中（i=0n）依次将入度为0的顶点存入栈中栈是否为空？ Y N推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Count+）对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1(Count+)n个顶点全输出 NReturn ERROR YReturn OK图3.2 拓扑排序流程图3.2 主要模块简介1、管理员要进入管理员界面，首先需要输入用户名和密码。输入正确的用户名和密码后，即可进入管理员界面；若输入错误，则提示输入正确的用户名或密码。2、 主函数本程序主要调用两个模块：主程序模块->拓扑排序模块，调用关系简单，通过主函数主要调用TopoSort（）输出G顶点的拓扑排序， Display（）输出图的邻接矩阵， CreateGraph（） 生成图，用来实现对教学计划的编制。 3、拓扑排序利用课程之间的先修关系，运用拓扑排序进行学期课程安排（4个学期），每学期都有学分上限，而每学期应学课程的学分应在学分上限内，超过学分上限后，将移到下一学期课程安排中。在满足课程先修关系和各学期课程安排的情况下，如果某门课程的学分超过该学期的学分上限，则系统返回值为Error，提示错误，需要进行修改，必须保证该学期的各课程学分不会超过学分上限，这时系统返回值为OK。第4章 详细设计4.1 数据结构1、图的数据结构typedef struct ArcNode /表结点int adjvex; /该弧所指向的顶点的位置，弧的节点结构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;2、栈的数据结构typedef struct SqStackSElemType *base;SElemType *top;int stacksize; /分配的存储空间SqStack;4.2 抽象数据类型的定义1、图的抽象数据类型定义 ADT Graph 数据对象 V：V是具有相同特性的数据元素的集合，称为顶点集。 数据关系 R: R=VR VR=<v,w>|v,wV且P（v,w),<v,w>表示从v到w的弧， 谓词P(v,w)定义了弧<v,w>的意义或信息 基本操作 P： CreateGraph（&G,V,VR)； 初始条件：V是图的顶点集，VR是图中弧的集合。 操作结果：按V和VR的定义构造图G。 LocateVex（G，u） 初始条件：图G存在，u和G中顶点有相同特征。 操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。 ADT Graph 2、栈的抽象数据类型定义 ADT Stack 数据对象：D=|ElemSet,i=1,2,.,n,n 数据关系：R1=<,>|,D,i=2,.,n 约定端为栈顶，端为栈底。 基本操作： InitStack(&S) 操作结果：构造一个空栈S。 StackEmpty(S) 初始条件：栈S已存在。 操作结果：若栈S为空栈，则返回TRUE,否则FALSE。 Pop(&S,&e) 初始条件：栈S已存在且非空。 操作结果：删除S的栈顶元素，并用e返回其值。 Push(&S,e) 初始条件：栈S已存在。 操作结果：插入元素e为新的栈顶元素。 ADT Stack 基本操作： int LocateVex(ALGraph G,VertexType u) /*查找图中某个顶点位置*/ int CreateGraph(ALGraph &G) /*采用邻接表存储结构*/ void Display(ALGraph G) /*输出图G的信息*/ void FindInDegree(ALGraph G,int indegree) /*求顶点的入度*/ int InitStack(SqStack &S) /*栈的初始化*/ int StackEmpty(SqStack S) /*判空*/ int Pop(SqStack &S,SElemType &e) /*出栈*/ int Push(SqStack &S,SElemType e) /*入栈*/4.3 设计说明教学计划编制问题主要用的是算法是拓扑排序。拓扑排序是由某个集合上的一个偏序得到该集合上的一个全序。偏序指集合中仅有部分成员之间可比较，而全序指集合中全体成员之间可比较。一个表示偏序的有向图可用来表示一个流程图。它或者是一个施工流程图，或者是一个产品生产的流程图，再或者是一个数据流图（每个顶点表示一个过程）。图中每一条边表示两个子工程之间的次序关系（领先关系）。拓扑排序的主要步骤：（1） 在有向图中选一个没有前驱的顶点且输出之。（2） 从图中删除该顶点和所有以它为尾的弧。（3） 重复上述两步，直至全部顶点均已输出，或者当前图中不存在无前驱的顶点为止。针对上述三步操作，我们可以用邻接表作为有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（indegree)。入度为零的顶点即为没有前驱的顶点，删除顶点及以它为尾的弧的操作，则可换以弧头顶点的入度减1来实现。为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。4.4 算法说明1、主函数的算法设计： 显示子菜单，调用各个子函数，最后退出程序，主要代码：void main()ALGraph G;AdjList Temp;printf0();struct NamenameN="1","2","3","4","5","6","7","8","9","10","11","12"OUTPUT();printf("*教学计划编制系统*nn");printf("请输入学期的总数:");scanf("%d",&TotalTerms);printf("请输入学期的学分上限:");scanf("%d",&MaxScores);CreateGraph(G);Display(G);TopoSort(G,Temp,name);2、各主要子函数的算法设计 （1）邻接表存储结构 代码：int CreateGraph(ALGraph &G)int i,j,k;VertexType va;ArcNode *p;printf("请输入教学计划的课程数:");scanf("%d",&G.vexnum); printf("请输入各门课程的先修课程的总和(弧总数):");scanf("%d",&G.arcnum);printf("请输入%d门课程的课程代码(最多%d个字符,数字):",G.vexnum,MAX_NAME);for(i=0;i<G.vexnum;+i) /构造头结点scanf("%s",&G.verticesi.data);G.verticesi.firstarc=NULL; for(i=0;i<G.vexnum;i+)printf("请输入第%d门课程的学分值:",i+1);scanf("%d",&G.verticesi.grades); while(G.verticesi.grades>MaxScores|G.verticesi.grades<=0)printf("警告!学分必须是在0到最大限制%d之间,请检查后再输入!n",MaxScores); /如果输入的学分大于上限或等于0，会出现警告printf("请输入第%d门课程的学分值:",i+1);scanf("%d",&G.verticesi.grades);printf("请输入下列课程的先修课程(无先修课程输入0,结束也输入0)n");for(k=0;k<G.vexnum;+k) /构造表结点链表,利用前插法printf("%s的先修课程:",G.verticesk.data); /scanf("%s",va); /while(va0!='0') /ikvai=LocateVex(G,va); /弧尾j=k; /弧头p=(ArcNode*)malloc(sizeof(ArcNode);p->adjvex=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;SqStack S;ArcNode *p;FindInDegree(G,indegree); /对各顶点求入度InitStack(S); /初始化栈for(i=0;i<G.vexnum;+i) /建零入度顶点栈Sif(!indegreei)Push(S,i); /入度为0者进栈count=0; /对输出顶点计数while(!StackEmpty(S)Pop(S,i);printf("%s(%d分),",G.verticesi.data,G.verticesi.grades);Tempj+=G.verticesi; /将当前的拓扑序列保存起来+count; /输出i号顶点并计数for(p=G.verticesi.firstarc;p;p=p->nextarc) /对i号顶点的每个邻接点的入度减1k=p->adjvex;if(!(-indegreek) /若入度减为0,则入栈Push(S,k);if(count<G.vexnum)printf("此有向图有回路,无法完成拓扑排序!");return ERROR;elseprintf("为一个拓扑序列");printf("n");第5章 编码与调试5.1 教学计划编制问题实例针对大学各专业本科课程，根据课程之间的依赖关系制定课程安排计划，并满足各学期课程数尽量排在前几个学期。例如：一个信息与计算科学专业的学生必须学习的一系列基本课程（如表5.1所示），其中有些课是基础课，它独立于其他课程，如程序设计基础；而另一些课程必须在学完作为它的基础的先修课程才能开始，如在学习离散数学之前要先学完它的先修课程程序设计基础。这些先修课程定义了课程之间的先修关系。课程编号课程名称先修课程1程序设计基础无2离散数学13数据结构1、24汇编语言15语言的设计和分析3、46计算机原理117编译原理5、38操作系统3、69高等数学无10线性代数911大学物理912数值分析9、10、1表5.1 信息与计算科学专业的学生必须学习的课程解答：某个学生学习了4个学期，每个学期的学分上限为15，教学计划的课程数为12,12门课程对应的学分为3、4、4、3、2、3、3、2、3、2、4、3，根据上表的先修课程可得：第一学期应学课程为：高等数学、线性代数、大学物理、计算机原理、程序设计基础；第二学期应学课程为：离散数学、数据结构、操作系统、汇编语言、语言的设计和分析；第三学期应学课程为: 编译原理、数值分析；第四学期应学课程为：无 课程优先关系有向图（如图5.1所示）：54 2173128910611图5.1 课程优先关系有向图得到一个拓扑有序序列为 （9，10，11，6，1，2，3，8，4，5，7，12）5.2 程序运行结果1、打开VC+6.0，输入教学计划编制问题程序，点击运行，首先进入系统主界面，输入用户名和密码（本系统用户名和密码均为123）进入管理员界面，如图5.2所示。图5.2 系统主界面2、在管理员界面，我们可以看到教学计划编制菜单，按Enter进行下一步操作，如图5.3所示。 图5.3 管理员界面 3、在操作界面里，我们按照系统提示输入某学生的学期课程编制的各类数据，如图5.4所示。图5.4 学期课程编制数据 4、根据该学生的课程编制数据，输出运行结果，如图5.5所示。 图5.5 运行结果第6章 总结通过这次课程设计我们学到了很多东西,如程序的模块化设计思想，同时也加深了对数据结构这门课程的理解和学会了如何在实际中应用数据结构。本次课程设计主要是拓扑排序的应用，我们根据问题描述给出了数据模型以及能够体现问题本身特点的逻辑结构。 在做程序之前，觉得教学计划编制这个问题，很难解决。在通过我们一次次的画图，推算结果时，明白了该程序的主要思路。在明白程序的实质后，开始选择数据的存储结构类型，最开始想到的是数组，但是用数组作为图的存储结构时，邻接矩阵可能是不对称的，没有多想就放弃了。后来在查阅资料时，发现可以用邻接表作为图的存储结构，在邻接表上容易找到任一顶点的第一个邻接点和下一个邻接点。确定了图的存储结构后，开始选择一种排序方法，通过上网查阅资料，发现拓扑排序可以很好的实现我们所需要的排序效果。 以前总是不清楚数据结构它有什么用途。通过这此课程设计，明白我们所学的虽然只是课本知识，但很多时候，我们可以利用所学的来解决生活中碰到的一些问题。同一个问题往往可以用不同的方法来解决。无论我们学习什么课程，概念永远是基础，所有的知识都是建立在基础概念之上的。数据结构包括线性结构、树形结构、图状结构或网状结构。线性结构包括线性表、栈、队列、串、数组、广义表等，栈和队列是操作受限的线性表，串的数据对象约束为字符集，数组和广义表是对线性表的扩展：表中的数据元素本身也是一个数据结构。除了线性表以外，栈是重点，因为栈和递归紧密相连，递归是程序设计中很重要的一种工具。树状结构中的重点自然是二叉树和huffman树。对于二叉树的很多操作都是基于对二叉树的遍历，掌握了如何遍历。huffman编码也有着很广泛的应用。对于图状结构，主要学习图的存储结构及图的遍历。对算法的学习是学习数据结构的关键。要注重对算法的掌握。对于一个算法，如果我们不是很理解的话，可以手动将算法走一遍，慢慢理解该算法的思想。学习这门课程的最终目的，还是要学会如何设计算法，这需要我们长期的练习和思考。参考文献1 严蔚敏，吴伟民.数据结构（c语言版）.北京：清华大学出版社，1997.42 严蔚敏，吴伟民.数据结构题集（c语言版）.北京：清华大学出版社，20053 谭浩强.C程序设计（第三版）.北京：清华大学出版社，2005附录 源程序源程序（附注释）：#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include<conio.h>#include<ctype.h>#define 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 12typedef char VertexTypeMAX_NAME;int TotalTerms; /学期总数int MaxScores; /学分上限/*-图的邻接表存储表示-*/typedef struct ArcNode /表结点int adjvex; /该弧所指向的顶点的位置，弧的节点结构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() / 界面 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("欢迎使用教学计划编制系统<按Enter继续>:");printf("n");/*-账号和密码设置-*/char lzhanghao="123",zhanghao10;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");printf("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 |程序设计基础 | 无 * 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");printf("t * 11 |大学物理 | 9 * n");printf("t * 12