數(shù)據(jù)結(jié)構(gòu)與算法實驗_課表安排

1、數(shù)據(jù)結(jié)構(gòu)與算法分析課程設(shè)計報告課題名稱：打印輸出計算機本科專業(yè) 4年每學(xué)期的課表提交文檔學(xué)生姓名：提交文檔學(xué)生學(xué)號：同組成員名單：指導(dǎo)教師姓名：指導(dǎo)教師評閱成績：指導(dǎo)教師評閱意見：提交報告時間：2010年12月 日1.2.3.4.1.2.3.4.實驗題目：拓撲排序一一打印輸出計算機本科專業(yè)4年每學(xué)期的課表 實驗的目的和要求：（1）采用C+實現(xiàn)；（2）熟練掌握圖的應(yīng)用；（3）熟練掌握圖的鄰接矩陣存儲結(jié)構(gòu)以級拓撲排序的基本思想;（4）上機調(diào)試程序，掌握查錯，排錯使程序能正確運行。 實驗的環(huán)境：（1）硬件環(huán)境：聯(lián)想G450筆記本電腦（2）軟件環(huán)境：WindowsXP, MicrosoftVisual

2、C+6.0算法描述：讀取文件，將課程信息 保存在鏈表中程序流程圖構(gòu)建課程信息圖調(diào)用拓撲排序，對list排序?qū)⒔Y(jié)果存入sortedlist中利用sortedlist安排課表打印課表，并將課表 存入文本文件（ 結(jié)束 丿類的層次結(jié)構(gòu)，每個類的設(shè)計，包括數(shù)據(jù)成員和成員函數(shù)組成.class Graphpublic:virtual int n()=0;virtual int e()=0;virtual int first(i nt)=0;virtual int n ext(i nt,i nt)=0;virtual void setEdge(i nt,i nt, in t)=0;virtual void d

3、elEdge(i nt,i nt)=0;virtual int weight(i nt, in t)=0;virtual int getMark(i nt)=0;virtual void setMark(i nt,i nt)=0;class Graphm:public Graphpublic:Graphm(i nt numVrt);Graphm();int n ();int e();int first(i nt);int n ext(i nt, in t);void setEdge(i nt, in t,i nt);void delEdge(i nt,i nt);int weight(i nt

4、,i nt);in t getMark(i nt);void setMark(i nt,i nt);private:int num Vertex ,nu mEdge;int *matrix;int *mark;class Linkpublic:Lin k();Li nk(stri ng code,stri ng n ame,i nt period,i nt semester,stri ng prec on diti on); stri ng getCode();void setCode(stri ng str);stri ng getName();void setName(stri ng st

5、r);int getPeriod();void setPeriod(i nt p);int getSemaster();void setSemester(i nt s);stri ng getPrec on diti on(); void setPreditio n(stri ng str);Li nk* getNext();void setNext(L in k*);private:stri ng code;stri ng n ame;int period;int semester;stri ng prec on diti on;Link *n ext;class Listpublic:Li

6、st();void addCourse(L ink* course); void in sertCourse(L ink* course);Li nk* getHead();Li nk* getTail();void prin tlist();private:Link *head;Link *tail;測試程序說明int mai n()readFromFile()從文件讀取課程信息Graphm graph(38);buildGraph(list,&graph)做課程信息圖 topsort(&graph)對圖進行拓撲排序 sortedlist.pri ntlist()打印排序后的

7、結(jié)構(gòu) cout«e ndl;courseArra nge()安 排課表prin tSchoolTimeTable(打/印課表，并將其存入文件 return 0;5.源程序清單：添加必要的注釋static List list;/存放初始課程信息static List sortedlist;/存放拓撲排序后的課程信息(順序)static int arrayn um8;保存每個學(xué)期要開設(shè)的課程數(shù)目static int in dex; /共八個學(xué)期static stri ng courName;/從文件讀取課程編碼static stri ng courCode;/從文件讀取課程名稱stati

8、c stri ng courPreco nditio n;從文件讀取課程的先決條件static in t courperiod;/從文件讀取對應(yīng)課程的開設(shè)學(xué)時數(shù)static in t coursemester;/從文件讀取對應(yīng)課程的開課學(xué)期/讀取文件數(shù)據(jù)，創(chuàng)建listvoid readFromFile()fstream in put;in put.ope n("course_ in f.txt");char ch;ch=in put.get();while( !(ch>='0'&&ch<='9') )/開始出現(xiàn)數(shù)字

9、時，開始讀取 arraynumch=in put.get();if(ch>='0'&&ch<='9 '&&(in dex<8)while(ch!='n')if(ch>='0'&&ch<='9'&&(in dex<8)array nu mi ndex+=ch-48;將讀入的字符轉(zhuǎn)換成對應(yīng)數(shù)字ch=in put.get();while(ch!='c')ch=in put.get();while(ch!=&

10、#39;n')ch=in put.get();跳過所有注釋行while(!i nput.eof()if(ch='c')while(ch!=9)courCode.insert(courCode.size(),1,ch);讀取 courCodech=in put.get();while(ch=9)ch=in put.get();while(ch!=9)courName.insert(courName.size(),1,ch);讀取 courNamech=in put.get();while(ch=9)ch=in put.get();courperiod=ch-48;讀取 c

11、ourperiodch=in put.get();while(ch=9)ch=in put.get();coursemester=ch-48;讀取 coursemesterch=in put.get();while(ch=9)ch=in put.get();if(ch='c')while(ch!='n')讀取 courPrec on diti oncourPrec on diti on .i nsert(courPrec on diti on .size(),1,ch);ch=in put.get(); /ifch=in put.get();if(courCod

12、e.size()>0)Lin k*courseli nk=n ewLi nk(courCode,courName,courperiod,coursemester,courPrecondition);讀取一次完整的信息即可將它生成一個Link節(jié)點list.addCourse(courselink);將 Link 節(jié)點加入 ListcourCode.erase(); 清除string中的內(nèi)容，用于下一行次讀取文件courName.erase();courPrec on diti on. erase();/whilein put.close();/建圖，添加有先決條件的結(jié)點之間的邊void b

13、uildGraph(List &courseList,Graph* courseGraph)Link* courseli nk=courseList.getHead();in t v1=0;while(coursel in k!=NULL)stri ng str=courseli nk->getPrec on diti on();for(i nt i=O;stri!='O')if(stri='c')課程以c開頭，由此分辨先決條件char ch1=str+i;char ch2=str+i;int v2=10*(ch1-48)+(ch2-48)-1;將

14、課程號轉(zhuǎn)換為整型數(shù)據(jù)，圖的下標(biāo)用int表示的courseGraph->setEdge(v2,v1,1);elsei+;v1+;courseli nk=courseli nk->getNext();void tophelp(Graph* G, i nt v)/ Process vG->setMark(v, 0);for (int w=G->first(v); w<G->n();w = G_>n ext(v,w)if (G->getMark(w) = 1)tophelp(G, w);Link* courseli nk=list.getHead();f

15、or(i nt i=0;i<v;i+)courseli nk=courseli nk->getNext();sortedlist.insertCourse(courselink);將拓撲排序的正序存入 sortedlist 中，用于課程的安排void topsort(Graph* G) / Topological sortint i;for (i=0; i<G-> n(); i+) / I ni tializeG->setMark(i,1);for (i=0; i<G-> n(); i+) / Do verticesif (G->getMark(

16、i) = 1)tophelp(G, i);/ Call helper void courseArrange() 安排課表Link* temp=sortedlist.getHead();int coun t8;for(i nt i=0;i<8;i+)coun ti=0;for(;co un t0<7&&temp!=NULL;temp=temp->getNext()優(yōu)先安排已經(jīng)預(yù)設(shè)學(xué)期的課程if(temp->getSemaster()=1)cou ntO+;else if(temp->getSemaster()=2)cou nt1+;else if(t

17、emp->getSemaster()=3)cou nt2+;else if(temp->getSemaster()=4)cou nt3+;else if(temp->getSemaster()=5)coun t4+;else if(temp->getSemaster()=6)coun t5+;else if(temp->getSemaster()=7)cou nt6+;else if(temp->getSemaster()=8)coun t7+;中的先temp=sortedlist.getHead();/再按學(xué)期順序安排已經(jīng)安排學(xué)期的課程，srtedlist

18、后順序?qū)?yīng)了學(xué)期的先后順序for(;temp!=NULL;temp=temp->getNext()if(co un t0<arra ynum 0)/semter1if(temp->getSemaster()=O)temp->setSemester(1);coun t0+;else if(co un t1<arra ynu m1)/semter2if(temp->getSemaster()=0)temp->setSemester(2);cou nt1+;else if(co un t2<arra ynu m2)/semter3if(temp->

19、;getSemaster()=0)temp->setSemester(3);coun t2+;else if(co un t3<arra ynu m3)/semter4if(temp->getSemaster()=0)temp->setSemester(4);coun t3+;else if(co un t4<arra ynu m4)/semter5if(temp->getSemaster()=0)temp->setSemester(5);coun t4+;else if(co un t5<arra ynu m5)/semter6if(temp-

20、>getSemaster()=O)temp->setSemester(6);coun t5+;else if(co un t6<arra ynu m6)/semter7if(temp->getSemaster()=0)temp->setSemester(7);coun t6+;else/semter8if(temp->getSemaster()=0)temp->setSemester(8);coun t7+;void prin tSchoolTimeTable() 打印課表Li nk* temp=sortedlist.getHead();/semter

21、1 cout«"courses of semester 1 :"<<e ndl; fstream output;output.ope n("course_table.txt");outputvv 第一學(xué)期課程:"<<e ndl; for(;temp!=NULL;temp=temp->getNext()if(temp->getSemaster()=1)outputv<temp->getCode()vv'"vvtemp->getName()vve ndl; cout&

22、lt;vtemp->getCode()vv""vvtemp->getName()vve ndl;temp=sortedlist.getHead();/semter2cout<<"courses of semester 2 :"<<e ndl; outputvv 第二學(xué)期課程:"<<e ndl; for(;temp!=NULL;temp=temp->getNext() if(temp->getSemaster()=2)outputvvtemp->getCode()vv'&q

23、uot;v<temp->getName()vve ndl; coutvvtemp->getCode()vv""v<temp->getName()vve ndl;temp=sortedlist.getHead();/semter3cout<<"courses of semester 3 :"<<e ndl; outputvv第三學(xué)期課程:"<<e ndl; for(;temp!=NULL;temp=temp->getNext()if(temp->getSemaster(

24、)=3) outputvvtemp->getCode()vv'"v<temp->getName()vve ndl; cout<vtemp->getCode()vv""vvtemp->getName()vve ndl;temp=sortedlist.getHead();/semter4 cout<<"courses of semester 4 :"<<e ndl; outputvv第四學(xué)期課程:"<<e ndl; for(;temp!=NULL;temp=t

25、emp->getNext() if(temp->getSemaster()=4)outputv<temp->getCode()vv'"vvtemp->getName()vve ndl; cout<vtemp->getCode()vv""vvtemp->getName()vve ndl;temp=sortedlist.getHead();/semter5 cout<<"courses of semester 5 :"<<e ndl; outputvv第五學(xué)期課程:&q

26、uot;<<e ndl; for(;temp!=NULL;temp=temp->getNext() if(temp->getSemaster()=5)outputvvtemp->getCode()vv'"v<temp->getName()vve ndl; coutvvtemp->getCode()vv""v<temp->getName()vve ndl;temp=sortedlist.getHead();/semter6cout<<"courses of semester 6

27、 :"<<e ndl; outputvv第六學(xué)期課程:"<<e ndl; for(;temp!=NULL;temp=temp->getNext()if(temp->getSemaster()=6) outputv<temp->getCode()vv"'vvtemp->getName()vve ndl; cout<vtemp->getCode()vv""vvtemp->getName()vve ndl;temp=sortedlist.getHead();/semter

28、7 cout<<"courses of semester 7 :"<<e ndl; outputvv第七學(xué)期課程:"<<e ndl;for(;temp!=NULL;temp=temp->getNext()if(temp->getSemaster()=7)outputv<temp->getCode()vv"'vvtemp->getName()vve ndl; cout<vtemp->getCode()vv""vvtemp->getName()vv

29、e ndl;temp=sortedlist.getHead();/semter8 cout<<"courses of semester 8 :"<<e ndl; output< <第八學(xué)期課程:"<<e ndl;for(;temp!=NULL;temp=temp->getNext()if(temp->getSemaster()=8)outputv<temp->getCode()vv"'vvtemp->getName()vve ndl; cout<vtemp->

30、;getCode()vv""vvtemp->getName()vve ndl; output.close();6.運行結(jié)果：測試數(shù)據(jù)選擇(課程編碼，課程名稱，開課學(xué)時，預(yù)設(shè)開課學(xué)期，先決條件)離散數(shù)學(xué)",6,0,"c01")("c01","程序設(shè)計基礎(chǔ)",5,0,"")("c02","0廠 OH3等口語通S52 «語散據(jù)悟+B e£大英數(shù)滋髙eS英離數(shù)eS英Ct ysPSES! 809632 U1546714 U223 U39 0

31、331111 03110100 o 3 0 ft 0 3 2 ccccccccccccccccccccccsnffla»関1-p ps s s u J A ec23 Powei'Wuildei' c22 C# .hsf!c21 Java石計 er設(shè) st序用me 理應(yīng)理計se 屈機。語向0 9®- oes英面或操es聲essshsFTT , _ t sst 羞理原Ine 象網(wǎng)原統(tǒng)se 對機景£悟八英ken5 0-810UL8 7 5 u 73 2 111 o 0 0 0 0 0 3 c c c c c c Elcc c c c能夠正確安排課程。7.

32、實驗運行情況分析（包括算法、運行結(jié)果、運行環(huán)境等問題的總體討論）收獲（1）進一步了解了圖結(jié)構(gòu);(2)學(xué)會了圖在安排課表上的運用；特色(1) 存放課程信息時用string型存放課程編碼，在查找先決條件時，借助課程編碼都是以'c' 開頭的，進行查找不同的先決條件，對用先決條件關(guān)系的課程對應(yīng)的圖標(biāo)記一條邊；(2) 用一個數(shù)組arry對每學(xué)期的課程數(shù)進行標(biāo)記，在每學(xué)期的課程安排時，先進行一次遍歷將 已安排的課程錄入array，在進行一次遍歷，按照學(xué)期順序進行安排(由于sortedlist 是拓撲 排序的正序結(jié)構(gòu)，即可以按順序安排)；不足對文件的操作顯得較復(fù)雜8源碼CourseList.

33、h#ifndef COURSELIST_H#defi ne COURSELIST_H#in clude<iostream>#in cludevstri ng>using n amespace std;class Link public:Lin k();Lin k(stri ng code,stri ng n ame,i nt period,i nt semester,stri ng prec on diti on); stri ng getCode();void setCode(stri ng str);stri ng getName();void setName(stri

34、ng str);int getPeriod();void setPeriod(i nt p);int getSemaster();void setSemester(i nt s);stri ng getPrec on diti on();void setPreditio n(stri ng str);Li nk* getNext();void setNext(L in k*);private:stri ng code;stri ng n ame;int period;int semester;stri ng prec on diti on;Link *n ext;class Listpubli

35、c:List();void addCourse(L ink* course);void in sertCourse(L ink* course);Link* getHead();Li nk* getTail();void prin tlist();private:Link *head;Li nk *tail;#en difCourseList .cpp#i nclude"COurseList.h"Li nk:Li nk()Li nk:Li nk(stri ng n ewcode,stri ng newn ame,i nt n ewperiod,i nt n ewsemest

36、er,stri ng n ewprec on diti on)code=n ewcode;n ame=newn ame;period=n ewperiod;semester =n ewsemester;prec on diti on=n ewprec on diti on; n ext=NULL;stri ng Lin k: getCode()retur n code;void Lin k:setCode(stri ng str)code=str;stri ng Lin k:getName()return n ame;void Lin k:setName(stri ng str)n ame=s

37、tr;int Lin k:getPeriod()retur n period; void Lin k:setPeriod(i nt p)period=p;int Li nk:getSemaster()return semester;void Lin k:setSemester(i nt s)semester=s;stri ng Lin k:getPrec on diti on()retur n prec on diti on;void Lin k:setPrediti on( stri ng str)prec on diti on=str;Link* Lin k: getNext()retur

38、n n ext;void Lin k:setNext(Li nk *n ewNext)n ext=n ewNext;List:List()head=tail=NULL;void List:addCourse(L ink* course)Link*temp=newLin k(course->getCode(),course->getName(),course->getPeriod(),course->getSemaster(),course->getPrec on diti on();if(head=NULL)head=temp;elsetail->setNe

39、xt(temp);tail=temp;void List:i nsertCourse(L ink* course)Link*temp=newLin k(course->getCode(),course->getName(),course->getPeriod(),course->getSemaster(),course->getPrec on diti on();if(head=NULL)head=temp;elsetemp->setNext(head);head=temp;Link* List:getHead() retur n head;Link* Li

40、st:getTail()return tail;void List:pri ntlist()Link* temp=head;while(temp!=NULL)cout«" code: "<<temp->getCode();cout«" n ame:"«temp->getName();cout«" period:"«temp->getPeriod();cout«" semester:"«temp->getSema

41、ster();/coutvv" prec on ditio n:"v<temp->getPrec on ditio n(); temp=temp->getNext();cout«e ndl;Graph.h#ifndef GRAPH_H#defi ne GRAPH_H#in clude<iostream>using n amespace std;class Graphpublic:virtual int n()=0;virtual int e()=0;virtual int first(i nt)=O;virtual int n ext(i nt,i nt)=O;virtual void setEdge(i nt,i nt, in t)=O; virtual void delEdge(i nt,i nt)=O;virtual int weight(i nt,i nt)=O; virtual in t getMark(i nt)=O;virtual void setMark(i nt,i nt)