本文格式為Word版，下載可任意編輯——數(shù)據(jù)結(jié)構(gòu)程設(shè)計(jì)

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

題目：教學(xué)計(jì)劃編制

一.需求分析

（1）試驗(yàn)內(nèi)容和試驗(yàn)?zāi)康模?/p>

1.大學(xué)的每個專業(yè)都要編制教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限，每學(xué)年含兩學(xué)期，每學(xué)期的時間長度和學(xué)分上限都相等。每個專業(yè)開設(shè)的課程都是確定的，而且課程的開設(shè)時間的安排必需滿足先修關(guān)系。每個課程的先修關(guān)系都是確定的，可以有任意多門，也可以沒有。每一門課程恰好一個學(xué)期。試在這樣的狀況下設(shè)置一個教學(xué)計(jì)劃編制程序。2.在大學(xué)的某個專業(yè)中選取幾個課程作為頂點(diǎn),通過各門課的先修關(guān)系來構(gòu)建個圖,該圖用鄰接表來存儲,鄰接表的頭結(jié)點(diǎn)存儲每門課的信息.

3.本程序的目的是為用戶編排課程,根據(jù)用戶輸入的信息來編排出每學(xué)期要學(xué)的課程.（2）測試數(shù)據(jù)：

學(xué)期總數(shù)：6；學(xué)分上限：10；該專業(yè)共開設(shè)12門課，課程號從01到12，學(xué)分順序?yàn)?，3，4，3，2，3，4，4，7，5，2，3。先修關(guān)系見教科書圖7．26。（3）測試結(jié)果（包含正確和錯誤的）：正確測試結(jié)果：

錯誤測試結(jié)果：

二.概要設(shè)計(jì)

1.抽象數(shù)據(jù)類型圖的定義如下:ADTGraph{

數(shù)據(jù)對象V:V是具有一致特性的數(shù)據(jù)元素的集合,稱為頂點(diǎn)集.數(shù)據(jù)關(guān)系R:

R={VR}

VR={(v,w)|v,w∈V,(v,w)表示v和w之間存在直接先修關(guān)系}

基本操作P:

voidCreatGraph(ALGraph*);

voidFindInDegree(ALGraph,int*);

voidTopologicalSort_1(ALGraphG,intnumterm,intmaxcredit);voidTopologicalSort_2(ALGraphG,intnumterm,intmaxcredit);}ADTGraph

棧的定義:ADTStack{

數(shù)據(jù)對象:D={ai|ai∈ElemSet,i=1,2,…n,n>=0}數(shù)據(jù)關(guān)系:R1={﹤ai-1ai﹥|ai-1,ai∈D,i=2,…,n}基本操作:

voidInitStack(SqStack*S);intStackEmpty(SqStackS);voidPush(SqStack*S,int);intPop(SqStack*S,int*e);}ADTStack2.主程序

intmain()//主函數(shù){

intnumterm;//學(xué)期總數(shù)

intuplcredit;//一個學(xué)期的學(xué)分上限

intselectway;ALGraphG;

printf(\請輸入學(xué)期總數(shù):\\n\scanf(\

printf(\請輸入一個學(xué)期的學(xué)分上限:\\n\scanf(\CreatGraph(

printf(\請選擇編排策略:1.課程盡可能集中到前幾個學(xué)期；2.課程盡量均勻分布\\n\

scanf(\

if(selectway==1)

TopologicalSort_1(G,numterm,uplcredit);if(selectway==2)

TopologicalSort_2(G,numterm,uplcredit);system(\return0;}

3.本程序只有兩個模塊,調(diào)用關(guān)系簡單.主程序模塊↓拓?fù)渑判蚰K三．詳細(xì)設(shè)計(jì)

1．頭結(jié)點(diǎn)，表結(jié)點(diǎn)，鄰接表的定義

#defineMAX_VERTEX_NUM100//最大課程總數(shù)typedefstructArcNode{intadjvex;

structArcNode*nextarc;}ArcNode;typedefstructVNode{

charname[24];//課程名intclassid;//課程號

intcredit;//課程的學(xué)分intindegree;//該結(jié)點(diǎn)的入度intstate;//該節(jié)點(diǎn)的狀態(tài)

ArcNode*firstarc;//指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList[MAX_VEXTEX_NUM];typedefstruct{

AdjListvertices;intvexnum,arcnum;}ALGraph;鄰接表的基本操作：

voidCreatGraph(ALGraph*);創(chuàng)立鄰接表

voidFindInDegree(ALGraph,int*);求一個結(jié)點(diǎn)的入度

voidTopologicalSort_1(ALGraphG,intnumterm,intmaxcredit);

拓?fù)渑判騺砭幣耪n程

voidTopologicalSort_2(ALGraphG,intnumterm,intmaxcredit);拓?fù)渑判騺砭幣耪n程2．棧的定義：

#defineSTACk_INIT_SIZE100//存儲空間的初時分派量#defineSTACKINCREMENT10//存儲空間的分派增量typedefintElemType;typedefstruct{

AdjListvertices;intvexnum,arcnum;}ALGraph;基本操作：

voidInitStack(SqStack*S);棧的初始化

intStackEmpty(SqStackS);判斷棧是否為空

voidPush(SqStack*S,int);入棧操作

intPop(SqStack*S,int*e);出棧操作

3．主程序和其他算法

intmain()//主函數(shù){intnumterm;//學(xué)期總數(shù)

intuplcredit;//一個學(xué)期的學(xué)分上限

intselectway;ALGraphG;

printf(\請輸入學(xué)期總數(shù):\\n\scanf(\

printf(\請輸入一個學(xué)期的學(xué)分上限:\\n\scanf(\

CreatGraph(

printf(\請選擇編排策略:1.課程盡可能集中到前幾個學(xué)期；2.課程盡量均勻分布\\n\

scanf(\if(selectway==1)

TopologicalSort_1(G,numterm,uplcredit);if(selectway==2)

TopologicalSort_2(G,numterm,uplcredit);system(\return0;}

voidCreatGraph(ALGraph*G)//構(gòu)件圖{inti,m,n;ArcNode*p;

printf(\請輸入需要編排課程總數(shù):\\n\scanf(\for(i=1;ivexnum;i++){

printf(\請輸入課程名\\n\

scanf(\printf(\請輸入課程號\\n\

scanf(\printf(\請輸入該課程的學(xué)分\\n\scanf(\G->vertices[i].indegree=0;G->vertices[i].state=NOTSTUDY;G->vertices[i].firstarc=NULL;}

printf(\請輸入課程先修關(guān)系總數(shù)：\scanf(\

printf(\請順序輸入每個課程先修關(guān)系(先修課程在前并以逗號作為間隔):\\n\

for(i=1;iarcnum;i++){

printf(\請輸入存在先修關(guān)系的兩個課程的序號:\scanf(\

while(nG->vexnum||mG->vexnum){

printf(\輸入的頂點(diǎn)序號不正確請重新輸入:\scanf(\}

p=(ArcNode*)malloc(sizeof(ArcNode));

if(p==NULL){

printf(\exit(1);}

p->adjvex=m;

p->nextarc=G->vertices[n].firstarc;G->vertices[n].firstarc=p;}

printf(\建立的鄰接表為:\\n\//輸出建立好的鄰接表

for(i=1;ivexnum;i++){

printf(\

for(p=G->vertices[i].firstarc;p!=NULL;p=p->nextarc)printf(\printf(\printf(\}}

voidInitStack(SqStack*S){

S->base=(int*)malloc(STACK_INIT_SIZE*sizeof(int));if(!S->base)

{

printf(\exit(1);}

S->top=S->base;

S->stacksize=STACK_INIT_SIZE;}

intStackEmpty(SqStack*S){

if(S->top==S->base)returnOK;else

returnERROR;}

voidPush(SqStack*S,inte){

if(S->top-S->base>=S->stacksize){

S->base=(int*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(int));if(!S->base){

printf(\exit(1);

}

S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}

*S->top++=e;}

intPop(SqStack*S,int*e){

if(S->top==S->base)exit(1);*e=*--S->top;return0;}

voidFindInDegree(ALGraphG,intindegree[])//求圖中各節(jié)點(diǎn)的入度{

inti;

for(i=1;iadjvex]++;

G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;}}}

voidTopologicalSort_1(ALGraphG,intnumterm,intuplcredit){

FILE*fp;

fp=fopen(\ArcNode*p;SqStackS;

intindegree[M];//存放各節(jié)點(diǎn)的入度inti,j,k,m,n;

intcount;//課程編排數(shù)目計(jì)數(shù)器

intsumcredit;//每個學(xué)期的課程學(xué)分累加器

FindInDegree(G,indegree);for(i=1;inextarc)//對j號頂點(diǎn)每個鄰接點(diǎn)的入度減一

G.vertices[p->adjvex].indegree--;}elsePush(//將未輸出的節(jié)點(diǎn)重新壓入棧

}}fprintf(fp,\}

printf(\if(count

{

printf(\課程編排成功\\n\}

fclose(fp);}

voidTopologicalSort_2(ALGraphG,intnumterm,intuplcredit){

FILE*fp;

fp=fopen(\

ArcNode*p;SqStackS;

intindegree[M];inti,j,k,m,n;

intmaxnum;intsumnum;

intcount;//課程編排數(shù)目計(jì)數(shù)器

intsumcredit;//每個學(xué)期的課程學(xué)分累加器

FindInDegree(G,indegree);

for(i=1;inextarc)//對j號頂點(diǎn)每個鄰接點(diǎn)的入度減一G.vertices[p->adjvex].indegree--;

}

elsePush(

}

}}fprintf(fp,\}

printf(\

if(count

四．調(diào)試分析：

（1）試驗(yàn)過程中出現(xiàn)的問題及解決方法

我們在試驗(yàn)過程中遇到的最大難題是兩個課程排序算法的編寫。剛開始的時候沒有任何的思路，網(wǎng)上也只有拓?fù)渑判虻乃惴?，對于課程設(shè)計(jì)要求的排序算法沒有任何頭緒。經(jīng)過請教老師和同學(xué)以及翻閱了一些相關(guān)書籍，并在網(wǎng)上的探尋有了排序算法的大體思路。經(jīng)過三天的修改，終究寫出了符合要求的排序算法。

（2）試驗(yàn)體會:

經(jīng)過此次課程設(shè)計(jì)，我們認(rèn)識到了理論與實(shí)踐結(jié)合的重要性，僅僅只是從課本上學(xué)到算法原理是遠(yuǎn)遠(yuǎn)不夠的。在實(shí)踐中，我們總會出現(xiàn)大量錯誤。這就要求我們以一個腳踏實(shí)地的態(tài)度來處理問題。我們深刻地認(rèn)識到自己寫程序的不足，使我們學(xué)到了好多有用的知識，讓我們明白了C語言的語句用法。

五．用戶使用和說明：

使用VC++，開啟教學(xué)計(jì)劃編制問題.cpp文件，接著編譯，無錯誤，然后重建也沒有錯誤，最終執(zhí)行該文件。顯示如下圖：

要求輸入學(xué)期總數(shù)、一個學(xué)期的學(xué)分上限、需要編排課程總數(shù)、課程名、課程號、該課程的學(xué)分，依照出現(xiàn)的每一步來輸入該課程設(shè)計(jì)所提供的相關(guān)數(shù)據(jù)。然后還要輸入課程先修課程總數(shù)，依據(jù)教科書圖7．26，可以算出有16種關(guān)系，分別輸出如下圖所示。接著程序會根據(jù)這些數(shù)據(jù)，自動生成建立好的鄰接表，用戶可以根據(jù)系統(tǒng)顯示的選擇編排策略進(jìn)行選擇，有兩種編排策略，最終結(jié)果表達(dá)在試驗(yàn)的正確測試結(jié)果里（如上圖）。

六.測試數(shù)據(jù)及程序運(yùn)行狀況:輸入的內(nèi)容如下:

課程編號課程名稱學(xué)分先決條件

01程序設(shè)計(jì)基

礎(chǔ)2