教学计划安排检验程序正文.docx
《教学计划安排检验程序正文.docx》由会员分享，可在线阅读，更多相关《教学计划安排检验程序正文.docx（21页珍藏版）》请在冰点文库上搜索。
教学计划安排检验程序正文
目录
1实验目的1
2问题描述1
3需求分析1
4概要设计2
4.1设计思想2
4.2设计流程图2
4.3数据库设计3
4.4函数及功能要求3
4.5模块调用关系4
5详细设计4
5.1制定课程计划伪码4
6测试分析8
7使用说明11
8总结12
9参考文献13
10附录14
教学计划安排检验
（德州学院计算机系，山东德州253023）
1实验目的
本次数据结构课程设计的主要目的是检验和巩固专业知识，提高综合素质和能力。
并在实际操作中掌握：
1．邻接表的存储结构。
2．栈的基本操作。
3．拓扑排序的思想。
通过实习，可以将我们课堂上掌握的理论知识与处理数据的业务相结合，以检验我们掌握知识的宽度、深度及对知识的综合运用能力。
2问题描述
针对学院的计算机系本科课程，根据课程之间的依赖关系，制定课程安排计划，并满足各学期课程数大致相同。
按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出每学期应学的课程。
3需求分析
该程序的工作是制定课程安排计划，并满足各学期课程数大致相同。
此程序规定：
1、输入的形式和输入值的范围：
输入间用空格隔开。
要求用户输入的课程数小于20，学期数小于或是等于8，课程名的长度小于等于10个字符。
2、程序所能达到的功能：
按照用户的输入，给出每学期应学的课程。
3、测试数据：
输入：
学期数：
５，课程数：
12，课程间的先后关系数：
16，课程的代表值：
v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,v12。
课程间两两间的先后关系：
v1v2,v1v3,v1v4,v1v12,v2v3,v3v5,v3v7,v3v8,v4v5,v5v7,v6v8,v9v10,v9v11,v9v12,v10v12,v11v6
输出：
第1学期应学的课程：
v1v9
第2学期应学的课程：
v2v4v10v11
第3学期应学的课程：
v3v6v12
第4学期应学的课程：
v5v8
第5学期应学的课程：
v7
4概要设计
4.1设计思想
总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。
首先根据课程的先后关系画出AOV网，网中的结点代表课程，有向边表示各学科之间的次序关系。
可以采用邻接表作AOV网的存储结构，且在头结点中增加一个存放顶点入度的数组。
为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。
然后根据拓扑排序依次输出应学的课程。
4.2设计流程图
图1流程图
4.3数据库设计
ADTGraph｛
数据对象V：
V是具有相同特性的数据元素的集合，称为顶点集。
数据系统用到的抽象数据类型定义：
1．关系R：
R=｛VR｝
VR=｛|v,w∈V且P（v,w）,表示从v到w的弧，
谓词P（v,w）定义了弧的意义和信息｝
基本操作：
（1）StatusCreateDG（ALGraph&G）；
（2）voidFindInDegree（ALGraphG）；
（3）StatusTopologicalSort（ALGraphG）；
｝ADTGraph
2.ADTStack｛
数据对象：
D={ai|ai∈ElemSet，i=1,2,…,n,n≥0}
数据关系：
R1=｛|ai-1，ai∈D,i=2,…，n｝
约定an端为栈顶，a1端为栈底。
基本操作：
（1）StatusInitStack（SqStack&S）；
（2）StatusPush（SqStack&S,SElemTypee）；
（3）StatusPop（SqStack&S,SElemType&e）；
（4）StatusStackEmpty（SqStackS）；
｝ADTStack
4.4函数及功能要求
（1）StatusInitStack（SqStack&S）：
构造一个空栈。
（2）StatusPush（SqStack&S,SElemTypee）：
插入元素e为新的栈顶元素。
（3）StatusPop（SqStack&S,SElemType&e）：
若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。
（4）StatusStackEmpty（SqStackS）：
判断栈是否为空,为空返回TRUE,否则返回FALSE。
（5）StatusCreateDG（ALGraph&G）：
建立邻接表。
（6）voidFindInDegree（ALGraphG）：
求图的入度。
（7）voidprint（intn[],ALGraphG）：
排序输出顶点数据。
（8）StatusTopologicalSort（ALGraphG）：
拓扑排序，有向图G采用邻接表存储结构。
4.5模块调用关系
各程序模块之间的调用关系（子程序编号见上）：
主函数可调用子程序5，8。
子程序8可调用子程序1，2，3，4，6，7。
5详细设计
5.1制定课程计划伪码
制定课程计划算法的伪码描述如下：
StatusCreateDG（ALGraph&G）{//建立邻接表
提示"请输入学期数目（学期数目必须小于等于8）：
";
scanf（"%d",&学期数目）;
if（学期数目>8）
{
提示"请重新输入学期数目（学期数目必须小于等于8）：
";
scanf（"%d",&学期数目）;
}
提示"请输入课程数目（课程数必须小于20）：
";
scanf（"%d",&课程数目）;
if（课程数目>=20）
{
提示"请重新输入课程数目（课程数必须小于20）：
";
scanf（"%d",&课程数目）;
}
图G的顶点数=课程数目;
提示"请输入课程间的先后关系数：
";
scanf（"%d",&图G的顶点数）;
提示"请输入课程的代表值（课程名的长度小于等于10个字符）:
";
for（i=0;i<图G的顶点数;i++）
{
scanf（"%s",&图G的第i个顶点的数据）;
图G的第i个顶点指向的第一条弧=NULL;
}//输入顶点信息
提示"请输入课程间两两间的先后关系：
";
for（i=0;i<图G的弧数;i++）{//输入弧的信息
scanf（"%d,%d",&弧尾v,&弧头w）;
ArcNode*p=newArcNode;//建立结点
if（p为空）returnERROR;
p所指向的顶点（p->adjvex）=w-1;
p所指向的下一条弧（p->nextarc）=G.vertices[v-1].firstarc;//顶点v的链表
G.vertices[v-1].firstarc=p;//添加到最左边
}
returnOK;
}
voidFindInDegree（ALGraphG）
{//求图各顶点的入度
ArcNode*p;
for（inti=0;i<图G的顶点数;i++）
{
p=G.vertices[i].firstarc;
while（p不为空）
{
for（intj=0;j<图G的顶点数;j++）
if（p所指向的顶点位置（p->adjvex）==j）
第j个顶点的入度+1;
p=p->nextarc;
}
}
}
voidprint（intn[],ALGraphG）//对刚出s1栈的数据进行排序然后输出
{
for（i=0;n[i]!
=-1;i++）
for（j=i+1;n[j]!
=-1;j++）
if（n[i]>n[j]）
{
n[i]与n[j]交换;
}
for（i=0;n[i]!
=-1;i++）
输出“G.vertices[n[i]].data”;
}
StatusTopologicalSort（ALGraphG）
{//拓扑排序
//有向图G采用邻接表存储结构
SqStackS1,S2;
ArcNode*p;
inti,count,k,m,n[20];
FindInDegree（G）;
InitStack（S1）;
InitStack（S2）;
for（i=0;i<20;i++）
n[i]=-1;//将数组n全部赋值为-1
for（i=图G的顶点数-1;i>=0;--i）
if（第i个顶点的入度为0）
把入度为0的压入栈S1
count=0;//对输出顶点计数
while（S1不为空栈）
{
输出（"第%d学期应学的课程:
",count+1）;
m=0;
while（S1不为空栈）
{
将S1的栈顶元素删除，并将其值返回给I;
n[m]=i;
把i号顶点压入栈S2
m++;
}
调用排序及输出函数
将数组n全部赋值为-1
count++;//计数
while（S2不为空）
{
将S1的栈顶元素删除，并将其值返回给I;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）
{
k=p->adjvex;//对i号顶点的每个邻接点的入度减1
if（!
（--indegree[k]））//若入度减为0,则入栈
将度为0的顶点入栈S1;
}
}
}
if（countreturnERROR;
elsereturnOK;
}//TopologicalSort
6测试分析
1运行程序打开界面如下图，并根据提示，输入学期数目：
图2测试1
输入出错时显示如下：
图3测试2
2输入正确继续根据提示输入课程数目：
图4测试3
3输入错误时的显示如下：
图5测试4
4输入正确则继续根据界面提示输入课程的代表值：
图6测试5
5根据界面提示输入课程间两两间的先后关系：
图7测试6
6输入课程间两两间的先后关系后，则输出每学期应学的课程：
图8测试7
7使用说明
运行程序，出现主页面，输入学期数目（学期数目必须小于等于8），输入完成后，按回车进行下一步；输入课程数目（课程数必须小于20），输入完成后，按回车进行下一步；输入课程间的先后关系，输入完成后，按回车进行下一步；输入课程的代表值（课程名的长度小于等于10个字符，课程名之间用空格隔开），输入完成后，按回车进行下一步；输入课程间两两间的先后关系（注意：
只输入课程代表值的数字部分，两两关系间用逗号隔开，不同组的关系用空格隔开），输入完成后，按回车，主界面上将显示每学期的课程安排。
至此，本程序运行结束。
8总结
本程序充分应用了我们数据结构中所学的知识，完成了教学计划安排的检验。
通过本次课程设计我们不仅仅掌握了邻接表的存储结构、栈的基本操作、拓扑排序的思想等知识。
其实我们收获的不仅仅是技术，本次程序设计使我不仅深化理解了教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，并且在总体分析、总体结构设计、算法设计、课程设计、上机操作及程序调试等基本技能方面受到了综合训练，使我在编读程序时更容易。
通过本次课程设计我们小组成员团结合作但又不缺乏分工，查找资料，编写代码，完成报告。
在此期间，我们充分认识了团结合作的重要性，查找、编写过程，我们有过思考，有过讨论，有过困难，但最终通过我们的团结，商讨，困难被化解，报告最终展现在我们面前。
9参考文献
1.严蔚敏，《数据结构C语言》，清华大学出版社
2.谭浩强，《c语言程序设计》，清华大学出版社
3.晋良颍，《数据结构》，人民邮电出版社，2002年
4.李春保，《数据结构习题》，清华大学出版社
5.严蔚敏，《数据结构习题》，清华大学出版社
6.王立柱，《c语言与数据结构》，清华大学出版社
7.李春葆，《数据结构（C语言篇）习题与解析》，清华大学出版社
9.徐孝凯，魏荣《数据结构》,机械工业出版社，1996年
10.徐孝凯，《数据结构简明教程》，清华大学出版社，1995年
11.陈文博，朱青《数据结构与算法》，机械工业出版社，1996年
12.许卓群，张乃孝，杨冬青，唐世渭《数据结构》，高等教育出版社，1988年
13..李廉治，姜文清，郭福顺《数据结构》，大连理工大学出版社，1989年
10附录
见源代码：
#include"malloc.h"
#include"stdio.h"
#defineOK1
#defineERROR0
#defineTRUE1
#defineFALSE0
#defineSTACK_INIT_SIZE100//存储空间初始分配量
#defineSTACKINCREMENT10//存储空间分配增量
#defineMAX_VERTEX_NUM20
typedefintStatus;
typedefintSElemType;
typedefstruct{
SElemType*base;//在栈构造之前和销毁之后,base的值为NULL
SElemType*top;//栈顶指针
intstacksize;//当前已分配的存储空间,以元素为单位
}SqStack;
typedefstructArcNode{
intadjvex;//该弧所指向的顶点的位置
structArcNode*nextarc;//指向第一条依附该顶点的弧的指针
}ArcNode;
typedefstructVNode{
chardata[10];
ArcNode*firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedefstruct{
AdjListvertices;
intvexnum,arcnum;//图的当前顶点数和弧数
}ALGraph;
intindegree[20]={0};//存储图的入度的全局变量数组
StatusInitStack（SqStack&S）
{
//构造一个空栈S
S.base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
if（!
S.base）
returnERROR;//内存分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
returnOK;
}//InitStack
StatusPush（SqStack&S,SElemTypee）
{
//插入元素e为新的栈顶元素
if（S.top-S.base>=S.stacksize）
{//栈满,追加存储空间
S.base=（SElemType*）realloc（S.base,（S.stacksize+STACKINCREMENT）*sizeof（SElemType））;
if（!
S.base）
returnERROR;//存储分配失败
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e;
returnOK;
}//Push
StatusPop（SqStack&S,SElemType&e）
{
//若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR
if（S.top==S.base）
returnERROR;
e=*--S.top;
returnOK;
}//Pop
StatusStackEmpty（SqStackS）
{//判断栈是否为空,为空返回TRUE,否则返回FALSE
if（S.top==S.base）
returnTRUE;
elsereturnFALSE;
}
StatusCreateDG（ALGraph&G）{//建立邻接表
inti,l,v,w,vex;
printf（"请输入学期数目（学期数目必须小于等于8）：
"）;
scanf（"%d",&l）;
if（l>8）
{
printf（"请重新输入学期数目（学期数目必须小于等于8）：
"）;
scanf（"%d",&l）;
}
printf（"请输入课程数目（课程数必须小于20）：
"）;
scanf（"%d",&vex）;
if（vex>=20）
{
printf（"请重新输入课程数目（课程数必须小于20）：
"）;
scanf（"%d",&vex）;
}
G.vexnum=vex;
printf（"请输入课程间的先后关系数：
"）;
scanf（"%d",&G.arcnum）;
printf（"请输入课程的代表值（课程名的长度小于等于10个字符）:
"）;
for（i=0;i{
scanf（"%s",&G.vertices[i].data）;
G.vertices[i].firstarc=NULL;
}//输入顶点信息
printf（"请输入课程间两两间的先后关系：
"）;
for（i=0;iscanf（"%d,%d",&v,&w）;//形式2
ArcNode*p=newArcNode;//建立结点
if（!
p）returnERROR;
p->adjvex=w-1;
p->nextarc=G.vertices[v-1].firstarc;//顶点v的链表
G.vertices[v-1].firstarc=p;//添加到最左边
}
returnOK;
}
voidFindInDegree（ALGraphG）
{//求图的入度
ArcNode*p;
for（inti=0;i{
p=G.vertices[i].firstarc;
while（p）
{
for（intj=0;jif（p->adjvex==j）
indegree[j]++;
p=p->nextarc;
}
}
}
StatusTopologicalSort（ALGraphG）
{//拓扑排序
//有向图G采用邻接表存储结构
SqStackS1,S2;
ArcNode*p;
inti,count,k;
FindInDegree（G）;
InitStack（S1）;
InitStack（S2）;
for（i=0;iif（!
indegree[i]）
Push（S1,i）;//把入度为0的压入栈S1
count=0;//对输出顶点计数
while（!
StackEmpty（S1））
{
printf（"第%d学期应学的课程:
",count+1）;
while（!
StackEmpty（S1））
{
Pop（S1,i）;
printf（"%s",G.vertices[i].data）;//输出i号顶点
Push（S2,i）;//把i号顶点压入栈S2
}
printf（"\n"）;
count++;//计数
while（!
StackEmpty（S2））
{
Pop（S2,i）;
for（p=G.vertices[i].firstarc;p;p=p->nextarc）
{
k=p->adjvex;//对i号顶点的每个邻接点的入度减1
if（!
（--indegree[k]））//若入度减为0,则入栈
Push（S1,k）;
}
}
}
if（countreturnERROR;
elsereturnOK;
}//TopologicalSort
intmain（）
{
ALGraphG;
CreateDG（G）;
TopologicalSort（G）;
return0;
}
升级会员 