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

學(xué)生姓名:張寧學(xué)號(hào)：102101?1524

學(xué)院:軟件學(xué)院專業(yè):軟件工程題目:教學(xué)計(jì)劃編制?問(wèn)題指導(dǎo)教師何志英

2011年1設(shè)計(jì)任務(wù)概述?1.1問(wèn)題描述大學(xué)的每個(gè)專?業(yè)都要制定教?學(xué)計(jì)劃。針對(duì)軟件工程?本專業(yè)制定一?個(gè)教學(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éi)有。每門課恰好占?一個(gè)學(xué)期。試在這樣的前?提下設(shè)計(jì)一個(gè)?教學(xué)計(jì)劃編制?程序。1.2需求分析根據(jù)問(wèn)題描述?及要求，可知設(shè)計(jì)中需?要定義先修關(guān)?系的AOV網(wǎng)?圖中的頂點(diǎn)及?弧邊的結(jié)構(gòu)體?，在運(yùn)行結(jié)果中?將圖的信息顯?示出來(lái)，利用先修關(guān)系?將課程排序，最后解決問(wèn)題?輸出每學(xué)期的?課程。（1）用學(xué)分來(lái)實(shí)現(xiàn)?每學(xué)期課程數(shù)?大致相同；（2）根據(jù)教學(xué)計(jì)劃?中的課程及其?關(guān)系和學(xué)分來(lái)?定義圖的頂點(diǎn)?及邊的結(jié)構(gòu)體?。（3）創(chuàng)建圖Cre?ateGra?ph（）：結(jié)合先修關(guān)系?的AOV網(wǎng)，采用鄰接表存?儲(chǔ)。（4）菜單OUTP?UT()：顯示代號(hào)所對(duì)?應(yīng)課程及課程?的先修課程。（5）拓?fù)渑判騎o?poSort?(G)：將課程排序后?并決定出每學(xué)?期所學(xué)課程。（6）輸出圖G的信?息Displ?ay(G)：將圖的頂點(diǎn)和?弧邊輸出。1.3本程序包括?2個(gè)模塊：主程序模塊和?拓?fù)渑判蚰K?。拓?fù)渑判蚰K?主程序模塊拓?fù)渑判蚰K?主程序模塊本設(shè)計(jì)所采用?的數(shù)據(jù)結(jié)構(gòu)(1)voidOUTPUT?()//顯示代號(hào)所對(duì)?應(yīng)課程及課程?的先修課程(2)intLocate?Vex(ALGrap?hG,Vertex?Typeu)

//查找圖中某個(gè)?頂點(diǎn)位置

(3)intCreate?Graph(ALGrap?hG)//采用鄰接表存?儲(chǔ)結(jié)構(gòu)(4)voidDispla?y(ALGrap?hG)//輸出圖G的信?息(5)voidFindIn?Degree?(ALGrap?hG,intindegr?ee[])//求頂點(diǎn)的入度?(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[])//拓?fù)渑判?12)voidmain()//主函數(shù)功能模塊詳細(xì)?設(shè)計(jì)3.1詳細(xì)設(shè)計(jì)思?想12main()12main()13411256789103.2核心代碼3.21．?dāng)?shù)據(jù)類型定義?（1）頭結(jié)點(diǎn)，表結(jié)點(diǎn)，鄰接表的定義?typede?fcharVertex?Type[MAX_NA?ME];intTotalT?erms;

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

//學(xué)分上限typede?fstruct?ArcNod?e{

intadjvex?;

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

struct?ArcNod?e*nextar?c;

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

//表結(jié)點(diǎn)

typede?fstruct?VNode

{

Vertex?Typedata;

//頂點(diǎn)信息

intgrades?;

//存儲(chǔ)學(xué)分信息?

ArcNod?e*firsta?rc;

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

//頭結(jié)點(diǎn)

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

AdjLis?tvertic?es;

//vertic?es存儲(chǔ)課程名

intvexnum?,arcnum?;

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

//棧類型#define?Stack_?NUM20

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

//存儲(chǔ)空間分配?增量typede?fstruct?SqStac?k{

SElemT?ype*base;

SElemT?ype*top;

intstacks?ize;

//分配的存儲(chǔ)空?間}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)主要?子程序詳細(xì)設(shè)?計(jì)（1）主函數(shù)模塊設(shè)?計(jì)voidmain(){ALGrap?hG;AdjLis?tTemp;struct?Namename[N]={{"C1"},{"C2"},{"C3"},{"C4"},{"C5"},{"C6"},{"C7"},{"C8"},{"C9"},{"C10"},{"C11"},{"C12"}};OUTPUT?();printf?("**********教學(xué)計(jì)劃編制?問(wèn)題**********\n");printf?("請(qǐng)輸入學(xué)期總?數(shù):");scanf("%d",&TotalT?erms);printf?("請(qǐng)輸入學(xué)期的?學(xué)分上限:");scanf("%d",&MaxSco?res);Create?Graph(G);Displa?y(G);TopoSo?rt(G,Temp,name);printf?("OK\n");scanf("*c");}（2）拓?fù)渑判蚰K?設(shè)計(jì)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);//對(duì)各頂點(diǎn)求入?度InitSt?ack(S);//初始化棧for(i=0;i<G.vexnum?;++i)//建零入度頂點(diǎn)?棧Sif(!indegr?ee[i])Push(S,i);//入度為0者進(jìn)?棧count=0;//對(duì)輸出頂點(diǎn)計(jì)?數(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];//將當(dāng)前的拓?fù)?序列保存起來(lái)?++count;//輸出i號(hào)頂點(diǎn)?并計(jì)數(shù)for(p=G.vertic?es[i].firsta?rc;p;p=p->nextar?c)//對(duì)i號(hào)頂點(diǎn)的?每個(gè)鄰接點(diǎn)的?入度減1{k=p->adjvex?;if(!(--indegr?ee[k]))//若入度減為0?,則入棧Push(S,k);}}if(count<G.vexnum?){printf?("此有向圖有回?路無(wú)法完成拓?撲排序");return?ERROR;}elseprintf?("為一個(gè)拓?fù)湫?列");printf?("\n");intq=1,Z=0;while(q<=TotalT?erms){intC=Temp[Z].grades?;printf?("\n第%d個(gè)學(xué)期應(yīng)學(xué)?課程:",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程序運(yùn)行結(jié)果?（1）主界面設(shè)計(jì)顯示課程代號(hào)?所對(duì)應(yīng)課程及?先修課程。（2）輸入1-16的任意數(shù)?回車（3）按要求輸入學(xué)?期數(shù)，學(xué)分上限，課程數(shù)，課程號(hào)和各課?程