湖南大學(xué)數(shù)據(jù)結(jié)構(gòu)教學(xué)計(jì)劃編制問題

HUNANUNIVERSITY

課程實(shí)習(xí)報(bào)告

題目：教學(xué)計(jì)劃編制問題

學(xué)生姓名______________________________________

學(xué)生學(xué)號(hào)______________________________

專業(yè)班級(jí)______________________________

指導(dǎo)老師___________李曉鴻_________________

完成日期_____________________________________

背景

大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)

期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在

開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，

也可以沒有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。

問題描述

若用有向網(wǎng)表示教學(xué)計(jì)劃，其中頂點(diǎn)表示某門課程,有向邊表示課程之間的先修關(guān)系（如

果A課程是B課程的先修課程，那么A到B之間有一條有向邊從A指向B）。試設(shè)計(jì)一個(gè)

教學(xué)計(jì)劃編制程序，獲取一個(gè)不沖突的線性的課程教學(xué)流程。（課程線性排列，每門課上課

時(shí)其先修課程己經(jīng)被安排）。

基本要求

（1）輸入?yún)?shù)：課程總數(shù)，每門課的課程號(hào)（固定占3位的字母數(shù)字串）和直接先

修課的課程號(hào).

（2）若根據(jù)輸入條件問題無解，則報(bào)告適當(dāng)?shù)男畔?；否則將教學(xué)計(jì)劃輸出到用戶指

定的文件中。

一、需求分析

根據(jù)課程間的依賴關(guān)系，制定課程安排計(jì)劃。按照用戶的輸入建立一個(gè)鄰接表，輸出拓

撲排序結(jié)果。按照用戶輸入的課程數(shù)，學(xué)期數(shù)，課程間的先后關(guān)系數(shù)目以及課程間兩兩間的

先后關(guān)系，程序執(zhí)行后會(huì)給出每學(xué)期應(yīng)學(xué)的課程順序。

（1）輸入的形式和輸入值的范圍：本程序要求首先輸入一個(gè)正整數(shù)值N,代表課程總數(shù),

然后依次輸入課程的代號(hào)（使用長(zhǎng)度為3位的字符串表示），每次輸入完該課程的代號(hào)后，

同時(shí)輸入先修的課程的代號(hào)。因此，用整數(shù)來存儲(chǔ)課程總數(shù)，字符串來存儲(chǔ)課程代號(hào)。

（2）輸出的形式：根據(jù)輸入的數(shù)據(jù)，進(jìn)行拓?fù)渑判?，若能成功，則輸出序列，表示應(yīng)學(xué)

的課程順序，若不能成功，則提示報(bào)錯(cuò)進(jìn)行課程調(diào)整。

（3）程序所能達(dá)到的功能：按照用戶的輸入，輸出拓?fù)渑判蚪Y(jié)果。按照用戶的輸入，給

出每學(xué)期應(yīng)學(xué)的課程。

（4）測(cè)試數(shù)據(jù)：

輸入請(qǐng)輸入課程數(shù)目：〃提示輸入

6

請(qǐng)輸入課程：〃提示輸入

S1

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

F//表示沒有

請(qǐng)輸入課程：〃提示輸入

S2

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

T//表不有

先修課程是：〃提示輸入

S1

輸出課程排列完成，為S1,S3,S5,S2,S6,S7,S4//排列成功

課程有誤，請(qǐng)重新調(diào)整〃失敗

二、概要設(shè)計(jì)

L抽象數(shù)據(jù)類型

ADT圖

數(shù)據(jù)對(duì)象：V,R（圖是由一個(gè)頂點(diǎn)集V和一個(gè)弧集R構(gòu)成的數(shù)據(jù)結(jié)構(gòu)）

數(shù)據(jù)關(guān)系：Graph=（V,R）

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

基本操作:

intn()=0;//返回圖節(jié)點(diǎn)數(shù)

inte()=0;〃返回圖邊數(shù)

intfirst(int)=0;〃返回該節(jié)點(diǎn)的第一條鄰邊

voidsetEdge(intvl,intv2)〃力口邊

intnext(int,int)=0;〃返回下一條鄰邊

intgetMark(int)=0;〃有標(biāo)記嗎

voidsetMark(int,int)=0;//設(shè)置標(biāo)記

2.程序的流程

程序由三個(gè)模塊組成：

（1）初始化模塊：首先輸入課程總數(shù)，輸入課程編號(hào)以及每個(gè)課程的先修課程，把

這種帶有先決條件的線性關(guān)系存入圖中；

（2）拓?fù)淠K：對(duì)圖做拓?fù)渑判颍?/p>

（3）輸出模塊：輸出拓?fù)渑判虻慕Y(jié)果，若成功，輸出排序后的序列，若不成功，則

輸出錯(cuò)誤。

3.算法的基本思想

（1）拓?fù)渌惴ǎ赫业降谝粋€(gè)入度為0的點(diǎn)，從有向圖中刪去此頂點(diǎn)以及所有以它為尾的弧,

再在這些點(diǎn)中找入度為0的點(diǎn)。重復(fù)上述操作，直至圖空，或者圖不空但找不到無前驅(qū)的

頂點(diǎn)為止。如果圖空，則說明課程可以安排成功，輸出序列。如果不空，說明課程安排失敗,

輸出失敗。

（2）圖的存儲(chǔ)：用鄰接矩陣來存儲(chǔ)

4.設(shè)計(jì)思路

先對(duì)課程編號(hào)及其先修課程編號(hào)進(jìn)行輸入。利用拓?fù)渑判驅(qū)φn程先后順序進(jìn)行分析，但

當(dāng)又向圖中存在環(huán)時(shí)，無法查找該圖的一個(gè)拓?fù)渑判?，?dāng)圖中的所有頂點(diǎn)全部輸出，表示對(duì)

該圖排序成功，實(shí)現(xiàn)拓?fù)渑判蛩惴〞r(shí)。根據(jù)課程的先后關(guān)系，對(duì)個(gè)學(xué)期的課程進(jìn)行排序，輸

出。

三、詳細(xì)設(shè)計(jì)

(1)圖的存儲(chǔ)：用鄰接矩陣來存儲(chǔ)

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)拓?fù)渌惴?。找到第一個(gè)入度為0的點(diǎn)，從有向圖中刪去此頂點(diǎn)以及所有以

它為尾的弧，再在這些點(diǎn)中找入度為0的點(diǎn)。重復(fù)上述操作，直至圖空，或者

圖不空但找不到無前驅(qū)的頂點(diǎn)為止。如果圖空，則說明課程可以安排成功，輸

出序列。如果不空，說明課程安排失敗，輸出失敗。

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）算法的時(shí)空分析

鄰接矩陣的空間代價(jià)為?（IW2）,減邊的拓?fù)渑判蛩惴〞r(shí)間待見為?（V+E）。

（5）函數(shù)的調(diào)用關(guān)系圖

<■提示用戶輸入課程總數(shù)

輸入課程代號(hào)和先修課程代號(hào)

主程序W

一拓?fù)渑判?/p>

輸出

（6）輸入和輸出的格式

輸入請(qǐng)輸入課程數(shù)目：〃提示輸入

6

請(qǐng)輸入課程：〃提示輸入

S1

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

F//表示沒有

請(qǐng)輸入課程：〃提示輸入

S2

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

T〃表示有

先修課程是：〃提示輸入

S1

輸出