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

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

2、.（2）測試數(shù)據(jù)：學期總數(shù)：6；學分上限：10；該專業(yè)共開設(shè)12門課，課程號從01到12，學分順序為2，3，4，3，2，3，4，4，7，5，2，3。先修關(guān)系見教科書圖726。（3）測試結(jié)果（包含正確和錯誤的）：正確測試結(jié)果：錯誤測試結(jié)果：二. 概要設(shè)計1. 抽象數(shù)據(jù)類型圖的定義如下: ADT Graph數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點集.數(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ù)對象: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;   /學期總數(shù)    int uplcredit; /一個學期的學分上限    int selectway;    ALGraph G;        printf("請輸入學期總數(shù):n");    scanf("%d",&numterm);    printf("請輸入一個學期的學分上限

6、:n");    scanf("%d",&uplcredit);    CreatGraph(&G);    printf("請選擇編排策略:1.課程盡可能集中到前幾個學期；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. 本程序只有兩個模塊,調(diào)用關(guān)系簡單.      主程序模塊 

8、60;           拓撲排序模塊三詳細設(shè)計1頭結(jié)點，表結(jié)點，鄰接表的定義#define MAX_VERTEX_NUM 100 /最大課程總數(shù)typedef struct ArcNode       int adjvex;        struct ArcNode *nextarc;        A

9、rcNode;typedef struct VNode       char name24;       /課程名         int classid;      /課程號        int credit;       &

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

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

12、建鄰接表void FindInDegree(ALGraph , int * );求一個結(jié)點的入度void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);拓撲排序來編排課程void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);拓撲排序來編排課程2棧的定義：#define STACk_INIT_SIZE 100 /存儲空間的初時分配量#define STACKINCREMENT 10    /存儲空間的分配增量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;   /學期總數(shù)    int uplcredit; /一個學期的學分上限    int selectway;    ALGraph G;    printf("請輸入學期總數(shù):n");&#

15、160;   scanf("%d",&numterm);    printf("請輸入一個學期的學分上限:n");    scanf("%d",&uplcredit);CreatGraph(&G);printf("請選擇編排策略:1.課程盡可能集中到前幾個學期；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("請輸入需要編排課程總數(shù):n");    scanf("%d",&G->vexnum);    for( i=1;i<=G->vexnum;i+)           

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

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

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

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

22、< 0 | m > G->vexnum)                    printf("輸入的頂點序號不正確 請重新輸入:");            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é)點的入度     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é)點的入度    int i,j, k, m,n;    int count; /課程編排數(shù)目計數(shù)器    int sumcredit;/每個學期的課程學分累加器        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é)點入棧，即無先修的課程入棧             if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)      

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

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

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

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

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

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)/對j號頂點每個鄰接點的入度減一                   

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

48、                      fprintf(fp,"n");        printf("n");    if(count<G.vexnum)        printf("n課程編排出錯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ù)目計數(shù)器    int sumcredit;/每個學期的課程學分累加器        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é)點入棧，即無先修的課程入棧                    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個學期學得課程有:",k);                     sumcredit = 0;                 

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

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

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

61、;     /棧非空&&學分總數(shù)小于學分上限&&學期課程數(shù)目小于學期最大數(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)/對j號頂點每個鄰接點的入度減一                                &#

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

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

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