《教学计划编制问题》数据结构课程设计说明书Word文档格式.doc
《《教学计划编制问题》数据结构课程设计说明书Word文档格式.doc》由会员分享，可在线阅读，更多相关《《教学计划编制问题》数据结构课程设计说明书Word文档格式.doc（32页珍藏版）》请在冰点文库上搜索。
附录源程序ﻩ21
I
教学计划编制问题
设计总说明
根据任务要求及对实际情况的了解，可知设计中需要定义先修关系的AOV网图中的顶点及弧边的结构体,采用邻接表存储结构,利用栈作辅助结构,在运行结果中将图的信息显示出来,利用先修关系将课程排序,最后解决问题-—输出每学期的课程。
整个系统从符合操作简便、界面简洁、灵活、实用、安全的要求出发,完成教学计划编制问题的全过程，包括创建三个数据结构（邻接表存储结构、栈、拓扑排序）、数据的处理与计算、数据的分析、结果的输出。
本课程主要介绍了本课题的开发背景,所要完成的功能和开发的过程。
重点说明了系统的设计思路、总体设计、各个功能模块的设计与实现方法.
关键词:
教学计划编制问题；
数据结构；
邻接表存储结构;
栈;
拓扑排序
ﻬ 第1章绪论
数据结构是研究数据元素之间的逻辑关系的一门课程,以及数据元素及其关系在计算机中的存储表示和对这些数据所施加的运算。
该课程设计的目的是通过课程设计的综合训练培养分析和编程等实际动手能力,系统掌握数据结构这门课程的主要内容。
本次课程设计的内容是教学计划编制问题，邻接表是图的一种链式存储结构。
在邻接表中，对图中每个顶点建立一个单链表,第i个单链表中的结点表示依附于顶点的边。
栈是一种限定性的线性表,它只允许在表尾插入元素或删除元素，所以栈具有后进先出的特性.拓扑排序是由某个集合上的一个偏序得到该集合上的一个全序．而教学计划编制问题就是对排序问题的应用，通过这个设计事例,我们有理由相信至此以后,我们对邻接表、栈和拓扑排序的理解将会是更上一层楼。
通过该课程设计,能运用所学知识，能上机解决一些实际问题,了解并初步掌握设计、实现较大程序的完整过程,包括系统分析、编码设计以及调试分析，熟练掌握数据结构的选择、设计、实现以及操作方法，为进一步的应用开发打好基础。
第2章教学计划编制问题陈述及需求分析
1 教学计划编制问题陈述
大学中每个专业都有固定的教学计划,任何专业的学习年限是固定的,每年两个学期,每个专业开设的课程是确定的,而课程之间的开设时间是必须满足先修关系的。
每们课可以有多门先修课，也可以没有。
以本科四年为准,要求设计一个教学计划。
输入学期总数，一学期的学分上限，每门课的课程号、学分和直接先修课的课程号。
一是使学生在各学期中的学习负担尽量均匀;
二是使课程尽可能地集中在前几个学期中。
输出教学计划到用户指定的文件中，计划表格格式自行设计,若无结果可报告适当的信息.
2.2功能需求分析
本系统主要实现对大学中每个专业的教学计划进行设计,需要实现以下几个方面的功能：
（1）创建存储结构：
创建邻接表。
（2）数据的输入:
学期总数，课程数,一学期的学分上限，每门课的课程号（固定占2位的数字串）、学分和直接先修课的课程号.
（3）数据的处理:
对输入的数据进行计算。
（4）结果的输出:
输出各门课程所对应的学分，以及每学期各门课程的安排。
第３章系统设计
3．1总体设计
允许用户指定下列两种编排策略之一:
采用第二种策略，使课程尽可能地集中在前几个学期中,根据教学计划中的课程及其关系和学分定义图的顶点和边的结构体,创建图,结合先修关系的AOV网，采用邻接链表存储和使用前插法，通过菜单显示代号所对应课程及课程的先修课程，运用拓扑排序将课程排序后并决定出每学期所学课程，最后输出图G的信息，将图的顶点和弧边输出.具体流程图如图3。
1所示。
开始
管理员：
输入用户名和密码
菜单OUTPUT（）：
显示课程代码、课程名称及先修课程
前插法
创建图CreateGraph（）：
结合先修关系的AOV网，采用邻接表存储
输出图G的信息Display（）：
输出图的顶点和弧边
使课程尽可能地集中在前几个学期中
拓扑排序TopoSort（）：
将课程排序后，编制出每学期所学的课程
结束
图３．１系统功能结构图
ﻬ首先，初始化栈,构造一个空栈S,判定这个栈是否为空栈,如果是,则进行下一步操作，否则，返回错误;
接下来对各个顶点求入度,将入度为零的顶点存入数组,当所有入度为零的顶点都存入数组后，执行完毕。
具体流程图如图3.2所示。
初始化栈InitStack（S）
对各顶点求入度，并存入数组InDegree[i]中（i=0…n）
依次将入度为0的顶点存入栈中
栈是否为空？
Ｙ
N
推出栈顶的一个元素（入度为零的顶点号）至i，输出i，计数器加1（Count++）
对以i号顶点为尾弧的每个邻接点的入度减1，并将入度减1后为零的顶点号压入栈中，输出i，计数器加1（Count++）
n个顶点全输出
N
Return
ERROR
Ｙ
OK
图3.2拓扑排序流程图
２主要模块简介
1、管理员
要进入管理员界面,首先需要输入用户名和密码。
输入正确的用户名和密码后，即可进入管理员界面;
若输入错误,则提示输入正确的用户名或密码.
2、主函数
本程序主要调用两个模块:
主程序模块—-——〉拓扑排序模块,调用关系简单,通过主函数主要调用ToｐｏSｏｒｔ（）输出G顶点的拓扑排序，
Display（）输出图的邻接矩阵,
CrｅateGｒａpｈ（）
生成图,用来实现对教学计划的编制。
3、拓扑排序
利用课程之间的先修关系，运用拓扑排序进行学期课程安排（4个学期）,每学期都有学分上限,而每学期应学课程的学分应在学分上限内，超过学分上限后，将移到下一学期课程安排中。
在满足课程先修关系和各学期课程安排的情况下,如果某门课程的学分超过该学期的学分上限,则系统返回值为Erroｒ,提示错误,需要进行修改，必须保证该学期的各课程学分不会超过学分上限,这时系统返回值为ＯK。
第28页共29页
第４章详细设计
4.1数据结构
1、图的数据结构
typｅdefｓｔrｕctAｒｃNｏｄe ／／表结点
｛
iｎt adjvex；
//该弧所指向的顶点的位置,弧的节点结构
ｓtrｕcｔArcNodｅ*ｎextarc;
//指向下一条弧的指针
}ArcNode；
//链表结点
typedｅfsｔｒｕcｔＶNｏdｅ //头结点
VertexＴypeｄａta；
/／顶点信息
ﻩiｎtgｒades;
//存储学分信息
ArcNode ＊firｓtarc；
／/指向第一条依附该顶点的弧的指针
}ＶNodｅ，AdjＬiｓt[MAＸ＿VERTEX_NＵM]；
typeｄefstruct //图的数据结构
{
ﻩAdjＬistvｅrtiｃｅs;
/／veｒtices存储课程名
ﻩiｎｔvexnｕm,arcｎｕｍ；
//图的当前顶点数和弧数
}ALGraph；
２、栈的数据结构
tyｐeｄｅｆｓｔructSqStａck
ﻩＳElemType *ｂase;
ＳEｌｅｍType*top;
ﻩｉntstａcksize；
//分配的存储空间
｝SｑＳtａｃk;
4.２抽象数据类型的定义
1、图的抽象数据类型定义
AＤTGｒａpｈ｛
数据对象Ｖ:
V是具有相同特性的数据元素的集合，称为顶点集。
数据关系 R:
Ｒ={VR}
VR=｛<
ｖ,w＞｜v,wV且P（v,w），〈v,w〉表示从v到w的弧，
谓词P（v,ｗ）定义了弧〈v,ｗ＞的意义或信息}
基本操作P:
CｒｅateGraｐh（&
Ｇ,Ｖ,VR）；
初始条件：
V是图的顶点集,VＲ是图中弧的集合.
操作结果:
按V和VＲ的定义构造图G。
LocateVｅx（G,u）
初始条件:
图G存在，u和G中顶点有相同特征.
操作结果：
若G中存在顶点ｕ，则返回该顶点在图中位置;
否则返回其他信息。
}ＡＤＴGｒaｐh
２、栈的抽象数据类型定义
AＤＴＳtａｃk{
数据对象：
D={｜ElｅmSet，i＝１，2,.。
。
ｎ,n｝
数据关系:
R1={〈，＞|,D，ｉ=2,。
，ｎ}
约定端为栈顶，端为栈底.
基本操作:
IｎitSｔacｋ（&
S）
操作结果：
构造一个空栈S。
StaｃkEｍｐｔｙ（S）
初始条件:
栈S已存在。
操作结果：
若栈S为空栈，则返回ＴRUＥ，否则FALSE。
Pop（&
Ｓ,＆e）
初始条件：
栈Ｓ已存在且非空。
操作结果：
删除S的栈顶元素,并用e返回其值。
Pusｈ（＆S，e）
初始条件：
操作结果：
插入元素ｅ为新的栈顶元素。
}ADTStaｃk
基本操作:
intLｏcateＶex（ALＧｒａｐhＧ，VeｒtexTypeu）/*查找图中某个顶点位置*/
iｎｔ CrｅaｔｅＧrａｐｈ（ALGraph&
Ｇ） ／*采用邻接表存储结构＊/
voidDisｐｌay（ＡＬGraｐhG） /＊输出图G的信息*/
ｖｏiｄＦindＩnDegree（ALGraｐｈG,inｔindegｒeｅ［]） /*求顶点的入度*/
intInitStack（ＳｑＳtack ＆S） /*栈的初始化*／
intStackEmｐｔｙ（SqStaｃｋS） ／＊判空＊／
intPoｐ（SqStａck＆Ｓ,SＥlemType &
e）/*出栈*/
intPush（SqStａck&
S，SEleｍＴype e） /*入栈＊/
4.3设计说明
教学计划编制问题主要用的是算法是拓扑排序。
拓扑排序是由某个集合上的一个偏序得到该集合上的一个全序。
偏序指集合中仅有部分成员之间可比较,而全序指集合中全体成员之间可比较。
一个表示偏序的有向图可用来表示一个流程图。
它或者是一个施工流程图，或者是一个产品生产的流程图，再或者是一个数据流图（每个顶点表示一个过程）。
图中每一条边表示两个子工程之间的次序关系（领先关系）。
拓扑排序的主要步骤:
（1）在有向图中选一个没有前驱的顶点且输出之。
（2）从图中删除该顶点和所有以它为尾的弧。
（3）重复上述两步，直至全部顶点均已输出,或者当前图中不存在无前驱的顶点为止。
针对上述三步操作，我们可以用邻接表作为有向图的存储结构，且在头结点中增加一个存放顶点入度的数组（indｅgｒee）.入度为零的顶点即为没有前驱的顶点,删除顶点及以它为尾的弧的操作,则可换以弧头顶点的入度减1来实现。
为了避免重复检测入度为零的顶点,可另设一栈暂存所有入度为零的顶点。
4.4算法说明
1、主函数的算法设计：
显示子菜单，调用各个子函数，最后退出程序,主要代码:
voidmaiｎ（）
ﻩALＧrapｈＧ；
ﻩAdjLｉstTemp;
pｒintf0（）；
sｔructName
name[N］＝{{"
1＂},{"
2"
｝,｛"
3＂},｛”４”},{"
5＂},｛＂６"
}，{”7”},｛”8"
｝,{＂9"
｝,｛＂１0”},｛"
11"
}，｛"
12”}｝;
ﻩOUTPUT（）；
ﻩprintf（”★****★****★教学计划编制系统★＊＊**★＊***★＼ｎ\n”）；
prｉｎtf（”请输入学期的总数:
”）;
scａｎf（"
％ｄ”，&
TｏtalTeｒｍｓ）;
prｉntf（"
请输入学期的学分上限:
"
）;
ﻩscａnf（”%d＂,&
MaxＳcoｒｅs）；
CrｅateGｒapｈ（G）;
ﻩDispｌay（G）;
ＴoｐｏSort（G,Temp,ｎame）;
}
2、各主要子函数的算法设计
（1）邻接表存储结构
代码:
inｔCｒeａteGraｐh（ＡLGraph&
G）
ﻩiｎti,j,ｋ；
VｅｒｔexＴypevａ;
ArcNoｄe *ｐ；
ｐｒintf（"
请输入教学计划的课程数：
＂）;
ﻩｓcanf（”％ｄ”,&
G.vexｎum）;
pｒｉｎｔf（”请输入各门课程的先修课程的总和（弧总数）:
sｃanf（”%ｄ”，＆Ｇ。
arcnum）;
ﻩpriｎtｆ（”请输入％d门课程的课程代码（最多%d个字符，数字）：
，G．ｖeｘnuｍ,MAＸ_NAME）；
ｆor（i=0；
i〈G.vexnum;
++i） ／/构造头结点
ﻩ{
ﻩscanｆ（＂%ｓ＂,&
G.verticeｓ[i].dａｔa）；
Ｇ.ｖerｔiceｓ[i]。
firstａrｃ=NUＬL；
}
for（i＝0;
i〈Ｇ.vexnｕｍ;
i＋+）
ﻩ｛
ﻩ ｐriｎtf（”请输入第%ｄ门课程的学分值：
”,i+1）;
ﻩﻩscanｆ（”%ｄ"
，&
Ｇ.verticｅs[i]。
gｒades）;
while（G.vｅrtices[ｉ］。
ｇradeｓ>
MａxScoｒes|｜G.ｖｅrtｉｃes［i]。
graｄes〈=0）
ﻩ｛
ﻩ pｒｉntｆ（＂警告!
学分必须是在０到最大限制％ｄ之间,请检查后再输入!
\n”，MaxScｏres）;
／／如果输入的学分大于上限或等于０，会出现警告
ﻩﻩﻩpｒｉntf（”请输入第%d门课程的学分值:
”，ｉ+1）；
ﻩｓcaｎf（”%d”,＆G。
veｒtices[ｉ].grａdes）；
ﻩﻩ｝
ﻩ}
ｐｒinｔｆ（"
请输入下列课程的先修课程（无先修课程输入0,结束也输入0）＼n”）;
ﻩfｏｒ（ｋ=０；
k〈Ｇ。
ｖexnum；
++k） ／/构造表结点链表,利用前插法
ﻩprintf（"
%ｓ的先修课程:
＂,G.vertices[k]。
datａ）；
///
scaｎf（”％s”，va）；
//
ﻩ whiｌｅ（vａ[0]!
=’0＇） //ｉkｖa
ﻩﻩ{
ﻩﻩ i=ＬocateVex（Ｇ，va）;
//弧尾
ﻩ ﻩj=k;
／/弧头
ﻩﻩp＝（AｒcNoｄｅ*）ｍaｌlｏc（ｓizｅｏf（ＡrcＮode））;
ﻩp—〉ａdjvex=j；
p—〉nextａｒｃ=G.vｅｒticeｓ[ｉ］．ｆirｓｔarc;
//插在表头
ﻩﻩG．veｒtｉｃes[ｉ].ｆirsｔarc=ｐ；
ﻩﻩﻩscａnｆ（”%s"
ｖa）；
ﻩﻩ}
ﻩ｝
ﻩsystｅm（"
cls”）;
retｕrnOK；
｝
（2）拓扑排序
代码:
iｎtTopoSort（ALGraphＧ,ＡdjLiｓｔTemp，struｃtNamenaｍe［]）
ﻩiｎtｉ,k,ｊ＝0，ｃount，ｉｎｄegree［MAX_VERTEX_NUM］;
ﻩSqStackS；
ArｃNode *p;
ﻩFindＩnDｅgree（G,inｄegreｅ）;
//对各顶点求入度
IｎitStack（S）；
//初始化栈
foｒ（ｉ=0；
i〈G.vｅxnum;
+＋i） ／/建零入度顶点栈S
ﻩﻩif（!
ｉndegree[i］）Ｐusｈ（S，i）;
/／入度为0者进栈
couｎt=0；
/／对输出顶点计数
while（!
ＳtackＥmｐtｙ（S））
ﻩ{
ﻩ ﻩＰoｐ（S，i）;
ﻩ pｒintf（”%s（%ｄ分），”，G。
veｒtｉceｓ[i].data,G。
vｅrtices［ｉ].gradeｓ）;
ﻩ Teｍｐ[j＋＋]=G.ｖｅrtｉcｅｓ[i］；
//将当前的拓扑序列保存起来
++coｕnt;
/／输出i号顶点并计数
ﻩ ｆor（p=Ｇ。
vertｉces[i].fｉｒｓtarc；
p;
p=p—>
nｅxtarｃ） /／对ｉ号顶点的每个邻接点的入度减1
ﻩ {
ﻩﻩﻩk＝p—〉aｄjvｅx;
ﻩ iｆ（!
（—－ｉndeｇree［ｋ]）） //若入度减为0,则入栈
ﻩ Pｕsｈ（S,ｋ）;
｝
ﻩﻩ｝
ﻩｉf（count<
Ｇ．vexnｕm）
ﻩﻩ｛
ﻩﻩｐrinｔf（"
此有向图有回路，无法完成拓扑排序!
ﻩ returnERROR;
}
ﻩelsｅ
ﻩ ｐｒintf（”为一个拓扑序列＂）；
ﻩprintf（”\n”）;
ﻬ第5章编码与调试
１教学计划编制问题实例
针对大学各专业本科课程，根据课程之间的依赖关系制定课程安排计划,并满足各学期课程数尽量排在前几个学期．例如：
一个信息与计算科学专业的学生必须学习的一系列基本课程（如表５.1所示）,其中有些课是基础课，它独立于其他课程，如《程序设计基础》;
而另一些课程必须在学完作为它的基础的先修课程才能开始，如在学习《离散数学》之前要先学完它的先修课程《程序设计基础》。
这些先修课程定义了课程之间的先修关系.
课程编号
课程名称
先修课程
1
程序设计基础
无
2
离散数学
3
数据结构
1、2
４
汇编语言
１
５
语言的设计和分析
3、４
６
计算机原理
１1
7
编译原理
5、3
８
操作系统
３、6
9
高等数学
1０
线性代数
大学物理
12
数值分析
9、１0、１
表5。
1信息与计算科学专业的学生必须学习的课程
解答：
某个学生学习了４个学期,每个学期的学分上限为１5，教学计划的课程数为１２，12门课程对应的学分为3、４、4、3、2、3、3、2、3、2、4、3,根据上表的先修课程可得：
第一学期应学课程为:
高等数学、线性代数、大学物理、计算机原理、程序设计基础；
第二学期应学课程为：
离散数学、数据结构、操作系统、汇编语言、语言的设计和分析;
第三学期应学课程为:
编译原理、数值分析；
第四学期应学课程为:
课程优先关系有向图（如图5.１所示）:
5
4
8
10
6
11
图５。
１课程优先关系有向图
得到一个拓扑有序序列为
（９，10,１１,6,1,2，3,８,４,5，7,１２）
ﻬ5.２程序运行结果
1、打开ＶC++６。
0,
升级会员 