目录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。
课程间两两间的先后关系：v1 v2,v1 v3, v1 v4,v1 v12,v2 v3,v3 v5,v3 v7,v3 v8,v4 v5, v5 v7,v6 v8,v9 v10, v9 v11 , v9 v12,v10 v12,v11v6输出：第1学期应学的课程：v1 v9第2学期应学的课程：v2 v4 v10 v11第3学期应学的课程：v3 v6 v12第4学期应学的课程：v5 v8第5学期应学的课程：v74 概要设计4.1设计思想总体思想是利用拓扑排序的思想和堆栈思想编写相应函数。
首先根据课程的先后关系画出AOV网，网中的结点代表课程，有向边表示各学科之间的次序关系。
可以采用邻接表作AOV网的存储结构，且在头结点中增加一个存放顶点入度的数组。
为了避免重复检测入度为零的顶点，可另设一栈暂存所有入度为零的顶点。
然后根据拓扑排序依次输出应学的课程。
4.2设计流程图图1 流程图4.3 数据库设计ADT Graph｛数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。
数据系统用到的抽象数据类型定义：1．关系R：R=｛VR｝VR=｛<v,w>|v,w∈V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义和信息｝基本操作：（1）Status CreateDG(ALGraph&G)；（2）void FindInDegree(ALGraph G)；（3）Status TopologicalSort(ALGraph G)；｝ADT Graph2. ADT Stack｛数据对象：D={ai |ai∈ElemSet，i=1,2,…,n, n≥0}数据关系：R1=｛<ai-1，ai>|ai-1，ai∈D,i=2,…，n｝约定an 端为栈顶，a1端为栈底。
基本操作：（1）Status InitStack(SqStack&S)；（2）Status Push(SqStack&S,SElemType e)；（3）Status Pop(SqStack&S,SElemType&e)；（4）Status StackEmpty(SqStack S)；｝ADT Stack4.4函数及功能要求（1）Status InitStack(SqStack&S)：构造一个空栈。
（2）Status Push(SqStack&S,SElemType e)：插入元素e为新的栈顶元素。
（3）Status Pop(SqStack&S,SElemType&e)：若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK；否则返回ERROR。
（4）Status StackEmpty(SqStack S)：判断栈是否为空,为空返回TRUE,否则返回FALSE。
（5）Status CreateDG(ALGraph&G)：建立邻接表。
（6）void FindInDegree(ALGraph G)：求图的入度。
（7）void print(int n[],ALGraph G)：排序输出顶点数据。
（8）Status TopologicalSort(ALGraph G)：拓扑排序，有向图G采用邻接表存储结构。
4.5模块调用关系各程序模块之间的调用关系（子程序编号见上）：主函数可调用子程序5，8。
子程序8可调用子程序1，2，3，4，6，7。
5详细设计5.1制定课程计划伪码制定课程计划算法的伪码描述如下：Status CreateDG(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= new ArcNode;//建立结点if(p为空) return ERROR;p所指向的顶点（p->adjvex）=w-1;p所指向的下一条弧（p->nextarc）=G.vertices[v-1].firstarc;//顶点v 的链表G.vertices[v-1].firstarc=p;//添加到最左边}return OK;}voidFindInDegree(ALGraph G){//求图各顶点的入度ArcNode* p;for(int i=0;i<图G的顶点数;i++){p=G.vertices[i].firstarc;while(p不为空){if(p所指向的顶点位置（p->adjvex）==j)第j个顶点的入度+1;p=p->nextarc;}}}void print(int n[],ALGraph G)//对刚出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”;}Status TopologicalSort(ALGraph G){ //拓扑排序//有向图G采用邻接表存储结构SqStack S1,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全部赋值为-1if(第i个顶点的入度为0)把入度为0的压入栈S1count=0; //对输出顶点计数while(S1不为空栈){输出("第%d学期应学的课程:",count+1);m=0;while(S1不为空栈){将S1的栈顶元素删除，并将其值返回给I;n[m]=i;把i号顶点压入栈S2m++;}调用排序及输出函数将数组n全部赋值为-1count++; //计数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(count<G.vexnum) //该有向图有回路return ERROR;else return OK;}//TopologicalSort6 测试分析1运行程序打开界面如下图，并根据提示，输入学期数目：图2 测试1输入出错时显示如下：图3 测试2 2 输入正确继续根据提示输入课程数目：图4 测试3 3输入错误时的显示如下：图5 测试44输入正确则继续根据界面提示输入课程的代表值：图6 测试55根据界面提示输入课程间两两间的先后关系：图7 测试66 输入课程间两两间的先后关系后，则输出每学期应学的课程：图8 测试77 使用说明运行程序，出现主页面，输入学期数目（学期数目必须小于等于8），输入完成后，按回车进行下一步；输入课程数目（课程数必须小于20），输入完成后，按回车进行下一步；输入课程间的先后关系，输入完成后，按回车进行下一步；输入课程的代表值（课程名的长度小于等于10个字符，课程名之间用空格隔开），输入完成后，按回车进行下一步；输入课程间两两间的先后关系（注意：只输入课程代表值的数字部分，两两关系间用逗号隔开，不同组的关系用空格隔开），输入完成后，按回车，主界面上将显示每学期的课程安排。
至此，本程序运行结束。
8 总结本程序充分应用了我们数据结构中所学的知识，完成了教学计划安排的检验。