教學(xué)計(jì)劃編制問(wèn)題.doc

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