教學計劃編制數(shù)據(jù)結(jié)構(gòu)課程設計報告

1、數(shù)據(jù)結(jié)構(gòu)課程設計教學計劃編制問題（圖的應用）班級學號21333班2133326學生姓名孫麗提交日期2015年7月23日成 績 計算機與通信工程學院目 錄一 需求分析11.設計任務12.功能模塊圖13.流程圖24.目標測試2二 詳細設計41.運行環(huán)境42.開發(fā)工具43.涉及知識點44.數(shù)據(jù)結(jié)構(gòu)定義及基本操作45.函數(shù)調(diào)用關系圖56.偽碼流程6三 調(diào)試分析91.調(diào)試過程中遇到的問題與解決方法92算法的時空分析93.改進思想94.經(jīng)驗體會9四 用戶手冊9五 測試結(jié)果111.輸入112.輸出14六 附錄16七 參考文獻23一、需求分析1、設計任務教學計劃編制問題（圖的應用）問題描述大學的每個專業(yè)都要制

2、定教學計劃。假設任何專業(yè)都有固定的學習年限，每學年含兩學期，每學期的時間長度和學分上限值均相等。每個專業(yè)開設的課程都是確定的，而且課程在開設時間的安排必須滿足先修關系。每門課程有哪些先修課程是確定的，可以有任意多門，也可以沒有。每門課恰好占一個學期。試在這樣的前提下設計一個教學計劃編制程序。實現(xiàn)提示輸入?yún)?shù)應包括：學期總數(shù)，一學期的學分上限，每門課的課程號（可以是固定占3位的字母數(shù)字串）、學分和直接先修課的課程號。應允許用戶指定下列兩種編排策略之一：一是使學生在各學期中的學習負擔盡量均勻；二是使課程盡可能地集中在前幾個學期中。若根據(jù)給定的條件問題無解，則報告適當?shù)男畔?；否則將教學計劃輸出到用戶

3、指定的文件中。計劃的表格格式可以自己設計?？稍O學期總數(shù)不超過12，課程總數(shù)不超過100。如果輸入的先修課程號不在該專業(yè)開設的課程序列中，則作為錯誤處理。2、功能模塊圖主程序模塊棧的定義及操作拓撲排序模塊圖的定義及操作1、棧的順序存儲表示2、構(gòu)造空棧3、判斷棧是否為空4、入棧 5、出棧1、圖的鄰接表存儲表示2、構(gòu)造圖3、求圖中各節(jié)點的入度1、在有向圖中選個沒有前驅(qū)頂點且輸出。2、從圖中刪除該頂點和所有以它為尾的弧。CreateGraph（）：構(gòu)造圖 InitStack（）：構(gòu)造一個空棧 StackEmpty（）：判斷是否為空棧 Push（）：入棧Pop（）：出棧 FindInDegree（）：求

4、頂點的入度TopologicalSort（）：輸出G頂點的拓撲排序結(jié)果3、流程圖（具體流程圖見詳細設計偽碼流程）主程序構(gòu)造圖GreateGraph ( )拓撲排序TopologicalSort開始結(jié)束4、目標測試正確測試：錯誤測試：二、詳細設計1、運行環(huán)境：（1）WINDOWS 7系統(tǒng)（2）C-Free 5.02、開發(fā)工具： C語言3、涉及知識點：(1) 棧。用到有關棧的操作有初始化棧、判斷棧是否為空、入棧和出棧。其中棧主要用來存放入度為零的頂點，即當前無先修關系可以編排的課程。(2) 圖。用到有關圖的操作有創(chuàng)建圖、統(tǒng)計圖中各頂點的入度。利用鄰接表作為有向圖的存儲結(jié)構(gòu)，且在頭結(jié)點中增加一個存放

5、頂點入度的數(shù)組（indegree）。入度為零的頂點即為沒有前驅(qū)的頂點，刪除頂點及以它為尾的弧的操作，則可換以弧頭頂點入度減一來實現(xiàn)。(3) 拓撲排序。 （a）在有向圖中選一個沒有前驅(qū)的頂點且輸出之。 （b）從圖中刪除該頂點和所有以它為尾的弧。重復上述兩步，直至全部頂點均已輸出，或者當前圖中不存在無前驅(qū)的頂點為止，后一種情況則說明有向圖中存在環(huán)。4、數(shù)據(jù)結(jié)構(gòu)定義及基本操作A.所用存儲結(jié)構(gòu)及宏定義：#define MAX_VERTEX_NUM 100 /最大課程總數(shù)#define STACK_INIT_SIZE 100 /存儲空間的初始分配量#define STACKINCREMENT 10 /存

6、儲空間的分配增量/圖的鄰接表存儲表示typedef struct ArcNode int adjvex;/該弧所指向頂點的位置struct ArcNode *nextarc;/指向下一條弧的指針ArcNode;typedef struct VNodechar name24;/課程名int classid; /課程號int credit;/課程的學分 int indegree;/該結(jié)點的入度 int state;/該節(jié)點的狀態(tài)，1代表已學，0代表未學 ArcNode *firstarc; /指向第一條依附該頂點的弧的指針VNode,AdjListMAX_VERTEX_NUM;typedef st

7、ructAdjList vertices;/頂點向量int vexnum,arcnum;/圖的當前頂點數(shù)和弧數(shù)ALGraph;typedef int ElemType;/棧的順序存儲表示typedef struct /棧ElemType *base;ElemType *top;int stacksize;SqStack;B.程序中各函數(shù)的簡要說明：（1） void CreatGraph(ALGraph &G)構(gòu)建圖。先輸入各頂點（課程）的信息，包括課程名、課程號、課程學分。再輸入弧信息（先修關系），將弧中頂點賦為弧尾，相應入度加1.最后輸出構(gòu)建好的鄰接表。（2） void InitStack(

8、SqStack &S)構(gòu)造空棧int StackEmpty(SqStack &S)判斷是否為空棧void Push(SqStack &S,int e)入棧 int Pop(SqStack &S, int *e)出棧（3） void FindInDegree(ALGraph G, int indegree)求圖中各節(jié)點的入度。從每個節(jié)點的第一條依附于該節(jié)點的弧出發(fā)，將該節(jié)點對應的入度加1，接著指向下一條弧執(zhí)行同樣的操作，直至指針為空。（3）void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)按課程盡可能集中到前幾個學期進行編排。當

9、每個學期的學分總數(shù)不超過學分上限時，在有向圖中選一個沒有前驅(qū)的頂點（課程）且輸出之。從圖中刪除該頂點（課程）和所有以它為尾的弧。當某學期的學分已滿時，進入下一學期的編排。重復上述幾步，直至全部頂點（課程）均已輸出，或者當前圖中不存在無前驅(qū)的頂點（課程）為止，后一種情況則說明有向圖中存在環(huán)。（4）void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)按課程盡量均勻分布編排。當每個學期的學分總數(shù)不超過學分上限且課程數(shù)不超過課程數(shù)上限時，在有向圖中選一個沒有前驅(qū)的頂點（課程）且輸出之。從圖中刪除該頂點（課程）和所有以它為尾的弧。當某學期

10、的學分已滿或課程數(shù)已滿時，進入下一學期的編排。重復上述幾步，直至全部頂點（課程）均已輸出，或者當前圖中不存在無前驅(qū)的頂點（課程）為止，后一種情況則說明有向圖中存在環(huán)。（5）int main()主函數(shù)。在主函數(shù)中輸出交互界面，要求用戶輸入各項信息。調(diào)用CreateGraph函數(shù)創(chuàng)建圖，之后根據(jù)用戶選擇調(diào)用TopologicalSort_1或者TopologicalSort_2函數(shù)進行拓撲排序并輸出編排結(jié)果，寫入文件中。5、函數(shù)調(diào)用關系圖Main函數(shù)GreateGraph ( )TopologicalSort_1或TopologicalSort _2FILE *fpFindInDegree ( )

11、InitStack ( )Push ( )Pop ( )StackEmpty ( )6、偽碼流程（1）void CreatGraph(ALGraph &G) （2）void FindInDegree(ALGraph G, int 構(gòu)造圖 indegree)求圖中各節(jié)點的入度 (4) void TopologicalSort_1 (5)void TopologicalSort_2 (ALGraph G,int numterm, (ALGraph G,int numterm, int uplcredit) int uplcredit)有向圖G采用鄰接表存儲結(jié)構(gòu) 有向圖G采用鄰接表存儲結(jié)構(gòu)(6)Ma

12、in主函數(shù)三、調(diào)試分析1、調(diào)試過程中遇到的問題與解決方法我在實驗過程中遇到的最大難題是兩個課程排序算法的編寫。剛開始的時候沒有任何的思路，書上、網(wǎng)上也只有拓撲排序的算法，對于課程設計要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學以及翻閱了一些相關書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法。在設計過程中，我的程序有不少漏洞，例如在選擇一次編排后，按任意鍵就會退出，不可以繼續(xù)選擇編排策略，經(jīng)過一系列的修改，成功地將程序添加選擇是否繼續(xù)的功能。2、算法的時空分析對有n個頂點和e條弧的有向圖而言，將建立求各頂點的入度的時間復雜度為O(e)；建立入度定點棧的

13、時間復雜度為O(n)，在拓撲排序過程中，若有向圖無環(huán)，則每個頂點進一次棧，出一次棧，入度減1的操作在while語句中總共執(zhí)行e次，所以，總的時間復雜度為O(n+e)。3、改進思想A.程序界面有很大的改進空間，可設計更簡潔美觀的界面。B.輸入數(shù)據(jù)比較繁瑣，分步太多，可編寫程序進行改善，如一步輸入課程名、課程號、學分。C.課程號為01,02等形式，也可改為C1、C2的形式。4、經(jīng)驗體會在這次課設中，我進行了大量的資料查閱，包括上網(wǎng)查詢和求助老師同學，對所學知識進行復習。通過這些努力，我對數(shù)據(jù)結(jié)構(gòu)這門課程有了新的認識，對編程的步驟，有了具體的體會。更重要的是，這個課題完全脫離于只限于書本上的問題，多

14、用在實際生活當中，讓我對計算機行業(yè)，充滿了信心和自豪。以往我們學的計算機知識一般停留在理論上，這讓我們不太理解計算機的應用和前景，而較少注重我們對算法的實踐鍛煉。而這一次的實習既需要我們?nèi)ヂ?lián)系理論，又需要我們?nèi)嵺`方法，很多東西看上去都學過，但是和實際聯(lián)系才知道變通的艱難。書上得來的并不是一切，大多還是需要在其它方面去吸收的，這是我這次課設的最大收獲。這次的實驗讓我們知道該如何跨過實際和理論之間的鴻溝。四、用戶手冊1、 按照提示輸入各個數(shù)據(jù)（如下圖）：包括：學期總數(shù)，一學期的學分上限，編排課程總數(shù)，每門課的課程名、課程號(固定占3位的字母數(shù)字串)、學分和直接先修課的課程號。課程名課程號學分先修

15、關系程序設計基礎012無離散數(shù)學02301數(shù)據(jù)結(jié)構(gòu)03401,02匯編語言04301語言的設計和分析05203,04計算機原理06311編譯原理07405,03操作系統(tǒng)08403,06高等數(shù)學097無線性代數(shù)10509普通物理11209數(shù)值分析12309,10,01先修順序有向圖：01104050212090811100607032、屏幕上會顯示您輸入的數(shù)據(jù)，確認無誤后選擇方案（如下圖）：3、選擇方案后會進行計算并輸出，之后可根據(jù)需要選擇是否繼續(xù)（如下圖）：五、測試結(jié)果1、輸入2、輸出策略1：bianpai1.txt策略2：bianpai2.txt六、附錄源程序清單及其說明如下：#includ

16、e stdio.h#include malloc.h#define MAX_VERTEX_NUM 100 /最大課程總數(shù)#define STACK_INIT_SIZE 100 /存儲空間的初始分配量#define STACKINCREMENT 10 /存儲空間的分配增量typedef struct ArcNode int adjvex;/該弧所指向頂點的位置struct ArcNode *nextarc;/指向下一條弧的指針ArcNode;typedef struct VNodechar name24;/課程名int classid; /課程號int credit;/課程的學分 int ind

17、egree;/該結(jié)點的入度 int state;/該節(jié)點的狀態(tài)，1代表已學，0代表未學 ArcNode *firstarc; /指向第一條依附該頂點的弧的指針VNode,AdjListMAX_VERTEX_NUM;typedef structAdjList vertices;int vexnum,arcnum;ALGraph;typedef int ElemType;typedef structElemType *base;ElemType *top;int stacksize;SqStack;void CreateGraph(ALGraph &G)/構(gòu)建圖int i, m, n;ArcNod

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

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

20、iled,goodbey);return;p-adjvex = m;p-nextarc=G.verticesn.firstarc;G.verticesn.firstarc = p;printf(n建立的鄰接表為:n);/輸出建立好的鄰接表for(i=1;i,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.base=(int *)malloc(STACK_INIT_S

21、IZE*sizeof(int);if (!S.base) printf(ERROR);return;S.top=S.base;S.stacksize=STACK_INIT_SIZE;int StackEmpty(SqStack &S)if(S.top=S.base)return 1;elsereturn 0;void Push(SqStack &S,int e)if(S.top-S.base=S.stacksize)S.base=(int*)realloc(S.base,(S.stacksize+10)*sizeof(int);if(!S.base) printf(ERROR);return;

22、S.top=S.base+S.stacksize;S.stacksize+=10;*S.top+=e;int Pop(SqStack &S, int *e)if(S.top=S.base)return 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 adjvex+;G.verticesi.firstarc = G.verticesi.firstarc-nextarc;vo

23、id TopologicalSort_1(ALGraph G,int numterm,int uplcredit)FILE *fp;fp=fopen(bianpai1.txt,w);struct ArcNode *p;SqStack S;int indegreeMAX_VERTEX_NUM;/存放各節(jié)點的入度 int i,j,k;int count; /課程編括排數(shù)目計數(shù)器int sumcredit;/每個學期的課程學分累加器FindInDegree(G,indegree);for (i = 1; i = G.vexnum; i+)G.verticesi.indegree=indegreei;

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

25、or(i=1;i=G.vexnum;i+)if(G.verticesi.indegree=0)&(G.verticesi.state=0)/入度為零的節(jié)點入棧，即無先修的課程入棧 Push(S,i);while(!StackEmpty(S)&(sumcredituplcredit)/棧非空&學分總數(shù)小于總學分上限 Pop(S,&j);sumcredit = sumcredit + G.verticesj.credit;if(sumcredit nextarc)/對j號頂點每個鄰接點的入度減一G.verticesp-adjvex.indegree-;else Push(S,j);/將未輸出的節(jié)點

26、重新壓入棧fprintf(fp,n);printf(n);if(countG.vexnum)printf(n課程編排出錯n);elseprintf(n課程編排成功n);fclose(fp);void TopologicalSort_2(ALGraph G,int numterm,int uplcredit)FILE *fp;fp=fopen(bianpai2.txt,w);struct ArcNode *p;SqStack S;int indegreeMAX_VERTEX_NUM;/存放各節(jié)點的入度int i,j,k,m,n;int maxnum;int sumnum;int count; /

27、課程編排數(shù)目計數(shù)器int sumcredit;/每個學期的課程學分累加器FindInDegree(G,indegree);for (i = 1; i = G.vexnum; i+)G.verticesi.indegree=indegreei;InitStack(S);count=0;k=0;maxnum=G.vexnum/numterm+1;sumnum=0;while(count!=G.vexnum & k=numterm)sumcredit=0;for(i=1;i=G.vexnum;i+) if(G.verticesi.indegree=0)&(G.verticesi.state=0)/入

28、度為零的節(jié)點入棧，即無先修的課程入棧Push(S,i);G.verticesi.state =1;/避免入度為零節(jié)點重復入棧if(!StackEmpty(S)&(sumcredit=uplcredit)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=0)Push(S,i);while(!StackEmpty(S)&(sumcredituplcredit)&(sumnummaxnum)/棧非空&學分總數(shù)小于學分上