教學計劃編制問題.doc

背景大學的每個專業(yè)都要制定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。問題描述若用有向網(wǎng)表示教學計劃，其中頂點表示某門課程，有向邊表示課程之間的先修關系（如果A課程是B課程的先修課程，那么A到B之間有一條有向邊從A指向B）。試設計一個教學計劃編制程序，獲取一個不沖突的線性的課程教學流程。（課程線性排列，每門課上課時其先修課程已經(jīng)被安排）。一 需求分析1. 頂點表示課程名稱（包含學分信息），有向邊表示課程之間的先修關系，用有向圖實現(xiàn)這個教學計劃編制問題。2. 采用廣度優(yōu)先的方法搜索每個節(jié)點是否有邊通向該節(jié)點。3. 對有向圖實行拓撲排序4. 程序輸出的拓撲排序就是其教學修讀課程的序列5. 測試數(shù)據(jù)：輸入：請輸入課程的數(shù)量和課程先后關系：6 7 每門課程的編號：001 002 003 004 005 006 先修課程編號（課程 課程） 001 002001 003002 003002 004003 005 004 006 005 006輸出：001 002 003 004 005 006二 概要設計1. 抽象數(shù)據(jù)類型：由于課程之間存在明顯的先后關系，采用拓撲排序進行教學計劃的排序，而拓撲排序不直接輸出課程信息，而采用隊列實現(xiàn)課程信息的輸出拓撲圖的ADT的定義：ADT Graph數(shù)據(jù)對象：Subject是課程編號，是類型為char的二維數(shù)組數(shù)據(jù)關系R：點a，bGraph，若點a到b有一條邊，則arcsab=1;否則=0；基本操作P：void Adj(Graph &G,char *c1,char *c2)/建立鄰接矩陣 int Locate(Graph G,char *c)/圖G中查找元素c的位置int Indegree(Graph G,int pos)/計算入度void DeleteDegree(Graph &G,int pos)/刪除一條邊隊列的抽象數(shù)據(jù)類型定義：ADT Queue數(shù)據(jù)對象：D=ai|aiElemSet,i=1,2,n,n0數(shù)據(jù)關系：Rl=|ai-1,aiD,i=2,n 約定其中ai端為隊列頭，an端為隊列尾?；静僮鱲oid InitQueue(Queue &Q)/初始化隊列 void EnQueue(Queue &Q,int e)/入隊列 void DeQueue(Queue &Q,int &e)/出隊列 bool EmptyQueue(Queue Q)/判斷是否為空void InitQueue(Queue &Q)操作結果：構造一個空隊列Qvoid EnQueue(Queue &Q,Node e)初始條件：隊列Q已存在操作結果：插入元素e為Q的新的隊尾元素void DeQueue(Queue &Q,Node &e)初始條件：Q為非空隊列操作結果：刪除Q的隊頭元素，并用e返回其值2. 算法的基本思想：a.在有向圖中選取一個入度為零的頂點并輸出b.刪除該頂點及所有以它為尾的弧c.重復a,b兩步，知道所有節(jié)點均輸出或者無度為零的節(jié)點結束。3.程序的流程程序由四個模塊組成：（1）輸入模塊：從鍵盤鍵入課程編號和課程之間的先修關系（2）建立Graph模塊：構建符合課程關系的有向圖（3）排序模塊：對有向圖圖進行拓撲排序（4）輸出模塊：輸出拓撲序列三、詳細設計物理數(shù)據(jù)類型由于課程與課程之間存在先修關系，可以采用有向圖來構建課程與課程之間的關系，用鄰接矩陣來實現(xiàn)圖，采用入度為零的廣度優(yōu)先搜索來實現(xiàn)拓撲排序，用隊列的方式來實現(xiàn)廣度優(yōu)先搜索typedef struct char SubjectMAX_VEX5; /頂點向量 int arcsMAX_VEXMAX_VEX; /鄰接矩陣 int vexnum,arcnum; /圖的當前頂點數(shù)和弧數(shù)Graph;圖的偽代碼：class Graph /圖類private:int numVertex;int numEdge;Line* line;public:Graph(int v,int e)numVertex=v;numEdge=e;line =new Linev;void pushVertex() /讀入點string ch;for(int i=0;inumVertex;i+)cout請輸入課程i+1ch;linei.head-node=ch;linei.head-position=i;void pushEdge() /讀入邊string ch1,ch2;int pos1,pos2;for(int i=0;inumEdge;i+)cout請輸入課程關系i+1ch1ch2;for(int j=0;jnode=ch1)pos1=j; /找到該字母對應的位置if(linej.head-node=ch2)pos2=linej.head-position;break;linepos1.insert(pos2,ch2);typedef struct int *base; int front; int rear; Queue;拓撲排序的偽代碼為：void topsort() /拓撲排序int i;int *d=new intnumVertex; for(i=0;inumVertex;i+)di=0; /數(shù)組初始化for(i=0;inext!=NULL)dp-next-position+; /計算每個點的入度 p=p-next;用隊列實現(xiàn)拓撲排序的偽代碼：int top=-1,m=0,j,k;for(i=0;inumVertex;i+)if(di=0)di=top; /找到第一個入度為0的點 top=i;while(top!=-1) j=top; top=dtop; coutnodenext!=NULL) k=p-next-position; dk-; /當起點被刪除，時后面的點的入度-1 if(dk=0)dk=top; top=k; p=p-next; 算法的具體步驟void CreateUDN(Graph &G)/建立一個有向圖 /輸入課程總數(shù)/輸入每門課程的編號/輸入課程的先修關系bool TopSort(Graph &G) /有向圖G采用鄰接表儲存結構 /若G無回路，則輸出G的頂點的一個top序列并返回ture，否則返回false/隊列實現(xiàn)top序列的存儲和輸出算法的時空分析Top排序：對有n個頂點和e條弧的有向圖而言，將建立求各頂點的入度的時間復雜度為O(e)；建零入度定點站的時間復雜度為O(n)，在top排序過程中，若有向圖無環(huán)，則每個頂點近義詞棧，出一次棧，入度減1的操作在while語句中總共執(zhí)行e次，所以，總的時間復雜度為O(n+e)。輸入輸出格式：輸入：請輸入課程的數(shù)量和課程先后關系的個數(shù)：6課程先后關系課程：7每門課程的編號：001 002 003 004 005 006輸入課程關系（課程 課程）001 002001 003002 003002 004003 005 004 006 005 006輸出：教學計劃為001 002 003 004 005 006實驗結果截圖：附錄（代碼）#include#includeusing namespace std;class Node/結點類public: string node; int position; /位置 Node* next; bool visit; /是否被訪問 Node()visit=false;next=NULL;position=0;node= ;class Line /線性表類public:int num;Node* head;Node* rear;Node* fence;Line()num=0;head=fence=rear=new Node(); void insert(int v,string ch) /插入元素Node* current=new Node();current-node=ch;current-position=v;fence-next=current;fence=current;num+;class Graph /圖類private:int numVertex;int numEdge;Line* line;public:Graph(int v,int e)numVertex=v;numEdge=e;line =new Linev;void pushVertex() /讀入點string ch;for(int i=0;inumVertex;i+)cout請輸入課程i+1ch;linei.head-node=ch;linei.head-position=i;void pushEdge() /讀入邊string ch1,ch2;int pos1,pos2;for(int i=0;inumEdge;i+)cout請輸入課程關系i+1ch1ch2;for(int j=0;jnode=ch1)pos1=j; /找到該字母對應的位置if(linej.head-node=ch2)pos2=linej.head-position;break;linepos1.insert(pos2,ch2); void topsort() /拓撲排序int i;int *d=new intnumVertex; for(i=0;inumVertex;i+)di=0; /數(shù)組初始化for(i=0;inext!=NULL)dp-next-position+; /計算每個點的入度 p=p-next;int top=-1,m=0,j,k;for(i=0;inumVertex;i+)if(di=0)di=top; /找到第一個入度為0的點 top=i;while(top!=-1) j=top; top=dtop; coutnodenext!=NULL) k=p-next-position; dk-; /當起點被刪除，時后面的點的入度-1 if(dk=0)dk=top; top=k; p=p-next; coutendl; if