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

HUNAN UNIVERSITY

课程实习报告

题 目： 教学计划编制问题

学生姓名 学生学号

专业班级 指导老师 李晓鸿 完 成 日 期

背景

大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这样的前提下设计一个教学计划编制程序。

问题描述

若用有向网表示教学计划，其中顶点表示某门课程，有向边表示课程之间的先修关系（如果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//排列成功

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

二、概要设计

1.抽象数据类型

ADT 图

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

数据关系：Graph = (V,R)

VR＝{<v,w>|v,w∈V且P(v,w)}

基本操作：

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

int e() =0; //返回图边数

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

void setEdge(int v1, int v2)//加边

int next(int, int) =0; //返回下一条邻边

int getMark(int) =0;//有标记吗

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

2.程序的流程

程序由三个模块组成：

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

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

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

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

输出错误。

3.算法的基本思想

（1）拓扑算法：找到第一个入度为0 的点，从有向图中删去此顶点以及所有以它为尾的弧，再在这些点中找入度为0 的点。重复上述操作，直至图空，或者图不空但找不到无前驱的顶点为止。如果图空，则说明课程可以安排成功，输出序列。如果不空，说明课程安排失败，输出失败。

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

4.设计思路

先对课程编号及其先修课程编号进行输入。利用拓扑排序对课程先后顺序进行分析，但当又向图中存在环时，无法查找该图的一个拓扑排序，当图中的所有顶点全部输出，表示对该图排序成功，实现拓扑排序算法时。根据课程的先后关系，对个学期的课程进行排序，输出。

三、详细设计

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

class Graphm : public Graph

{

private:

int numVertex, numEdge;

int **matrix;

int *mark;

public:

Graphm(int numVert)

{

int i, j;

numVertex = numVert;

numEdge = 0;

mark = new int[numVert];

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

mark[i] = UNVISITED;

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

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

matrix[i] = new int[numVertex];

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

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

}

（2）拓扑算法。找到第一个入度为0 的点，从有向图中删去此顶点以及所有以它为尾的弧，再在这些点中找入度为0 的点。重复上述操作，直至图空，或者图不空但找不到无前驱的顶点为止。如果图空，则说明课程可以安排成功，输出序列。如果不空，说明课程安排失败，输出失败。

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

int Count[G->n()];

int v, w;

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

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

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

Count[w]++; // Add to v2's count

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

if (Count[v] == 0) // No prereqs

Q->enqueue(v);

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

Q->dequeue(v);

printout(v); // PreVisit for V

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

{

Count[w]--; // One less prereq

if (Count[w] == 0) // Now free

Q->enqueue(w);

}

}

}

（3）图的基本操作

int first(int v)

{

int i;

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

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

return i;

return i;

}

int next(int v1, int v2)

{

int i;

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

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

return i;

return i;

}

void setEdge(int v1, int v2)

{

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

numEdge++;

matrix[v1][v2] = 1;

}

int n()

{

return numVertex;

}

int e()

{

return numEdge;

}

} int getMark(int v) { return mark[v]; } void setMark(int v, int val) { mark[v] = val; }

（4）算法的时空分析

邻接矩阵的空间代价为Θ(|V|2)，减边的拓扑排序算法时间待见为 …… 此处隐藏：2101字，全部文档内容请下载后查看。喜欢就下载吧 ……