任務(wù)要求:大學(xué)的每個(gè)專業(yè)都要制定教學(xué)方案。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程在開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個(gè)學(xué)期，試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)方案編制程序。內(nèi)容摘要:本程序是一個(gè)教學(xué)方案的編制的問題，而由任務(wù)要求了解到的的條件及這次設(shè)計(jì)的目的。我們?cè)诜治鰡栴}后決定采用AOV網(wǎng)圖來解決。首先，了解本系統(tǒng)要實(shí)現(xiàn)的根本功能，大致劃分模塊。其次，由條件畫出先修關(guān)系圖，以此來設(shè)計(jì)鄰接表存儲(chǔ)結(jié)構(gòu)。接下來，借助于棧，設(shè)計(jì)拓?fù)渑判虻牧鞒獭Ｗ詈?，?duì)系統(tǒng)開始進(jìn)行詳細(xì)的前臺(tái)界面和后臺(tái)程序的設(shè)計(jì)，完善系統(tǒng)。教師評(píng)語:成績(jī)簽名:日期:課程設(shè)計(jì)報(bào)告書教學(xué)方案編制問題一設(shè)計(jì)思想根據(jù)任務(wù)要求及對(duì)實(shí)際情況的了解，可知設(shè)計(jì)中需要定義先修關(guān)系的AOV網(wǎng)圖中的頂點(diǎn)及弧邊的結(jié)構(gòu)體，采用鄰接表存儲(chǔ)結(jié)構(gòu)，利用棧作輔助結(jié)構(gòu)，在運(yùn)行結(jié)果中將圖的信息顯示出來，利用先修關(guān)系將課程排序，最后解決問題——輸出每學(xué)期的課程。二系統(tǒng)完成功能及功能框圖endend采用第二種策略：使課程盡可能地集中在前幾個(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)和弧邊輸出圖1系統(tǒng)功能框圖0C11C22C33C44C55C66C7^7C8^8C99C1010C1111C12^圖2：鄰接表對(duì)每個(gè)頂點(diǎn)求入度，并存入數(shù)組InDegree[i]中〔i=0對(duì)每個(gè)頂點(diǎn)求入度，并存入數(shù)組InDegree[i]中〔i=0…n〕初始化棧Stack,Counter=0ReturnOKReturnERROR依次將入度為0的頂點(diǎn)存入棧中對(duì)以i號(hào)頂點(diǎn)為尾弧的每個(gè)鄰接點(diǎn)的入度減1，并將入度減1后為零的頂點(diǎn)號(hào)壓入棧中，輸出i，計(jì)數(shù)器加1(Counter++)推出棧頂?shù)囊粋€(gè)元素〔入度為零的頂點(diǎn)號(hào)〕至i，輸出i，計(jì)數(shù)器加1〔Counter++〕堆棧是否為空？n個(gè)頂點(diǎn)全輸出YYNNNNYY圖3拓?fù)渑判蛄鞒虉DCC1C4C5C7C2C3C8C9C12C10C11C6圖4課程先修關(guān)系圖三核心算法及說明〔1〕采用鄰接表存儲(chǔ)結(jié)構(gòu)，創(chuàng)立圖intCreateGraph(ALGraph&G){inti,j,k;VertexTypeva;ArcNode*p;printf("請(qǐng)輸入教學(xué)方案的課程數(shù):");scanf("%d",&G.vexnum);printf("請(qǐng)輸入各個(gè)課程的先修課程的總和(弧總數(shù)):");scanf("%d",&G.arcnum);printf("請(qǐng)輸入%d個(gè)課程的課程號(hào)(最多%d個(gè)字符,數(shù)字+字母):",G.vexnum,MAX_NAME);for(i=0;i<G.vexnum;++i){scanf("%s",&G.vertices[i].data);G.vertices[i].firstarc=NULL;}printf("請(qǐng)輸入%d個(gè)課程的學(xué)分值:",G.vexnum);for(i=0;i<G.vexnum;++i){scanf("%d",&G.vertices[i].grades);}printf("請(qǐng)輸入以下課程的先修課程(無先修課程輸入0結(jié)束后也輸入0)\n");for(k=0;k<G.vexnum;++k)//構(gòu)造表結(jié)點(diǎn)鏈表,利用前插法{printf("%s的先修課程:",G.vertices[k].data);scanf("%s",va);while(va[0]!='0'){i=LocateVex(G,va);//弧頭j=k;

//弧尾p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;//插在表頭G.vertices[i].firstarc=p;scanf("%s",va);}}returnOK;}〔2〕通過棧實(shí)現(xiàn)拓?fù)渑判騀indInDegree(G,indegree);

//對(duì)各頂點(diǎn)求入度InitStack(S);

//初始化棧for(i=0;i<G.vexnum;++i)

//建零入度頂點(diǎn)棧Sif(!indegree[i])Push(S,i);

//入度為0者進(jìn)棧count=0;

//對(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);}}if(count<G.vexnum){printf("此有向圖有回路無法完成拓?fù)渑判?);returnERROR;}elseprintf("

為一個(gè)拓?fù)湫蛄?);printf("\n");returnok;〔3〕解決問題根據(jù)學(xué)分上限決定出每學(xué)期應(yīng)學(xué)課程，其中Temp[]中存儲(chǔ)的是經(jīng)過拓?fù)渑判蚝蟮恼n程先后順序。intq=1,Z=0;while(q<=TotalTerms){intC=Temp[Z].grades;printf("第%d個(gè)學(xué)期應(yīng)學(xué)課程:",q);while(C<=MaxScores){C=C+Temp[Z+1].grades;if(Z<G.vexnum)

printf("%4s",Temp[Z].data);++Z;}printf("\n");if(q==TotalTerms)printf("課程編制完成！");q++;}四界面設(shè)計(jì)五結(jié)論本次課程設(shè)計(jì)主要是拓?fù)渑判虻膽?yīng)用，我們根據(jù)問題描述給出了數(shù)據(jù)模型以及能夠表達(dá)問題本身特點(diǎn)的邏輯結(jié)構(gòu)。但是，在算法設(shè)計(jì)創(chuàng)立鄰接表的局部仍然有一些缺乏。通過與同學(xué)的討論、上網(wǎng)查詢和請(qǐng)教老師，解決了疑難，同時(shí)我們也穩(wěn)固和豐富了這方面的知識(shí)以及動(dòng)手實(shí)踐的能力。參考資料1．《數(shù)據(jù)結(jié)構(gòu)》〔C語言版〕嚴(yán)蔚敏、吳偉民

清華大學(xué)出版社

2．《C++語言根底教程》〔第二版〕徐孝凱

清華大學(xué)出版社

3.《數(shù)據(jù)結(jié)構(gòu)題集》〔C語言版〕嚴(yán)蔚敏、吳偉民、米寧

清華大學(xué)出版附錄#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#defineTRUE1#defineFALSE0#defineOK1#defineERROR0#defineMAX_NAME3#defineMAXCLASS100//頂點(diǎn)字符串的最大長(zhǎng)度#defineMAX_VERTEX_NUM100//最大頂點(diǎn)數(shù)#defineN12typedefcharVertexType[MAX_NAME];intTotalTerms;//學(xué)期總數(shù)intMaxScores;//學(xué)分上限/*----圖的鄰接表存儲(chǔ)表示----*/typedefstructArcNode{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(){ints;printf("\t\t教學(xué)方案編制菜單\n");printf("\t\t課程代碼|課程名稱|優(yōu)先課程\n");printf("\t\tC1|程序設(shè)計(jì)根底|無\n");printf("\t\tC2|離散數(shù)學(xué)|C1\n");printf("\t\tC3|數(shù)據(jù)結(jié)構(gòu)|C1，C2\n");printf("\t\tC4|匯編語言|C1\n");printf("\t\tC5|語言的設(shè)計(jì)和分析|C3，C4\n");printf("\t\tC6|計(jì)算機(jī)原理|C11\n");printf("\t\tC7|編譯原理|C5，C3\n");printf("\t\tC8|操作系統(tǒng)|C3，C6\n");printf("\t\tC9|高等數(shù)學(xué)|無\n");printf("\t\tC10|線性代數(shù)|C9\n");printf("\t\tC11|普通物理|C9\n");printf("\t\tC12|數(shù)值分析|C9,C10,C1\n");printf("pressanynumkeytocontinue:");scanf("%d",&s);//scanf("格式控制符",&地址表列)格式輸入函數(shù)，即按用戶指定的格式從鍵盤上把數(shù)據(jù)輸入到指定的變量之中}/*查找圖中某個(gè)頂點(diǎn)位置*/intLocateVex(ALGraphG,VertexTypeu){inti;for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vertices[i].data)==0)returni;return-1;}/*采用鄰接表存儲(chǔ)結(jié)構(gòu)*/intCreateGraph(ALGraph&G){inti,j,k;VertexTypeva;ArcNode*p;printf("請(qǐng)輸入教學(xué)方案的課程數(shù):");scanf("%d",&G.vexnum);//????printf("請(qǐng)輸入各個(gè)課程的先修課程的總和(弧總數(shù)):");scanf("%d",&G.arcnum);printf("請(qǐng)輸入%d個(gè)課程的課程號(hào)(最多%d個(gè)字符,數(shù)字+字母):",G.vexnum,MAX_NAME);//??for(i=0;i<G.vexnum;++i)//循環(huán)與鏈表？？？{scanf("%s",&G.vertices[i].data);G.vertices[i].firstarc=NULL;//????}printf("請(qǐng)輸入%d個(gè)課程的學(xué)分值:",G.vexnum);for(i=0;i<G.vexnum;++i){scanf("%d",&G.vertices[i].grades);}printf("請(qǐng)輸入以下課程的先修課程(無先修課程輸入0結(jié)束后也輸入0)\n");for(k=0;k<G.vexnum;++k)//構(gòu)造表結(jié)點(diǎn)鏈表,利用前插法{printf("%s的先修課程:",G.vertices[k].data);///scanf("%s",va);//while(va[0]!='0')//?????????ikva{i=LocateVex(G,va);//弧頭j=k;//弧尾p=(ArcNode*)malloc(sizeof(ArcNode));p->adjvex=j;p->nextarc=G.vertices[i].firstarc;//插在表頭G.vertices[i].firstarc=p;scanf("%s",va);}}returnOK;}/*輸出圖G的信息*/voidDisplay(ALGraphG){inti;ArcNode*p;printf("有向圖\n");printf("%d個(gè)頂點(diǎn)",G.vexnum);for(i=0;i<G.vexnum;++i)printf("%4s",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\n",G.vertices[i].data,G.vertices[p->adjvex].data);p=p->nextarc;}}}/*求頂點(diǎ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;}}}structName{charc[20];}name;/*棧定義*/typedefintSElemType;//棧類型#defineStack_NUM20//存儲(chǔ)空間初始分配量#defineStack_MoreNUM5//存儲(chǔ)空間分配增量typedefstructSqStack{SElemType*base;SElemType*top;intstacksize;//分配的存儲(chǔ)空間}SqStack;/*棧的初始化*/intInitStack(SqStack&S){S.base=(SElemType*)malloc(Stack_NUM*sizeof(SElemType));if(!S.base)exit(-1);S.top=S.base;S.stacksize=Stack_NUM;returnOK;}/*判空*/intStackEmpty(SqStackS){if(S.top==S.base)returnTRUE;elsereturnFALSE;}/*出棧*/intPop(SqStack&S,SElemType&e){if(S.top==S.base)returnERROR;e=*--S.top;returnOK;}/*入棧*/intPush(SqStack&S,SElemTypee){if(S.top-S.base>=S.stacksize){S.base=(SElemType*)realloc(S.base,(S.stacksize+Stack_MoreNUM)*sizeof(SElemType));if(!S.base)exit(-1);S.top=S.base+S.stacksize;S.stacksize+=Stack_MoreNUM;}*S.top++=e;returnOK;}/*拓?fù)渑判?/intTopoSort(ALGraphG,AdjListTemp,structNamename[]){inti,k,j=0,count,indegree[MAX_VERTEX_NUM];SqStackS;ArcNode*p;FindInDegree(G,indegree);//對(duì)各頂點(diǎn)求入度InitStack(S);//初始化棧for(i=0;i<G.vexnum;++i)//建零入度頂點(diǎn)棧Sif(!indegree[i])Push(S,i);//入度為0者進(jìn)棧count=0;//對(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);}}if(count<G.vexnum){printf("此有向圖有回路無法完成拓?fù)渑判?);returnERROR;}elseprintf("為一個(gè)拓?fù)湫蛄?);printf("\n");intq=1,Z=0;//解決問題，學(xué)分while(q<=TotalTerms){intC=Temp[Z].grades;printf("\n第%d個(gè)學(xué)期應(yīng)學(xué)課程:",q);while(C<=MaxScores){C=C+Temp[Z+1].grades;if(Z<G.vexnum)////////如c1和程序設(shè)計(jì)根底////////kaishi{printf("%4s",Temp[Z].data);if(strcmp(Temp[Z].data,"c1")==0)printf("程序設(shè)計(jì)根底");if(strcmp(Temp[Z].data,"c2")==0)printf("離散數(shù)學(xué)");if(strcmp(Temp[Z].data,"c3")==0)printf("數(shù)據(jù)結(jié)構(gòu)");if(strcmp(Temp[Z].data,"c4")==0)printf("匯編語言");if(strcmp(Temp[Z].data,"c5")==0)printf("語言的設(shè)計(jì)和分析");if(strcmp(Temp[Z].data,"c6")==0)printf("計(jì)算機(jī)原理");if(strcmp(Temp[Z].data,"c7")==0)p