教學(xué)計劃編制問題課程設(shè)計報告

問題描述大學(xué)的每個專業(yè)都要制定教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限值均相等，每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序。[基本要求]（1）輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(固定占3位的字母數(shù)字串)、學(xué)分和直接先修課的課程號。（2）允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個學(xué)期中。（3）若根據(jù)給定的條件問題無解，則報告適當(dāng)?shù)男畔?；否則將教學(xué)計劃輸出到用戶指定的文件中。計劃的表格格式自行設(shè)計。[測試數(shù)據(jù)]學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從C01到C12，學(xué)分順序為2,3,4,3,2,3,4,4,7,5,2,3。先修關(guān)系如下：課程編號課程名稱先決條件C1程序設(shè)計基礎(chǔ)無C2離散數(shù)學(xué)C1C3數(shù)據(jù)結(jié)構(gòu)C1，C2C4匯編語言C1C5語言的設(shè)計和分析C3，C4C6計算機原理C11C7編譯原理C5，C3C8操作系統(tǒng)C3，C6C9高等數(shù)學(xué)無C10線性代數(shù)C9C11普通物理C9C12數(shù)值分析C9，C10，C12需求分析大學(xué)的每個專業(yè)都要編制教學(xué)計劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限都相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程的開設(shè)時間的安排必須滿足先修關(guān)系。每個課程的先修關(guān)系都是確定的，可以有任意多門，也可以沒有。每一門課程恰好一個學(xué)期。試在這樣的情況下設(shè)置一個教學(xué)計劃編制程序。在大學(xué)的某個專業(yè)中選取幾個課程作為頂點,通過各門課的先修關(guān)系來構(gòu)建個圖,該圖用鄰接表來存儲,鄰接表的頭結(jié)點存儲每門課的信息.本程序的目的是為用戶編排課程,根據(jù)用戶輸入的信息來編排出每學(xué)期要學(xué)的課程.針對計算機系本科課程，根據(jù)課程之間的依賴關(guān)系（如離散數(shù)學(xué)應(yīng)在數(shù)據(jù)結(jié)構(gòu)之前開設(shè)）制定課程安排計劃，并滿足各學(xué)期課程數(shù)目大致相同,而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門課的課程號(固定占3位的字母數(shù)字串)、學(xué)分和直接先修課的課程號。3概要設(shè)計3．1抽象數(shù)據(jù)類型定義ADTGraph{數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點集.數(shù)據(jù)關(guān)系R:R={VR}VR={(v,w)|v,w∈V,(v,w)表示v和w之間存在直接先修關(guān)系}基本操作P:voidCreatGraph(ALGraph*);voidFindInDegree(ALGraph,int*);voidTopologicalSort_1(ALGraphG,intnumterm,intmaxcredit);voidTopologicalSort_2(ALGraphG,intnumterm,intmaxcredit);}ADTGraph棧的定義:ADTStack{數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0}數(shù)據(jù)關(guān)系:R1={﹤ai-1ai﹥|ai-1,ai∈D,i=2,…,n}基本操作:voidInitStack(SqStack*S);intStackEmpty(SqStackS);voidPush(SqStack*S,int);intPop(SqStack*S,int*e);}ADTStack3．2模塊劃分主程序模塊拓撲排序模塊4詳細設(shè)計4．1數(shù)據(jù)類型的定義1．頭結(jié)點，表結(jié)點，鄰接表的定義#defineMAX_VERTEX_NUM100//最大課程總數(shù)typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{charname[24];//課程名intclassid;//課程號intcredit;//課程的學(xué)分intindegree;//該結(jié)點的入度intstate;//該節(jié)點的狀態(tài)ArcNode*firstarc;//指向第一條依附該頂點的弧的指針}VNode,AdjList[MAX_VEXTEX_NUM];typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;鄰接表的基本操作：voidCreatGraph(ALGraph*);創(chuàng)建鄰接表voidFindInDegree(ALGraph,int*);求一個結(jié)點的入度voidTopologicalSort_1(ALGraphG,intnumterm,intmaxcredit);拓撲排序來編排課程voidTopologicalSort_2(ALGraphG,intnumterm,intmaxcredit);2．棧的定義：#defineSTACk_INIT_SIZE100//存儲空間的初時分配量#defineSTACKINCREMENT10//存儲空間的分配增量typedefintElemType;typedefstruct{AdjListvertices;intvexnum,arcnum;}ALGraph;基本操作：voidInitStack(SqStack*S);棧的初始化intStackEmpty(SqStackS);判斷棧是否為空voidPush(SqStack*S,int);入棧操作intPop(SqStack*S,int*e);出棧操作intSort(SqStack*S,int*t);4．2主要模塊的算法描述1.LocateVex（）：圖的鄰接表存儲的基本操作。由初始條件:圖G存在,u和G中頂點有相同特征轉(zhuǎn)而進行判斷，若G中存在頂點u,則返回該頂點在圖中位置;否則返回-1。intiintii=0i=0i<G.vexnumi<G.vexnumreturnireturni++i++ireturn-1return-1圖4.12.CreateGraph（）：構(gòu)造生成圖。采用鄰接表存儲結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的圖G(用一個函數(shù)構(gòu)造種圖)。inti,j,k;inti,j,k;i=0i=0i<(*G).vexnumi<(*G).vexnumscanf("%s",(*G).vertices[i].data);scanf("%s",(*G).vertices[i].data);++i++iprintf("請輸入%dprintf("請輸入%d個課程的學(xué)分值”)i=0i=0i<(*G).vexnumi<(*G).vexnumscanf("%s",(*G).verticestwo[i].data);scanf("%s",(*G).verticestwo[i].data);++i++imultimulti圖4.23.Display（）：輸出圖的鄰接矩陣。采用循環(huán)設(shè)置輸出圖的鄰接矩陣。inti;inti;G.kind=DGG.kind=DGprintf("%dprintf("%d個頂點：\n",G.vexnum);i=0i=0i<Gvexnumi<Gvexnum++i++imultimulti圖4.34.FindInDegree（）：求頂點的入度。intiintii=0i=0i<G.vexnumi<G.vexnumi++i++i=0i=0i<G.vexnumi<G.vexnump=G.vertices[i].firstarc;p=G.vertices[i].firstarc;ppindegree[p->adjvex]++;indegree[p->adjvex]++;i++;i++;maxcreditmaxcredit圖4.45.TopologicalSort（）：輸出G頂點的拓撲排序結(jié)果。有向圖G采用鄰接表存儲結(jié)構(gòu)。若G無回路,則輸出G的頂點的一個拓撲序列并返回OK,否則返ERROR。inti,k,j=0,count,indegree[MAX_VERTEX_NUM];inti,k,j=0,count,indegree[MAX_VERTEX_NUM];i=0i=0i<G.vexnumi<G.vexnumPush(&S,i);Push(&S,i);++i++icount=0count=0!StackEmpty(S)!StackEmpty(S)multimultimultimulti圖4.55測試分析使用VC++，打開教學(xué)計劃編制問題.cpp文件，接著編譯，無錯誤，然后重建也沒有錯誤，最后執(zhí)行該文件。要求輸入學(xué)期總數(shù)、一個學(xué)期的學(xué)分上限、需要編排課程總數(shù)、課程名、課程號、該課程的學(xué)分，按照出現(xiàn)的每一步來輸入該課程設(shè)計所提供的相關(guān)數(shù)據(jù)。然后還要輸入課程先修課程總數(shù)，可以算出有16種關(guān)系，分別輸出。接著程序會根據(jù)這些數(shù)據(jù)，自動生成建立好的鄰接表，用戶可以根據(jù)系統(tǒng)顯示的選擇編排策略進行選擇，有兩種編排策略，最后結(jié)果體現(xiàn)在實驗的正確測試結(jié)果里。顯示如下圖：6課程設(shè)計總結(jié)6.1問題和解決方法及經(jīng)驗教訓(xùn)、心得體會雖然在大一我們已經(jīng)學(xué)習(xí)了C語言，但是，直到本期我們才開設(shè)了數(shù)據(jù)結(jié)構(gòu)這一門課程。這門課程讓我從C語言那基礎(chǔ)再深入的了解了軟件開發(fā)的復(fù)雜性。對以往模糊的經(jīng)驗，起了總結(jié)提升的作用。在學(xué)習(xí)了這門課程后，我們進行了2個星期的課程設(shè)計，來實踐我們所學(xué)這門課的內(nèi)容。這次實驗，我進行了大量的資料查閱，包括向老師請求幫助解釋題目要求，對所學(xué)知識進行復(fù)習(xí)。通過這些努力，我對數(shù)據(jù)結(jié)構(gòu)這門課程有了新的認識，對編程的步驟，有了具體的體會。通過和同學(xué)的廣泛交流，我體會到了合作的必要性及合作的優(yōu)勢。更重要的是，這個課題完全脫離于只限于書本上的問題，多用在實際生活當(dāng)中，讓我對計算機行業(yè)，充滿了信心和自豪。以往我們學(xué)的計算機知識一般停留在理論上，這讓我們不太理解計算機的應(yīng)用和前景，而較少注重我們對算法的實踐鍛煉。而這一次的實習(xí)既需要我們?nèi)ヂ?lián)系理論，又需要我們?nèi)嵺`方法，很多東西看上去都學(xué)過，但是和實際聯(lián)系才知道變通的艱難。書上得來的并不是一切，大多還是需要在其它方面去吸收的，這是我這次實習(xí)的最大收獲。這次的實驗讓我們知道該如何跨過實際和理論之間的鴻溝。由于程序十分的復(fù)雜，遇到了很多常見的語法錯誤，及邏輯錯誤。這需要我們不參考獻中的內(nèi)容為五號宋體。斷的調(diào)試分析。符號的格式之類，指針的用法，判斷輸入輸出的條件都是十分容易出錯的地方。在逐條排除，向同學(xué)老師請教后，程序終于得以完成。這讓我明白了，解決問題，要細心認真，集思廣益，這樣才能把問題解決。參考獻中的內(nèi)容為五號宋體。6.2致謝本次的課程設(shè)計，并不是我自己一個人設(shè)計出來的。首先，我要感謝我的數(shù)據(jù)結(jié)構(gòu)老師——黃老師，本次課程設(shè)計黃老師幫助了我們不少，所以在這里我致以最誠摯的謝意，老師，謝謝您！另外，我還要感謝在我這次課程設(shè)計中幫助過我的同學(xué)，謝謝你們一直以來對我的幫助，沒有你們也沒有我此次的成果，謝謝。參考文獻[1]黃同成，黃俊民，董建寅．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國電力出版社，2008[2]董建寅，黃俊民，黃同成．?dāng)?shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)與題解[M]．北京：中國電力出版社，2008[3]嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2002[4]劉振鵬，張曉莉，郝杰．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國鐵道出版社，2003附錄（源程序清單）#include<string.h>#include<malloc.h>#include<stdio.h>#include<stdlib.h>#include<math.h>#include<process.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;typedefintBoolean;#defineMAX_NAME10#defineMAXCLASS100intZ=0;intX=0;intxqzs,q=1,xfsx;typedefintInfoType;typedefcharVertexType[MAX_NAME];#defineMAX_VERTEX_NUM100typedefenum{DG}GraphKind;typedefstructArcNode{intadjvex;structArcNode*nextarc;InfoType*info;}ArcNode;typedefstruct{VertexTypedata;ArcNode*firstarc;}VNode,AdjList[MAX_VERTEX_NUM];typedefstruct{AdjListvertices,verticestwo;intvexnum,arcnum;intkind;}ALGraph;intLocateVex(ALGraphG,VertexTypeu){inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}StatusCreateGraph(ALGraph*G){inti,j,k;VertexTypeva,vb;ArcNode*p;printf("請輸入教學(xué)計劃的課程數(shù):");scanf("%d",&(*G).vexnum);printf("請輸入拓撲排序所形成的課程先修關(guān)系的邊數(shù):");scanf("%d",&(*G).arcnum);printf("輸入%d個課程的代表值(<%d個字符):\n",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i){scanf("%s",(*G).vertices[i].data);(*G).vertices[i].firstarc=NULL;}printf("輸入%d個課程的學(xué)分值(<%d個符):\n",(*G).vexnum,MAX_NAME);for(i=0;i<(*G).vexnum;++i){scanf("%s",(*G).verticestwo[i].data);}printf("請順序輸入每條弧(邊)的弧尾和弧頭(以空格作為間隔):\n");for(k=0;k<(*G).arcnum;++k){scanf("%s%s",va,vb);i=LocateVex(*G,va);j=LocateVex(*G,vb);p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->info=NULL;p->nextarc=(*G).vertices[i].firstarc;(*G).vertices[i].firstarc=p;}returnOK;}voidDisplay(ALGraphG){inti;ArcNode*p;switch(G.kind){caseDG:printf("有向圖\n");}printf("%d個頂點：\n",G.vexnum);for(i=0;i<G.vexnum;++i)printf("%s",G.vertices[i].data);printf("\n%d條弧(邊):\n",G.arcnum);for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){printf("%s→%s",G.vertices[i].data,G.vertices[p->adjvex].data);p=p->nextarc;}printf("\n");}}voidFindInDegree(ALGraphG,intindegree[]){inti;ArcNode*p;for(i=0;i<G.vexnum;i++)indegree[i]=0;for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p){indegree[p->adjvex]++;p=p->nextarc;}}}typedefintSElemType;#defineSTACK_INIT_SIZE10#defineSTACKINCREMENT2typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;}SqStack;StatusInitStack(SqStack*S){(*S).base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);(*S).top=(*S).base;(*S).stacksize=STACK_INIT_SIZE;returnOK;}StatusStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}StatusPop(SqStack*S,SElemType*e){if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}StatusPush(SqStack*S,SElemTypee){if((*S).top-(*S).base>=(*S).stacksize){(*S).base=(SElemType*)realloc((*S).base,((*S).stacksize+STACKINCREMENT)*sizeof(SElemType));if(!(*S).base)exit(OVERFLOW);(*S).top=(*S).base+(*S).stacksize;(*S).stacksize+=STACKINCREMENT;}*((*S).top)++=e;returnOK;}typedefintpathone[MAXCLASS];typedefintpathtwo[MAXCLASS];StatusTopologicalSort(ALGraphG){inti,k,q=1,j=0,count,indegree[MAX_VERTEX_