數(shù)據(jù)結(jié)構(gòu) 教學(xué)計(jì)劃編制

1、軟 件 學(xué) 院課程設(shè)計(jì)報(bào)告書(shū)課程名稱 數(shù)據(jù)結(jié)構(gòu) 設(shè)計(jì)題目 教學(xué)計(jì)劃編制 2011年 1 月27目 錄1 設(shè)計(jì)時(shí)間12 設(shè)計(jì)目的13設(shè)計(jì)任務(wù)14 設(shè)計(jì)內(nèi)容14.1需求分析14.2總體設(shè)計(jì)24.3詳細(xì)設(shè)計(jì)54.4測(cè)試與分析124.4.1測(cè)試124.4.2分析154.5 附錄155 總結(jié)與展望26參考文獻(xiàn)27成績(jī)?cè)u(píng)定281 設(shè)計(jì)時(shí)間 2011年1月3日至2011年1月6日2 設(shè)計(jì)目的 1）通過(guò)課程設(shè)計(jì)，加深對(duì)數(shù)據(jù)結(jié)構(gòu)這一課程所學(xué)內(nèi)容的進(jìn)一步理解與鞏固。2）通過(guò)課程設(shè)計(jì)，提高程序開(kāi)發(fā)能力，能運(yùn)用合理的控制流程編寫(xiě)清晰高效的程序。3）通過(guò)課程設(shè)計(jì)，提高C程序調(diào)試能力，加強(qiáng)實(shí)踐能力。4）通過(guò)課程設(shè)計(jì)，培養(yǎng)

2、分析問(wèn)題、解決實(shí)際問(wèn)題的能力。5）通過(guò)課程設(shè)計(jì)，培養(yǎng)軟件設(shè)計(jì)能力和開(kāi)發(fā)能力。6）通過(guò)課程設(shè)計(jì)，培養(yǎng)交流、團(tuán)結(jié)協(xié)作精神。7）通過(guò)課程設(shè)計(jì)，加強(qiáng)個(gè)人程序設(shè)計(jì)能力。3設(shè)計(jì)任務(wù)大學(xué)的每個(gè)專業(yè)都要制定教學(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én)課程有哪些先修課程是確定的，可以有任意多門(mén)，也可以沒(méi)有。每門(mén)課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。4 設(shè)計(jì)內(nèi)容4.1需求分析 1、程序所能達(dá)到的功能(1)數(shù)據(jù)結(jié)構(gòu)使用有向圖和棧。 (2)課程先修關(guān)系（圖7.26）課程編

3、號(hào)課程名稱先決條件課程學(xué)分01程序設(shè)計(jì)基礎(chǔ)無(wú)202離散數(shù)學(xué)01303數(shù)據(jù)結(jié)構(gòu)01,02404匯編語(yǔ)言01305語(yǔ)言的設(shè)計(jì)和分析03,04206計(jì)算機(jī)原理11307編譯原理05，03408操作系統(tǒng)03，06409高等數(shù)學(xué)無(wú)710線性代數(shù)09511普通物理09212數(shù)值分析09，10，013 (3)如果輸入的先修課程號(hào)不在該專業(yè)開(kāi)設(shè)的課程序列內(nèi)，則作為錯(cuò)誤處理。2、輸入的形式和輸入值的范圍輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，每門(mén)課的課程號(hào)（固定占3位的字母數(shù)字串）、學(xué)分和直接先修課的課程號(hào)。3、輸出的形式每學(xué)期課程安排4、測(cè)試數(shù)據(jù)： 學(xué)期總數(shù)6，一學(xué)期的學(xué)分上限10，該專業(yè)共開(kāi)課程數(shù)目12，

4、按照?qǐng)D7.26輸入課程名，課程號(hào)，課程學(xué)分。輸出正確的課程編排結(jié)果。4.2總體設(shè)計(jì)1、說(shuō)明本程序中用到的所有抽象數(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 *G)操作結(jié)果：創(chuàng)造圖Gvoid InitStack(SqSttack *S)操作結(jié)果：構(gòu)造一個(gè)空棧Svoid StackEmpty(SqStack *S)初始條件：棧S已存在操作結(jié)果：若棧S為空棧，則返回TRUE，否則FALSEvoid

5、 Push（SqStack *S，int e）初始條件：棧S已存在操作結(jié)果：插入元素e為新的棧頂元素void Pop（SqStack *S，int *e）初始條件：棧S已存在且非空操作結(jié)果：刪除S的棧頂元素，并用e返回其值void FindInDegree(ALGraph G, int indegree)初始條件：拓?fù)渑判蛲瓿刹僮鹘Y(jié)果：構(gòu)造關(guān)鍵路徑的先修關(guān)系網(wǎng)void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)初始條件：圖G已存在操作結(jié)構(gòu)：進(jìn)行拓?fù)渑判?，并完成關(guān)系網(wǎng)的構(gòu)造，使課程盡可能集中在前幾個(gè)學(xué)期void Topologic

6、alSort_2(ALGraph G,int numterm,int uplcredit)初始條件：圖G已存在操作結(jié)果：進(jìn)行拓?fù)渑判?，并完成關(guān)系網(wǎng)的構(gòu)造，使課程盡量均勻分布ADT Graph2、說(shuō)明主程序的流程開(kāi)始輸入學(xué)期總數(shù)，一學(xué)期學(xué)分上限輸出編排結(jié)果結(jié)束構(gòu)造圖表G選擇編排方式拓?fù)渑判?課程盡量均勻分布拓?fù)渑判?課程盡可能集中到前幾個(gè)學(xué)期選擇1選擇2圖4.2-2 主程序流程圖3、說(shuō)明各程序模塊之間的層次（調(diào)用）關(guān)系（圖4.2-3）主程序模塊拓?fù)渑判蚰K順序棧SqStack模塊圖4.2-3各程序模塊之間的層次（調(diào)用）關(guān)系4.3詳細(xì)設(shè)計(jì)1、實(shí)現(xiàn)概要設(shè)計(jì)中定義的所有數(shù)據(jù)類型，對(duì)每個(gè)操作只需要寫(xiě)出偽

7、碼算法1）采用鄰接表存儲(chǔ)結(jié)構(gòu),構(gòu)造沒(méi)有相關(guān)信息的圖G,并儲(chǔ)存鍵入的相關(guān)信息 void CreatGraph(ALGraph *G) 通過(guò)循環(huán)語(yǔ)句完成對(duì)鍵入的課程名稱，課程號(hào)，學(xué)分的存儲(chǔ)，并課程先修關(guān)系建立鄰接表 for (i = 1; i <= G->arcnum; i+) /* 構(gòu)造頂點(diǎn)向量 */ printf("n請(qǐng)輸入存在先修關(guān)系的兩個(gè)課程的序號(hào):"); scanf(&n,&m); while (課程號(hào)不在編入范圍) printf("輸入的頂點(diǎn)序號(hào)不正確 請(qǐng)重新輸入:"); scanf(&n,&m); 分

8、配頭結(jié)點(diǎn)的存儲(chǔ)空間 if (p為空) printf("分配失敗"); 建立鄰接表 printf("建立的鄰接表);for(i=1;i<=G->vexnum;i+) printf("%d:->",G->verticesi.classid); for(p=G->verticesi.firstarc;p!=NULL;p=p->nextarc) printf("%d->",p->adjvex); printf("NULL"); printf("n"

9、;); 2）構(gòu)造一個(gè)空棧Svoid InitStack(SqStack *S) 賦予順序棧足夠的存儲(chǔ)空間 if (!S->base) printf(存儲(chǔ)分配失敗) exit(1); top=base初始棧為空，存儲(chǔ)空間為所分配的足夠的存儲(chǔ)空間3）判斷是否為空棧int StackEmpty(SqStack *S) if(棧S為空棧) return OK; else return ERROR;4）入棧操作void Push(SqStack *S,int e) 插入元素e為新的棧頂元素 if(棧滿)為棧重新分配存儲(chǔ)空間 if(!S->base) printf(存儲(chǔ)分配失敗) exit(1

10、); top=base初始棧為空，存儲(chǔ)空間為所分配的足夠的存儲(chǔ)空間 棧頂指針上移5. 取棧頂操作int Pop(SqStack *S, int *e) 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if(棧頂元素為空) exit(1); 棧頂指針下移并將其值返回給*e6）求圖中各節(jié)點(diǎn)的入度void FindInDegree(ALGraph G, int indegree) for (i = 1; i <= G.vexnum; i+) indegreei = 0; for (i = 1; i <= G.vexnum; i+) while (G.verti

11、cesi.firstarc) indegreeG.verticesi.firstarc->adjvex+; G.verticesi.firstarc = G.verticesi.firstarc->nextarc; 7）有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)若G無(wú)回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K,否則返回ERROR。 int indegreeM;存放各節(jié)點(diǎn)的入度 int count; 課程編排數(shù)目計(jì)數(shù)器 int sumcredit;每個(gè)學(xué)期的課程學(xué)分累加器 Find

12、InDegree(G, indegree);對(duì)各頂點(diǎn)求入度indegree0.vernum-1 for (i = 1; i <= G.vexnum; i+) G.verticesi.indegree=indegreei; 初始化棧 while(count!=G.vexnum && k<=numterm) sumcredit=0; for(無(wú)先修的課程入棧) if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY

13、;避免入度為零節(jié)點(diǎn)重復(fù)入棧 if(棧非空且學(xué)分計(jì)數(shù)器小于學(xué)分上限) k= k+1; printf("第%d個(gè)學(xué)期學(xué)得課程有:n",k); for(i=1;i<=G.vexnum;i+)入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧 if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(棧非空&&學(xué)分總數(shù)小于學(xué)分上限) Pop(&S,&j); sumcredit = sumcredit + G.verticesj.credit;

14、 if(學(xué)分計(jì)數(shù)器小于等于學(xué)分上限) printf(" %s ",G.); 課程數(shù)目累加 對(duì)j號(hào)頂點(diǎn)每個(gè)鄰接點(diǎn)的入度減一 將未輸出的節(jié)點(diǎn)重新壓入棧 if(被編排課程<編排課程總數(shù)) printf(課程編排出錯(cuò)); else printf(課程編排成功); 8) 有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)若G無(wú)回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K,否則返回ERRORvoid TopologicalSort_2(ALGraph G,int numterm,int uplcredit) 頭結(jié)點(diǎn)指針P調(diào)用棧S FindInDegree(G, indegre

15、e); for (i = 1; i <= G.vexnum; i+) G.verticesi.indegree = indegreei; InitStack(&S); 課程編排計(jì)數(shù)器賦值為0 課程名計(jì)數(shù)器賦值 maxnum = G.vexnum/numterm+1; sumnum = 0; while(count!=G.vexnum && k<=numterm) for(i=1;i<=G.vexnum;i+) 入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的if(G.verticesi.indegree=0)&&(G.verticesi.state=NO

16、TSTUDY) Push(&S,i); G.verticesi.state = STUDY; if(棧非空，學(xué)分計(jì)數(shù)器小于學(xué)分上限) k= k+1; printf("第%d個(gè)學(xué)期學(xué)得課程有:",k); sumcredit = 0; sumnum = 0; for(i=1;i<=G.vexnum;i+)入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧 if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)Push(&S,i); while(棧非空&&學(xué)分總數(shù)小于學(xué)分上限&am

17、p;&學(xué)期課程數(shù)目小于學(xué)期最大數(shù)目) 出棧 積分器累加 sumnum = sumnum+1; if(sumcredit <= uplcredit)&&(sumnum <= maxnum) printf(" %s ",G.); 編排計(jì)數(shù)器累加 for(對(duì)j號(hào)頂點(diǎn)每個(gè)鄰接點(diǎn)的入度減一) G.verticesp->adjvex.indegree-; else Push(&S,j); if(課程未全部編排，有剩余) printf(課程編排出錯(cuò)) else printf(課程編排成功) 2、對(duì)主程序和其它主

18、要函數(shù)寫(xiě)出偽碼算法int main() int numterm; /*學(xué)期總數(shù)*/ int uplcredit; /*一個(gè)學(xué)期的學(xué)分上限*/ int selectway; 建立鄰接表 scanf("%d",&numterm); 輸入學(xué)期總數(shù) scanf("%d",&uplcredit); 輸入一個(gè)學(xué)期的學(xué)分上限 printf("選擇編排策略:1.課程盡可能集中到前幾個(gè)學(xué)期；2.課程盡量均勻分布"); if(選擇1) TopologicalSort_1(G,numterm,uplcredit); if(選擇2) Topo

19、logicalSort_2(G,numterm,uplcredit); return 0;3、畫(huà)出函數(shù)的調(diào)用關(guān)系圖（圖4.3-3）main( )GreatGraph（）InitStack（）FindInDegree（）圖4.3-3函數(shù)的調(diào)用關(guān)系圖FindInDegree（）InitStack（）Topologicalsort_1（）Topologicalsort_2（）4.4測(cè)試與分析4.4.1測(cè)試學(xué)期總數(shù): 6 一學(xué)期的學(xué)分上限: 10 該專業(yè)共開(kāi)課程數(shù)目: 121.鍵入學(xué)期總數(shù)，學(xué)分上限，比安排課程總數(shù)2.輸入課程名，課程號(hào)及相應(yīng)學(xué)分3. 輸入課程先修關(guān)系總數(shù) 4. 順序輸入先修關(guān)系 5.

20、輸出鄰接表6.選擇編排策略1，輸出編排結(jié)果7. 選擇編排策略2，輸出編排結(jié)果8.錯(cuò)誤運(yùn)行：當(dāng)輸入兩個(gè)相同課程號(hào)的不同課程9.運(yùn)行結(jié)果4.4.2分析1、調(diào)試過(guò)程中遇到的問(wèn)題是如何解決的以及對(duì)設(shè)計(jì)與實(shí)現(xiàn)的回顧討論和分析在實(shí)驗(yàn)過(guò)程中遇到的最大難題是兩個(gè)課程排序算法的編寫(xiě)。剛開(kāi)始的時(shí)候沒(méi)有任何的思路，網(wǎng)上也只有拓?fù)渑判虻乃惴ǎ瑢?duì)于課程設(shè)計(jì)要求的排序算法沒(méi)有任何頭緒。經(jīng)過(guò)請(qǐng)教老師和同學(xué)以及翻閱了一些相關(guān)書(shū)籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過(guò)三天的修改，終于寫(xiě)出了符合要求的排序算法。2、算法的時(shí)間復(fù)雜度和空間復(fù)雜度的分析本程序算法的時(shí)間復(fù)雜度為O(n)，空間復(fù)雜度為O(2n) 4.5 附錄源程序

21、代碼及必要注釋/* Note:Your choice is C IDE */#include "stdio.h"#include "string.h"#include "malloc.h"#include "stdlib.h"/* 圖的鄰接表存儲(chǔ)表示 */#define MAX_VERTEX_NUM 100 /*最大課程總數(shù)*/#define STACK_INIT_SIZE 100 /*存儲(chǔ)空間的初時(shí)分配量*/#define STACKINCREMENT 10 /*存儲(chǔ)空間的分配增量*/#define OK 1#d

22、efine ERROR 0#define M 100#define NOTSTUDY -1#define STUDY 1typedef struct ArcNode int adjvex; /* 該弧所指向的頂點(diǎn)的位置 */ struct ArcNode *nextarc; /* 指向下一條弧的指針 */ ArcNode;typedef struct VNode char name24; /*課程名*/ int classid; /*課程號(hào)*/ int credit; /*課程的學(xué)分*/ int indegree; /*該結(jié)點(diǎn)的入度*/ int state; /*該節(jié)點(diǎn)的狀態(tài)*/ ArcNod

23、e *firstarc; /* 第一個(gè)表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指針 */VNode,AdjList100;typedef int ElemType;typedef struct AdjList vertices; int vexnum, arcnum; /* 圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) */ ALGraph;typedef structElemType *base; /* 在棧構(gòu)造之前和銷毀之后，base的值為NULL */ ElemType *top; /*棧頂指針*/ int stacksize; /* 當(dāng)前已分配的存儲(chǔ)空間，以元素為單位 */ SqStack; /* 順序棧 *

24、/ void CreatGraph(ALGraph *G) /* 采用鄰接表存儲(chǔ)結(jié)構(gòu),構(gòu)造沒(méi)有相關(guān)信息的圖G,并儲(chǔ)存鍵入的相關(guān)信息 */ int i, m, n; ArcNode *p; printf("請(qǐng)輸入需要編排課程總數(shù):n"); scanf("%d",&G->vexnum); for(i=1;i<=G->vexnum;i+) /* 構(gòu)造頂點(diǎn)向量 */ printf("請(qǐng)輸入課程名n"); scanf("%s",&G->); printf(&

25、quot;請(qǐng)輸入課程號(hào)n"); scanf("%d",&G->verticesi.classid); printf("請(qǐng)輸入該課程的學(xué)分n"); scanf("%d",&G->verticesi.credit); G->verticesi.indegree=G->vertices i.state=NOTSTUDY; G->verticesi.firstarc=NULL; printf("請(qǐng)輸入課程先修關(guān)系總數(shù)："); scanf("%d",

26、&G->arcnum); printf("請(qǐng)順序輸入每個(gè)課程先修關(guān)系(先修課程在前并以逗號(hào)作為間隔):n"); for (i = 1; i <= G->arcnum; i+) /* 構(gòu)造頂點(diǎn)向量 */ printf("n請(qǐng)輸入存在先修關(guān)系的兩個(gè)課程的序號(hào):"); scanf("%d,%d",&n,&m); while (n < 0 | n > G->vexnum | m < 0 | m > G->vexnum) printf("輸入的頂點(diǎn)序號(hào)不正確

27、 請(qǐng)重新輸入:"); scanf("%d,%d",&n,&m); p = (ArcNode*)malloc(sizeof(ArcNode); if (p = NULL) printf("memory allocation failed,goodbey"); exit(1); p->adjvex = m; p->nextarc = G->verticesn.firstarc; G->verticesn.firstarc = p; printf("n建立的鄰接表為:n"); /*輸出建立好

28、的鄰接表*/ for(i=1;i<=G->vexnum;i+) printf("%d:->",G->verticesi.classid); for(p=G->verticesi.firstarc;p!=NULL;p=p->nextarc) printf("%d->",p->adjvex); printf("NULL"); printf("n"); /* 順序棧的基本操作 */ void InitStack(SqStack *S) /* 構(gòu)造一個(gè)空棧S */S->

29、base=(int *)malloc(STACK_INIT_SIZE *sizeof(int); if (!S->base) printf("ERROR"); /* 存儲(chǔ)分配失敗 */ exit(1); S->top=S->base; S->stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack *S) /* 若棧S為空棧，則返回TRUE，否則 返回FALSE */ if(S->top=S->base) return OK; else return ERROR;void Push(SqStack

30、*S,int e) /* 插入元素e為新的棧頂元素 */ if(S->top - S->base >= S->stacksize) S->base = (int *) realloc (S->base , (S->stacksize + STACKINCREMENT) * sizeof(int); if(!S->base) printf("ERROR");/* 存儲(chǔ)分配失敗 */ exit(1); S->top = S->base + S->stacksize; S->stacksize += STAC

31、KINCREMENT; *S->top+ = e;int Pop(SqStack *S, int *e)/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ if(S->top = S->base) exit(1); *e = * -S->top; return 0;void FindInDegree(ALGraph G, int indegree)/*求圖中各節(jié)點(diǎn)的入度*/ int i; for (i = 1; i <= G.vexnum; i+) indegreei = 0; for (i = 1; i <= G.vex

32、num; i+) while (G.verticesi.firstarc) indegreeG.verticesi.firstarc->adjvex+; G.verticesi.firstarc = G.verticesi.firstarc->nextarc; void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)/* 有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)。若G無(wú)回路,則輸出G的頂點(diǎn)的一個(gè)拓?fù)湫蛄胁⒎祷豋K,否則返回ERROR。*/ int i=0,j, k; ArcNode *p; SqStack S; int indegre

33、eM;/*存放各節(jié)點(diǎn)的入度*/ int count; /*課程編排數(shù)目計(jì)數(shù)器*/ int sumcredit;/*每個(gè)學(xué)期的課程學(xué)分累加器*/ FindInDegree(G, indegree); /* 對(duì)各頂點(diǎn)求入度indegree0.vernum-1 */ for (i = 1; i <= G.vexnum; i+) G.verticesi.indegree=indegreei; InitStack(&S); /* 初始化棧 */ count=0; k=0; while(count!=G.vexnum && k<=numterm) sumcredit=0

34、; for(i=1;i<=G.vexnum;i+) /*入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧*/ if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY;/*避免入度為零節(jié)點(diǎn)重復(fù)入棧*/ if(!StackEmpty(&S)&&(sumcredit<=uplcredit) k= k+1; printf("n"); printf("第%d個(gè)學(xué)期學(xué)得課程有:n",k

35、); sumcredit = 0; for(i=1;i<=G.vexnum;i+)/*入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧*/ if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(!StackEmpty(&S)&&(sumcredit<uplcredit)/*棧非空&&學(xué)分總數(shù)小于學(xué)分上限*/ Pop(&S,&j); sumcredit = sumcredit + G.verticesj.credit;

36、if(sumcredit <= uplcredit) printf(" %s ",G.); count+; for(p=G.verticesj.firstarc;p;p=p->nextarc)/*對(duì)j號(hào)頂點(diǎn)每個(gè)鄰接點(diǎn)的入度減一*/ G.verticesp->adjvex.indegree-; else Push(&S,j);/*將未輸出的節(jié)點(diǎn)重新壓入棧*/ printf("n"); if(count<G.vexnum) printf("n課程編排出錯(cuò)n"); else pri

37、ntf("n課程編排成功n"); void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) FILE *fp; int indegreeM; int i,j, k; int maxnum; int sumnum; int count; /*課程編排數(shù)目計(jì)數(shù)器*/ int sumcredit=0;/*每個(gè)學(xué)期的課程學(xué)分累加器*/ ArcNode *p; SqStack S; FindInDegree(G, indegree); for (i = 1; i <= G.vexnum; i+) G.vertices

38、i.indegree = indegreei; InitStack(&S); count=0; k=0; maxnum = G.vexnum/numterm+1; sumnum = 0; while(count!=G.vexnum && k<=numterm) for(i=1;i<=G.vexnum;i+) /*入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧*/if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STU

39、DY; if(!StackEmpty(&S)&&(sumcredit<=uplcredit)&&(sumnum<=maxnum) k= k+1; printf("n"); printf("第%d個(gè)學(xué)期學(xué)得課程有:",k); sumcredit = 0; sumnum = 0; for(i=1;i<=G.vexnum;i+)/*入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧*/ if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)

40、Push(&S,i); while(!StackEmpty(&S)&&(sumcredit<uplcredit)&&(sumnum<maxnum) /*棧非空&&學(xué)分總數(shù)小于學(xué)分上限&&學(xué)期課程數(shù)目小于學(xué)期最大數(shù)目*/ Pop(&S,&j);/*出棧*/ sumcredit = sumcredit + G.verticesj.credit; sumnum = sumnum+1; if(sumcredit <= uplcredit)&&(sumnum <= maxnum) printf(" %s ",G.); count+; for(p=G.verticesj.firstarc;p;p=p->nextarc)/*對(duì)j號(hào)頂點(diǎn)每個(gè)鄰接點(diǎn)的入度減一*/ G.verticesp->adjvex.indegree-; else Push(&S,j); printf("n"); if(count<G.vexnum) printf("課程編排出錯(cuò)