教學(xué)計(jì)劃編制問題課程設(shè)計(jì)報(bào)告

1、中北大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)說 明 書 學(xué) 院、系：軟件學(xué)院專 業(yè):軟件工程學(xué) 生 姓 名:學(xué) 號(hào)：設(shè) 計(jì) 題 目：教學(xué)計(jì)劃編制問題起 迄 日 期：2013年12月9日2013年12月20日指 導(dǎo) 教 師：   2013 年12月 20 日1需求分析1。 在大學(xué)的某個(gè)專業(yè)中選取幾個(gè)課程作為頂點(diǎn),通過各門課的先修關(guān)系來構(gòu)建個(gè)圖，該圖用鄰接表來存儲(chǔ)，鄰接表的頭結(jié)點(diǎn)存儲(chǔ)每門課的信息。2. 本程序的目的是為用戶編排課程，根據(jù)用戶輸入的信息來編排出每學(xué)期要學(xué)的課程.3。測試數(shù)據(jù):學(xué)期總數(shù):6；學(xué)分上限：9；本專業(yè)共開設(shè)12門課，課程號(hào)從C00到C11,學(xué)分順序?yàn)?/p>

2、2，3，4，3,2,3，4,4,7，5，2,3.2概要設(shè)計(jì)1.抽象數(shù)據(jù)類型圖的定義如下:ADT Graph數(shù)據(jù)對(duì)象V：V是具有相同特性的數(shù)據(jù)元素的集合，稱為頂點(diǎn)集。數(shù)據(jù)關(guān)系R:R=VRVR=(v，w)|v，wV，(v,w)表示v和w之間存在直接先修關(guān)系基本操作P：void CreatGraph（ALGraph *）；void FindInDegree（ALGraph ， int * ）；int TopologicalOrder（ALGraph G，AdjList R，struct Name name）int LocateVex(ALGraph G， VertexType u）/ 查找圖中某個(gè)頂

3、點(diǎn)位置 / ADT Graph2。棧的定義如下：ADT Stack數(shù)據(jù)對(duì)象：D=aiaiElemSet，i=1，2，n，n=0 數(shù)據(jù)關(guān)系：R1=ai-1 aiai-1,aiD,i=2，,n基本操作:void InitStack （SqStack *S）；int StackEmpty(SqStack S)；void Push（SqStack *S， int ）；int Pop(SqStack S， int *e);ADT Stack3。本程序有兩個(gè)模塊，調(diào)用關(guān)系簡單:主程序模塊  拓?fù)渑判蚰K3系統(tǒng)完成功能及功能框圖end采用第二種策略：使課程盡可能地集中在前幾個(gè)學(xué)期中根據(jù)教學(xué)計(jì)劃中的

4、課程及其關(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)和弧邊輸出 圖3。1系統(tǒng)功能框圖0C11 5 11 111067 6 4 72 1134 9 1C22C33C44C55C66C77C88C99C1010C1111C12 圖3.2 鄰接表對(duì)每個(gè)頂點(diǎn)求入度，并存入數(shù)組InDegreei中（i=0n）初始化棧Stack,Counter=0Return O

5、KReturn ERROR依次將入度為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)全輸出Y Y N Y N Y 圖3。3 拓?fù)渑判蛄鞒虉DC1C4C5C7C2C3C8C9C12C10C11C6圖3.4 課程先修關(guān)系圖4 詳細(xì)設(shè)計(jì)1. 圖的鄰接表的存儲(chǔ)表示，即結(jié)構(gòu)體的定義:typedef struct ArcNodeint AdjOfV; / 該弧所指向的頂點(diǎn)的位置struct ArcNode next； /

6、指向下一條弧的指針ArcNode；typedef char VertexTypeMAXOfNAME; typedef struct /鏈接表VertexType data； /頂點(diǎn)信息int grades; /存儲(chǔ)學(xué)分信息ArcNode first； /指向第一條依附該頂點(diǎn)的弧的指針VNode, AdjListMAX_VER； / 頭結(jié)點(diǎn)typedef structAdjList ver； /vertices 存儲(chǔ)課程名int vexnum， arcnum； / 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph;2。 建立圖的鄰接鏈表：printf(”請(qǐng)輸入下列課程的先修課程（無先修課程輸入0 結(jié)束后也輸入

7、0）n”）;for （h=0；hG。vexnum；+h） / 構(gòu)造表結(jié)點(diǎn)鏈表,利用前插法 printf("s的先修課程:",G。verh。data)； scanf("s”，va);getchar()； while （va0!=0） i = LocateVex（G, va）； /弧頭 j = h； /弧尾 p = (ArcNode)malloc(sizeof（ArcNode）; pAdjOfV = j; p->next = G。veri。first； / 插在表頭 G。veri.first = p; scanf（”s”,va)； getchar（); 3. 輸

8、出圖的頂點(diǎn)和邊：printf("d個(gè)頂點(diǎn)”， G。vexnum）； for （i = 0;i G。vexnum；+i）printf（”4s", G.veri.data）； printf(” n%d條弧邊:n”，G。arcnum）; for （i = 0；i G。vexnum；i+) p = G.veri。first； while （p） printf（”%s-sn”，G。veri。data，G。verpAdjOfV.data）； p = p>next；  4. 通過棧實(shí)現(xiàn)拓?fù)渑判?   int TopologicalOrder（

9、ALGraph G，AdjList R，struct Name name） int i， k， j = 0, count， indegreeMAX_VER; SqStack S；ArcNode *p；FindInDegree（G， indegree）； / 對(duì)各頂點(diǎn)求入度InitStack（S）; / 初始化棧for （i = 0；i G.vexnum;+i) /建零入度頂點(diǎn)棧Sif （!indegreei) Push（S, i)； / 入度為0者進(jìn)棧count = 0; / 對(duì)輸出頂點(diǎn)計(jì)數(shù)while （!StackEmpty(S）) Pop（S， i)；printf（”s（d學(xué)分),&quo

10、t;，G.veri。data，G。veri.grades）；Rj+ = G.veri； /將當(dāng)前的拓?fù)湫蛄斜４嫫饋?count； / 輸出i號(hào)頂點(diǎn)并計(jì)數(shù)for （p =G。veri。first； p； p=p-next)/ 對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1 k = p>AdjOfV;if (！(-indegreek) / 若入度減為0，則入棧Push（S, k）;if （count < G。vexnum)printf（”此有向圖有回路無法完成拓?fù)渑判颉?；return 0；else printf（ ” 為一個(gè)拓?fù)湫蛄?quot;）;printf（"n"）;int

11、 q=1，Z=0;while （q = TotalOfTerms)int C = RZ.grades ；printf（”n第%d個(gè)學(xué)期應(yīng)學(xué)課程:”,q）;while (C = MaxScores）C = C + RZ+1。grades；if （Z G。vexnum)CmpOfStr（RZ。data,name，N）;/讓C1C12分別與12門課程對(duì)應(yīng)起來/+Z;printf（"n”）;if （q = TotalOfTerms）printf（ ”nOK Over！”）；q+；return 1；/5。主程序和其他偽碼算法：void main（) ALGraph G; AdjList R；S

12、truct name；nameN=”C1”，"C2”,”C3”，"C4”,”C5”，”C6",”C7"，”C8”，”C9”,”C10"，”C11"，”C12"；printf（” *教學(xué)計(jì)劃編制問題*n" ）； printf（ ”請(qǐng)以課件92上課程先序圖為例輸入學(xué)期總數(shù):"）; scanf（”d”，TotalOfTerms）； getchar()； printf("請(qǐng)輸入學(xué)期的學(xué)分上限（8或9）：")； scanf（”d"，&MaxScores）； getchar（）；

13、 CreateGraph（G）； Display(G）; TopologicalOrder（G,R，name）；int InitStack（SqStack S) /棧的初始化/ S。a= （int )malloc(StackofNUM sizeof(int）)；if （!S.a)exit（-1）;S.top =S.a;S。size =StackofNUM;return 1；int StackEmpty（SqStack S） /*判斷棧是否為空/ if （S。top = S。a)return 1；else return 0；int Push（SqStack S， int x）/入棧*/ if （

14、S。top - S。a = S。size）S.a = （int ） realloc （ S。a， （S。size + StackforMore） sizeof（int）)；if （ !S。a ） exit（1);S。top =S。a +S。size；S.size +=StackforMore;S。top+ = x；return 1；int Pop（SqStack &S， int x） /出棧/ if （S。top = S.a)return 0；x = S。top； return 1；int LocateVex（ALGraph G， VertexType u）/* 查找圖中某個(gè)頂點(diǎn)位置

15、*/ int i； for （i = 0；i G.vexnum；+i） if （strcmp（u，G。veri。data）=0）return i； return 1；int CreateGraph(ALGraph G） /采用鄰接表存儲(chǔ)結(jié)構(gòu)/ int i， j, h； VertexType va；ArcNode p; printf（”請(qǐng)輸入教學(xué)計(jì)劃的課程數(shù): " ）; scanf(”d”，G.vexnum）； getchar（）； printf（ ”請(qǐng)輸入各個(gè)課程的先修課程的總和(弧總數(shù)）： ”); scanf（”%d”,G。arcnum）； getchar()； printf（ ”

16、請(qǐng)輸入%d個(gè)課程的課程號(hào)（最多d個(gè)字符，字母+數(shù)字如C10）："， G.vexnum,MAXOfNAME); for （i = 0；i G。vexnum；+i) scanf（”%s”,G。veri。data）； getchar（)； G。veri。first = NULL； printf（”請(qǐng)輸入%d個(gè)課程的學(xué)分值:",G.vexnum)； for （i = 0；i < G.vexnum;+i） scanf(”d”,&G。veri.grades)；getchar（)； printf（"請(qǐng)輸入下列課程的先修課程（無先修課程輸入0 結(jié)束后也輸入0)n”）

17、； for （h=0；hG。vexnum；+h) / 構(gòu)造表結(jié)點(diǎn)鏈表，利用前插法 printf(”s的先修課程："，G.verh。data）； scanf（"%s”，va）；getchar（）; while （va0！=0'） i = LocateVex(G， va)； /弧頭 j = h； /弧尾 p = （ArcNode*)malloc（sizeof（ArcNode)）； p-AdjOfV = j； pnext = G。veri。first; / 插在表頭 G.veri。first = p; scanf（"s”,va)； getchar（）； retu

18、rn 1;void Display（ALGraph G） / 輸出圖G的信息*/ int i； ArcNode p; printf（”有向圖n”）； printf（”d個(gè)頂點(diǎn)”， G.vexnum）； for (i = 0；i G.vexnum;+i）printf（"4s", G.veri。data）； printf（" nd條弧邊:n”,G.arcnum)； for （i = 0；i G。vexnum；i+） p = G。veri.first； while (p) printf(”s->sn”,G.veri.data，G。verpAdjOfV。data）；

19、 p = pnext； void FindInDegree（ALGraph G， int indegree） /*求頂點(diǎn)的入度/ int i； ArcNode *p; for (i = 0;i G。vexnum；i+) indegreei = 0; for (i = 0;i G.vexnum；i+) p = G。veri。first； while (p） indegreepAdjOfV+; p = pnext; struct Namechar c20；name；void CmpOfStr（VertexType str，struct Name name，int n） /讓C1C12分別與12門課

20、程對(duì)應(yīng)起來*/ if（strcmp（str，name0。c）=0）printf(” C程序設(shè)計(jì)"）； if（strcmp(str,name1。c）=0）printf(” 模擬數(shù)字電路"）； if（strcmp（str，name2.c）=0)printf（" 數(shù)據(jù)結(jié)構(gòu)"）; if(strcmp（str，name3。c）=0)printf（” C+面向?qū)ο?”)； if（strcmp(str，name4.c）=0）printf(" 大學(xué)英語 ”）； if（strcmp(str，name5。c)=0）printf（" 計(jì)算機(jī)組成原理”）；

21、if(strcmp（str，name6.c）=0)printf（" 傳感器原理"）； if（strcmp(str，name7.c)=0）printf（” 軟件工程導(dǎo)論"）; if（strcmp（str,name8。c）=0)printf（” 高等數(shù)學(xué)”）； if（strcmp(str，name9。c）=0）printf（” 線性代數(shù)”）； if(strcmp(str，name10.c）=0）printf(” 大學(xué)物理基礎(chǔ)”）； if（strcmp（str，name11。c）=0）printf(" 電工技術(shù)"）； 4 界面設(shè)計(jì)5 源代碼inclu

22、de<stdio。h>includestdlib.hincludemath。hinclude<string。hdefine N 12#define MAXOfNAME 3 /最多字符個(gè)數(shù)define MAX_VER 100 /最大頂點(diǎn)數(shù)#define StackofNUM 20 /存儲(chǔ)空間初始分配量#define StackforMore 5 / 存儲(chǔ)空間分配增量int TotalOfTerms ; /學(xué)期總數(shù)int MaxScores；typedef struct SqStackint a;int *top;int size; /分配的存儲(chǔ)空間SqStack；typedef

23、 struct ArcNodeint AdjOfV； / 該弧所指向的頂點(diǎn)的位置struct ArcNode next； /指向下一條弧的指針ArcNode；typedef char VertexTypeMAXOfNAME；typedef struct /鏈接表VertexType data； /頂點(diǎn)信息int grades； /存儲(chǔ)學(xué)分信息ArcNode *first； /指向第一條依附該頂點(diǎn)的弧的指針VNode, AdjListMAX_VER; / 頭結(jié)點(diǎn)typedef structAdjList ver； /vertices 存儲(chǔ)課程名int vexnum， arcnum； / 圖的當(dāng)前

24、頂點(diǎn)數(shù)和弧數(shù)ALGraph； /學(xué)分上限int InitStack（SqStack S) /*棧的初始化/S.a= （int *)malloc（StackofNUM sizeof(int）；if （！S。a)exit(1)；S.top =S。a；S.size =StackofNUM；return 1;int StackEmpty（SqStack S） /*判斷棧是否為空/if （S.top = S。a）return 1；else return 0；int Push(SqStack S， int x)/*入棧/if （S。top S。a = S。size)S。a = （int ） realloc

25、 ( S。a， (S.size + StackforMore） sizeof（int)；if ( ！S.a ） exit（1）；S。top =S.a +S.size；S。size +=StackforMore；S。top+ = x；return 1;int Pop（SqStack S， int x) /出棧/if (S。top = S.a)return 0；x = -S.top； return 1;int LocateVex（ALGraph G， VertexType u）/* 查找圖中某個(gè)頂點(diǎn)位置 / int i； for (i = 0；i G。vexnum;+i） if （strcmp（u

26、，G。veri。data)=0）return i； return -1；int CreateGraph(ALGraph G） /采用鄰接表存儲(chǔ)結(jié)構(gòu)/ int i， j， h; VertexType va； ArcNode p； printf（”請(qǐng)輸入教學(xué)計(jì)劃的課程數(shù)： ” ）; scanf（”d",G。vexnum)； getchar（); printf（ "請(qǐng)輸入各個(gè)課程的先修課程的總和(弧總數(shù))： ”）; scanf（”%d"，G。arcnum); getchar（）； printf( "請(qǐng)輸入d個(gè)課程的課程號(hào)(最多d個(gè)字符，字母+數(shù)字如C10)：”

27、， G.vexnum，MAXOfNAME)； for （i = 0；i G。vexnum;+i） scanf(”s”,G。veri。data）; getchar（)； G。veri.first = NULL； printf（"請(qǐng)輸入%d個(gè)課程的學(xué)分值：”，G。vexnum）； for （i = 0；i G.vexnum；+i) scanf（”d”，G。veri。grades);getchar（）； printf("請(qǐng)輸入下列課程的先修課程(無先修課程輸入0 結(jié)束后也輸入0）n”）; for （h=0;h<G。vexnum；+h) / 構(gòu)造表結(jié)點(diǎn)鏈表，利用前插法 pri

28、ntf(”%s的先修課程：”,G。verh。data）； scanf（”s”,va）;getchar（）； while (va0！='0) i = LocateVex（G， va); /弧頭 j = h； /弧尾 p = (ArcNode*)malloc(sizeof(ArcNode）； p>AdjOfV = j； p-next = G.veri.first； / 插在表頭 G。veri。first = p; scanf（”s"，va）; getchar（）； return 1；void Display(ALGraph G) / 輸出圖G的信息*/ int i; Arc

29、Node *p； printf（”有向圖n”）； printf(”%d個(gè)頂點(diǎn)”, G.vexnum）； for (i = 0;i G。vexnum；+i)printf(”%4s”， G。veri.data)； printf（” n%d條弧邊：n”，G。arcnum)； for （i = 0;i G.vexnum;i+） p = G.veri。first; while （p） printf（”s->sn"，G。veri.data,G。verp>AdjOfV。data）； p = pnext; void FindInDegree（ALGraph G， int indegree

30、） /求頂點(diǎn)的入度*/ int i; ArcNode *p； for （i = 0;i G。vexnum；i+） indegreei = 0； for (i = 0；i G。vexnum；i+） p = G。veri.first； while （p） indegreep>AdjOfV+； p = p-next； struct Name char c20；name;void CmpOfStr（VertexType str，struct Name name，int n) /讓C1C12分別與12門課程對(duì)應(yīng)起來/ if(strcmp（str,name0。c）=0)printf（” c程序設(shè)計(jì)”

31、）； if（strcmp（str，name1.c)=0）printf（" 模擬數(shù)字電路"); if（strcmp（str，name2。c)=0)printf(” 數(shù)據(jù)結(jié)構(gòu)”）; if(strcmp（str，name3.c)=0)printf(” C+面向?qū)ο?”）; if（strcmp（str，name4。c）=0）printf（” 大學(xué)英語 "）； if（strcmp（str,name5。c）=0)printf（" 計(jì)算機(jī)組成原理”）; if（strcmp（str,name6。c)=0）printf(" 傳感器原理”)； if（strcmp（

32、str,name7.c)=0）printf（" 軟件工程導(dǎo)論 ")； if（strcmp（str,name8.c）=0）printf（” 高等數(shù)學(xué)"）； if(strcmp（str,name9.c)=0)printf(" 線性代數(shù)"）； if(strcmp(str,name10。c）=0）printf（” 大學(xué)物理基礎(chǔ)"）; if（strcmp(str,name11。c)=0）printf(” 電工技術(shù)");int TopologicalOrder（ALGraph G，AdjList R，struct Name name)int i, k, j = 0， count， indegreeMAX_VER；char q=1,Z=0；SqStack S；ArcNode p;FindInDegree(G， indegree）； / 對(duì)各頂點(diǎn)求入度InitStack(S)； / 初始化棧for (i =