數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報(bào)告-教學(xué)計(jì)劃編制(共18頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)實(shí)驗(yàn)實(shí) 驗(yàn) 報(bào) 告課程名稱數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)實(shí)驗(yàn)課程編號(hào)實(shí)驗(yàn)項(xiàng)目名稱教學(xué)計(jì)劃編制學(xué)號(hào)年級(jí)姓名專業(yè)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)生所在學(xué)院計(jì)算機(jī)學(xué)院指導(dǎo)教師楊靜實(shí)驗(yàn)室名稱地點(diǎn)21B276哈爾濱工程大學(xué)實(shí)驗(yàn)報(bào)告五實(shí)驗(yàn)課名稱：數(shù)據(jù)結(jié)構(gòu)與程序設(shè)計(jì)實(shí)驗(yàn)實(shí)驗(yàn)名稱：教學(xué)計(jì)劃編制班級(jí)：學(xué)號(hào)：姓名：時(shí)間：2016.05.03一、問題描述學(xué)歷進(jìn)修需要學(xué)生在一定的時(shí)間內(nèi)完成一定的課程學(xué)習(xí)，每一門課有一定的學(xué)分，修滿學(xué)分，可獲取相應(yīng)的學(xué)歷。因?yàn)橛行┱n程內(nèi)容是另一些課程的學(xué)習(xí)基礎(chǔ)，所以課程學(xué)習(xí)之間存有一定的先后次序。如：某學(xué)歷的計(jì)算機(jī)專業(yè)需要學(xué)習(xí) 的課程及課程之間的關(guān)系如表 1 所示。表

2、 1 計(jì)算機(jī)專業(yè)進(jìn)修課程課程進(jìn)修關(guān)系圖課程編號(hào)課程名稱學(xué)分C1程序設(shè)計(jì)基礎(chǔ)2C2離散數(shù)學(xué)3C3數(shù)據(jù)結(jié)構(gòu)4C4匯編語言3C5程序設(shè)計(jì)與分析2C6計(jì)算機(jī)原理3C7編譯原理4C8操作系統(tǒng)4C9高等數(shù)學(xué)7C10線性代數(shù)5C11普通物理2C12數(shù)值分析3C13軟件工程3C14數(shù)據(jù)庫原理3 本設(shè)計(jì)的主要任務(wù)是根據(jù)需要完成的課程的先修關(guān)系、每學(xué)期開設(shè)的課程總數(shù)及總的學(xué)習(xí)時(shí)間，制定出教學(xué)計(jì)劃。需事先的基本功能如下。a. 課程進(jìn)修目錄的讀入。b. 課程進(jìn)修目錄的編輯，如課程增加、刪除、信息修改等。c. 滿足一定條件的教學(xué)計(jì)劃的輸出。二、數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)1. 以鄰接表存儲(chǔ)課程名和學(xué)分#define MAX_VERTE

3、X_NUM 100typedef struct ArcNode /弧結(jié)構(gòu) int adjvex; /該弧所指向的頂點(diǎn)的位置; struct ArcNode *nextarc; /指向下一條弧的指針 InfoType *info; /弧的權(quán)值指針ArcNode; /表結(jié)點(diǎn)typedef struct /頭節(jié)點(diǎn) VertexType data; /頂點(diǎn)信息 ArcNode *firstarc; /第一個(gè)表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指針VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices,vertices2; /分別存課

4、程名和學(xué)分 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int kind; /圖的種類標(biāo)志ALGraph; /圖2. 拓?fù)渑判驎r(shí)為了避免重復(fù)檢測(cè)入度為0的頂點(diǎn),用棧暫存所有入度為0的頂點(diǎn)typedef struct SqStack SElemType *base; SElemType *top; int stacksize;SqStack;三、算法設(shè)計(jì)1. 利用鄰接表作為存儲(chǔ)結(jié)構(gòu)，構(gòu)造課程先后關(guān)系的AOV網(wǎng)int LocateVex(ALGraph G, VertexType u) /返回頂點(diǎn)u在圖G中的位置 int i; for(i=0; i<G.vexnum; +i

5、) if(strcmp(u, G.verticesi.data)=0) return i; return -1;Status CreateGraph(ALGraph &G) /構(gòu)造圖 int i,j,k; VertexType v1,v2; /頂點(diǎn)信息,字符串類型 ArcNode *p; /指向第一條依附某頂點(diǎn)的弧的指針 printf("請(qǐng)輸入教學(xué)計(jì)劃的課程數(shù): "); /課程數(shù)即為頂點(diǎn)數(shù) scanf("%d",& G.vexnum); printf("請(qǐng)輸入課程先修關(guān)系數(shù)(弧的數(shù)目): "); scanf("

6、;%d",& G.arcnum); printf("請(qǐng)輸入%d個(gè)課程的名稱(以字符代替):n",G.vexnum); for(i=0; i<G.vexnum; +i) scanf("%s",G.verticesi.data); /存儲(chǔ)課程名 G.verticesi.firstarc=NULL; printf("請(qǐng)輸入%d個(gè)課程的學(xué)分值:n", (G).vexnum); for(i=0; i<G.vexnum; +i) scanf("%s",G.vertices2i.data);/存儲(chǔ)學(xué)

7、分 printf("請(qǐng)順序輸入每條弧的弧尾和弧頭(以空格作為間隔):n"); for(k=0; k<G.arcnum; +k) scanf("%s%s",v1,v2); i=LocateVex(G,v1); j=LocateVex(G,v2); p = (ArcNode*)malloc(sizeof(ArcNode); /新建一個(gè)弧節(jié)點(diǎn) p->adjvex = j; /指向下一個(gè)頂點(diǎn)的位置 p->info = NULL; p->nextarc = G.verticesi.firstarc; G.verticesi.firstarc

8、 = p; return OK;2. 在拓?fù)渑判驎r(shí)為了避免重復(fù)檢測(cè)入度為0的頂點(diǎn),需要用棧暫存所有入度為0的頂點(diǎn)，以下為棧的相關(guān)操作Status InitStack(SqStack *S)/構(gòu)造一個(gè)空棧 (*S).base=(SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK;void ClearStack(SqStack *S) /清空棧 S->t

9、op=S->base;Status StackEmpty(SqStack S) / 判斷棧是否為空 if(S.top=S.base) return TRUE; else return FALSE;Status Pop(SqStack *S,SElemType *e) if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK;Status Push(SqStack *S,SElemType e) if(*S).top-(*S).base>=(*S).stacksize) (*S).base=(SElemType *)re

10、alloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); (*S).top=(*S).base+(*S).stacksize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return OK;3. 拓?fù)渑判虿⑤敵稣n程設(shè)計(jì)a.在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之b.從圖中刪除該頂點(diǎn)和所有以它為尾的弧重復(fù)a,b直至全部頂點(diǎn)均已輸出，或者不存在無前驅(qū)的頂點(diǎn)(圖中存在環(huán))Status TopologicalSort(A

11、LGraph G) /輸出G頂點(diǎn)的拓?fù)渑判蚪Y(jié)果 int i,k,count; int indegreeMAX_VERTEX_NUM; /indegree數(shù)組存放頂點(diǎn)入度 bool has = false; SqStack S; pathone a; pathtwo b; ArcNode * p; FindInDegree(G,indegree); /對(duì)各頂點(diǎn)求入度indegree0.vernum-1 InitStack(&S); for(i=0;i<G.vexnum;+i) if(!indegreei) Push(&S,i); /入度為0者入棧 count = 0; /對(duì)

12、輸出頂點(diǎn)計(jì)數(shù) while(!StackEmpty(S) Pop(&S,&i); ai=*G.verticesi.data; /課程名； bi=*G.vertices2i.data; /學(xué)分； printf("課程%s學(xué)分%s ",G.verticesi.data,G.vertices2i.data); +count; for(p=G.verticesi.firstarc; p; p=p->nextarc) k=p->adjvex; if(!(-indegreek) /對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度-1 Push(&S,k); if(coun

13、t < G.vexnum) /圖中有不存在前驅(qū)的頂點(diǎn) printf("此有向圖有回路n"); return ERROR; else printf("為一個(gè)拓?fù)湫蛄小n"); has=true; printf("各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻（輸入1）n"); printf("用盡可能短的時(shí)間完成教學(xué)計(jì)劃（輸入2）？n"); int pattern; printf("請(qǐng)選擇(1 or 2):"); scanf("%d",&pattern); FindInDegree

14、(G,indegree); /對(duì)各頂點(diǎn)求入度indegree0.vernum-1 ClearStack(&S); printf("=n"); printf("教學(xué)計(jì)劃如下：n"); int xq = 1; /學(xué)期數(shù); int xfh; /學(xué)分和； int now=0; int top = G.vexnum / term_num ; /平均每學(xué)期課程數(shù)； int pjxf = sum(G) / term_num ; /每學(xué)期平均學(xué)分； while(xq <= term_num + 1) int result20; /某個(gè)學(xué)期的課程； int

15、m = 0; xfh = 0; now=0; /當(dāng)前學(xué)期課程數(shù) ； for(i=0;i<G.vexnum;+i) if(0 = indegreei) Push(&S,i); if(xq = term_num+1 && !StackEmpty(S) printf("還有課程未安排！n"); while(!StackEmpty(S) && xq <= term_num) int xf; Pop(&S,&i); /彈出棧頂元素； xf = atoi(G.vertices2i.data); /atoi:字符串轉(zhuǎn)換成

16、整型數(shù), xf:學(xué)分; xfh = xfh+xf; now+; if(xfh > credit_lim) ClearStack(&S); break; if(pattern = 1) if(xq!=term_num/2 && now>top) ClearStack(&S); /該操作使程序跳出此內(nèi)層的while循環(huán); now = 0; break; if(pattern = 2) if(xq!=1 && xq!=term_num/2 && xq!=term_num/2-1 && now>top)

17、ClearStack(&S); now = 0; break; indegreei-; /減為-1,避免被再次計(jì)入； for(p=G.verticesi.firstarc; p; p=p->nextarc) k=p->adjvex; indegreek-; if(indegreek=0) Push(&S,k); resultm=i; m+; if(xq <= term_num) printf("第%d個(gè)學(xué)期的課程為：",xq); for(int j=0; j<m; j+) printf("課程%s ",G.vert

18、icesresultj.data); printf("n"); xq+; ClearStack(&S); printf("=n"); return OK;4其他輔助操作void Display(ALGraph G) /輸出圖的信息 int i; ArcNode * p; switch(G.kind) case DG: printf("有向圖n"); printf("%d個(gè)頂點(diǎn)：n",G.vexnum); for(i=0;i<G.vexnum;+i) printf("%s ", G.

19、verticesi.data); printf("n%d條弧:n",G.arcnum); for(i=0;i<G.vexnum;i+) p=G.verticesi.firstarc; while(p) printf("%s%s ", G.verticesi.data, G.verticesp->adjvex.data); p=p->nextarc; printf("n"); void FindInDegree(ALGraph G,int indegree) /求頂點(diǎn)的入度 int i; ArcNode *p; for

20、(i=0;i<G.vexnum;i+) indegreei=0; for(i=0;i<G.vexnum;i+) p=G.verticesi.firstarc; while(p) indegreep->adjvex+; p=p->nextarc; Status sum(ALGraph G) /求大學(xué)所有課程總學(xué)分； int z=0; for(int i=0; i < G.vexnum; i+) z += atoi(G.vertices2i.data); return z;四、界面設(shè)計(jì)輸入?yún)?shù)包括：學(xué)期總數(shù)，一學(xué)期的學(xué)分上限，課程數(shù)，弧的數(shù)目，每門課的課程號(hào)、學(xué)分和直

21、接先修課的關(guān)系。 輸出各門課程所對(duì)應(yīng)的學(xué)分，以及每學(xué)期各門課程的安排。所有輸入輸出均以提示給出。五、運(yùn)行測(cè)試與分析1輸入學(xué)期總數(shù)，學(xué)分上限，課程數(shù)，弧的數(shù)目2輸入每門課的課程號(hào)，學(xué)分，與直接先修課的關(guān)系(以弧的形式給出)3構(gòu)造圖并輸出圖的信息4按各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻地制定教學(xué)計(jì)劃5按盡可能短的時(shí)間完成學(xué)習(xí)，制定教學(xué)計(jì)劃6當(dāng)存在回路時(shí)輸出提示六、實(shí)驗(yàn)收獲與思考 通過實(shí)際的編程，鞏固了圖的鄰接表存儲(chǔ)。拓?fù)渑判虻戎R(shí)，同時(shí)在編程過程中發(fā)現(xiàn)了自己的不足，遇到了很多語法錯(cuò)誤及邏輯錯(cuò)誤，通過不斷的調(diào)試解決問題，使我對(duì)編程有了更加深入的體會(huì)和認(rèn)識(shí)。七、附錄(源代碼)#include <

22、stdio.h>#include <stdlib.h>#include <string.h>#include <math.h>#include <process.h>#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1typedef int Status; / Status是函數(shù)的返回類型typedef int Boolean;#define MAX_NAME 10 /頂點(diǎn)字符串的最大長度#define MAX_CLASS_NUM 100i

23、nt Z=0;int X=0;int term_num, credit_lim, q=1;typedef int InfoType; /權(quán)值typedef char VertexTypeMAX_NAME; /字符串類型#define MAX_VERTEX_NUM 100typedef enumDGGraphKind; /有向圖,有向網(wǎng),無向圖,無向網(wǎng)typedef struct ArcNode /弧結(jié)構(gòu) int adjvex; /該弧所指向的頂點(diǎn)的位置; struct ArcNode *nextarc; /指向下一條弧的指針 InfoType *info; /弧的權(quán)值指針ArcNode; /表

24、結(jié)點(diǎn)typedef struct /頭節(jié)點(diǎn) VertexType data; /頂點(diǎn)信息 ArcNode *firstarc; /第一個(gè)表結(jié)點(diǎn)的地址,指向第一條依附該頂點(diǎn)的弧的指針VNode, AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices,vertices2; /分別存課程名和學(xué)分 int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù) int kind; /圖的種類標(biāo)志ALGraph; /圖int LocateVex(ALGraph G, VertexType u) /返回頂點(diǎn)u在圖G中的位置 int i; for(i=0;

25、 i<G.vexnum; +i) if(strcmp(u, G.verticesi.data)=0) return i; return -1;Status CreateGraph(ALGraph &G) /構(gòu)造圖 int i,j,k; VertexType v1,v2; /頂點(diǎn)信息,字符串類型 ArcNode *p; /指向第一條依附某頂點(diǎn)的弧的指針 printf("請(qǐng)輸入教學(xué)計(jì)劃的課程數(shù): "); /課程數(shù)即為頂點(diǎn)數(shù) scanf("%d",& G.vexnum); printf("請(qǐng)輸入課程先修關(guān)系數(shù)(弧的數(shù)目): &q

26、uot;); scanf("%d",& G.arcnum); printf("請(qǐng)輸入%d個(gè)課程的名稱(以字符代替):n",G.vexnum); for(i=0; i<G.vexnum; +i) scanf("%s",G.verticesi.data); /存儲(chǔ)課程名 G.verticesi.firstarc=NULL; printf("請(qǐng)輸入%d個(gè)課程的學(xué)分值:n", (G).vexnum); for(i=0; i<G.vexnum; +i) scanf("%s",G.ver

27、tices2i.data);/存儲(chǔ)學(xué)分 printf("請(qǐng)順序輸入每條弧的弧尾和弧頭(以空格作為間隔):n"); for(k=0; k<G.arcnum; +k) scanf("%s%s",v1,v2); i=LocateVex(G,v1); j=LocateVex(G,v2); p = (ArcNode*)malloc(sizeof(ArcNode); /新建一個(gè)弧節(jié)點(diǎn) p->adjvex = j; /指向下一個(gè)頂點(diǎn)的位置 p->info = NULL; p->nextarc = G.verticesi.firstarc; G.

28、verticesi.firstarc = p; return OK;void Display(ALGraph G) /輸出圖的信息 int i; ArcNode * p; switch(G.kind) case DG: printf("有向圖n"); printf("%d個(gè)頂點(diǎn)：n",G.vexnum); for(i=0;i<G.vexnum;+i) printf("%s ", G.verticesi.data); printf("n%d條弧:n",G.arcnum); for(i=0;i<G.vexn

29、um;i+) p=G.verticesi.firstarc; while(p) printf("%s%s ", G.verticesi.data, G.verticesp->adjvex.data); p=p->nextarc; printf("n"); void FindInDegree(ALGraph G,int indegree) /求頂點(diǎn)的入度 int i; ArcNode *p; for(i=0;i<G.vexnum;i+) indegreei=0; for(i=0;i<G.vexnum;i+) p=G.vertices

30、i.firstarc; while(p) indegreep->adjvex+; p=p->nextarc; typedef int SElemType;#define STACK_INIT_SIZE 10#define STACKINCREMENT 2typedef struct SqStack /為了避免重復(fù)檢測(cè)入度為0的頂點(diǎn),暫存所有入度為0的頂點(diǎn) SElemType *base; SElemType *top; int stacksize;SqStack;Status InitStack(SqStack *S)/構(gòu)造一個(gè)空棧 (*S).base=(SElemType *)m

31、alloc(STACK_INIT_SIZE*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); (*S).top=(*S).base; (*S).stacksize=STACK_INIT_SIZE; return OK;void ClearStack(SqStack *S) /清空棧 S->top=S->base;Status StackEmpty(SqStack S) / 判斷棧是否為空 if(S.top=S.base) return TRUE; else return FALSE;Status Pop(SqStack *S,SEl

32、emType *e) if(*S).top=(*S).base) return ERROR; *e=*-(*S).top; return OK;Status Push(SqStack *S,SElemType e) if(*S).top-(*S).base>=(*S).stacksize) (*S).base=(SElemType *)realloc(*S).base,(*S).stacksize+STACKINCREMENT)*sizeof(SElemType); if(!(*S).base) exit(OVERFLOW); (*S).top=(*S).base+(*S).stacks

33、ize; (*S).stacksize+=STACKINCREMENT; *(*S).top)+=e; return OK;Status sum(ALGraph G) /求大學(xué)所有課程總學(xué)分； int z=0; for(int i=0; i < G.vexnum; i+) z += atoi(G.vertices2i.data); return z;typedef int pathoneMAX_CLASS_NUM;typedef int pathtwoMAX_CLASS_NUM;Status TopologicalSort(ALGraph G) /輸出G頂點(diǎn)的拓?fù)渑判蚪Y(jié)果 int i,k

34、,count; int indegreeMAX_VERTEX_NUM; /indegree數(shù)組存放頂點(diǎn)入度 Boolean has = FALSE; SqStack S; pathone a; pathtwo b; ArcNode * p; FindInDegree(G,indegree); /對(duì)各頂點(diǎn)求入度indegree0.vernum-1 InitStack(&S); for(i=0;i<G.vexnum;+i) if(!indegreei) Push(&S,i); /入度為0者入棧 count = 0; /對(duì)輸出頂點(diǎn)計(jì)數(shù) while(!StackEmpty(S)

35、Pop(&S,&i); ai=*G.verticesi.data; /課程名； bi=*G.vertices2i.data; /學(xué)分； printf("課程%s學(xué)分%s ",G.verticesi.data,G.vertices2i.data); +count; for(p=G.verticesi.firstarc; p; p=p->nextarc) k=p->adjvex; if(!(-indegreek) /對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度-1 Push(&S,k); if(count < G.vexnum) /圖中有不存在前驅(qū)的頂

36、點(diǎn) printf("此有向圖有回路n"); return ERROR; else printf("為一個(gè)拓?fù)湫蛄?。nn"); has=TRUE; printf("各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻（輸入1）n"); printf("用盡可能短的時(shí)間完成教學(xué)計(jì)劃（輸入2）？n"); int pattern; printf("請(qǐng)選擇(1 or 2):"); scanf("%d",&pattern); FindInDegree(G,indegree); /對(duì)各頂點(diǎn)求入度indegr

37、ee0.vernum-1 ClearStack(&S); printf("=n"); printf("教學(xué)計(jì)劃如下：n"); int xq = 1; /學(xué)期數(shù); int xfh; /學(xué)分和； int now=0; int top = G.vexnum / term_num ; /平均每學(xué)期課程數(shù)； int pjxf = sum(G) / term_num ; /每學(xué)期平均學(xué)分； while(xq <= term_num + 1) int result20; /某個(gè)學(xué)期的課程； int m = 0; xfh = 0; now=0; /當(dāng)前學(xué)期課程數(shù) ； for(i=0;i<G.vexnum;+i) if(0 = indegreei) Push(&S,i); if(xq = term_num+1 && !StackEmpty(S) printf("還有課程未安排！n"); while(!StackEmpty(S) && xq <= term_num) int xf; Pop(&S,&am