




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
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)系來構(gòu)建個(gè)圖,該圖用鄰接表來存儲(chǔ),鄰接表的頭結(jié)點(diǎn)存儲(chǔ)每門課的信息.3.本程序的目的是為用戶編排課程,根據(jù)用戶輸入的信息來編排出每學(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ù)渑判騺砭幣耪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 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)入棧,即無先修的課程入棧 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)入棧,即無先修的課程入棧 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)入棧,即無先修的課程入棧 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)入棧,即無先修的課程入棧
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è)課程排序算法的
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 高端制造車間租賃及技術(shù)研發(fā)合同
- 老妖消防課件
- 美術(shù)說課課件詳細(xì)
- 美術(shù)大師課件介紹
- 關(guān)于生產(chǎn)安全事故應(yīng)急預(yù)案的說法正確的有
- 涉爆粉塵企業(yè)安全檢查表
- 工程項(xiàng)目管理論文安全
- 企業(yè)安全生產(chǎn)的八大主體責(zé)任
- 安全生產(chǎn)百日攻堅(jiān)戰(zhàn)
- 小店運(yùn)營(yíng)教程培訓(xùn)課件
- GB/T 20946-2007起重用短環(huán)鏈驗(yàn)收總則
- GB/T 18391.3-2009信息技術(shù)元數(shù)據(jù)注冊(cè)系統(tǒng)(MDR)第3部分:注冊(cè)系統(tǒng)元模型與基本屬性
- GA/T 935-2011法庭科學(xué)槍彈痕跡檢驗(yàn)鑒定文書編寫規(guī)范
- 濟(jì)源幼兒園等級(jí)及管理辦法
- 湖北省黃石市基層診所醫(yī)療機(jī)構(gòu)衛(wèi)生院社區(qū)衛(wèi)生服務(wù)中心村衛(wèi)生室信息
- DB44-T 2163-2019山地自行車賽場(chǎng)服務(wù) 基本要求-(高清現(xiàn)行)
- DB15T 933-2015 內(nèi)蒙古地區(qū)極端高溫、低溫和降雨標(biāo)準(zhǔn)
- 工傷責(zé)任保險(xiǎn)單
- 圍堰施工監(jiān)理實(shí)施細(xì)則
- 《世界經(jīng)濟(jì)史》課程教學(xué)大綱
- 小學(xué)語文一到六年級(jí)生字表
評(píng)論
0/150
提交評(píng)論