/數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告主題：教學(xué)計(jì)劃編制問(wèn)題學(xué)號(hào)：20091003768班級(jí)：計(jì)科四班姓名：熊金蓮指導(dǎo)老師：郭艷內(nèi)容概要題目要求教學(xué)計(jì)劃編制問(wèn)題的要點(diǎn)函數(shù)模塊及各函數(shù)可實(shí)現(xiàn)的功能簡(jiǎn)介具體的源代碼使用說(shuō)明實(shí)驗(yàn)心得一：題目要求如下：大學(xué)的每個(gè)專業(yè)都要制定教學(xué)計(jì)劃。假設(shè)任何專業(yè)都有固定的學(xué)習(xí)年限,每學(xué)年含兩學(xué)期,每學(xué)期的時(shí)間長(zhǎng)度和學(xué)分上限值均相等。每個(gè)專業(yè)開(kāi)設(shè)的課程都是確定的,而且課程在開(kāi)設(shè)時(shí)間的安排必須滿足先修關(guān)系。每門課程有哪些先修課程是確定的,可以有任意多門,也可以沒(méi)有。每門課恰好占一個(gè)學(xué)期。試在這樣的前提下設(shè)計(jì)一個(gè)教學(xué)計(jì)劃編制程序。要求〔1輸入?yún)?shù)包括：學(xué)期總數(shù),一學(xué)期的學(xué)分上限,每門課的課程號(hào)〔固定占3位的字母數(shù)字串學(xué)分和直接先修課的課程號(hào)。〔2允許用戶指定下列兩種編排策略之一：一是使學(xué)生在各學(xué)期中的學(xué)習(xí)負(fù)擔(dān)盡量均勻；二是使課程盡可能地集中在前幾個(gè)學(xué)期中?！?若根據(jù)給定的條件問(wèn)題無(wú)解,則報(bào)告適當(dāng)?shù)男畔ⅲ环駝t將教學(xué)計(jì)劃輸出到用戶指定的文件中。計(jì)劃的表格格式自行設(shè)計(jì)。二：教學(xué)計(jì)劃編制問(wèn)題的要點(diǎn)：根據(jù)問(wèn)題描述及要求,可知設(shè)計(jì)中需要定義先修關(guān)系的AOV網(wǎng)圖中的頂點(diǎn)及弧邊的結(jié)構(gòu)體,在運(yùn)行結(jié)果中將圖的信息顯示出來(lái),利用先修關(guān)系將課程排序,最后解決問(wèn)題——輸出每學(xué)期的課程。采用第二種策略：使課程盡可能地集中在前幾個(gè)學(xué)期中；根據(jù)教學(xué)計(jì)劃中的課程及其關(guān)系和學(xué)分定義圖的頂點(diǎn)和邊的結(jié)構(gòu)體創(chuàng)建圖CreateGraph〔：結(jié)合先修關(guān)系的AOV網(wǎng),顯示代號(hào)所對(duì)應(yīng)課程及課程的先修課程4拓?fù)渑判騎opologicalOrder<G>：將課程排序后并決定出每學(xué)期所學(xué)課程,輸出圖G的信息Display<G>：將圖的頂點(diǎn)和弧邊輸出三：程序模塊及可實(shí)現(xiàn)的功能簡(jiǎn)介：1、圖的鄰接表的存儲(chǔ)表示,即結(jié)構(gòu)體的定義typedefstructArcNode{ intAdjOfV;//該弧所指向的頂點(diǎn)的位置 structArcNode*next;//指向下一條弧的指針}ArcNode;typedefcharVertexType[MAXOfNAME];typedefstruct//鏈接表{ VertexTypedata;//頂點(diǎn)信息 intgrades;//存儲(chǔ)學(xué)分信息 ArcNode*first;//指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList[MAX_VER];//頭結(jié)點(diǎn)typedefstruct{ AdjListver;//vertices存儲(chǔ)課程名 intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}ALGraph;2、利用前插法,建立圖的鄰接鏈表printf<"請(qǐng)輸入下列課程的先修課程<無(wú)先修課程輸入0結(jié)束后也輸入0>\n">;for<h=0;h<G.vexnum;++h>//構(gòu)造表結(jié)點(diǎn)鏈表,利用前插法{printf<"%s的先修課程:",G.ver[h].data>;scanf<"%s",va>;getchar<>;while<va[0]!='0'>{i=LocateVex<G,va>;//弧頭j=h;//弧尾p=<ArcNode*>malloc<sizeof<ArcNode>>;p->AdjOfV=j;p->next=G.ver[i].first;//插在表頭G.ver[i].first=p;scanf<"%s",va>;getchar<>;}}

3、輸出圖的頂點(diǎn)和邊printf<"%d個(gè)頂點(diǎn)",G.vexnum>;for<i=0;i<G.vexnum;++i>printf<"%4s",G.ver[i].data>;printf<"\n%d條弧邊:\n",G.arcnum>;for<i=0;i<G.vexnum;i++>{p=G.ver[i].first;while<p> {printf<"%s>%s\n",G.ver[i].data,G.ver[p->AdjOfV].data>;p=p->next;}}

4、通過(guò)棧實(shí)現(xiàn)拓?fù)渑判?/p>

intTopologicalOrder<ALGraphG,AdjListR,structNamename[]>{ inti,k,j=0,count,indegree[MAX_VER]; SqStackS; ArcNode*p; FindInDegree<G,indegree>;//對(duì)各頂點(diǎn)求入度 InitStack<S>;//初始化棧 for<i=0;i<G.vexnum;++i>//建零入度頂點(diǎn)棧S if<!indegree[i]>Push<S,i>;//入度為0者進(jìn)棧count=0;//對(duì)輸出頂點(diǎn)計(jì)數(shù)while<!StackEmpty<S>> { Pop<S,i>; printf<"%s<%d學(xué)分>,",G.ver[i].data,G.ver[i].grades>; R[j++]=G.ver[i];//將當(dāng)前的拓?fù)湫蛄斜４嫫饋?lái) ++count;//輸出i號(hào)頂點(diǎn)并計(jì)數(shù) for<p=G.ver[i].first;p;p=p->next>//對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1 { k=p->AdjOfV; if<!<--indegree[k]>>//若入度減為0,則入棧 Push<S,k>; } } if<count<G.vexnum> { printf<"此有向圖有回路無(wú)法完成拓?fù)渑判?>; return0; } elseprintf<"為一個(gè)拓?fù)湫蛄?>; printf<"\n">; intq=1,Z=0; while<q<=TotalOfTerms> { intC=R[Z].grades; printf<"\n第%d個(gè)學(xué)期應(yīng)學(xué)課程:",q>; while<C<=MaxScores> { C=C+R[Z+1].grades; if<Z<G.vexnum>{CmpOfStr<R[Z].data,name,N>;/*讓C1~C12分別與12門課程對(duì)應(yīng)起來(lái)*/ ++Z; } } printf<"\n">; if<q==TotalOfTerms>printf<"\nOKOver!">; q++; } return1;/**/}拓?fù)渑判蛞c(diǎn)：依次將入度為0的頂點(diǎn)存入InDegree中,對(duì)每個(gè)頂點(diǎn)求入度,并存入數(shù)組InDegree[i]中〔i=0…n,初始化棧Stack,Counter=0,對(duì)以i號(hào)頂點(diǎn)為尾弧的每個(gè)鄰接點(diǎn)的入度減1,并將入度減1后為零的頂點(diǎn)號(hào)壓入棧中,輸出i,計(jì)數(shù)器加1<Counter++>,推出棧頂?shù)囊粋€(gè)元素〔入度為零的頂點(diǎn)號(hào)至i,輸出i,計(jì)數(shù)器加1〔Counter++,堆棧是否為空？,n個(gè)頂點(diǎn)全輸出,依次將入度為0的頂點(diǎn)存入InDegree中5>根據(jù)學(xué)分上限決定出每學(xué)期應(yīng)學(xué)課程,其中R[]中存儲(chǔ)的是經(jīng)過(guò)拓?fù)渑判蚝蟮恼n程先后順序。

intq=1,Z=0; while<q<=TotalOfTerms> { intC=R[Z].grades; printf<"\n第%d個(gè)學(xué)期應(yīng)學(xué)課程:",q>; while<C<=MaxScores>{C=C+R[Z+1].grades; if<Z<G.vexnum> {CmpOfStr<R[Z].data,name,N>;/*讓C1~C12分別與12門課程對(duì)應(yīng)起來(lái)*/ ++Z;} } printf<"\n">; if<q==TotalOfTerms>printf<"\nOKOver!">; q++; }四：具體的源代碼本程序分為三部分A:::::::::SeqStack.h#defineStackofNUM20//存儲(chǔ)空間初始分配量#defineStackforMore5//存儲(chǔ)空間分配增量typedefstructSqStack{ int*a; int*top; intsize;//分配的存儲(chǔ)空間}SqStack;intInitStack<SqStack&S>/*棧的初始化*/{ S.a=<int*>malloc<StackofNUM*sizeof<int>>; if<!S.a>exit<-1>; S.top=S.a; S.size=StackofNUM; return1;}intStackEmpty<SqStackS>/*判斷棧是否為空*/{ if<S.top==S.a>return1; elsereturn0;}intPush<SqStack&S,intx>/*入棧*/{ if<S.top-S.a>=S.size> { S.a=<int*>realloc<S.a,<S.size+StackforMore>*sizeof<int>>; if<!S.a>exit<-1>; S.top=S.a+S.size; S.size+=StackforMore; } *S.top++=x; return1;}intPop<SqStack&S,int&x>/*出棧*/{ if<S.top==S.a>return0; x=*--S.top; return1;}B:::::::::ALGraph.h#defineMAXOfNAME3//最多字符個(gè)數(shù)#defineMAX_VER100//最大頂點(diǎn)數(shù)typedefstructArcNode{ intAdjOfV;//該弧所指向的頂點(diǎn)的位置 structArcNode*next;//指向下一條弧的指針}ArcNode;typedefcharVertexType[MAXOfNAME];typedefstruct//鏈接表{ VertexTypedata;//頂點(diǎn)信息 intgrades;//存儲(chǔ)學(xué)分信息 ArcNode*first;//指向第一條依附該頂點(diǎn)的弧的指針}VNode,AdjList[MAX_VER];//頭結(jié)點(diǎn)typedefstruct{ AdjListver;//vertices存儲(chǔ)課程名 intvexnum,arcnum;//圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)}ALGraph;intTotalOfTerms;//學(xué)期總數(shù)intMaxScores;//學(xué)分上限intLocateVex<ALGraphG,VertexTypeu>/*查找圖中某個(gè)頂點(diǎn)位置*/{inti;for<i=0;i<G.vexnum;++i>if<strcmp<u,G.ver[i].data>==0>returni;return-1;}intCreateGraph<ALGraph&G>/*采用鄰接表存儲(chǔ)結(jié)構(gòu)*/{inti,j,h;VertexTypeva;ArcNode*p;printf<"請(qǐng)輸入教學(xué)計(jì)劃的課程數(shù):">;scanf<"%d",&G.vexnum>; getchar<>;printf<"請(qǐng)輸入各個(gè)課程的先修課程的總和<弧總數(shù)>:">;scanf<"%d",&G.arcnum>; getchar<>;printf<"請(qǐng)輸入%d個(gè)課程的課程號(hào)<最多%d個(gè)字符,字母+數(shù)字如C10>:",G.vexnum,MAXOfNAME>;for<i=0;i<G.vexnum;++i>{scanf<"%s",&G.ver[i].data>; getchar<>;G.ver[i].first=NULL;}printf<"請(qǐng)輸入%d個(gè)課程的學(xué)分值:",G.vexnum>;for<i=0;i<G.vexnum;++i>{scanf<"%d",&G.ver[i].grades>;getchar<>;}printf<"請(qǐng)輸入下列課程的先修課程<無(wú)先修課程輸入0結(jié)束后也輸入0>\n">;for<h=0;h<G.vexnum;++h>//構(gòu)造表結(jié)點(diǎn)鏈表,利用前插法{printf<"%s的先修課程:",G.ver[h].data>;scanf<"%s",va>;getchar<>;while<va[0]!='0'>{i=LocateVex<G,va>;//弧頭j=h;//弧尾p=<ArcNode*>malloc<sizeof<ArcNode>>;p->AdjOfV=j;p->next=G.ver[i].first;//插在表頭G.ver[i].first=p;scanf<"%s",va>;getchar<>;}}return1;}voidDisplay<ALGraphG>/*輸出圖G的信息*/{inti;ArcNode*p;printf<"有向圖\n">;printf<"%d個(gè)頂點(diǎn)",G.vexnum>;for<i=0;i<G.vexnum;++i>printf<"%4s",G.ver[i].data>;printf<"\n%d條弧邊:\n",G.arcnum>;for<i=0;i<G.vexnum;i++>{p=G.ver[i].first;while<p> {printf<"%s>%s\n",G.ver[i].data,G.ver[p->AdjOfV].data>;p=p->next;}}}voidFindInDegree<ALGraphG,intindegree[]>/*求頂點(diǎn)的入度*/{inti;ArcNode*p;for<i=0;i<G.vexnum;i++>indegree[i]=0;for<i=0;i<G.vexnum;i++>{p=G.ver[i].first;while<p>{indegree[p->AdjOfV]++;p=p->next;}}}structName{charc[20];}name;voidCmpOfStr<VertexTypestr,structNamename[],intn>/*讓C1~C12分別與12門課程對(duì)應(yīng)起來(lái)*/{if<strcmp<str,name[0].c>==0>printf<"程序設(shè)計(jì)基礎(chǔ)">;if<strcmp<str,name[1].c>==0>printf<"離散數(shù)學(xué)">;if<strcmp<str,name[2].c>==0>printf<"數(shù)據(jù)結(jié)構(gòu)">;if<strcmp<str,name[3].c>==0>printf<"匯編語(yǔ)言">;if<strcmp<str,name[4].c>==0>printf<"語(yǔ)言的設(shè)計(jì)和分析">;if<strcmp<str,name[5].c>==0>printf<"計(jì)算機(jī)原理">;if<strcmp<str,name[6].c>==0>printf<"編譯原理">;if<strcmp<str,name[7].c>==0>printf<"操作系統(tǒng)">;if<strcmp<str,name[8].c>==0>printf<"高等數(shù)學(xué)">;if<strcmp<str,name[9].c>==0>printf<"線性代數(shù)">;if<strcmp<str,name[10].c>==0>printf<"普通物理">;if<strcmp<str,name[11].c>==0>printf<"數(shù)值分析">;C::::::::::::::::::教學(xué)計(jì)劃編制問(wèn)題.Cpp#include<stdio.h>#include<stdlib.h>#include<math.h>#include<string.h>#include"SeqStack.h"#include"ALGraph.h"#defineN12intTopologicalOrder<ALGraphG,AdjListR,structNamename[]>{ inti,k,j=0,count,indegree[MAX_VER]; SqStackS; ArcNode*p; FindInDegree<G,indegree>;//對(duì)各頂點(diǎn)求入度 InitStack<S>;//初始化棧 for<i=0;i<G.vexnum;++i>//建零入度頂點(diǎn)棧S if<!indegree[i]>Push<S,i>;//入度為0者進(jìn)棧 count=0;//對(duì)輸出頂點(diǎn)計(jì)數(shù) while<!StackEmpty<S>> { Pop<S,i>; printf<"%s<%d學(xué)分>,",G.ver[i].data,G.ver[i].grades>; R[j++]=G.ver[i];//將當(dāng)前的拓?fù)湫蛄斜４嫫饋?lái) ++count;//輸出i號(hào)頂點(diǎn)并計(jì)數(shù) for<p=G.ver[i].first;p;p=p->next>//對(duì)i號(hào)頂點(diǎn)的每個(gè)鄰接點(diǎn)的入度減1 { k=p->AdjOfV; if<!<--indegree[k]>>//若入度減為0,則入棧 Push<S,k>; } } if<count<G.vexnum> { printf<"此有向圖有回路無(wú)法完成拓?fù)渑判?>; return0; } elseprintf<"為一個(gè)拓?fù)湫?/p>