數(shù)據(jù)結構 教學計劃編制

1、軟 件 學 院課程設計報告書課程名稱 數(shù)據(jù)結構 設計題目 教學計劃編制 2011年 1 月27目 錄1 設計時間12 設計目的13設計任務14 設計內(nèi)容14.1需求分析14.2總體設計24.3詳細設計54.4測試與分析124.4.1測試124.4.2分析154.5 附錄155 總結與展望26參考文獻27成績評定281 設計時間 2011年1月3日至2011年1月6日2 設計目的 1）通過課程設計，加深對數(shù)據(jù)結構這一課程所學內(nèi)容的進一步理解與鞏固。2）通過課程設計，提高程序開發(fā)能力，能運用合理的控制流程編寫清晰高效的程序。3）通過課程設計，提高C程序調(diào)試能力，加強實踐能力。4）通過課程設計，培養(yǎng)

2、分析問題、解決實際問題的能力。5）通過課程設計，培養(yǎng)軟件設計能力和開發(fā)能力。6）通過課程設計，培養(yǎng)交流、團結協(xié)作精神。7）通過課程設計，加強個人程序設計能力。3設計任務大學的每個專業(yè)都要制定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。4 設計內(nèi)容4.1需求分析 1、程序所能達到的功能(1)數(shù)據(jù)結構使用有向圖和棧。 (2)課程先修關系（圖7.26）課程編

3、號課程名稱先決條件課程學分01程序設計基礎無202離散數(shù)學01303數(shù)據(jù)結構01,02404匯編語言01305語言的設計和分析03,04206計算機原理11307編譯原理05，03408操作系統(tǒng)03，06409高等數(shù)學無710線性代數(shù)09511普通物理09212數(shù)值分析09，10，013 (3)如果輸入的先修課程號不在該專業(yè)開設的課程序列內(nèi)，則作為錯誤處理。2、輸入的形式和輸入值的范圍輸入?yún)?shù)包括：學期總數(shù)，一學期的學分上限，每門課的課程號（固定占3位的字母數(shù)字串）、學分和直接先修課的課程號。3、輸出的形式每學期課程安排4、測試數(shù)據(jù)： 學期總數(shù)6，一學期的學分上限10，該專業(yè)共開課程數(shù)目12，

4、按照圖7.26輸入課程名，課程號，課程學分。輸出正確的課程編排結果。4.2總體設計1、說明本程序中用到的所有抽象數(shù)據(jù)類型的定義ADT Graph數(shù)據(jù)對象V:V是具有相同特性的數(shù)據(jù)元素的集合,稱為頂點集.數(shù)據(jù)關系R: R=VRVR=(v,w)|v,wV,(v,w)表示v和w之間存在直接先修關系基本操作P:void CreatGraph(ALGraph *G)操作結果：創(chuàng)造圖Gvoid InitStack(SqSttack *S)操作結果：構造一個空棧Svoid StackEmpty(SqStack *S)初始條件：棧S已存在操作結果：若棧S為空棧，則返回TRUE，否則FALSEvoid

5、 Push（SqStack *S，int e）初始條件：棧S已存在操作結果：插入元素e為新的棧頂元素void Pop（SqStack *S，int *e）初始條件：棧S已存在且非空操作結果：刪除S的棧頂元素，并用e返回其值void FindInDegree(ALGraph G, int indegree)初始條件：拓撲排序完成操作結果：構造關鍵路徑的先修關系網(wǎng)void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)初始條件：圖G已存在操作結構：進行拓撲排序，并完成關系網(wǎng)的構造，使課程盡可能集中在前幾個學期void Topologic

6、alSort_2(ALGraph G,int numterm,int uplcredit)初始條件：圖G已存在操作結果：進行拓撲排序，并完成關系網(wǎng)的構造，使課程盡量均勻分布ADT Graph2、說明主程序的流程開始輸入學期總數(shù)，一學期學分上限輸出編排結果結束構造圖表G選擇編排方式拓撲排序2課程盡量均勻分布拓撲排序1課程盡可能集中到前幾個學期選擇1選擇2圖4.2-2 主程序流程圖3、說明各程序模塊之間的層次（調(diào)用）關系（圖4.2-3）主程序模塊拓撲排序模塊順序棧SqStack模塊圖4.2-3各程序模塊之間的層次（調(diào)用）關系4.3詳細設計1、實現(xiàn)概要設計中定義的所有數(shù)據(jù)類型，對每個操作只需要寫出偽

7、碼算法1）采用鄰接表存儲結構,構造沒有相關信息的圖G,并儲存鍵入的相關信息 void CreatGraph(ALGraph *G) 通過循環(huán)語句完成對鍵入的課程名稱，課程號，學分的存儲，并課程先修關系建立鄰接表 for (i = 1; i <= G->arcnum; i+) /* 構造頂點向量 */ printf("n請輸入存在先修關系的兩個課程的序號:"); scanf(&n,&m); while (課程號不在編入范圍) printf("輸入的頂點序號不正確 請重新輸入:"); scanf(&n,&m); 分

8、配頭結點的存儲空間 if (p為空) printf("分配失敗"); 建立鄰接表 printf("建立的鄰接表);for(i=1;i<=G->vexnum;i+) printf("%d:->",G->verticesi.classid); for(p=G->verticesi.firstarc;p!=NULL;p=p->nextarc) printf("%d->",p->adjvex); printf("NULL"); printf("n"

9、;); 2）構造一個空棧Svoid InitStack(SqStack *S) 賦予順序棧足夠的存儲空間 if (!S->base) printf(存儲分配失敗) exit(1); top=base初始棧為空，存儲空間為所分配的足夠的存儲空間3）判斷是否為空棧int StackEmpty(SqStack *S) if(棧S為空棧) return OK; else return ERROR;4）入棧操作void Push(SqStack *S,int e) 插入元素e為新的棧頂元素 if(棧滿)為棧重新分配存儲空間 if(!S->base) printf(存儲分配失敗) exit(1

10、); top=base初始棧為空，存儲空間為所分配的足夠的存儲空間 棧頂指針上移5. 取棧頂操作int Pop(SqStack *S, int *e) 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR if(棧頂元素為空) exit(1); 棧頂指針下移并將其值返回給*e6）求圖中各節(jié)點的入度void FindInDegree(ALGraph G, int indegree) for (i = 1; i <= G.vexnum; i+) indegreei = 0; for (i = 1; i <= G.vexnum; i+) while (G.verti

11、cesi.firstarc) indegreeG.verticesi.firstarc->adjvex+; G.verticesi.firstarc = G.verticesi.firstarc->nextarc; 7）有向圖G采用鄰接表存儲結構void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)若G無回路,則輸出G的頂點的一個拓撲序列并返回OK,否則返回ERROR。 int indegreeM;存放各節(jié)點的入度 int count; 課程編排數(shù)目計數(shù)器 int sumcredit;每個學期的課程學分累加器 Find

12、InDegree(G, indegree);對各頂點求入度indegree0.vernum-1 for (i = 1; i <= G.vexnum; i+) G.verticesi.indegree=indegreei; 初始化棧 while(count!=G.vexnum && k<=numterm) sumcredit=0; for(無先修的課程入棧) if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY

13、;避免入度為零節(jié)點重復入棧 if(棧非空且學分計數(shù)器小于學分上限) k= k+1; printf("第%d個學期學得課程有:n",k); for(i=1;i<=G.vexnum;i+)入度為零的節(jié)點入棧，即無先修的課程入棧 if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(棧非空&&學分總數(shù)小于學分上限) Pop(&S,&j); sumcredit = sumcredit + G.verticesj.credit;

14、 if(學分計數(shù)器小于等于學分上限) printf(" %s ",G.); 課程數(shù)目累加 對j號頂點每個鄰接點的入度減一 將未輸出的節(jié)點重新壓入棧 if(被編排課程<編排課程總數(shù)) printf(課程編排出錯); else printf(課程編排成功); 8) 有向圖G采用鄰接表存儲結構若G無回路,則輸出G的頂點的一個拓撲序列并返回OK,否則返回ERRORvoid TopologicalSort_2(ALGraph G,int numterm,int uplcredit) 頭結點指針P調(diào)用棧S FindInDegree(G, indegre

15、e); for (i = 1; i <= G.vexnum; i+) G.verticesi.indegree = indegreei; InitStack(&S); 課程編排計數(shù)器賦值為0 課程名計數(shù)器賦值 maxnum = G.vexnum/numterm+1; sumnum = 0; while(count!=G.vexnum && k<=numterm) for(i=1;i<=G.vexnum;i+) 入度為零的節(jié)點入棧，即無先修的if(G.verticesi.indegree=0)&&(G.verticesi.state=NO

16、TSTUDY) Push(&S,i); G.verticesi.state = STUDY; if(棧非空，學分計數(shù)器小于學分上限) k= k+1; printf("第%d個學期學得課程有:",k); sumcredit = 0; sumnum = 0; for(i=1;i<=G.vexnum;i+)入度為零的節(jié)點入棧，即無先修的課程入棧 if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)Push(&S,i); while(棧非空&&學分總數(shù)小于學分上限&am

17、p;&學期課程數(shù)目小于學期最大數(shù)目) 出棧 積分器累加 sumnum = sumnum+1; if(sumcredit <= uplcredit)&&(sumnum <= maxnum) printf(" %s ",G.); 編排計數(shù)器累加 for(對j號頂點每個鄰接點的入度減一) G.verticesp->adjvex.indegree-; else Push(&S,j); if(課程未全部編排，有剩余) printf(課程編排出錯) else printf(課程編排成功) 2、對主程序和其它主

18、要函數(shù)寫出偽碼算法int main() int numterm; /*學期總數(shù)*/ int uplcredit; /*一個學期的學分上限*/ int selectway; 建立鄰接表 scanf("%d",&numterm); 輸入學期總數(shù) scanf("%d",&uplcredit); 輸入一個學期的學分上限 printf("選擇編排策略:1.課程盡可能集中到前幾個學期；2.課程盡量均勻分布"); if(選擇1) TopologicalSort_1(G,numterm,uplcredit); if(選擇2) Topo

19、logicalSort_2(G,numterm,uplcredit); return 0;3、畫出函數(shù)的調(diào)用關系圖（圖4.3-3）main( )GreatGraph（）InitStack（）FindInDegree（）圖4.3-3函數(shù)的調(diào)用關系圖FindInDegree（）InitStack（）Topologicalsort_1（）Topologicalsort_2（）4.4測試與分析4.4.1測試學期總數(shù): 6 一學期的學分上限: 10 該專業(yè)共開課程數(shù)目: 121.鍵入學期總數(shù)，學分上限，比安排課程總數(shù)2.輸入課程名，課程號及相應學分3. 輸入課程先修關系總數(shù) 4. 順序輸入先修關系 5.

20、輸出鄰接表6.選擇編排策略1，輸出編排結果7. 選擇編排策略2，輸出編排結果8.錯誤運行：當輸入兩個相同課程號的不同課程9.運行結果4.4.2分析1、調(diào)試過程中遇到的問題是如何解決的以及對設計與實現(xiàn)的回顧討論和分析在實驗過程中遇到的最大難題是兩個課程排序算法的編寫。剛開始的時候沒有任何的思路，網(wǎng)上也只有拓撲排序的算法，對于課程設計要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學以及翻閱了一些相關書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法。2、算法的時間復雜度和空間復雜度的分析本程序算法的時間復雜度為O(n)，空間復雜度為O(2n) 4.5 附錄源程序

21、代碼及必要注釋/* Note:Your choice is C IDE */#include "stdio.h"#include "string.h"#include "malloc.h"#include "stdlib.h"/* 圖的鄰接表存儲表示 */#define MAX_VERTEX_NUM 100 /*最大課程總數(shù)*/#define STACK_INIT_SIZE 100 /*存儲空間的初時分配量*/#define STACKINCREMENT 10 /*存儲空間的分配增量*/#define OK 1#d

22、efine ERROR 0#define M 100#define NOTSTUDY -1#define STUDY 1typedef struct ArcNode int adjvex; /* 該弧所指向的頂點的位置 */ struct ArcNode *nextarc; /* 指向下一條弧的指針 */ ArcNode;typedef struct VNode char name24; /*課程名*/ int classid; /*課程號*/ int credit; /*課程的學分*/ int indegree; /*該結點的入度*/ int state; /*該節(jié)點的狀態(tài)*/ ArcNod

23、e *firstarc; /* 第一個表結點的地址,指向第一條依附該頂點的弧的指針 */VNode,AdjList100;typedef int ElemType;typedef struct AdjList vertices; int vexnum, arcnum; /* 圖的當前頂點數(shù)和弧數(shù) */ ALGraph;typedef structElemType *base; /* 在棧構造之前和銷毀之后，base的值為NULL */ ElemType *top; /*棧頂指針*/ int stacksize; /* 當前已分配的存儲空間，以元素為單位 */ SqStack; /* 順序棧 *

24、/ void CreatGraph(ALGraph *G) /* 采用鄰接表存儲結構,構造沒有相關信息的圖G,并儲存鍵入的相關信息 */ int i, m, n; ArcNode *p; printf("請輸入需要編排課程總數(shù):n"); scanf("%d",&G->vexnum); for(i=1;i<=G->vexnum;i+) /* 構造頂點向量 */ printf("請輸入課程名n"); scanf("%s",&G->); printf(&

25、quot;請輸入課程號n"); scanf("%d",&G->verticesi.classid); printf("請輸入該課程的學分n"); scanf("%d",&G->verticesi.credit); G->verticesi.indegree=G->vertices i.state=NOTSTUDY; G->verticesi.firstarc=NULL; printf("請輸入課程先修關系總數(shù)："); scanf("%d",

26、&G->arcnum); printf("請順序輸入每個課程先修關系(先修課程在前并以逗號作為間隔):n"); for (i = 1; i <= G->arcnum; i+) /* 構造頂點向量 */ printf("n請輸入存在先修關系的兩個課程的序號:"); scanf("%d,%d",&n,&m); while (n < 0 | n > G->vexnum | m < 0 | m > G->vexnum) printf("輸入的頂點序號不正確

27、 請重新輸入:"); scanf("%d,%d",&n,&m); p = (ArcNode*)malloc(sizeof(ArcNode); if (p = NULL) printf("memory allocation failed,goodbey"); exit(1); p->adjvex = m; p->nextarc = G->verticesn.firstarc; G->verticesn.firstarc = p; printf("n建立的鄰接表為:n"); /*輸出建立好

28、的鄰接表*/ for(i=1;i<=G->vexnum;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 InitStack(SqStack *S) /* 構造一個空棧S */S->

29、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) /* 若棧S為空棧，則返回TRUE，否則 返回FALSE */ if(S->top=S->base) return OK; else return ERROR;void Push(SqStack

30、*S,int e) /* 插入元素e為新的棧頂元素 */ if(S->top - S->base >= S->stacksize) S->base = (int *) realloc (S->base , (S->stacksize + STACKINCREMENT) * sizeof(int); if(!S->base) printf("ERROR");/* 存儲分配失敗 */ exit(1); S->top = S->base + S->stacksize; S->stacksize += STAC

31、KINCREMENT; *S->top+ = e;int Pop(SqStack *S, int *e)/* 若棧不空，則刪除S的棧頂元素，用e返回其值，并返回OK；否則返回ERROR */ if(S->top = S->base) exit(1); *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; i <= G.vex

32、num; i+) while (G.verticesi.firstarc) indegreeG.verticesi.firstarc->adjvex+; G.verticesi.firstarc = G.verticesi.firstarc->nextarc; void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)/* 有向圖G采用鄰接表存儲結構。若G無回路,則輸出G的頂點的一個拓撲序列并返回OK,否則返回ERROR。*/ int i=0,j, k; ArcNode *p; SqStack S; int indegre

33、eM;/*存放各節(jié)點的入度*/ int count; /*課程編排數(shù)目計數(shù)器*/ int sumcredit;/*每個學期的課程學分累加器*/ FindInDegree(G, indegree); /* 對各頂點求入度indegree0.vernum-1 */ 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

34、; for(i=1;i<=G.vexnum;i+) /*入度為零的節(jié)點入棧，即無先修的課程入棧*/ if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STUDY;/*避免入度為零節(jié)點重復入棧*/ if(!StackEmpty(&S)&&(sumcredit<=uplcredit) k= k+1; printf("n"); printf("第%d個學期學得課程有:n",k

35、); sumcredit = 0; for(i=1;i<=G.vexnum;i+)/*入度為零的節(jié)點入棧，即無先修的課程入棧*/ if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); while(!StackEmpty(&S)&&(sumcredit<uplcredit)/*棧非空&&學分總數(shù)小于學分上限*/ Pop(&S,&j); sumcredit = sumcredit + G.verticesj.credit;

36、if(sumcredit <= uplcredit) printf(" %s ",G.); count+; for(p=G.verticesj.firstarc;p;p=p->nextarc)/*對j號頂點每個鄰接點的入度減一*/ G.verticesp->adjvex.indegree-; else Push(&S,j);/*將未輸出的節(jié)點重新壓入棧*/ printf("n"); if(count<G.vexnum) printf("n課程編排出錯n"); else pri

37、ntf("n課程編排成功n"); void TopologicalSort_2(ALGraph G,int numterm,int uplcredit) FILE *fp; int indegreeM; int i,j, k; int maxnum; int sumnum; int count; /*課程編排數(shù)目計數(shù)器*/ int sumcredit=0;/*每個學期的課程學分累加器*/ ArcNode *p; SqStack S; FindInDegree(G, indegree); for (i = 1; i <= G.vexnum; i+) G.vertices

38、i.indegree = indegreei; InitStack(&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é)點入棧，即無先修的課程入棧*/if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY) Push(&S,i); G.verticesi.state = STU

39、DY; if(!StackEmpty(&S)&&(sumcredit<=uplcredit)&&(sumnum<=maxnum) k= k+1; printf("n"); printf("第%d個學期學得課程有:",k); sumcredit = 0; sumnum = 0; for(i=1;i<=G.vexnum;i+)/*入度為零的節(jié)點入棧，即無先修的課程入棧*/ if(G.verticesi.indegree=0)&&(G.verticesi.state=NOTSTUDY)

40、Push(&S,i); while(!StackEmpty(&S)&&(sumcredit<uplcredit)&&(sumnum<maxnum) /*棧非空&&學分總數(shù)小于學分上限&&學期課程數(shù)目小于學期最大數(shù)目*/ Pop(&S,&j);/*出棧*/ sumcredit = sumcredit + G.verticesj.credit; sumnum = sumnum+1; if(sumcredit <= uplcredit)&&(sumnum <= maxnum) printf(" %s ",G.); count+; for(p=G.verticesj.firstarc;p;p=p->nextarc)/*對j號頂點每個鄰接點的入度減一*/ G.verticesp->adjvex.indegree-; else Push(&S,j); printf("n"); if(count<G.vexnum) printf("課程編排出錯