數(shù)據(jù)結(jié)構(gòu)課程設(shè)計教學計劃編制問題報告

中北大學數(shù)據(jù)結(jié)構(gòu)課程設(shè)計說明書

學生姓名:張寧學號：102101?1524

學院:軟件學院專業(yè):軟件工程題目:教學計劃編制?問題指導教師何志英

2011年1設(shè)計任務(wù)概述?1.1問題描述大學的每個專?業(yè)都要制定教?學計劃。針對軟件工程?本專業(yè)制定一?個教學計劃。假設(shè)任何專業(yè)?都有固定的學?習年限，每學年含兩學?期，每學期的時間?長度和學分上?限值均相等，每個專業(yè)開設(shè)?的課程都是確?定的，而且課程在開?設(shè)時間的安排?必須滿足先修?關(guān)系。每門課程有哪?些先修課程是?確定的，可以有任意多?門，也可以沒有。每門課恰好占?一個學期。試在這樣的前?提下設(shè)計一個?教學計劃編制?程序。1.2需求分析根據(jù)問題描述?及要求，可知設(shè)計中需?要定義先修關(guān)?系的AOV網(wǎng)?圖中的頂點及?弧邊的結(jié)構(gòu)體?，在運行結(jié)果中?將圖的信息顯?示出來，利用先修關(guān)系?將課程排序，最后解決問題?輸出每學期的?課程。（1）用學分來實現(xiàn)?每學期課程數(shù)?大致相同；（2）根據(jù)教學計劃?中的課程及其?關(guān)系和學分來?定義圖的頂點?及邊的結(jié)構(gòu)體?。（3）創(chuàng)建圖Cre?ateGra?ph（）：結(jié)合先修關(guān)系?的AOV網(wǎng)，采用鄰接表存?儲。（4）菜單OUTP?UT()：顯示代號所對?應(yīng)課程及課程?的先修課程。（5）拓撲排序To?poSort?(G)：將課程排序后?并決定出每學?期所學課程。（6）輸出圖G的信?息Displ?ay(G)：將圖的頂點和?弧邊輸出。1.3本程序包括?2個模塊：主程序模塊和?拓撲排序模塊?。拓撲排序模塊?主程序模塊拓撲排序模塊?主程序模塊本設(shè)計所采用?的數(shù)據(jù)結(jié)構(gòu)(1)voidOUTPUT?()//顯示代號所對?應(yīng)課程及課程?的先修課程(2)intLocate?Vex(ALGrap?hG,Vertex?Typeu)

//查找圖中某個?頂點位置

(3)intCreate?Graph(ALGrap?hG)//采用鄰接表存?儲結(jié)構(gòu)(4)voidDispla?y(ALGrap?hG)//輸出圖G的信?息(5)voidFindIn?Degree?(ALGrap?hG,intindegr?ee[])//求頂點的入度?(6)voidpuandu?an(Vertex?Typestr,struct?Namename[],intn)(7)intInitSt?ack(SqStac?k&S)//棧的初始化(8)intStackE?mpty(SqStac?kS)//判空(9)intPop(SqStac?k&S,SElemT?ype&e)//出棧(10)intPush(SqStac?k&S,SElemT?ypee)//入棧(11)intTopoSo?rt(ALGrap?hG,AdjLis?tTemp,struct?Namename[])//拓撲排序(12)voidmain()//主函數(shù)功能模塊詳細?設(shè)計3.1詳細設(shè)計思?想12main()12main()13411256789103.2核心代碼3.21．數(shù)據(jù)類型定義?（1）頭結(jié)點，表結(jié)點，鄰接表的定義?typede?fcharVertex?Type[MAX_NA?ME];intTotalT?erms;

//學期總數(shù)intMaxSco?res;

//學分上限typede?fstruct?ArcNod?e{

intadjvex?;

//該弧所指向的?頂點的位置弧的節(jié)點結(jié)構(gòu)?

struct?ArcNod?e*nextar?c;

//指向下一條弧?的指針}ArcNod?e;

//表結(jié)點

typede?fstruct?VNode

{

Vertex?Typedata;

//頂點信息

intgrades?;

//存儲學分信息?

ArcNod?e*firsta?rc;

//指向第一條依?附該頂點的弧?的指針}VNode,AdjLis?t[MAX_VE?RTEX_N?UM];

//頭結(jié)點

typede?fstruct?ALGrap?h//鄰接表{

AdjLis?tvertic?es;

//vertic?es存儲課程名

intvexnum?,arcnum?;

//圖的當前頂點?數(shù)和弧數(shù)}ALGrap?h;鄰接表的基本?操作：voidCreatG?raph(ALGrap?h*);創(chuàng)建鄰接表voidFindIn?Degree?(ALGrap?h,int*);求一個結(jié)點的?入度intTopoSo?rt(ALGrap?hG,AdjLis?tTemp,struct?Namename[])//拓撲排序（2）棧的定義：typede?fintSElemT?ype;

//棧類型#define?Stack_?NUM20

//存儲空間初始?分配量#define?Stack_?MoreNU?M5

//存儲空間分配?增量typede?fstruct?SqStac?k{

SElemT?ype*base;

SElemT?ype*top;

intstacks?ize;

//分配的存儲空?間}SqStac?k;基本操作：voidInitSt?ack(SqStac?k*S);棧的初始化intStackE?mpty(SqStac?kS);判斷棧是否為?空voidPush(SqStac?k*S,int);入棧操作intPop(SqStac?k*S,int*e);出棧操作3.22系統(tǒng)主要?子程序詳細設(shè)?計（1）主函數(shù)模塊設(shè)?計voidmain(){ALGrap?hG;AdjLis?tTemp;struct?Namename[N]={{"C1"},{"C2"},{"C3"},{"C4"},{"C5"},{"C6"},{"C7"},{"C8"},{"C9"},{"C10"},{"C11"},{"C12"}};OUTPUT?();printf?("**********教學計劃編制?問題**********\n");printf?("請輸入學期總?數(shù):");scanf("%d",&TotalT?erms);printf?("請輸入學期的?學分上限:");scanf("%d",&MaxSco?res);Create?Graph(G);Displa?y(G);TopoSo?rt(G,Temp,name);printf?("OK\n");scanf("*c");}（2）拓撲排序模塊?設(shè)計intTopoSo?rt(ALGrap?hG,AdjLis?tTemp,struct?Namename[]){inti,k,j=0,count,indegr?ee[MAX_VE?RTEX_N?UM];SqStac?kS;ArcNod?e*p;FindIn?Degree?(G,indegr?ee);//對各頂點求入?度InitSt?ack(S);//初始化棧for(i=0;i<G.vexnum?;++i)//建零入度頂點?棧Sif(!indegr?ee[i])Push(S,i);//入度為0者進?棧count=0;//對輸出頂點計?數(shù)while(!StackE?mpty(S)){Pop(S,i);printf?("%s(%d分),",G.vertic?es[i].data,G.vertic?es[i].grades?);Temp[j++]=G.vertic?es[i];//將當前的拓撲?序列保存起來?++count;//輸出i號頂點?并計數(shù)for(p=G.vertic?es[i].firsta?rc;p;p=p->nextar?c)//對i號頂點的?每個鄰接點的?入度減1{k=p->adjvex?;if(!(--indegr?ee[k]))//若入度減為0?,則入棧Push(S,k);}}if(count<G.vexnum?){printf?("此有向圖有回?路無法完成拓?撲排序");return?ERROR;}elseprintf?("為一個拓撲序?列");printf?("\n");intq=1,Z=0;while(q<=TotalT?erms){intC=Temp[Z].grades?;printf?("\n第%d個學期應(yīng)學?課程:",q);while(C<=MaxSco?res){C=C+Temp[Z+1].grades?;if(Z<G.vexnum?){puandu?an(Temp[Z].data,name,N);++Z;}}printf?("\n");if(q==TotalT?erms)printf?("\n課程編制完?成!");q++;}return?OK;}3.3程序運行結(jié)果?（1）主界面設(shè)計顯示課程代號?所對應(yīng)課程及?先修課程。（2）輸入1-16的任意數(shù)?回車（3）按要求輸入學?期數(shù)，學分上限，課程數(shù)，課程號和各課?程