數(shù)據(jù)結(jié)構(gòu)實驗五：教學(xué)計劃編制

1、HUNAN UNIVERSITY實驗五最終報告題 目 教學(xué)計劃編制問題 學(xué)生姓名 學(xué)生學(xué)號 專業(yè)班級 指導(dǎo)老師 李曉鴻 完 成 日 期 2015年12月17日 一需求分析1.程序的功能 用戶通過鍵盤輸入課程總數(shù)、每門課的課程編號和直接先修的課程號等的參數(shù)。用有向網(wǎng)表示教學(xué)計劃，其中頂點表示某門課程，有向邊表示課程之間的先修關(guān)系（如果A課程是B課程的先修課程，那么A到B之間有一條有向邊從A指向B）。最終輸出一個不沖突的線性的課程教學(xué)流程。2.輸入形式 請輸入課程總數(shù)： /輸入一個正整數(shù)n 請輸入課程1的名稱： /輸入任意字符串 請輸入課程2的名稱： . 請輸入課程n的名稱： (課程1)否是有先修

2、（1/0）： /輸入1表示有，0表示沒有若輸入1： 請輸入先修課程的名稱： /輸入存在的先修課程名稱 . (課程n)否是有先修（1/0）： 請輸入先修課程的名稱：3. 輸出形式 輸出成功： 課程表的排序為： /輸出沒有沖突的課表排序 輸出失?。?課程輸入錯誤！教學(xué)計劃編制失敗，請重新輸入。4.測試數(shù)據(jù)： .正常的輸入輸入： 輸入課程總數(shù)：3請輸入課程1的名稱：小學(xué)數(shù)學(xué)請輸入課程2的名稱：初中數(shù)學(xué)請輸入課程3的名稱：大學(xué)數(shù)學(xué)小學(xué)數(shù)學(xué)是否有先修（1/0）：0初中數(shù)學(xué)是否有先修（1/0）：1請輸入先修課程的名稱：小學(xué)數(shù)學(xué)高中數(shù)學(xué)是否有先修（1/0）：1請輸入先修課程的名稱：初中數(shù)學(xué)輸出： 課程表的排

3、序為： 小學(xué)數(shù)學(xué) 初中數(shù)學(xué) 高中數(shù)學(xué) .正常的輸入輸入： 輸入課程總數(shù)：4請輸入課程1的名稱：1請輸入課程2的名稱：2請輸入課程3的名稱：3請輸入課程4的名稱：4 1是否有先修（1/0）：0請輸入先修課程的名稱：42是否有先修（1/0）：1請輸入先修課程的名稱：33是否有先修（1/0）：1請輸入先修課程的名稱：44是否有先修（1/0）：0輸出： 課程表的排序為：4 1 3 2有兩個先修課程的情況輸入： 輸入課程總數(shù)：4請輸入課程1的名稱：A請輸入課程2的名稱：B請輸入課程3的名稱：C請輸入課程4的名稱：D A是否有先修（1/0）：0B是否有先修（1/0）：1請輸入先修課程的名稱：AC是否有先修

4、（1/0）：1請輸入先修課程的名稱：AD是否有先修（1/0）：1請輸入先修課程的名稱：C輸出： 課程表的排序為：A B C D有三個先修課程的情況輸入： 輸入課程總數(shù)：4請輸入課程1的名稱：A請輸入課程2的名稱：B請輸入課程3的名稱：C請輸入課程4的名稱：D A是否有先修（1/0）：1請輸入先修課程的名稱：DB是否有先修（1/0）：1請輸入先修課程的名稱：DC是否有先修（1/0）：1請輸入先修課程的名稱：DD是否有先修（1/0）：0輸出： 課程表的排序為：D A B C所有課程無先修輸入： 輸入課程總數(shù)：3請輸入課程1的名稱：1請輸入課程2的名稱：2請輸入課程3的名稱：3 A是否有先修（1/0

5、）：0B是否有先修（1/0）：0C是否有先修（1/0）：0輸出： 課程表的排序為：1 2 3 二、概要設(shè)計1.抽象數(shù)據(jù)類型 題設(shè)要求使用一個有向圖表示教學(xué)計劃，頂點表示某門課程，有向邊表示課程之間的先修關(guān)系，數(shù)據(jù)的對象是圖中的每一個頂點和有向邊。由此為本問題確定一個圖的數(shù)據(jù)關(guān)系。 本題目需要一個數(shù)據(jù)結(jié)構(gòu)來儲存遍歷過的圖的結(jié)點，該數(shù)據(jù)結(jié)構(gòu)滿足先進(jìn)先出，所以用隊列來實現(xiàn)。 2.ADTADT Edge數(shù)據(jù)對象： N(邊的名稱) V（標(biāo)記） F（先修課結(jié)點）數(shù)據(jù)關(guān)系：（N&&V&&F）R （R1&&R2&&Rn）Graph基本操作： st

6、ring getVal(int v)/返回邊的名稱 int getMark(int v)/返回標(biāo)記 void setVal(int v, string val)/設(shè)邊的名稱 void setMark(int v, int Mark)/設(shè)置標(biāo)記 void setfirst(int v)/設(shè)置先修結(jié)點標(biāo)記ADT Graph數(shù)據(jù)對象：V,R（分別代表某門課程的頂點組成的一個頂點集 V 和代表課程先修關(guān)系 的有向弧邊組成的一個弧集 R。）數(shù)據(jù)關(guān)系：VR<v,w>| v,wV 且 P(v,w)<v,w>表示從 v 到 w 的一條弧，并稱 v 為弧頭，

7、w 為弧尾。 基本操作：int n(); /返回圖中的頂點數(shù)int first(int); /返回該點的第一條鄰邊int next(int); /返回該店的下一條鄰邊void setEdge(int,int,int); /為有向邊設(shè)置權(quán)值void Find(string search, int& v) int n()ADT queue數(shù)據(jù)對象： 前指針front,后指針rear數(shù)據(jù)關(guān)系：R=<ai-1 ,ai>|ai-1,aicar,i=1,2,3.n約定a1 為隊列頭，an為隊列尾?；静僮鳎簈ueue(); /隊列結(jié)構(gòu)初始化queue(); /結(jié)構(gòu)銷毀操作bool pu

8、sh(const int& it); /數(shù)據(jù)入列bool pop(int& it); /數(shù)據(jù)出列int size(); /獲取隊列長度3.算法的基本思想通過用戶輸入的頂點的個數(shù)(課程數(shù))初始化一個表示有向圖的相鄰矩陣，初始化邊的訪問次數(shù)全部設(shè)置為零，通過輸入邊的信息和先修關(guān)系，設(shè)置先修關(guān)系的計數(shù)器，記錄每條邊先修關(guān)系的數(shù)量，完成對有項圖的構(gòu)建。將先修關(guān)系為零的邊放入隊列，然后開始處理隊列。當(dāng)從隊列中刪除一個頂點時，把它打印出來，同時將其所有相鄰頂點的先修關(guān)系計數(shù)器減一。當(dāng)某個相鄰頂點的計數(shù)器為0時，就將其放入隊列。如果還有頂點未被打印，而隊列已經(jīng)為空，則圖中必然包含回路（既不可

9、能不違反先決條件完成任務(wù)）。4.程序的流程 （1） 初始化模塊：輸入課程總數(shù)，再輸入相應(yīng)數(shù)量的課程編號及每個課程的先修課程，用這些信息初始化一個有向圖。（2） 拓?fù)渑判蚰K：對有向圖進(jìn)行拓?fù)渑判?。?） 輸出模塊：根據(jù)有向圖是否為空輸出。為空時，輸出拓?fù)渑判蚪Y(jié)果；不為空時輸出輸入錯誤提示。三、詳細(xì)設(shè)計1.物理數(shù)據(jù)類型用戶輸入的課程個數(shù)不定，所以存儲拓?fù)渑判蚝蟮捻旤c的個數(shù)不定，對于圖有兩種存儲方式，本題中用鄰接矩陣來存儲圖的信息，對于邊很少的圖來說，雖然用鄰接矩陣有些浪費空間，但是題目做起來相對方便。由于用戶輸入的課程個數(shù)不定，使用鏈?zhǔn)綏！Ｊ褂胹tring類型儲存用戶信息和邊的信息。2. 算法的

10、具體步驟 初始化一個有向圖先修信息的儲存拓?fù)渑判蚺c輸出初始化一個有向圖：包括初始化被訪問標(biāo)記和先修標(biāo)記,動態(tài)創(chuàng)建二維數(shù)組和用于儲存邊信息的一維數(shù)組。 Graph(int numVert)int i, j;numVertex = numVert;numEdge = 0;mark = new PointnumVert; / Initialize mark arrayfor (i = 0; i < numVertex; i+)marki.visit = -1;/包括初始化被訪問標(biāo)記和先修標(biāo)記marki.first = 0;matrix = (int*) new int*numVertex; /

11、 Make matrixfor (i = 0; i < numVertex; i+)matrixi = new intnumVertex;for (i = 0; i < numVertex; i+)/Edges start w/0 weightfor (int j = 0; j < numVertex; j+) matrixij = 0; .先修信息的存儲：由用戶輸入是否有先修課程后，用戶每輸入一個先修課程，就將這個課程對應(yīng)的先修標(biāo)記加1. cout << a.getVal(i) << "是否有先修（1/0）"cin >>

12、; judge;if (judge)a.setfirst(i);cout << "請輸入先修課程的名稱:"cin >> Ch1;a.Find(Ch1, v1);a.setEdge(v1, i, 10); void setfirst(int v) markv.first+;拓?fù)渑判蚺c輸出：定義兩個隊列A和 B，將先修關(guān)系為零的邊放入隊列A，然后開始處理隊列。當(dāng)從隊列A中刪除一個頂點時，該頂點進(jìn)入B隊列，再把該頂點打印出來，同時將其所有相鄰頂點的先修關(guān)系計數(shù)器減一。當(dāng)某個相鄰頂點的計數(shù)器為0時，就將其放入隊列。如果還有頂點未被打印，而隊列已經(jīng)為空，則圖中

13、必然包含回路（既不可能不違反先決條件完成任務(wù)）。輸出：重復(fù)將隊列B中首元素輸出并刪除，直到隊列為空，就是課程表的排序。void DFS(Graph* G, queue<int> *Q, queue<int> *L)for (int v = 0; v < n(); v+)if (markv.first = 0)Q->push(v);setMark(v, 1);while (Q->size() != 0)int i = Q->front();/獲取Q棧首元素Q->pop();/彈出Q棧L->push(i);/進(jìn)L棧for (int w =

14、 first(i); w < n(); w = next(i, w)markw.first-;if (markw.first = 0)Q->push(w); setMark(w, 1);for (int i = 0; i < n(); i+)if (getMark(i) = -1) /為0時表示還未被刪除，圖不為空cout << "課程輸入錯誤！教學(xué)計劃編制失敗，請重新輸入。" << endl;exit(0); 3.算法的時空分析及改進(jìn)設(shè)想因為圖的鄰接矩陣是一個|V|×|V|矩陣，所以鄰接矩陣的空間代價為(|V|2)，對于

15、有n個頂點的和E條弧的有向圖而言，對此圖的拓?fù)渑判蛩惴〞r間復(fù)雜度為（V+E） 4.輸入和輸出的格式輸入： 1.輸入課程數(shù)ncout << "請輸入課程總數(shù)："cin >> n;if (n <= 0)cout << "輸入錯誤重新輸入(大于零的整數(shù))" << endl;cout << "請輸入課程總數(shù)："cin >> n;2.輸入每門課的課程編號for (int i = 0; i < n; i+)cout << "請輸入課程&quo

16、t; << i + 1 << "名稱:"cin >> Ch;a.setVal(i, Ch); 3. 獲得先修的課程編號for (int i = 0; i < n; i+)judge = 0;cout << a.getVal(i) << "是否有先修（1/0）"cin >> judge;if (judge)a.setfirst(i);cout << "請輸入先修課程的名稱:"cin >> Ch1;a.Find(Ch1, v1);a.se

17、tEdge(v1, i, 10);輸出：1. 編制成功，把隊列S中的頂點序列輸出。 cout << "課程表的排序為:" << endl;a.DFS(&a, &Q, &L);for (int i = 0; i < n; i+)int j = L.front();cout << a.getVal(j) << " "L.pop();2. 編制失敗，圖中有回路，輸出錯誤信息，結(jié)束程序。if(G.getMark(i)=0) /為0時表示該頂點未經(jīng)過拓?fù)渑判?cout<<&q

18、uot;課程輸入錯誤！教學(xué)計劃編制失敗，請重新輸入。"<<endl;exit(0);四調(diào)試分析 DFS問題，書上思路很明確并且有很多源碼，沒有大的問題。五測試結(jié)果1. 正常的輸入輸出 .正常的輸入3.有兩個先修課程的情況有三個先修課程的情況所有課程無先修附錄#include<iostream>#include<queue>#include<fstream>#include<string>#include<iomanip>using namespace std;class Pointpublic:string Le

19、ssonName;int visit;int first;/1有先修，0無;class Graph/Implement adjacency matrixprivate:int numVertex, numEdge;/Store number of vertices edgesint *matrix; / Pointer to adjacency matrixPoint *mark; / Pointer to mark arraypublic:Graph(int numVert)/ Make graph w/ numVert verticesint i, j;numVertex = numVer

20、t;numEdge = 0;mark = new PointnumVert; / Initialize mark arrayfor (i = 0; i < numVertex; i+)marki.visit = -1;marki.first = 0;matrix = (int*) new int*numVertex; / Make matrixfor (i = 0; i < numVertex; i+)matrixi = new intnumVertex;for (i = 0; i < numVertex; i+)/Edges start w/0 weightfor (int

21、 j = 0; j < numVertex; j+) matrixij = 0;Graph()delete mark;for (int i = 0; i < numVertex; i+)delete matrixi;delete matrix;int n()return numVertex;int e()return numEdge;int first(int v)/ Return v's first neighborint i;for (i = 0; i < numVertex; i+)if (matrixvi != 0 && marki.visit

22、 = -1) return i;return i; / Return n if noneint next(int v1, int v2)/ Get v1's neighbor after v2int i;for (i = v2 + 1; i < numVertex; i+)if (matrixv1i != 0 && marki.visit = -1)/cout<<"此時next的i值是:"<<v1+1<<" "<<i+1<<endl; return i;return

23、 i;/ Set edge (v1, v2) to wgtvoid setEdge(int v1, int v2, int wgt)numEdge+;/ERRORmatrixv1v2 = wgt;void delEdge(int v1, int v2) / Delete edge (v1, v2)if (matrixv1v2 != 0)numEdge-;matrixv1v2 = 0;int weight(int v1, int v2)return matrixv1v2;string getVal(int v)return markv.LessonName;int getMark(int v)r

24、eturn markv.visit;void setVal(int v, string val)markv.LessonName = val;void setMark(int v, int Mark)markv.visit = Mark;void setfirst(int v)markv.first+;void Find(string search, int& v)for (int i = 0; i < numVertex; i+)if (marki.LessonName = search)v = i;return;cout << "路徑錯誤" &

25、lt;< endl;return;void DFS(Graph* G, queue<int> *Q, queue<int> *L)for (int v = 0; v < n(); v+)if (markv.first = 0)Q->push(v);setMark(v, 1);while (Q->size() != 0)int i = Q->front();/獲取Q棧首元素Q->pop();/彈出Q棧L->push(i);/進(jìn)L棧for (int w = first(i); w < n(); w = next(i, w)markw.first-;if (markw.first = 0)Q->push(w); setMark(w, 1);for (int i = 0; i < n(); i+)if (getMark(i) = -1) /為0時表示還未被刪除，圖不為空cout << "課程輸入錯誤！教學(xué)計劃編制失敗，請重新輸入。" << endl;exit(0);int main()int n;int v1;int v2;int