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

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告 題目：教學(xué)計(jì)劃編制 一. 需求分析（1）實(shí)驗(yàn)內(nèi)容和實(shí)驗(yàn)?zāi)康模?.大學(xué)的每個(gè)專業(yè)都要編制教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限都相等。每個(gè)專業(yè)開設(shè)的課程都是確定的，而且課程的開設(shè)時(shí)間的安排必須滿足先修關(guān)系。每個(gè)課程的先修關(guān)系都是確定的，可以有任意多門，也可以沒有。每一門課程恰好一個(gè)學(xué)期。試在這樣的情況下設(shè)置一個(gè)教學(xué)計(jì)劃編制程序。2.在大學(xué)的某個(gè)專業(yè)中選取幾個(gè)課程作為頂點(diǎn),通過各門課的先修關(guān)系來(lái)構(gòu)建個(gè)圖,該圖用鄰接表來(lái)存儲(chǔ),鄰接表的頭結(jié)點(diǎn)存儲(chǔ)每門課的信息.3.本程序的目的是為用戶編排課程,根據(jù)用戶輸入的信息來(lái)編排出每學(xué)期要學(xué)的課程

2、.（2）測(cè)試數(shù)據(jù)：學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號(hào)從01到12，學(xué)分順序?yàn)?，3，4，3，2，3，4，4，7，5，2，3。先修關(guān)系見教科書圖726。（3）測(cè)試結(jié)果（包含正確和錯(cuò)誤的）：正確測(cè)試結(jié)果：錯(cuò)誤測(cè)試結(jié)果：二. 概要設(shè)計(jì)1. 抽象數(shù)據(jù)類型圖的定義如下: ADT Graph數(shù)據(jù)對(duì)象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點(diǎn)集.數(shù)據(jù)關(guān)系R:           R=VR        

3、   VR=(v,w)|v,wV,(v,w)表示v和w之間存在直接先修關(guān)系基本操作P:void CreatGraph(ALGraph *);void FindInDegree(ALGraph , int * );void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);ADT Graph棧的定義:ADT Stack   數(shù)據(jù)對(duì)象:D=ai|aiElemSet,i=1

4、,2,n,n>=0     數(shù)據(jù)關(guān)系:R1=ai-1 ai|ai-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 Stack2. 主程序 int main()            /主函數(shù)    in

5、t numterm;   /學(xué)期總數(shù)    int uplcredit; /一個(gè)學(xué)期的學(xué)分上限    int selectway;    ALGraph G;        printf("請(qǐng)輸入學(xué)期總數(shù):n");    scanf("%d",&numterm);    printf("請(qǐng)輸入一個(gè)學(xué)期的學(xué)分上限

6、:n");    scanf("%d",&uplcredit);    CreatGraph(&G);    printf("請(qǐng)選擇編排策略:1.課程盡可能集中到前幾個(gè)學(xué)期；2.課程盡量均勻分布n");  scanf("%d",&selectway);        if(selectway=1)   &

7、#160;    TopologicalSort_1(G,numterm,uplcredit);    if(selectway=2)      TopologicalSort_2(G,numterm,uplcredit);    system("pause");    return 0;3. 本程序只有兩個(gè)模塊,調(diào)用關(guān)系簡(jiǎn)單.      主程序模塊 

8、60;           拓?fù)渑判蚰K三詳細(xì)設(shè)計(jì)1頭結(jié)點(diǎn)，表結(jié)點(diǎn)，鄰接表的定義#define MAX_VERTEX_NUM 100 /最大課程總數(shù)typedef struct ArcNode       int adjvex;        struct ArcNode *nextarc;        A

9、rcNode;typedef struct VNode       char name24;       /課程名         int classid;      /課程號(hào)        int credit;       &

10、#160; /課程的學(xué)分        int indegree;       /該結(jié)點(diǎn)的入度        int state;          /該節(jié)點(diǎn)的狀態(tài)        ArcNode *firstarc; /指向第一條依附該頂點(diǎn)

11、的弧的指針        VNode,AdjListMAX_VEXTEX_NUM;typedef struct        AdjList vertices;        int vexnum, arcnum;        ALGraph;鄰接表的基本操作：void CreatGraph(ALGraph *);創(chuàng)

12、建鄰接表void FindInDegree(ALGraph , int * );求一個(gè)結(jié)點(diǎn)的入度void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);拓?fù)渑判騺?lái)編排課程void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);拓?fù)渑判騺?lái)編排課程2棧的定義：#define STACk_INIT_SIZE 100 /存儲(chǔ)空間的初時(shí)分配量#define STACKINCREMENT 10    /存儲(chǔ)空間的分配增量typedef int Ele

13、mType;typedef struct        AdjList vertices;        int vexnum, arcnum;        ALGraph;基本操作：void InitStack (SqStack *S);棧的初始化int StackEmpty(SqStack S);判斷棧是否為空void Push(SqStack *S, int );入棧操作int

14、Pop(SqStack *S, int *e);出棧操作3主程序和其他算法int main()           /主函數(shù) int numterm;   /學(xué)期總數(shù)    int uplcredit; /一個(gè)學(xué)期的學(xué)分上限    int selectway;    ALGraph G;    printf("請(qǐng)輸入學(xué)期總數(shù):n");&#

15、160;   scanf("%d",&numterm);    printf("請(qǐng)輸入一個(gè)學(xué)期的學(xué)分上限:n");    scanf("%d",&uplcredit);CreatGraph(&G);printf("請(qǐng)選擇編排策略:1.課程盡可能集中到前幾個(gè)學(xué)期；2.課程盡量均勻分布n");    scanf("%d",&selectway); &

16、#160;  if(selectway=1)        TopologicalSort_1(G,numterm,uplcredit);    if(selectway=2)      TopologicalSort_2(G,numterm,uplcredit);    system("pause");    return 0;void CreatGrap

17、h(ALGraph *G)/構(gòu)件圖   int i, m, n;    ArcNode *p;    printf("請(qǐng)輸入需要編排課程總數(shù):n");    scanf("%d",&G->vexnum);    for( i=1;i<=G->vexnum;i+)           

18、 printf("請(qǐng)輸入課程名n");        scanf("%s",&G->);         printf("請(qǐng)輸入課程號(hào)n");        scanf("%d",&G->verticesi.classid);   &

19、#160;     printf("請(qǐng)輸入該課程的學(xué)分n");        scanf("%d",&G->verticesi.credit);         G->verticesi.indegree=0;        G->vertices i.state=NOTSTUDY;

20、        G->verticesi.firstarc=NULL;        printf("請(qǐng)輸入課程先修關(guān)系總數(shù)：");    scanf("%d",&G->arcnum);     printf("請(qǐng)順序輸入每個(gè)課程先修關(guān)系(先修課程在前并以逗號(hào)作為間隔):n");    for (i

21、 = 1; i <= G->arcnum; i+)            printf("n請(qǐng)輸入存在先修關(guān)系的兩個(gè)課程的序號(hào):");        scanf("%d,%d",&n,&m);        while (n < 0 | n > G->vexnum | m

22、< 0 | m > G->vexnum)                    printf("輸入的頂點(diǎn)序號(hào)不正確 請(qǐng)重新輸入:");            scanf("%d,%d",&n,&m);   

23、;             p = (ArcNode*)malloc(sizeof(ArcNode);        if (p = NULL)                    printf("memory allocati

24、on failed,goodbey");            exit(1);                p->adjvex = m;        p->nextarc = G->verticesn.firstarc;  &

25、#160;     G->verticesn.firstarc = p;        printf("n建立的鄰接表為:n");          /輸出建立好的鄰接表    for(i=1;i<=G->vexnum;i+)          

26、60; printf("%d:->",G->verticesi.classid);        for(p=G->verticesi.firstarc;p!=NULL;p=p->nextarc)        printf("%d->",p->adjvex);        printf("NULL");

27、60;       printf("n");    void InitStack(SqStack *S)   S->base=(int *)malloc(STACK_INIT_SIZE *sizeof(int);     if (!S->base)        printf("ERROR");    &#

28、160;   exit(1);         S->top=S->base;     S->stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack *S)    if(S->top=S->base)        return OK;    else  &

29、#160;     return ERROR;void Push(SqStack *S,int e)       if(S->top - S->base >= S->stacksize)            S->base = (int *) realloc (S->base , (S->stacksize + STACKINCREMENT) * sizeof(i

30、nt);        if(!S->base)                     printf("ERROR");            exit(1);      

31、          S->top = S->base + S->stacksize;        S->stacksize += STACKINCREMENT;        *S->top+ = e;int Pop(SqStack *S, int *e)    if(S->top = S->base) exit(1);&#

32、160;   *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;

33、i <= G.vexnum; i+)            while (G.verticesi.firstarc)                    indegreeG.verticesi.firstarc->adjvex+;      &#

34、160;     G.verticesi.firstarc = G.verticesi.firstarc->nextarc;            void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)     FILE *fp;    fp=fopen("bianpai.txt","w&

35、quot;);    ArcNode *p;        SqStack S;   int indegreeM;/存放各節(jié)點(diǎn)的入度    int i,j, k, m,n;    int count; /課程編排數(shù)目計(jì)數(shù)器    int sumcredit;/每個(gè)學(xué)期的課程學(xué)分累加器        FindInDegree(G, indegree)

36、;    for (i = 1; i <= G.vexnum; i+)      G.verticesi.indegree=indegreei;    InitStack(&S);    count=0;    k=0;     while(count!=G.vexnum && k<=numterm)      

37、      sumcredit=0;        for(i=1;i<=G.vexnum;i+) /入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧             if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)      

38、;                         Push(&S,i);              G.verticesi.state = STUDY;/避免入度為零節(jié)點(diǎn)重復(fù)入棧       

39、0;             if(!StackEmpty(&S)&&(sumcredit<=uplcredit)                     k= k+1;          

40、  printf("n");            printf("第%d個(gè)學(xué)期學(xué)得課程有:n",k);            sumcredit = 0;                 

41、 for(i=1;i<=G.vexnum;i+)/入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧                 if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)                 

42、   Push(&S,i);                    while(!StackEmpty(&S)&&(sumcredit<uplcredit)/棧非空&&學(xué)分總數(shù)小于學(xué)分上限                

43、60;            Pop(&S,&j);                sumcredit = sumcredit + G.verticesj.credit;               if(sumcredit

44、 <= uplcredit)                                   printf(" %s ",G.);         &#

45、160;          fprintf(fp," %s ",G.);                                   

46、     count+;                   for(p=G.verticesj.firstarc;p;p=p->nextarc)/對(duì)j號(hào)頂點(diǎn)每個(gè)鄰接點(diǎn)的入度減一                   

47、0;    G.verticesp->adjvex.indegree-;                                else Push(&S,j);/將未輸出的節(jié)點(diǎn)重新壓入棧      

48、                      fprintf(fp,"n");        printf("n");    if(count<G.vexnum)        printf("n課程編排出錯(cuò)n&qu

49、ot;);    else               printf("n課程編排成功n");        fclose(fp);void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)    FILE *fp;    fp=fopen(&quo

50、t;bianpai.txt","w");    ArcNode *p;        SqStack S;     int indegreeM;     int i,j, k, m,n;            int maxnum;       int sum

51、num;    int count; /課程編排數(shù)目計(jì)數(shù)器    int sumcredit;/每個(gè)學(xué)期的課程學(xué)分累加器        FindInDegree(G, indegree);    for (i = 1; i <= G.vexnum; i+)            G.verticesi.indegree = indegreei;

52、0;   InitStack(&S);    count=0;    k=0;       maxnum = G.vexnum/numterm+1;     sumnum = 0;             while(count!=G.vexnum && k<=numterm)  

53、;              for(i=1;i<=G.vexnum;i+) /入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧                    if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)      

54、60;                                    Push(&S,i);                        &#

55、160;   G.verticesi.state = STUDY;                               if(!StackEmpty(&S)&&(sumcredit<=uplcredit)&&(sumnum<=maxnum)     

56、                            k= k+1;                     printf("n");       

57、              printf("第%d個(gè)學(xué)期學(xué)得課程有:",k);                     sumcredit = 0;                 

58、0;   sumnum = 0;                                  for(i=1;i<=G.vexnum;i+)/入度為零的節(jié)點(diǎn)入棧，即無(wú)先修的課程入棧             

59、            if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)                             Push(&S,i);     

60、                             while(!StackEmpty(&S)&&(sumcredit<uplcredit)&&(sumnum<maxnum)               

61、;     /棧非空&&學(xué)分總數(shù)小于學(xué)分上限&&學(xué)期課程數(shù)目小于學(xué)期最大數(shù)目                                               Pop(&

62、S,&j);/出棧                         sumcredit = sumcredit + G.verticesj.credit;                       

63、    sumnum = sumnum+1;                                      if(sumcredit <= uplcredit)&&(sumnum <= maxnum) 

64、0;                                                       printf(" %s ",G.verticesj.na

65、me);                                                   fprintf(fp," %s ",G.); 

66、60;                              count+;                               

67、0;                  for(p=G.verticesj.firstarc;p;p=p->nextarc)/對(duì)j號(hào)頂點(diǎn)每個(gè)鄰接點(diǎn)的入度減一                                &#

68、160;      G.verticesp->adjvex.indegree-;                                                else Push

69、(&S,j);                                     fprintf(fp,"n");        printf("n");    if(count<

70、G.vexnum)        printf("課程編排出錯(cuò)n");    else                printf("課程編排成功n");        fclose(fp);流程圖如下所示：void FindInDegree(ALGraph G, int indegree)/求圖中各節(jié)點(diǎn)的入度（如下左圖）void CreatGraph(ALGraph *G)/構(gòu)件圖（如下右圖） void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) /有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)(如下左圖)void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) /有向圖G采用鄰接表存儲(chǔ)結(jié)構(gòu)（如下右圖）主函數(shù)：void main()四調(diào)試分析：（1）實(shí)驗(yàn)過程中出現(xiàn)的問題及解決方法我們?cè)趯?shí)驗(yàn)過程中遇到的最大難題是兩個(gè)課程排序算法的