教學計劃編制問題-試驗5

1、題 目： 教學計戈U編制問題學生姓名 學生學號專業(yè)班級 指導老師完成日期2014年5月15日一、 需求分析1 輸入形式： 用戶通過鍵盤輸入課程總數(shù)、每門課的課程編號(固定占 3 位的字母數(shù)字串)和直接先修的課程號等的參數(shù)。實驗五最終報告不對非法輸入做處理，假定輸入的數(shù)據(jù)都合法。2 輸出形式： 如果拓撲排序成功，輸出拓撲排序后的教學計劃編制的順序； 如果拓撲排序不成功，輸出排序錯誤信息，結(jié)束程序。3 程序功能：對于用戶輸入的一組課程編號，根據(jù)輸入的先修順序創(chuàng)建鄰接矩陣進行 存儲，并輸出拓撲排序后的課程編號的順序。4 測試數(shù)據(jù) 輸入： 輸入課程總數(shù)： 3 輸入每門課的課程編號： A01 是否有直接

2、先修的課程(T/F) ：F輸入每門課的課程編號： A02 是否有直接先修的課程(T/F) ：T先修課程編號： A01 是否有直接先修的課程 (T/F) ：F輸入每門課的課程編號： A03 是否有直接先修的課程(T/F) ：T先修課程編號： A02 是否有直接先修的課程 (T/F) ：F輸出： 教學計劃編制完成，課程修讀順序為： A01,A02,A03 (輸入有誤)課程輸入錯誤！教學計劃編制失敗，請重新輸入。二、概要設計 抽象數(shù)據(jù)類型題設要求使用一個有向圖表示教學計劃， 頂點表示某門課程， 有向邊表示課程之間的先 修關系，數(shù)據(jù)的對象是圖中的每一個頂點和有向邊。由此為本問題確定一個圖的數(shù)據(jù)關系。拓

3、撲排序可以用頂點入度為 0 的方法實現(xiàn)， 所以為實現(xiàn)拓撲排序的頂點順序的存放， 創(chuàng) 建一個隊列來存放。圖的 ADT數(shù)據(jù)對象：V,R (分別代表某門課程的頂點組成的一個頂點集V 和代表課程先修關系的有向弧邊組成的一個弧集R。)數(shù)據(jù)關系：VR = | v,w V 且 P(v,w)表示從 V 到 w 的一條弧，并稱 v 為弧頭，w 為弧尾。基本操作：int n();/返回圖中的頂點數(shù)int first(int); /返回該點的第一條鄰邊int next(int); /返回該店的下一條鄰邊void setEdge(int,int,int); /為有向邊設置權(quán)值int getMark(int); /獲得

4、頂點的標志值void setMark(int); /為頂點設置標志值隊列 ADT數(shù)據(jù)對象：int數(shù)據(jù)關系:R=|a/,ai car,i=1,2,3 .n約定 ai為隊列頭，an 為隊列尾。基本操作：queue();隊列結(jié)構(gòu)初始化queue();/結(jié)構(gòu)銷毀操作bool push(co nst int& it);數(shù)據(jù)入列bool pop(i nt& it);數(shù)據(jù)出列int size(); /獲取隊列長度算法的基本思想通過用戶輸入的頂點的個數(shù)(課程數(shù))初始化一個表示有向圖的相鄰矩陣，課程編號作為相鄰矩陣的行列值以及有向邊的關系(課程先修關系)完成一個有向圖的構(gòu)建。為了檢驗圖中頂點是否

5、都經(jīng)過拓撲排序，為每個頂點初始化一個標志值0,當一個頂點經(jīng)過拓撲排序后更改該頂點標志值 0。對相鄰矩陣棕的頂點進行入度為0 的方法進行拓撲排序。排序結(jié)束后，遍歷一次圖中所有頂點的標志值，當有一個標志值為0 時，輸出錯誤信息，結(jié)束程序。否則，排序成功，輸出排序后的頂點序列。程序的流程(1)初始化模塊：輸入課程總數(shù)，再輸入相應數(shù)量的課程編號及每個課程的先修課 程，用這些信息初始化一個有向圖。(2)拓撲排序模塊：對有向圖進行拓撲排序。(3)輸出模塊：根據(jù)有向圖是否為空輸出。為空時，輸出拓撲排序結(jié)果；不為空時 輸出輸入錯誤提示。各層次模塊之間的調(diào)用關系三、詳細設計物理數(shù)據(jù)類型由于用戶輸入的課程個數(shù)不定

6、，所以存儲拓撲排序后的頂點的個數(shù)不定，由此用鏈式隊列來存儲排序后的頂點。為了檢查圖中是否有回路，把每一個頂點的標志值初始化為0。(一)有向圖的基本操作1.初始化一個有向圖Graphm(i nt num Vert)int i,j;num Vertex = num Vert;/ 頂點數(shù)nu mEdge=0;mark= new intnum Vert;/ 初始化標志數(shù)組for(i=0;inumVertex;i+)marki=0;/ 每一個頂點的標志值初始化為 0 matrix =(int*) new int*numVertex;for(i=0;inumVertex;i+)matrixi=new in

7、tnumVertex;/ 構(gòu)建一個相鄰矩陣for(i=0;inumVertex;i+)for(j=0;jnumVertex;j+) matrixij=0;2.有向圖的銷毀Graphm()delete mark;for(int i=0;inumVertex;i+)delete matrixi;delete matrix;/ 銷毀相鄰矩陣3.獲取第一個鄰居int first(int v)/ 返回該點的第一條鄰邊int i;for(i=0;inumVertex;i+)if(matrixvi!=0) return i;/當頂點和頂點 i 有邊時，返回頂點return i;int next(int v1

8、,int v2)/ 獲得 v1 的鄰居 v2int i;for(i=v2+1;inumVertex;i+) if(matrixv1i!=0) return i;return i;4.其他基本操作void setEdge(int v1,int v2)/ 設置有向圖的邊if(matrixv1v2=0) numEdge+;matrixv1v2=1;int getMark(int v) / 獲取頂點標記的值return markv;int setMark(int v,int val)/設置訪問的標記markv=val;(二 ) 拓撲排序找到第一個入度為 0 的點存入隊列中， 從有向圖中刪去此頂點以及所

9、有以它為尾的 弧，再在這些點中找入度為 0 的點。 重復上述操作，直至圖空，或者圖不空但找不到無 前驅(qū)的頂點為止，此時返回該隊列。queue topsort(Graphm G ,queue Q,queue L, int n )i 的值int count100;int v,w,i;for(v=0;vn;v+)countv=0; for(v=0;vn;v+) for(w=G .first(v);wn;w=G.next(v,w) countw+;for(v=0;vn;v+)if(countv=0) /找到度為 0 的點 Q.push(v); G.setMark(v,1); / 頂點進隊列，并更改頂點

10、標志值為 1while(Q.size()!=0)i=Q.front();Q.pop();L.push(i);for(w=G .first(i);welem;qnode* ltemp=front;front=front-next;delete ltemp;if(front=NULL) rear=NULL;size-;return true;/出隊列bool push (const char*& it)if(rear=NULL)fron t=rear =new qno de(it,NULL);else /appe ndrear-n ext =new qno de(it,NULL);rear

11、=rear- n ext;size+;return true;獲取隊列長度int size() const return size; 最后，判斷圖中是否有回路?？梢酝ㄟ^遍歷圖中的每一個頂點的標記值，如果有一個 為 0,那么說明圖中存在回路。for(i=0;i n ;i+)if(G.getMark(i)=0)/為 0 時表示該頂點未經(jīng)過拓撲排序cout課程輸入錯誤！教學計劃編制失敗，請重新輸入。endl;exit(0);算法的具體步驟創(chuàng)建一個數(shù)組存儲頂點信息，再構(gòu)建一個鄰接矩陣存儲輸入的課程編號(頂點)，和課程先修關系(有向邊)構(gòu)成的有向圖的信息，然后對鄰接矩陣中的圖的信息進行拓撲排序，把排 序

12、結(jié)果存放在一個隊列中。如果一次排序結(jié)束后，遍歷頂點標志值有為0，輸出輸入錯誤提示，結(jié)束程序；否則，輸出隊列中存儲的課程編號序列。流程圖如下：偽代碼如下，char v1005;char v14,v24;Graphm T; queue S;cin.get(n);/輸入課程總數(shù) nT.CreatGraphm(n);cin.get(v);/ 輸入每門課的編號，保存在*v4 數(shù)組中for(i=0;in;i+)coutvich;while(ch=T)GetNum(n2);/輸入先修課程編號T.setEdge(n2,i); /n2 在前表示先修的順序 coutch;S=topsort(T,Q,L,n);/

13、對圖 T 進行拓撲排序，排序序列存儲在隊列中返回到 Scout 教學計劃編制完成，課程修讀順序為： endl;printout(S);/輸出排序后的頂點序列算法的時空分析及改進設想因為圖的鄰接矩陣是一個|V|料 I 矩陣，所以鄰接矩陣的空間代價為(VF2)，對于有 n 個頂點的和 E 條弧的有向圖而言，對此圖的拓撲排序算法時間復雜度為E(V+E)輸入和輸出的格式輸入：1.輸入課程數(shù) n-cin.get(n) ；cout 輸入課程總數(shù)： ;cinn;2.輸入每門課的課程編號 -cin.get(v);for(i=0;in;i+)cout 輸入每門課的課程編號： endl; cin.get();ci

14、n.getline(v1,4); strcpy(vi,v1); /要用字符串拷貝函數(shù)，用等號不能正確的賦值！ ！3.獲得先修的課程編號 -GetNum(n2);cout 先修課程編號： ; cin.get();in.getline(v2,4);輸出:1.編制成功，把隊列 S 中的頂點序列輸出。-printout(S);for(i=0;i n ;i+)j=S.fro nt();coutvj;S.pop();2.編制失敗，圖中有回路，輸出錯誤信息，結(jié)束程序。if(G.getMark(i)=O) /為 0 時表示該頂點未經(jīng)過拓撲排序cout課程輸入錯誤！教學計劃編制失敗，請重新輸入。001-002編

15、制失敗，001-002,002-001換木邊程總2貉入?yún)呜暾n苗課程編號；001輸入每門課的課程編號：002001是否有直接先修的課程廠=1先修課程002杲否君直謂蕪蟹的課程6F) : F囲 H-一是否有賣接先樓的課程門 先修課程綿號；091是否有直接羌傷的課程成恥:F課程輸入錯誤！教學計刻編制失敗，請重新輸入PressSLViyIto conizLoue附上完整代碼n2=getNum(v ,n,v2);入課程總殊：丁俞入每仃課的課程編號;入每門課的課程編號;102轅有餓毎讎雜解 M程編號：001否有直挨咗:修的課 : F接先慘的課|S=F文學計劃編制完成，課程修讀M序為匕| 鯽901S02r-

16、ess a_ny key to contjaiiiE#include#include#includeusing namespace std;class edgepublic:int vertex,weight; /頂點和權(quán)edge() vertex=-1;weight=-1;edge(int v,int w) vertex=v;weight=w; ;class Graphmprivate:int numVertex,numEdge;int *matrix;/ 矩陣int *mark;public:Graphm()void CreatGraphm(int numVert)int i,j;numV

17、ertex = numVert; /vertex 頂點數(shù) numEdge=0;mark=new intnumVert; for(i=0;inumVertex;i+) marki=0;matrix =(int*) new int*numVertex; for(i=0;inumVertex;i+)matrixi=new intnumVertex;for(i=0;inumVertex;i+) for(j=0;jnumVertex;j+) matrixij=0;Graphm()delete mark;for(int i=0;inumVertex;i+)delete matrixi;delete mat

18、rix;int n()return numVertex; int e()return numEdge;int first(int v)int i;for(i=0;inumVertex;i+)if(matrixvi!=0) return i;return i;int next(int v1,int v2)/ 獲得 v1 的鄰居 v2int i;for(i=v2+1;inumVertex;i+)if(matrixv1i!=0) return i;return i;void setEdge(int v1,int v2) if(matrixv1v2=0) numEdge+;matrixv1v2=1;i

19、nt getMark(int v)return markv;void setMark(int v,int val)markv=val;queue topsort(Graphm G ,queue Q,queue L, int n )int count100;int v,w,i;for(v=0;vn;v+)countv=0; for(v=0;vn;v+)for(w=G.first(v);wn;w=G .next(v,w) countw+;for(v=0;vn;v+)if(countv=0) Q.push(v); G.setMark(v,1); while(Q.size()!=0) i=Q.front(); Q.pop(); L.push(i); for(w=G.first(i);wn;w=G .next(i,w)countw-; if(countw=0) Q.push(w); G.setMark(w,1); for(i=0;in;i+)if(G.getMark(i)=0) /為 0 時表