数据结构与算法实验_课表安排

1、数据结构与算法分析课程设计报告课题名称：打印输出计算机本科专业 4年每学期的课表提交文档学生姓名：提交文档学生学号：同组成员名单：指导教师姓名：指导教师评阅成绩：指导教师评阅意见：提交报告时间：2010年12月 日1.2.3.4.1.2.3.4.实验题目：拓扑排序一一打印输出计算机本科专业4年每学期的课表 实验的目的和要求：（1）采用C+实现；（2）熟练掌握图的应用；（3）熟练掌握图的邻接矩阵存储结构以级拓扑排序的基本思想;（4）上机调试程序，掌握查错，排错使程序能正确运行。 实验的环境：（1）硬件环境：联想G450笔记本电脑（2）软件环境：WindowsXP, MicrosoftVisual

2、C+6.0算法描述：读取文件，将课程信息 保存在链表中程序流程图构建课程信息图调用拓扑排序，对list排序将结果存入sortedlist中利用sortedlist安排课表打印课表，并将课表 存入文本文件（ 结束 丿类的层次结构，每个类的设计，包括数据成员和成员函数组成.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、结构 cout«e ndl;courseArra nge()安 排课表prin tSchoolTimeTable(打/印课表，并将其存入文件 return 0;5.源程序清单：添加必要的注释static List list;/存放初始课程信息static List sortedlist;/存放拓扑排序后的课程信息(顺序)static int arrayn um8;保存每个学期要开设的课程数目static int in dex; /共八个学期static stri ng courName;/从文件读取课程编码static stri ng courCode;/从文件读取课程名称stati

8、c stri ng courPreco nditio n;从文件读取课程的先决条件static in t courperiod;/从文件读取对应课程的开设学时数static in t coursemester;/从文件读取对应课程的开课学期/读取文件数据，创建listvoid readFromFile()fstream in put;in put.ope n("course_ in f.txt");char ch;ch=in put.get();while( !(ch>='0'&&ch<='9') )/开始出现数字

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;将读入的字符转换成对应数字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节点list.addCourse(courselink);将 Link 节点加入 ListcourCode.erase(); 清除string中的内容，用于下一行次读取文件courName.erase();courPrec on diti on. erase();/whilein put.close();/建图，添加有先决条件的结点之间的边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、课程号转换为整型数据，图的下标用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()优先安排已经预设学期的课程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();/再按学期顺序安排已经安排学期的课程，srtedlist

18、后顺序对应了学期的先后顺序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 第一学期课程:"<<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 第二学期课程:"<<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第三学期课程:"<<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第四学期课程:"<<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第五学期课程:&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第六学期课程:"<<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第七学期课程:"<<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< <第八学期课程:"<<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.运行结果：测试数据选择(课程编码，课程名称，开课学时，预设开课学期，先决条件)离散数学",6,0,"c01")("c01","程序设计基础",5,0,"")("c02","0厂 OH3等口语通S52 «语散据悟+B e£大英数滋髙eS英离数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设 st序用me 理应理计se 屈机。语向0 9®- oes英面或操es聲essshsFTT , _ t sst 羞理原Ine 象网原统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、实验运行情况分析（包括算法、运行结果、运行环境等问题的总体讨论）收获（1）进一步了解了图结构;(2)学会了图在安排课表上的运用；特色(1) 存放课程信息时用string型存放课程编码，在查找先决条件时，借助课程编码都是以'c' 开头的，进行查找不同的先决条件，对用先决条件关系的课程对应的图标记一条边；(2) 用一个数组arry对每学期的课程数进行标记，在每学期的课程安排时，先进行一次遍历将 已安排的课程录入array，在进行一次遍历，按照学期顺序进行安排(由于sortedlist 是拓扑 排序的正序结构，即可以按顺序安排)；不足对文件的操作显得较复杂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)