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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(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í)間長度和學(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)系來構(gòu)建個(gè)圖,該圖用鄰接表來存儲(chǔ),鄰接表的頭結(jié)點(diǎn)存儲(chǔ)每門課的信息.3.本程序的目的是為用戶編排課程,根據(jù)用戶輸入的信

2、息來編排出每學(xué)期要學(xué)的課程.（2）測試數(shù)據(jù)：學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從01到12，學(xué)分順序?yàn)?，3，4，3，2，3，4，4，7，5，2，3。先修關(guān)系見教科書圖726。（3）測試結(jié)果（包含正確和錯(cuò)誤的）：正確測試結(jié)果：錯(cuò)誤測試結(jié)果：二. 概要設(shè)計(jì)1. 抽象數(shù)據(jù)類型圖的定義如下: ADT Graph數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點(diǎn)集.數(shù)據(jù)關(guān)系R: R=VR VR=(v,w)|v,wV,(v,w)表示v和w之間存在直接先修關(guān)系基本操作P:void CreatGraph(ALGraph *);void FindInDegree(ALGraph ,

3、 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,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 )

4、;int Pop(SqStack *S, int *e);ADT Stack2. 主程序 int main() /主函數(shù) int numterm; /學(xué)期總數(shù) int uplcredit; /一個(gè)學(xué)期的學(xué)分上限 int selectway; ALGraph G; printf(請輸入學(xué)期總數(shù):n); scanf(%d,&numterm); printf(請輸入一個(gè)學(xué)期的學(xué)分上限:n); scanf(%d,&uplcredit); CreatGraph(&G); printf(請選擇編排策略:1.課程盡可能集中到前幾個(gè)學(xué)期；2.課程盡量均勻分布n);scanf(%d,&selectway); i

5、f(selectway=1) TopologicalSort_1(G,numterm,uplcredit); if(selectway=2) TopologicalSort_2(G,numterm,uplcredit); system(pause); return 0;3. 本程序只有兩個(gè)模塊,調(diào)用關(guān)系簡單. 主程序模塊 拓?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; ArcNode;typedef st

6、ruct VNode char name24; /課程名 int classid; /課程號 int credit; /課程的學(xué)分 int indegree; /該結(jié)點(diǎn)的入度 int state; /該節(jié)點(diǎn)的狀態(tài) ArcNode *firstarc; /指向第一條依附該頂點(diǎn)的弧的指針 VNode,AdjListMAX_VEXTEX_NUM;typedef struct AdjList vertices; int vexnum, arcnum; ALGraph;鄰接表的基本操作：void CreatGraph(ALGraph *);創(chuàng)建鄰接表void FindInDegree(ALGraph ,

7、 int * );求一個(gè)結(jié)點(diǎn)的入度void TopologicalSort_1(ALGraph G,int numterm,int maxcredit);拓?fù)渑判騺砭幣耪n程void TopologicalSort_2(ALGraph G,int numterm,int maxcredit);拓?fù)渑判騺砭幣耪n程2棧的定義：#define STACk_INIT_SIZE 100 /存儲(chǔ)空間的初時(shí)分配量#define STACKINCREMENT 10 /存儲(chǔ)空間的分配增量typedef int ElemType;typedef struct AdjList vertices; int vexnum

8、, arcnum; ALGraph;基本操作：void InitStack (SqStack *S);棧的初始化int StackEmpty(SqStack S);判斷棧是否為空void Push(SqStack *S, int );入棧操作int Pop(SqStack *S, int *e);出棧操作3主程序和其他算法int main() /主函數(shù) int numterm; /學(xué)期總數(shù) int uplcredit; /一個(gè)學(xué)期的學(xué)分上限 int selectway; ALGraph G; printf(請輸入學(xué)期總數(shù):n); scanf(%d,&numterm); printf(請輸入一個(gè)

9、學(xué)期的學(xué)分上限:n); scanf(%d,&uplcredit);CreatGraph(&G);printf(請選擇編排策略:1.課程盡可能集中到前幾個(gè)學(xué)期；2.課程盡量均勻分布n); scanf(%d,&selectway); if(selectway=1) TopologicalSort_1(G,numterm,uplcredit); if(selectway=2) TopologicalSort_2(G,numterm,uplcredit); system(pause); return 0;void CreatGraph(ALGraph *G)/構(gòu)件圖int i, m, n; ArcNo

10、de *p; printf(請輸入需要編排課程總數(shù):n); scanf(%d,&G-vexnum); for( i=1;ivexnum;i+) printf(請輸入課程名n); scanf(%s,&G-); printf(請輸入課程號n); scanf(%d,&G-verticesi.classid); printf(請輸入該課程的學(xué)分n); scanf(%d,&G-verticesi.credit); G-verticesi.indegree=0; G-vertices i.state=NOTSTUDY; G-verticesi.firstarc=NULL; pr

11、intf(請輸入課程先修關(guān)系總數(shù)：); scanf(%d,&G-arcnum); printf(請順序輸入每個(gè)課程先修關(guān)系(先修課程在前并以逗號作為間隔):n); for (i = 1; i arcnum; i+) printf(n請輸入存在先修關(guān)系的兩個(gè)課程的序號:); scanf(%d,%d,&n,&m); while (n G-vexnum | m G-vexnum) printf(輸入的頂點(diǎn)序號不正確 請重新輸入:); scanf(%d,%d,&n,&m); p = (ArcNode*)malloc(sizeof(ArcNode); if (p = NULL) printf(memor

12、y allocation failed,goodbey); exit(1); p-adjvex = m; p-nextarc = G-verticesn.firstarc; G-verticesn.firstarc = p; printf(n建立的鄰接表為:n); /輸出建立好的鄰接表 for(i=1;ivexnum;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 In

13、itStack(SqStack *S) S-base=(int *)malloc(STACK_INIT_SIZE *sizeof(int); if (!S-base) printf(ERROR); exit(1); S-top=S-base; S-stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack *S) if(S-top=S-base) return OK; else return ERROR;void Push(SqStack *S,int e) if(S-top - S-base = S-stacksize) S-base = (int *)

14、 realloc (S-base , (S-stacksize + STACKINCREMENT) * sizeof(int); if(!S-base) printf(ERROR); exit(1); 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); *e = * -S-top; return 0;void FindInDegree(ALGraph G, int indegree)/求圖中

15、各節(jié)點(diǎn)的入度 int i; for (i = 1; i = G.vexnum; i+) indegreei = 0; for (i = 1; i adjvex+; G.verticesi.firstarc = G.verticesi.firstarc-nextarc; void TopologicalSort_1(ALGraph G,int numterm,int uplcredit) FILE *fp; fp=fopen(bianpai.txt,w); ArcNode *p; SqStack S; int indegreeM;/存放各節(jié)點(diǎn)的入度 int i,j, k, m,n; int co

16、unt; /課程編排數(shù)目計(jì)數(shù)器 int sumcredit;/每個(gè)學(xué)期的課程學(xué)分累加器 FindInDegree(G, indegree); 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; for(i=1;i=G.vexnum;i+) /入度為零的節(jié)點(diǎn)入棧，即無先修的課程入棧 if(G.verticesi.indegree=0)&(G.verticesi.state=

17、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); sumcredit = 0; for(i=1;i=G.vexnum;i+)/入度為零的節(jié)點(diǎn)入棧，即無先修的課程入棧 if(G.verticesi.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(!StackEmpty(&S)&(sumc

18、redituplcredit)/棧非空&學(xué)分總數(shù)小于學(xué)分上限 Pop(&S,&j); sumcredit = sumcredit + G.verticesj.credit; if(sumcredit nextarc)/對j號頂點(diǎn)每個(gè)鄰接點(diǎn)的入度減一 G.verticesp-adjvex.indegree-; else Push(&S,j);/將未輸出的節(jié)點(diǎn)重新壓入棧 fprintf(fp,n); printf(n); if(countG.vexnum) printf(n課程編排出錯(cuò)n); else printf(n課程編排成功n); fclose(fp);void TopologicalSor

19、t_2(ALGraph G,int numterm,int uplcredit) FILE *fp; fp=fopen(bianpai.txt,w); ArcNode *p; SqStack S; int indegreeM; int i,j, k, m,n; int maxnum; int sumnum; int count; /課程編排數(shù)目計(jì)數(shù)器 int sumcredit;/每個(gè)學(xué)期的課程學(xué)分累加器 FindInDegree(G, indegree); for (i = 1; i = G.vexnum; i+) G.verticesi.indegree = indegreei; Init

20、Stack(&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)入棧，即無先修的課程入棧 if(G.verticesi.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY; if(!StackEmpty(&S)&(sumcredit=uplcredit)&(sumnum=maxnum) k=

21、k+1; printf(n); printf(第%d個(gè)學(xué)期學(xué)得課程有:,k); sumcredit = 0; sumnum = 0; for(i=1;i=G.vexnum;i+)/入度為零的節(jié)點(diǎn)入棧，即無先修的課程入棧 if(G.verticesi.indegree=0)&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(!StackEmpty(&S)&(sumcredituplcredit)&(sumnummaxnum) /棧非空&學(xué)分總數(shù)小于學(xué)分上限&學(xué)期課程數(shù)目小于學(xué)期最大數(shù)目 Pop(&S,&j);/出棧 sumcredit = sumcre

22、dit + G.verticesj.credit; sumnum = sumnum+1; if(sumcredit = uplcredit)&(sumnum nextarc)/對j號頂點(diǎn)每個(gè)鄰接點(diǎn)的入度減一 G.verticesp-adjvex.indegree-; else Push(&S,j); fprintf(fp,n); printf(n); if(countG.vexnum) printf(課程編排出錯(cuò)n); else printf(課程編排成功n); fclose(fp);流程圖如下所示：void FindInDegree(ALGraph G, int indegree)/求圖中各

23、節(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)的問題及解決方法我們在實(shí)驗(yàn)過程中遇到的最大難題是兩個(gè)課程排序算法的編寫。剛開始的時(shí)候沒有任何的思路，網(wǎng)上也只有拓?fù)渑判虻乃惴?，對于課程設(shè)計(jì)要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學(xué)以及翻閱了一些相關(guān)書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法。（2