湖南大学数据结构教学计划编制问题

HUNANUNIVERSITY

课程实习报告

题目：教学计划编制问题

学生姓名______________________________________

学生学号______________________________

专业班级______________________________

指导老师___________李晓鸿_________________

完成日期_____________________________________

背景

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学

期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在

开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，

也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

问题描述

若用有向网表示教学计划，其中顶点表示某门课程,有向边表示课程之间的先修关系（如

果A课程是B课程的先修课程，那么A到B之间有一条有向边从A指向B）。试设计一个

教学计划编制程序，获取一个不冲突的线性的课程教学流程。（课程线性排列，每门课上课

时其先修课程己经被安排）。

基本要求

（1）输入参数：课程总数，每门课的课程号（固定占3位的字母数字串）和直接先

修课的课程号.

（2）若根据输入条件问题无解，则报告适当的信息；否则将教学计划输出到用户指

定的文件中。

一、需求分析

根据课程间的依赖关系，制定课程安排计划。按照用户的输入建立一个邻接表，输出拓

扑排序结果。按照用户输入的课程数，学期数，课程间的先后关系数目以及课程间两两间的

先后关系，程序执行后会给出每学期应学的课程顺序。

（1）输入的形式和输入值的范围：本程序要求首先输入一个正整数值N,代表课程总数,

然后依次输入课程的代号（使用长度为3位的字符串表示），每次输入完该课程的代号后，

同时输入先修的课程的代号。因此，用整数来存储课程总数，字符串来存储课程代号。

（2）输出的形式：根据输入的数据，进行拓扑排序，若能成功，则输出序列，表示应学

的课程顺序，若不能成功，则提示报错进行课程调整。

（3）程序所能达到的功能：按照用户的输入，输出拓扑排序结果。按照用户的输入，给

出每学期应学的课程。

（4）测试数据：

输入请输入课程数目：〃提示输入

6

请输入课程：〃提示输入

S1

是否有先修课程（T/F）

F//表示没有

请输入课程：〃提示输入

S2

是否有先修课程（T/F）

T//表不有

先修课程是：〃提示输入

S1

输出课程排列完成，为S1,S3,S5,S2,S6,S7,S4//排列成功

课程有误，请重新调整〃失败

二、概要设计

L抽象数据类型

ADT图

数据对象：V,R（图是由一个顶点集V和一个弧集R构成的数据结构）

数据关系：Graph=（V,R）

VR={<v,w>|v,wwV且P（v,w）}

基本操作:

intn()=0;//返回图节点数

inte()=0;〃返回图边数

intfirst(int)=0;〃返回该节点的第一条邻边

voidsetEdge(intvl,intv2)〃力口边

intnext(int,int)=0;〃返回下一条邻边

intgetMark(int)=0;〃有标记吗

voidsetMark(int,int)=0;//设置标记

2.程序的流程

程序由三个模块组成：

（1）初始化模块：首先输入课程总数，输入课程编号以及每个课程的先修课程，把

这种带有先决条件的线性关系存入图中；

（2）拓扑模块：对图做拓扑排序；

（3）输出模块：输出拓扑排序的结果，若成功，输出排序后的序列，若不成功，则

输出错误。

3.算法的基本思想

（1）拓扑算法：找到第一个入度为0的点，从有向图中删去此顶点以及所有以它为尾的弧,

再在这些点中找入度为0的点。重复上述操作，直至图空，或者图不空但找不到无前驱的

顶点为止。如果图空，则说明课程可以安排成功，输出序列。如果不空，说明课程安排失败,

输出失败。

（2）图的存储：用邻接矩阵来存储

4.设计思路

先对课程编号及其先修课程编号进行输入。利用拓扑排序对课程先后顺序进行分析，但

当又向图中存在环时，无法查找该图的一个拓扑排序，当图中的所有顶点全部输出，表示对

该图排序成功，实现拓扑排序算法时。根据课程的先后关系，对个学期的课程进行排序，输

出。

三、详细设计

(1)图的存储：用邻接矩阵来存储

classGraphm:publicGraph

(

private:

intnumVertex,numEdge;

int**matrix;

int*mark;

public:

Graphm(intnumVert)

(

inti,j;

numVertex=numVert;

numEdge=0;

mark=newint[numVert];

for(i=0;i<numVertex;i++)

mark[i]=UNVISITED;

matrix=(int**)newint*[numVertex];

for(i=0;i<numVertex;i++)

matrix[i]=newint[numVertex];

for(i=0;i<numVertex;i++)

for(intj=0;j<numVertex;j++)matrix[i][j]=0;

)

(2)拓扑算法。找到第一个入度为0的点，从有向图中删去此顶点以及所有以

它为尾的弧，再在这些点中找入度为0的点。重复上述操作，直至图空，或者

图不空但找不到无前驱的顶点为止。如果图空，则说明课程可以安排成功，输

出序列。如果不空，说明课程安排失败，输出失败。

voidtopsort(Graph*G,Queue<int>*Q){

intCount[G->n()];

intv,w;

for(v=0;v<G->n();v++)Count[v]=0;

for(v=0;v<G->n();v++)//Processedges

for(w=G->first(v);w<G->n();w=G->next(v,w))

Count[w]++;//Addtov2'scount

for(v=0;v<G->n();v++)//InitializeQ

if(Count[v]==0)//Noprereqs

Q->enqueue(v);

while(Q->length()!=0){

Q->dequeue(v);

printout(v);//PreVisitforV

for(w=G->first(v);w<G->n();w=G->next(v,w))

(

Count[w]―;//Onelessprereq

if(Count[w]==0)//Nowfree

Q->enqueue(w);

)

}

(3)图的基本操作

intfirst(intv)

(

inti;

for(i=0;i<numVertex;i++)

if(matrix[v][i]!=0)

returni;

returni;

)

intnext(intvl,intv2)

(

inti;

for(i=v2+l;i<numVertex;i++)

if(matrix[vl][i]!=0)

returni;

returni;

)

voidsetEdge(intvl,intv2)

(

if(matrix[vl][v2]==0)

numEdge++;

matrix[vl][v2]=1;

)

intn()

(

returnnumVertex;

)

inte()

returnnumEdge;

intgetMark(intv)

(

returnmark[v];

)

voidsetMark(intv,intval)

(

mark[v]=val;

（4）算法的时空分析

邻接矩阵的空间代价为®（IW2）,减边的拓扑排序算法时间待见为®（V+E）。

（5）函数的调用关系图

<■提示用户输入课程总数

输入课程代号和先修课程代号

主程序W

一拓扑排序

输出

（6）输入和输出的格式

输入请输入课程数目：〃提示输入

6

请输入课程：〃提示输入

S1

是否有先修课程（T/F）

F//表示没有

请输入课程：〃提示输入

S2

是否有先修课程（T/F）

T〃表示有

先修课程是：〃提示输入

S1

输出