教學(xué)計(jì)劃編制系統(tǒng)

6*******************實(shí)踐教學(xué)*******************蘭州理工大學(xué)計(jì)算機(jī)與通信學(xué)院2011年春季學(xué)期數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)題目：教學(xué)方案編制問題專業(yè)班級(jí)：軟件一班姓名：學(xué)號(hào)：指導(dǎo)教師：成績：_____________________前言本學(xué)期開設(shè)了算法與數(shù)據(jù)結(jié)構(gòu)，通過學(xué)習(xí)算法與數(shù)據(jù)結(jié)構(gòu)，大家對(duì)編程有了更多的了解，為了讓大家將自己所學(xué)的知識(shí)應(yīng)用到實(shí)際當(dāng)中，學(xué)校開設(shè)了算法與數(shù)據(jù)結(jié)構(gòu)課設(shè)，通過這次課設(shè)大家可以更好地將c語言應(yīng)用到實(shí)際當(dāng)中，而且可以更好的掌握算法與數(shù)據(jù)結(jié)構(gòu)，將數(shù)據(jù)結(jié)構(gòu)和c語言有效的結(jié)合起來，使大家的編程能力得到更大的提高。目錄摘要------------------------------------------------------------------------------------1關(guān)鍵字----------------------------------------------------------------------------1正文------------------------------------------------------------------------------------21.采用類c語言定義相關(guān)的數(shù)據(jù)類型-----------------------------------------22．各模塊的偽碼算法-------------------------------------------------------------33函數(shù)調(diào)用關(guān)系圖-----------------------------------------------------------------64試調(diào)分析--------------------------------------------------------------------------75測試結(jié)果--------------------------------------------------------------------------8總結(jié)--------------------------------------------------------------------------------9參考文獻(xiàn)------------------------------------------------------------------------------9致謝---------------------------------------------------------------------------------10附件Ⅰ1.源程序[帶注釋]〔結(jié)構(gòu)體文件〕---------------------------------------------------------102.運(yùn)行結(jié)果----------------------------------------------------------------------------28摘要大學(xué)的每個(gè)專業(yè)都要制定教學(xué)方案。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期。此程序就可以滿足這些要求，輸出正確的結(jié)果，幫助我們實(shí)現(xiàn)教學(xué)方案編制關(guān)鍵字：數(shù)據(jù)結(jié)構(gòu)，方案，編制正文1采用類c語言定義相關(guān)的數(shù)據(jù)類型typedefcharVertexType[MAX_NAME];intTotalTerms;//學(xué)期總數(shù)intMaxScores;//學(xué)分上限typedefstructArcNode{intadjvex;//該弧所指向的頂點(diǎn)的位置弧的節(jié)點(diǎn)結(jié)構(gòu)structArcNode*nextarc;//指向下一條弧的指針}ArcNode;/*查找圖中某個(gè)頂點(diǎn)位置*/intLocateVex(ALGraphG,VertexTypeu)/*輸出圖G的信息*/voidDisplay(ALGraphG)*求頂點(diǎn)的入度*/voidFindInDegree(ALGraphG,intindegree[])structName{charc[20];}name;voidpuanduan(VertexTypestr,structNamename[],intn)/*棧定義*/typedefintSElemType;//棧類型#defineStack_NUM20//存儲(chǔ)空間初始分配量#defineStack_MoreNUM5//存儲(chǔ)空間分配增量typedefstructSqStack*拓?fù)渑判?/intTopoSort(ALGraphG,AdjListTemp,structNamename[])2．各模塊的偽碼算法〔1〕-圖的鄰接表存儲(chǔ)表示-intadjvex;該弧所指向的頂點(diǎn)的位置弧的節(jié)點(diǎn)結(jié)構(gòu)structArcNode*nextarc;指向下一條弧的指針}ArcNode;鏈表結(jié)點(diǎn)typedefstruct鏈接表{VertexTypedata;頂點(diǎn)信息intgrades;存儲(chǔ)學(xué)分信息ArcNode*firstarc;指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList[MAX_VERTEX_NUM];頭結(jié)點(diǎn)typedefstruct{AdjListvertices;vertices存儲(chǔ)課程名intvexnum,arcnum;圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}ALGraph;voidOUTPUT()輸出菜單〔2〕采用鄰接表存儲(chǔ)結(jié)構(gòu)輸出提示，按提示操作程序printf("請(qǐng)輸入教學(xué)方案的課程數(shù):");printf("請(qǐng)輸入各個(gè)課程的先修課程的總和(弧總數(shù)):");printf("請(qǐng)輸入%d個(gè)課程的課程號(hào)(最多%d個(gè)字符,數(shù)字+字母):",G.vexnum,MAX_NAME);printf("請(qǐng)輸入以下課程的先修課程(無先修課程輸入0結(jié)束后也輸入0)\n");〔3〕輸出圖G的信息voidDisplay(ALGraphG)printf("有向圖\n");printf("%d個(gè)頂點(diǎn)",G.vexnum);拓?fù)渑判駻rcNode*p;//對(duì)輸出頂點(diǎn)計(jì)數(shù)while(!StackEmpty(S)){Pop(S,i);printf("%s(%d分),",G.vertices[i].data,G.vertices[i].grades);Temp[j++]=G.vertices[i];//將當(dāng)前的拓?fù)湫蛄斜４嫫饋?+count;//輸出i號(hào)頂點(diǎn)并計(jì)數(shù)for(p=G.vertices[i].firstarc;p;p=p->nextarc)//對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1{k=p->adjvex;if(!(--indegree[k]))//假設(shè)入度減為0,那么入棧Push(S,k);〔4〕voidmain()初始化strucNamename[N]={{"C1"},{"C2"},{"C3"},{"C4"},{"C5"},{"C6"},{"C7"},{"C8"},{"C9"},{"C10"},{"C11"},{"C12"}};3函數(shù)調(diào)用關(guān)系圖Display(G)Display(G)CreateGraph(G)輸出圖G的信息TopoSort(G,Temp,name)name);TopoSort(G,Temp,name);TopoSort(G,Temp,name);TopoSort(G,Temp,name);TopoSort(G,Temp,name);TopoSort(G,Temp,name)TopoSort(G,Temp,name)采用鄰接表存儲(chǔ)結(jié)構(gòu)拓?fù)渑判騰oidmain()-4試調(diào)分析-根據(jù)問題描述及要求，可知設(shè)計(jì)中需要定義先修關(guān)系的AOV網(wǎng)圖中的頂點(diǎn)及弧邊的結(jié)構(gòu)體，在運(yùn)行結(jié)果中將圖的信息顯示出來，利用先修關(guān)系將課程排序，最后解決問題——輸出每學(xué)期的課程。end采用第二種策略：使課程盡可能地集中在前幾個(gè)學(xué)期中根據(jù)教學(xué)方案中的課程及其關(guān)系和學(xué)分定義圖的頂點(diǎn)和邊的結(jié)構(gòu)體創(chuàng)立圖CreateGraph〔〕：結(jié)合先修關(guān)系的AOV網(wǎng)，采用鄰接鏈表存儲(chǔ)菜單OUTPUT()：顯示代號(hào)所對(duì)應(yīng)課程及課程的先修課程前插法main拓?fù)渑判騎opoSort(G)：將課程排序后并決定出每學(xué)期所學(xué)課程

輸出圖G的信息Display(G)：將圖的頂點(diǎn)和弧邊輸出5測試結(jié)果測試數(shù)據(jù)：輸入的內(nèi)容如下:

課程編號(hào)

課程名稱

學(xué)分

先決條件

01

程序設(shè)計(jì)根底

2

無

02

離散數(shù)學(xué)

3

01

03

數(shù)據(jù)結(jié)構(gòu)

4

01，02

04

匯編語言

3

01

05

語言的設(shè)計(jì)和分析

2

03，04

06

計(jì)算機(jī)原理

3

11

07

編譯原理

4

05，03

08

操作系統(tǒng)

4

03，06

09

高等數(shù)學(xué)

7

無

10

線性代數(shù)

5

09

11

普通物理

2

09

12

數(shù)值分析

3

09，10，01

學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號(hào)從C1到C12，學(xué)分順序?yàn)?，3，4，3，2，3，4，4，7，5，2，3。兩種編譯都輸出結(jié)果：第一學(xué)期學(xué)的課程有:高等數(shù)學(xué)

第二學(xué)期學(xué)的課程有:普通物理線性代數(shù)計(jì)算機(jī)原理

第三學(xué)期學(xué)的課程有:課程設(shè)計(jì)根底數(shù)據(jù)結(jié)構(gòu)離散數(shù)學(xué)

第四學(xué)期學(xué)的課程有:操作系統(tǒng)匯編語言語言的設(shè)計(jì)與分析

第五學(xué)期學(xué)的課程有:編譯原理數(shù)值分析第六學(xué)期學(xué)的課程有：總結(jié)我們?cè)趯?shí)驗(yàn)過程中遇到的最大難題是兩個(gè)課程排序算法的編寫。剛開始的時(shí)候沒有任何的思路，網(wǎng)上也只有拓?fù)渑判虻乃惴?，?duì)于課程設(shè)計(jì)要求的排序算法沒有任何頭緒。經(jīng)過請(qǐng)教老師和同學(xué)以及翻閱了一些相關(guān)書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法經(jīng)過此次課程設(shè)計(jì)，自己解決編程中從在的問題，我們認(rèn)識(shí)到了理論與實(shí)踐結(jié)合的重要性，僅僅只是從課本上學(xué)到算法原理是遠(yuǎn)遠(yuǎn)不夠的。在實(shí)踐中，我們總會(huì)出現(xiàn)許多錯(cuò)誤。這就要求我們以一個(gè)腳踏實(shí)地的態(tài)度來處理問題。我們深刻地認(rèn)識(shí)到自己寫程序的缺乏，使我們學(xué)到了好多有用的知識(shí)，讓我們明白了算法與編程的密切關(guān)系，使我們受益匪淺。參考文獻(xiàn)1《數(shù)據(jù)結(jié)構(gòu)》〔c語言描述〕冶金工業(yè)出版社2《C程序設(shè)計(jì)》譚浩強(qiáng)3王連相，馮鋒編著.C/C++程序設(shè)計(jì).北京：中國科學(xué)技術(shù)出版社，20054嚴(yán)蔚敏，吳偉民編著.數(shù)據(jù)結(jié)構(gòu)〔C語言版〕.北京：清華大學(xué)出版社，19975嚴(yán)蔚敏，吳偉民編著.數(shù)據(jù)結(jié)構(gòu)題集〔C語言版〕.北京：清華大學(xué)出版社，致謝首先感謝我的指導(dǎo)老師張永老師，他在我的課程設(shè)計(jì)過程中提出了指導(dǎo)性的方案和架構(gòu)，并指引我閱讀相關(guān)的資料和書籍，使我在不熟悉的領(lǐng)域中仍能迅速掌握新的技術(shù)。并且在課設(shè)期間屢次親身檢查給出我程序中的缺乏，也為我拓寬思路，不至于我的程序過于單一，非常感謝張永老師我的同學(xué)在設(shè)計(jì)完成后對(duì)程序的測試，沒有他們，也許就難以發(fā)現(xiàn)一些潛在的錯(cuò)誤，在此一并表示感謝。附件11.源程序代碼〔/*************************************************************************************結(jié)構(gòu)體文件|結(jié)構(gòu)體名|作用|備注__________________________________________________________________________________||用于在處理數(shù)據(jù)時(shí)保存各個(gè)信息|||1.該門課程是否已經(jīng)編排|動(dòng)態(tài)數(shù)組|CourseHead|2.給課程的直接先修課的個(gè)數(shù)|與CourseLink一起構(gòu)成鏈表||3.以該門課程為先修的后修課程結(jié)點(diǎn)|存儲(chǔ)結(jié)構(gòu)||4.課程的名字5.課程號(hào)6.學(xué)分|_________________________________________________________________________________|CourseLink| CourseHead的鏈|動(dòng)態(tài)結(jié)點(diǎn)||1.課程在CourseHead的下標(biāo)|與CourseHead一起構(gòu)成鏈表||2.下一個(gè)CourseLink的地址|存儲(chǔ)結(jié)構(gòu)_________________________________________________________________________________||保存符合要求的課程安排情況|動(dòng)態(tài)結(jié)點(diǎn)，頭結(jié)點(diǎn)不保存|Topo|1.課程安排的平均性|課程安排情況，但是保存||2.ArryInTopo型數(shù)組存儲(chǔ)安排情況|課程安排平均的總數(shù)目||3.下一中課程安排的結(jié)點(diǎn)地址|__________________________________________________________________________________||保存某一門課的開課時(shí)間|動(dòng)態(tài)數(shù)組，|ArryInTopo|1.該門課在CourseHead的下標(biāo)|它在Topo的內(nèi)部||2.該課程的開課時(shí)間|___________________________________________________________________________________||保存可以選擇的課程|動(dòng)態(tài)結(jié)點(diǎn)|Zero|1.課程在CourseHead的下標(biāo)|在編程是因?yàn)檫f歸的需要||2.下一個(gè)課程結(jié)點(diǎn)的地址|即時(shí)地加上去的結(jié)構(gòu)體___________________________________________________________________________________**************************************************************************************//*該結(jié)構(gòu)體用于保存課程的學(xué)分和該課程在一維數(shù)組的下標(biāo)因?yàn)橛玫芥湵泶鎯?chǔ)結(jié)構(gòu)(表頭是先修課程，鏈?zhǔn)桥c以該課程的為先修的課程)所以有假設(shè)下*/〕#include<malloc.h>#include<stdio.h>#include<stdlib.h>#include<string.h>#include<math.h>#include<windows.h>#include<conio.h>#include<fstream.h>structCourseLink//該結(jié)構(gòu)體用于具體運(yùn)算{//關(guān)聯(lián)了課程的關(guān)系intIndex;//該課程在一維數(shù)組的下標(biāo)，綁定他與課程的關(guān)系CourseLink*next;//下一門與他同一尾節(jié)點(diǎn)的課程};structCourseHead//表頭結(jié)點(diǎn)的結(jié)構(gòu)體{ intflag;//標(biāo)記該門課程是否已經(jīng)編排intpriornum;//給課程的直接先修課的個(gè)數(shù)CourseLink*first;//以該門課程為先修的后修課程charName[30];//課程的名字charOfcourse[4];//課程號(hào)floatScore;//學(xué)分};structArryInTopo{ intIndex;//保存課程的序號(hào) intTime;//保存課程的開課時(shí)間};structTopo{ intlevel;//標(biāo)記是否平均分配,也就是課程安排效果標(biāo)記 ArryInTopo*toporesualt;//一個(gè)一維數(shù)組保存拓?fù)渑判?-保存課程的序號(hào) Topo*next;//拓?fù)渑判虻南乱环N情況};structZero//保存可以選擇的課程{ intzero;//課程在原始數(shù)據(jù)里的下標(biāo) Zero*next;//下一個(gè)課程結(jié)點(diǎn)的地址};//**************函數(shù)介紹********************************************voidInitData();//......................1調(diào)用一下兩個(gè)函數(shù)完成數(shù)據(jù)初始化voidInitData(intnum);//.................2由課程數(shù)目num來完成數(shù)據(jù)的細(xì)節(jié)floatInitData(char*b);//..............2方便判斷輸入數(shù)據(jù)的準(zhǔn)確性而已voidStartTopoSort();//..................1初始化要用到的各個(gè)數(shù)據(jù)再調(diào)用下面這個(gè)函數(shù)voidTopoSort(inttopotempsum,inttime);//.2遞歸函數(shù)，完成拓?fù)渑判?，用到以下四個(gè)函數(shù)voidCheck(intindex);//...................3中選擇course[index]時(shí)，相應(yīng)的鏈表的 //3頭結(jié)點(diǎn)的priornum項(xiàng)要減一voidCheckBack(intindex);//...............3當(dāng)退選course[index]時(shí)，相應(yīng)的鏈表的 //3頭結(jié)點(diǎn)的priornum項(xiàng)要加一 intZERO();//............................3統(tǒng)計(jì)該層遞歸可以選擇的課程 //并且完成可選課程的記錄voidIfsuccessed();//......................3當(dāng)課程安排成功時(shí)將課程安排記錄保存 //并對(duì)課程安排做評(píng)價(jià)voidPrint();//............................1根據(jù)客戶要求輸出相應(yīng)的課程安排voidprintf0();//..........................1界面voidprintf1(int);//......................1負(fù)責(zé)輸出課程信息,并且還調(diào)用下面voidprintf2();//...........................2輸出課程的聯(lián)系voidprintf1(FILE*);//......................1負(fù)責(zé)將課程信息寫入文件,并且還調(diào)用下面voidprintf2(FILE*);//...........................2將課程的聯(lián)系寫入文件//**************函數(shù)介紹********************************************intTime=0;//全局變量學(xué)期總數(shù)floatMaxSource=0.0;//全局變量一學(xué)期的學(xué)分上限intSourceNum=0;//全局變量課程總數(shù)CourseHead*coursehead;//全局變量鏈表的有節(jié)點(diǎn)數(shù)組Topo*topo;//全局變量保存課程的安排情況,//頭結(jié)點(diǎn)保存課程安排平均的總數(shù)目ArryInTopo*topotemp;//全局變量數(shù)組臨時(shí)保存某一種拓?fù)渑判蚯闆rZero*ZeroTemp;//全局變量鏈?zhǔn)奖４嫒攵葹榱愕恼n程的index//隨著遞歸的進(jìn)行他的值也在變化int*ClassInTime;//全局變量臨時(shí)保存每一學(xué)期課程的數(shù)目voidmain(){chari; printf0(); do { printf("按任意非<Esc>鍵開始，按<Esc>退出!\n\n");i=getch(); fflush(stdin);//刷新輸入流 if(i!=27) { system("cls");//刷新屏幕printf0(); InitData();//輸入數(shù)據(jù) StartTopoSort();//處理數(shù)據(jù)Print();//按要求輸出結(jié)果 } if(i==27) return; }while(i!=27);}//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@數(shù)據(jù)初始化全部完成voidInitData(){ Time=int(InitData("學(xué)期總數(shù)"));//輸入學(xué)期總數(shù) MaxSource=InitData("一學(xué)期的學(xué)分上限");//輸入一學(xué)期的學(xué)分上限 SourceNum=int(InitData("課程總數(shù)"));//輸入課程總數(shù)InitData(SourceNum);//輸入課程有關(guān)的各個(gè)信息}//@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@數(shù)據(jù)初始化全部完成floatInitData(char*b)//輸入學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，課程總數(shù){intflag=0; floata=0; do { if(flag==1) printf("請(qǐng)重新輸入%s\n",b); else printf("請(qǐng)輸入%s:\n",b); scanf("%f",&a); fflush(stdin); flag=1; }while(a<=0.0);//嚴(yán)格檢查輸入數(shù)據(jù)的準(zhǔn)確性 returna;}voidInitData(intnum)/*輸入課程有關(guān)的各個(gè)信息:每門課的課程名Source->name[];課程號(hào)(固定占3位的字母數(shù)字串)Source->OfSource[];學(xué)分Source->Source;直接先修課的課程號(hào)*/{inti=0,j=0; intflag=0;//標(biāo)記出錯(cuò)coursehead=(CourseHead*)malloc(num*sizeof(CourseHead)); //為全局變量course和coursehead分配內(nèi)存 CourseLink*courselink=NULL; CourseLink*courselinktemp=NULL; for(i=0;i<num;++i) { coursehead[i].Name[0]='\0'; coursehead[i].Ofcourse[0]='\0'; coursehead[i].Score=0; coursehead[i].flag=0; coursehead[i].first=NULL; coursehead[i].priornum=0; } //為全局變量course和coursehead完成初始化 for(i=0;i<num;++i)//............輸入每一門課程的信息 { do {flag=0; if(flag==1) printf("輸入的信息不符合要求，請(qǐng)檢查后再輸入!\n請(qǐng)重新輸入第%d門課程的課程名(限長12位),課程號(hào)(固定占3位)，學(xué)分\n",i); printf("請(qǐng)輸入第%d門課程的課程名(限長14位),課程號(hào)(固定占3位)，學(xué)分\n",i+1);scanf("%s%s%f",coursehead[i].Name,coursehead[i].Ofcourse,&(coursehead[i].Score)); fflush(stdin); //正確輸入課程名 if(strlen(coursehead[i].Name)>28) { printf("警告!課程名太長，請(qǐng)簡寫!\n\n");flag=1; } //正確輸入課程號(hào) if(strlen(coursehead[i].Ofcourse)!=3) { printf("警告!課程號(hào)必須是是三位\n\n\n");flag=1; } for(j=0;flag==0&&j<i;++j) if(strcmp(coursehead[i].Ofcourse,coursehead[j].Ofcourse)==0) {printf("警告!已經(jīng)有了一個(gè)同樣的課程號(hào)!\n\n"); flag=1; break; } if(coursehead[i].Score>MaxSource||coursehead[i].Score<=0.0) { printf("警告!學(xué)分必須是在0到最大限制%3.1f之間,請(qǐng)檢查后再輸入\n\n",MaxSource);flag=1; }//正確輸入學(xué)分 }while(flag==1); //嚴(yán)格控制輸入數(shù)據(jù)的正確性 }printf1(1);//輸出已經(jīng)輸入的課程信息//以下是輸入課程的關(guān)系intSort=0,NUM=0;//先修課的序號(hào),先修課的的個(gè)數(shù)chartemp[4];//保存輸入的課程號(hào)do{printf("請(qǐng)輸入課程號(hào)與它的先修課的的個(gè)數(shù)(輸入00結(jié)束):\n");scanf("%s%d",temp,&NUM);fflush(stdin);Sort=SourceNum; for(i=0;i<SourceNum;++i) if(strcmp(temp,coursehead[i].Ofcourse)==0) { Sort=i; break; }if(NUM>=SourceNum) printf("警告!先修課數(shù)目值無意義!\n\n"); if(Sort==SourceNum) printf("警告!該課程不存在!\n\n"); if(Sort<SourceNum&&coursehead[Sort].priornum!=0) { printf("警告!該課程已經(jīng)輸入過!\n\n");Sort=SourceNum; } if(Sort!=SourceNum&&NUM<SourceNum)//輸入各個(gè)關(guān)系 for(i=1;i<=NUM;++i) { if(i==1) coursehead[Sort].priornum=NUM; //先修課程數(shù)目 flag=0; do { printf("請(qǐng)"); if(flag==1){printf("重新");flag=0;} printf("輸入課程%s的第%d個(gè)直接先修課的課程號(hào)\n",coursehead[Sort].Ofcourse,i); scanf("%s",temp); fflush(stdin);//*********************檢查輸入的課程號(hào)的正確性 for(j=0;j<SourceNum;++j) if(strcmp(temp,coursehead[j].Ofcourse)==0&&Sort!=j) { break; } //課程號(hào)不與自己相同 if(j==SourceNum) {printf("警告!輸入的課程號(hào)有誤!!\n\n");flag=1;} //課程號(hào)存在 if(flag==0) { courselinktemp=NULL;courselink=coursehead[Sort].first; while(courselink!=NULL) { if(courselink->Index==j) { printf("警告!課程不能互為先修課!\n\n");flag=1; break; }courselink=courselink->next; } }//不存在a--->b&&b--->a的情況 if(flag==0) { courselinktemp=NULL;courselink=coursehead[j].first; while(courselink!=NULL) { if(courselink->Index==Sort) { printf("警告!關(guān)系重復(fù)了!\n\n");flag=1; break; }courselink=courselink->next; } }//**********************檢查輸入的課程號(hào)的正確性//######################輸入正確時(shí)給相應(yīng)的地方賦值if(flag==0) { courselink=(CourseLink*)malloc(sizeof(CourseLink)); courselink->Index=Sort; courselink->next=coursehead[j].first; coursehead[j].first=courselink; } //######################輸入正確時(shí)給相應(yīng)的地方賦值 }while(flag==1);//輸入有錯(cuò)那么重新輸入//TheEndofdo{}while(); printf1(0); } //TheEndoffor(){}}while(!(Sort==SourceNum&&NUM==0));//判斷關(guān)系是否結(jié)束}//..........................所有的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)初始化已經(jīng)完成voidStartTopoSort()//初始化要用到的各個(gè)數(shù)據(jù){//再調(diào)用遞歸函數(shù)TopoSort(inttopotempsum,inttime) //來完成課程的具體安排inti=0; topotemp=(ArryInTopo*)malloc(SourceNum*sizeof(ArryInTopo)); for(;i<SourceNum;++i) {topotemp[i].Time=0; topotemp[i].Index=0; } //為全局變量ArryInTopo*topotemp完成初始化 topo=(Topo*)malloc(sizeof(Topo)); topo->level=0; topo->toporesualt=NULL; topo->next=NULL; //為全局變量Topo*topo完成初始化 ZeroTemp=(Zero*)malloc(sizeof(Zero));ZeroTemp->next=NULL; ZeroTemp->zero=0; //為全局變量Zero*ZeroTemp完成初始化，頭結(jié)點(diǎn)不用 ClassInTime=(int*)malloc(Time*sizeof(int)); for(i=0;i<Time;i++)ClassInTime[i]=0; //為全局變量int*ClassInTime完成初始化 TopoSort(0,1);//調(diào)用遞歸函數(shù)TopoSort完成課程安排}voidTopoSort(inttempsum,inttime){//遞歸完成拓?fù)渑判?/tempsum，已經(jīng)安排的課程的數(shù)目//要安排課程的time學(xué)期 inti=0,j=0;intzero=ZERO();//index課程的后繼課程中前驅(qū)為零的個(gè)數(shù) if(zero==0)return;//沒有課程可選，返回 int*ZeroArry; ZeroArry=(int*)malloc(zero*sizeof(int)); Zero*zerolink=ZeroTemp->next;for(i=0;i<zero;++i) { ZeroArry[i]=zerolink->zero; zerolink=zerolink->next; }//將Zero*ZeroTemp鏈里的數(shù)據(jù)賦給 //局部變量int*ZeroArry賦值，方便操作intxuan=1;//該層遞歸在ZeroArry[i]已經(jīng)選擇的課程的數(shù)目 intsum=tempsum;//已經(jīng)安排的課程的數(shù)目 doubleScoreNum=0;//該層遞歸選擇的課程的學(xué)分的和 intflag=0;//標(biāo)記某一種課程選擇是否正確 for(i=1;i<int(pow(2,zero));++i) {//這是本人寫這個(gè)程序的唯一的得意之處 //將課程的選擇情況用二進(jìn)制的0，1表示 //例如i=6那么i=110(2) //i分別與j100(2),10(2),1(2)進(jìn)行“與”運(yùn)算 //分別得到j(luò)100(2),10(2),0(2)//j==j110 //那么表示在這種情況下在數(shù)組int*ZeroArry里面 //選擇ZeroArry[1-1],ZeroArry[2-1]的課程 //不選ZeroArry[3-1] //并且是i從1到pow(2,zero)-1, //這樣可以不重不漏地將所有情況都考慮進(jìn)去 sum=tempsum; //已經(jīng)安排的第sum課程 ScoreNum=0; flag=0; ClassInTime[time-1]=0; //每一次循環(huán)都必須將數(shù)據(jù)初始化for(j=1,xuan=1;xuan<=zero;xuan++) {if((j&i)==j)//選擇ZeroArry[xuan-1]的課程 { coursehead[ZeroArry[xuan-1]].flag=1; //標(biāo)記已選 topotemp[sum].Index=ZeroArry[xuan-1];topotemp[sum].Time=time; //全局變量數(shù)組ArryInTopo*topotemp記錄選課情況 Check(ZeroArry[xuan-1]); //將課程Course[index]的后繼課程的入度減一 ScoreNum+=coursehead[ZeroArry[xuan-1]].Score; //選擇的課程的學(xué)分的和 sum++; ClassInTime[time-1]++; //更改全局變量time學(xué)期課程的數(shù)目 } j=j*2;//也可以用j=j<<1; } if(sum==SourceNum) {//課程安排成功 Ifsuccessed(); flag=1; } if(ScoreNum!=0&&ScoreNum<=MaxSource&&time<Time)TopoSort(sum,time+1); //繼續(xù)遞歸 for(j=1,xuan=1;xuan<=zero;xuan++) { if((j&i)==j) { CheckBack(ZeroArry[xuan-1]); coursehead[ZeroArry[xuan-1]].flag=0; } j=j*2; }//這個(gè)for循環(huán)用于在i=i+1之前將所有的數(shù)據(jù)復(fù)原 if(flag==1) { ClassInTime[time-1]=0; return; } }ClassInTime[time-1]=0;free(ZeroArry);}voidIfsuccessed()//當(dāng)課程安排成功時(shí)將課程安排記錄保存{ //并對(duì)課程安排做評(píng)價(jià)inti=0;Topo*temp;temp=(Topo*)malloc(sizeof(Topo));temp->level=0; temp->toporesualt=(ArryInTopo*)malloc(SourceNum*sizeof(ArryInTopo));temp->next=NULL;temp->next=topo->next;topo->next=temp; //當(dāng)某一種課程安排成立時(shí)新建一個(gè) //Topo*temp結(jié)點(diǎn)，并且連接到全局變量topo后面for(i=0;i<SourceNum;++i) {temp->toporesualt[i].Index=topotemp[i].Index;temp->toporesualt[i].Time=topotemp[i].Time; }//完成對(duì)結(jié)點(diǎn)Topo*temp的內(nèi)容的添加//下面對(duì)該種安排做一個(gè)評(píng)估 intAverage=int(SourceNum/Time);//平均每學(xué)期的課程數(shù)目 for(i=0;i<Time;++i)if(ClassInTime[i]<Average||ClassInTime[i]>Average+1||ClassInTime[Time-1]==0) break; //判斷是否平均 if(i==Time) { temp->level=1;//標(biāo)記課程安排平均 topo->level++;//課程安排平均的數(shù)目+1 }}intZERO()//統(tǒng)計(jì)某層遞歸可以選擇的課程{ //并且完成可選課程的記錄 Zero*p=ZeroTemp->next; Zero*zerotemp=NULL; ZeroTemp->next=NULL; while(p!=NULL) { zerotemp=p->next; free(p); p=zerotemp; } //釋放全局變量Zero*ZeroTemp的內(nèi)存//為記錄新的入度為零的課程做準(zhǔn)備 p=ZeroTemp; intzero=0; inti=0;for(i=0;i<SourceNum;++i) if(coursehead[i].priornum==0&&coursehead[i].flag==0) {//入度為零，并且還沒有被選中 zerotemp=(Zero*)malloc(sizeof(Zero)); p->next=zerotemp; p=zerotemp; zerotemp->zero=i; zerotemp->next=NULL; zero++;//完成對(duì)全局變量Zero*ZeroTemp重新賦值 } returnzero;//返回可選課程的個(gè)數(shù)}voidCheck(intindex)//將課程coursehead[index]的后繼課程的入度減一{ CourseLink*courselinktemp=NULL; courselinktemp=coursehead[index].first; while(courselinktemp!=NULL) {coursehead[courselinktemp->Index].priornum--; courselinktemp=courselinktemp->next; }}voidCheckBack(intindex)//當(dāng)coursehead[index]課程"推選"時(shí)，要將與他有關(guān)的課程的入度數(shù)復(fù)原{CourseLink*courselinktemp; courselinktemp=coursehead[index].first; while(courselinktemp!=NULL) {coursehead[courselinktemp->Index].priornum++; courselinktemp=courselinktemp->next; }}voidPrint()//根據(jù)客戶要求輸出相應(yīng)的課程安排{ printf1(1);//刷新屏幕 inti=0,j=1,flag=1; FILE*f; Topo*pp=topo->next; do { printf("課程編排結(jié)束!!\n\n"); printf("請(qǐng)選擇操作!\n");printf("選項(xiàng)(0/1/2):\n");printf("(0)重新初始化課程信息!\n"); printf("(1)學(xué)習(xí)負(fù)擔(dān)盡量均勻!\n"); printf("(2)所有課程安排情況!\n"); do { if(!(flag==1||flag==2||flag==0)) printf("注意!!!請(qǐng)輸入合法選擇!\n");scanf("%d",&flag); fflush(stdin); }while(!(flag==1||flag==2||flag==0)); //嚴(yán)格控制輸入的準(zhǔn)確性 printf("以下是所有符合您要求的課程安排情況!\n");printf1(1);//刷新屏幕 if(flag==1) f=fopen("分配均勻.txt","w"); else f=fopen("所有情況.txt","w"); printf1(f); if(flag==0)return; else { pp=topo->next; j=1;while(pp!=NULL) { if(flag==1&&pp->level==1||flag==2) { printf("第%d種課程安排!\n\n",j); printf("開課時(shí)間課程名稱課程號(hào)學(xué)分先修課數(shù)目\n"); fprintf(f,"第%d種課程安排!\n\n",j); fprintf(f,"開課時(shí)間課程名稱課程號(hào)學(xué)分先修課數(shù)目\n"); for(i=0;i<SourceNum;++i) {printf("%8d%20s%11s%7.1f%10d\n",pp->toporesualt[i].Time,coursehead[pp->toporesualt[i].Index].Name,coursehead[pp->toporesualt[i].Index].Ofcourse,coursehead[pp->toporesualt[i].Index].Score,coursehead[i].priornum); fprintf(f,"%8d%20s%11s%7.1f%10d\n",pp->toporesualt[i].Time,coursehead[pp->toporesualt[i].Index].Name,coursehead[pp->toporesualt[i].Index].Ofcourse,coursehead[pp->toporesualt[i].Index].Score,coursehead[i].priornum); } fprintf(f,"\n\n"); printf("\n\n"); j++; } pp=pp->next; } //輸出完畢 printf("一共%d種符合您要求的課程安排!\n\n",j-1);fprintf(f,"一共%d種符合您要求的課程安排!\n\n",j-1); fclose(f); } }while(1);}voidprintf0()//界面{printf("*****************************************************************************\n