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

輸出