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

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

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

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

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

5、頂點(diǎn)入度的數(shù)組（indegree）。入度為零的頂點(diǎn)即為沒有前驅(qū)的頂點(diǎn)，刪除頂點(diǎn)及以它為尾的弧的操作，則可換以弧頭頂點(diǎn)入度減一來實(shí)現(xiàn)。(3) 拓?fù)渑判颉?（a）在有向圖中選一個(gè)沒有前驅(qū)的頂點(diǎn)且輸出之。 （b）從圖中刪除該頂點(diǎn)和所有以它為尾的弧。重復(fù)上述兩步，直至全部頂點(diǎn)均已輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)為止，后一種情況則說明有向圖中存在環(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;/該弧所指向頂點(diǎn)的位置struct ArcNode *nextarc;/指向下一條弧的指針ArcNode;typedef struct VNodechar name24;/課程名int classid; /課程號int credit;/課程的學(xué)分 int indegree;/該結(jié)點(diǎn)的入度 int state;/該節(jié)點(diǎn)的狀態(tài)，1代表已學(xué)，0代表未學(xué) ArcNode *firstarc; /指向第一條依附該頂點(diǎn)的弧的指針VNode,AdjListMAX_VERTEX_NUM;typedef st

7、ructAdjList vertices;/頂點(diǎn)向量int vexnum,arcnum;/圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)ALGraph;typedef int ElemType;/棧的順序存儲表示typedef struct /棧ElemType *base;ElemType *top;int stacksize;SqStack;B.程序中各函數(shù)的簡要說明：（1） void CreatGraph(ALGraph &G)構(gòu)建圖。先輸入各頂點(diǎn)（課程）的信息，包括課程名、課程號、課程學(xué)分。再輸入弧信息（先修關(guān)系），將弧中頂點(diǎn)賦為弧尾，相應(yīng)入度加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é)點(diǎn)的入度。從每個(gè)節(jié)點(diǎn)的第一條依附于該節(jié)點(diǎn)的弧出發(fā)，將該節(jié)點(diǎn)對應(yīng)的入度加1，接著指向下一條弧執(zhí)行同樣的操作，直至指針為空。（3）void TopologicalSort_1(ALGraph G,int numterm,int uplcredit)按課程盡可能集中到前幾個(gè)學(xué)期進(jìn)行編排。當(dāng)

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

10、的學(xué)分已滿或課程數(shù)已滿時(shí)，進(jìn)入下一學(xué)期的編排。重復(fù)上述幾步，直至全部頂點(diǎn)（課程）均已輸出，或者當(dāng)前圖中不存在無前驅(qū)的頂點(diǎn)（課程）為止，后一種情況則說明有向圖中存在環(huán)。（5）int main()主函數(shù)。在主函數(shù)中輸出交互界面，要求用戶輸入各項(xiàng)信息。調(diào)用CreateGraph函數(shù)創(chuàng)建圖，之后根據(jù)用戶選擇調(diào)用TopologicalSort_1或者TopologicalSort_2函數(shù)進(jìn)行拓?fù)渑判虿⑤敵鼍幣沤Y(jié)果，寫入文件中。5、函數(shù)調(diào)用關(guān)系圖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é)點(diǎn)的入度 (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)試過程中遇到的問題與解決方法我在實(shí)驗(yàn)過程中遇到的最大難題是兩個(gè)課程排序算法的編寫。剛開始的時(shí)候沒有任何的思路，書上、網(wǎng)上也只有拓?fù)渑判虻乃惴?，對于課程設(shè)計(jì)要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學(xué)以及翻閱了一些相關(guān)書籍，并在網(wǎng)上的搜索有了排序算法的大體思路。經(jīng)過三天的修改，終于寫出了符合要求的排序算法。在設(shè)計(jì)過程中，我的程序有不少漏洞，例如在選擇一次編排后，按任意鍵就會退出，不可以繼續(xù)選擇編排策略，經(jīng)過一系列的修改，成功地將程序添加選擇是否繼續(xù)的功能。2、算法的時(shí)空分析對有n個(gè)頂點(diǎn)和e條弧的有向圖而言，將建立求各頂點(diǎn)的入度的時(shí)間復(fù)雜度為O(e)；建立入度定點(diǎn)棧的

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

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

15、關(guān)系程序設(shè)計(jì)基礎(chǔ)012無離散數(shù)學(xué)02301數(shù)據(jù)結(jié)構(gòu)03401,02匯編語言04301語言的設(shè)計(jì)和分析05203,04計(jì)算機(jī)原理06311編譯原理07405,03操作系統(tǒng)08403,06高等數(shù)學(xué)097無線性代數(shù)10509普通物理11209數(shù)值分析12309,10,01先修順序有向圖：01104050212090811100607032、屏幕上會顯示您輸入的數(shù)據(jù)，確認(rèn)無誤后選擇方案（如下圖）：3、選擇方案后會進(jìn)行計(jì)算并輸出，之后可根據(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;/該弧所指向頂點(diǎn)的位置struct ArcNode *nextarc;/指向下一條弧的指針ArcNode;typedef struct VNodechar name24;/課程名int classid; /課程號int credit;/課程的學(xué)分 int ind

17、egree;/該結(jié)點(diǎn)的入度 int state;/該節(jié)點(diǎn)的狀態(tài)，1代表已學(xué)，0代表未學(xué) ArcNode *firstarc; /指向第一條依附該頂點(diǎn)的弧的指針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請輸入該課程的學(xué)分:);scanf(%d,&G.verticesi.credit); G.verticesi.indegree=0;G.vertices i.state=0;/NOTSTUDYG.verticesi.firstarc=NULL;printf

19、(請輸入課程先修關(guān)系總數(shù)：);scanf(%d,&G.arcnum); printf(請順序輸入每個(gè)課程先修關(guān)系(先修課程在前并以逗號作為間隔):n);for (i = 1; i = G.arcnum; i+)printf(n請輸入存在先修關(guān)系的兩個(gè)課程的序號:);scanf(%d,%d,&n,&m);while (nG.vexnum|mG.vexnum)printf(輸入的頂點(diǎn)序號不正確請重新輸入:);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é)點(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;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é)點(diǎn)的入度 int i,j,k;int count; /課程編括排數(shù)目計(jì)數(shù)器int sumcredit;/每個(gè)學(xué)期的課程學(xué)分累加器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é)點(diǎn)入棧，即無先修的課程入棧Push(S,i);G.verticesi.state =1;/避免入度為零節(jié)點(diǎn)重復(fù)入棧if(!StackEmpty(S)&(sumcredit=uplcredit)k= k+1;printf(n);printf(第%d個(gè)學(xué)期學(xué)得課程有:,k);sumcredit = 0;f

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

26、重新壓入棧fprintf(fp,n);printf(n);if(countG.vexnum)printf(n課程編排出錯(cuò)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é)點(diǎn)的入度int i,j,k,m,n;int maxnum;int sumnum;int count; /

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