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

目錄一、課題的主要功..................................................................31.1程序的功.................................................................31.2.輸入輸出的要.............................................................31.3運行環(huán)...................................................................31.4開發(fā)工...................................................................3二、概要設(shè)........................................................................42.1程序的模塊組..............................................................42.2模塊的層次結(jié)構(gòu)及調(diào)用關(guān)....................................................42.3模塊的主要功..............................................................42.4數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)........................................................5三．主要功能的實..................................................................53.1用C語言定義相關(guān)的數(shù)據(jù)類型..............................................53.2主要函數(shù)的流程............................................................53.3畫出各函數(shù)的調(diào)用關(guān)系.....................................................12四、程序調(diào).......................................................................134.1測試數(shù)據(jù)................................................................134.2使用說..................................................................14五．心得體.......................................................................17六、附...........................................................................156.1參考書..................................................................156.2源程序清單（帶注釋）.......................................................16

一、課題的主要功1.1程序的功每學(xué)期的時間長度和學(xué)分上限均相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學(xué)期。試在這樣的前提下設(shè)計一個教學(xué)計劃編制程序制定好學(xué)習(xí)計劃。在輸入相關(guān)數(shù)據(jù)后，程序會安排好每學(xué)期的課程1.2.輸入輸出的要求輸入?yún)?shù)包括學(xué)期總數(shù)一學(xué)期的學(xué)分上限每門課的課程（固定占3位的字母數(shù)字串學(xué)分和直接先修課的課程號輸出要求輸出各門課程所對應(yīng)的學(xué)分，以及每學(xué)期各門課程的安排1.3運行環(huán)境1.WINDOWS7系2.Vc++6.0編譯環(huán)境1.4開發(fā)工具C 第3頁

二、概要設(shè)2.1所負責(zé)的程序的模塊LocateVe（：圖的鄰接表存儲的基本操CreateGraph（：構(gòu)造生成Display（：輸出圖的鄰接矩FindInDegree：求頂點的入2.2模塊的層次結(jié)構(gòu)及調(diào)用關(guān)系函TopologicalSor2.3模塊的主要功能y出圖的鄰接陣CreateGrap生成圖見“詳細設(shè)計”－“主要函數(shù)流程圖 第4頁

2.4數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)庫結(jié)構(gòu)儲存的數(shù)據(jù)為結(jié)構(gòu)體類型數(shù)組，以及結(jié)構(gòu)體單鏈表結(jié)點類型1typedefstructArcNode弧所指定點位置 指向下一條弧的指針 網(wǎng)的權(quán)值指針int struct InfoType2typedefstruct頂點信息 第一個表結(jié)點的地址VertexType ArcNode三．主要功能的實3.1采用C語言定義相關(guān)的數(shù)據(jù)類型。其中包括字符常量，整型，字符型，字符串型，typedef定義的類型，結(jié)構(gòu)體型，單鏈表節(jié)點類型，結(jié)構(gòu)體數(shù)組3.2主要函數(shù)的流程圖1.LocateVex（：圖的鄰接表存儲的基本操作。由初始條件:圖G存在u和G轉(zhuǎn)而進行判斷，若G中存在頂點u,則返回該頂點在圖中位置否則返回1 第5頁

i=0.vexnum++i2.CreateGrap（構(gòu)造生成圖采用鄰接表存儲結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的圖種圖 第6頁

i=0

++i

++i請輸%d個課程的學(xué)分值”)i=0++i3.Displa（：輸出圖的鄰接矩陣。采用循環(huán)設(shè)置輸出圖的鄰接矩陣 第7頁

.kind=DG.kind=DG.kind=DG個頂點： i=0i<Gvexnum++i4.FindInDegre（：求頂點的入度 第8頁

i=0.vexnumi++i=0.vexnump=p所負責(zé)的部分程序/*圖的鄰接表存儲的基本操*/intLocateVex(ALGraphG,VertexTypeu){/*初始條件圖在u和G中頂點有相同特征*/ 第9頁

操作結(jié):G中存在頂點u,則返回該頂點在圖中位置否則返回-1*/inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}StatusCreateGraph(ALGraph*G){/*采用鄰接表存儲結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的G(用一個函數(shù)構(gòu)造種圖)*/inti,j,k;VertexTypeva,vb;ArcNode*p;請輸入d個課程的代表請輸入d個課程的代表*/for(i=0;i<(*G).vexnum;++i)/*構(gòu)造頂點向*/*/(*G).vertices[i].firstarc=NULL;}for(i=0;i<(*G).vexnum;++i)/*構(gòu)造頂點向for(i=0;i<(*G).vexnum;++i)/*構(gòu)造頂點向*/*/}請順序輸入每條弧邊)的弧尾和弧頭請順序輸入每條弧邊)的弧尾和弧頭*/for(k=0;k<(*G).arcnum;++k)/*構(gòu)造表結(jié)點鏈表*/*/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){/*輸出圖的鄰接矩G*/inti;ArcNode*p;switch(G.kind)switch(G.kind)switch(G.kind)}for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)for(i=0;i<G.vexnum;++i)弧(for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p)while(p)while(p)p=p->nextarc;}}

voidFindInDegree(ALGraphG,intindegree[]){/*求頂點的入度，算法調(diào)*/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;}}}3.3畫出各函數(shù)的調(diào)用關(guān)系圖Main函數(shù)（ （

四、程序調(diào)4.1測試數(shù)據(jù)：準備典型的測試數(shù)據(jù)和測試方案數(shù)據(jù)如下：學(xué)期總數(shù)：學(xué)分上限：10該專業(yè)共開設(shè)課數(shù)12課程號：從C01到C12學(xué)分順序2，，，3，3，，，75，，先修順序有向圖表示)10136578

明輸入學(xué)期總數(shù)，學(xué)分上限，課程數(shù)，先修關(guān)系邊

輸入課程代表符號輸入相對學(xué)分值

回車，將顯示頂點的個數(shù)和弧的條輸入完成后執(zhí)行可得到每個學(xué)期的課程計劃結(jié)

．會雖這門課程讓我從C總結(jié)提升的作用。在學(xué)習(xí)了這門課程后，我們進行課的內(nèi)容。由于程序十分的復(fù)雜，遇到了很多常見的語法錯誤，及邏輯錯誤。這需要我們不斷的調(diào)試分析。符號的格式之類，指針的用法，判斷輸入輸出的條件都是十分容易出錯的地方。在逐條排除，向同學(xué)老師請教后，程序終于得以完成。這讓我明白了，解決問題，要細心認真，集思廣益，這樣才能把問題解決六、附錄6.1參考書目1黃同成，黃俊民，董建寅．?dāng)?shù)據(jù)結(jié)構(gòu)[M]．北京：中國電力出版社，20082董建寅，黃俊民，黃同成．?dāng)?shù)據(jù)結(jié)構(gòu)實驗指導(dǎo)與題解[M]．北京：中國電力出版社，20083嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，20024唐策善，李龍澍，黃劉生．?dāng)?shù)據(jù)結(jié)構(gòu)—用C語言描述[M]．北京：高等教育出版社，20016.2源程序清單（帶注釋）#include<string.h>#include<ctype.h>#include<malloc.h>//malloc()#include<limits.h>//INT_MAX#include<stdio.h>//EOF(=^或F6),NULL#include<stdlib.h>//atoi()52#include<io.h>//eof()#include<math.h>//floor(),ceil(),abs()#include<process.h>//exit()

#include<iostream.h>//cout,cin//函數(shù)結(jié)果狀態(tài)代#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineINFEASIBLE-1typedefintStatus;//Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OKtypedefintBoolean;//Boolea是布爾類型,其值是TRUEFALSE#defineMAX_NAME10/*頂點字符串的最大長度*/#defineMAXCLASS100intZ=0;intX=0;intxqzs,q=1,xfsx;typedefintInfoType;typedefcharVertexType[MAX_NAME];/*字符串類型*//*圖的鄰接表存儲表*/#defineMAX_VERTEX_NUM100typedefenum{DG}GraphKind;/*有向圖,有向無向圖,無向網(wǎng)}*/typedefstructArcNode{intadjvex;/*該弧所指向的頂點的位*/structArcNode*nextarc;/*指向下一條弧的指針*/InfoType*info;/*網(wǎng)的權(quán)值指針*/}ArcNode;/*表結(jié)點*/typedefstruct{VertexTypedata;/*頂點信息*/ArcNode*firstarc;/*第一個表結(jié)點的地址指向第一條依附該頂點的弧的指針*/

}VNode,AdjList[MAX_VERTEX_NUM];/*頭結(jié)點*/typedefstruct{AdjListvertices,verticestwo;intvexnum,arcnum;/*圖的當(dāng)前頂點數(shù)和弧*/intkind;/*圖的種類標*/}ALGraph;/*圖的鄰接表存儲的基本操*/intLocateVex(ALGraphG,VertexTypeu){/*初始條件圖在u和G中頂點有相同特征*//*操作結(jié):G中存在頂點u,則返回該頂點在圖中位置否則返回-1*/inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}StatusCreateGraph(ALGraph*G){/*采用鄰接表存儲結(jié)構(gòu),構(gòu)造沒有相關(guān)信息的G(用一個函數(shù)構(gòu)造種圖)*/inti,j,k;VertexTypeva,vb;ArcNode*p;請輸入d個課程的代表請輸入d個課程的代表for(i=0;i<(*G).vexnum;++i)/*構(gòu)造頂點向*/

(*G).vertices[i].firstarc=NULL;}for(i=0;i<(*G).vexnum;++i)/*構(gòu)造頂點向for(i=0;i<(*G).vexnum;++i)/*構(gòu)造頂點向*/*/}請順序輸入每條弧請順序輸入每條弧邊)的弧尾和弧頭*/for(k=0;k<(*G).arcnum;++k)/*構(gòu)造表結(jié)點鏈表*/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){/*輸出圖的鄰接矩G*/inti;ArcNode*p;switch(G.kind)switch(G.kind)switch(G.kind)}for(i=0;i<G.vexnum;++i)

弧(for(i=0;i<G.vexnum;i++){p=G.vertices[i].firstarc;while(p)while(p)while(p)p=p->nextarc;}}}voidFindInDegree(ALGraphG,intindegree[]){/*求頂點的入度，算法調(diào)*/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/*存儲空間初始分配量*/

#defineSTACKINCREMENT2/*存儲空間分配增*/typedefstructSqStack{SElemType*base;/*在棧構(gòu)造之前和銷毀之后，base的值為NULL*/SElemType*top;/*棧頂指針*/intstacksize;/*當(dāng)前已分配的存儲空間，以元素為單*/}SqStack;/*順序棧*//*順序棧的基本操作*/StatusInitStack(SqStack*S){/*構(gòu)造一個空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;}voidClearStack(SqStack*S)//清空棧的操{ S->top=S->base;}StatusStackEmpty(SqStackS){/*若棧S為空棧，則返回TRUE，否則返回FALSE*/if(S.top==S.base)returnTRUE;elsereturnFALSE;

StatusPop(SqStack*S,SElemType*e){/*若棧不空，則刪的棧頂元素，e返回其值，并返回OK；否則返回ERROR*/if((*S).top==(*S).base)returnERROR;*e=*--(*S).top;returnOK;}StatusPush(SqStack*S,SElemTypee){/*插入元e為新的棧頂元*/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){/*有向圖采用鄰接表存儲結(jié)構(gòu)。若無回路,則輸出的頂點的一個拓撲序列并返回OK,*//*否則返ERROR。inti,k,j=0,count,indegree[MAX_VERTEX_NUM];boolhas=false;SqStackS;pathonea;pathtwob;ArcNode*p;FindInDegree(G,indegree);/*對各頂點求入indegree[0..vernum-1]*/InitStack(&S);/*初始化*/for(i=0;i<G.vexnum;++i)/*建零入度頂點棧S*/if(!indegree[i]) {Push(&S,i); //cout<<*G.vertices[i].data<<endl; } /*入度為者進棧*/count=0;/*對輸出頂點計*/while(!StackEmpty(S)){/*棧不*/Pop(&S,&i);a[i]=*G.vertices[i].data;b[i]=*G.verticestwo[i].data;b[i]=*G.verticestwo[i].data;b[i]=*G.verticestwo[i].data;課程s分出號頂點并計數(shù)*/++count;for(p=G.vertices[i].firstarc;p;p=p->nextarc){/*對號頂點的每個鄰接點的入度減*/k=p->adjvex;

if(!(--indegree[k]))/*若入度減,棧*/ {Push(&S,k); //cout<<*G.vertices[i].data<<endl; }}}if(count<G.vexnum)if(count<G.vexnum)returnERROR;}elseelseelse為一個拓撲序列。 has=tru