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

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

2、icrosoftVisualC+6.04. 算法描述:l 程序流程图 开 始l读取文件，将课程信息保存在链表中lll构建课程信息图ll调用拓扑排序，对list排序将结果存入sortedlist中lll利用sortedlist安排课表ll打印课表，并将课表存入文本文件lll 结束lll 类的层次结构，每个类的设计, 包括数据成员和成员函数组成.l class Graphl l public:l virtual int n()=0;l virtual int e()=0;l virtual int first(int)=0;l virtual int next(int,int)=0;l virtu

3、al void setEdge(int,int,int)=0;l virtual void delEdge(int,int)=0;l virtual int weight(int,int)=0;l virtual int getMark(int)=0;l virtual void setMark(int,int)=0;l ;l class Graphm:public Graphl l public:l Graphm(int numVert);l Graphm();l int n();l int e();l int first(int);l int next(int,int);l void se

4、tEdge(int,int,int);l void delEdge(int,int);l int weight(int,int);l int getMark(int);l void setMark(int,int);l private:l int numVertex,numEdge;l int *matrix;l int *mark;l ;l class Linkl l public:l Link();l Link(string code,string name,int period,int semester,string precondition);l string getCode();l

5、void setCode(string str);l string getName();l void setName(string str);l int getPeriod();l void setPeriod(int p);l int getSemaster();l void setSemester(int s);l string getPrecondition();l void setPredition(string str);l Link* getNext();l void setNext(Link*);l private:l string code;l string name;l in

6、t period;l int semester;l string precondition;l Link *next;l ;l class Listl l public:l List();l void addCourse(Link* course);l void insertCourse(Link* course);l Link* getHead();l Link* getTail();l void printlist();l private:l Link *head;l Link *tail;l ;l 测试程序说明l int main()l l readFromFile();/从文件读取课程

7、信息l Graphm graph(38);l buildGraph(list,&graph);/做课程信息图l topsort(&graph);/对图进行拓扑排序l sortedlist.printlist();/打印排序后的结构l cout=0&ch=0&ch=9&(index=0&ch=9&(index0)l l Link*courselink=newLink(courCode,courName,courperiod,l coursemester,courPrecondition);/读取一次完整的信息即可将它生成一个Link节点l list.addCourse(courselink);/

8、将Link节点加入Listl l courCode.erase();/清除string中的内容，用于下一行次读取文件l courName.erase();l courPrecondition.erase();l /whilel input.close();l l /建图，添加有先决条件的结点之间的边l void buildGraph(List &courseList,Graph* courseGraph)l l Link* courselink=courseList.getHead();l int v1=0;l while(courselink!=NULL)l l string str=cou

9、rselink-getPrecondition();l for(int i=0;stri!=0;)l l if(stri=c)/课程以c开头，由此分辨先决条件l l char ch1=str+i;l char ch2=str+i;l int v2=10*(ch1-48)+(ch2-48)-1;/将课程号转换为整型数据,图的下标用int表示的l courseGraph-setEdge(v2,v1,1);l l elsel i+;l l v1+;l courselink=courselink-getNext();l l l void tophelp(Graph* G, int v)/ Proces

10、s v l l G-setMark(v, 0);l for (int w=G-first(v); wn();w = G-next(v,w)l if (G-getMark(w) = 1)l tophelp(G, w);l Link* courselink=list.getHead();l for(int i=0;igetNext();l l sortedlist.insertCourse(courselink);/将拓扑排序的正序存入sortedlist中，用于课程的安排l l void topsort(Graph* G) / Topological sortl l int i;l for (i

11、=0; in(); i+) / Initialize l G-setMark(i,1);l for (i=0; in(); i+) / Do verticesl if (G-getMark(i) = 1)l tophelp(G, i); / Call helperl l void courseArrange()/安排课表l l Link* temp=sortedlist.getHead();l int count8;l for(int i=0;i8;i+)l counti=0;l for(;count0getNext()/优先安排已经预设学期的课程l l if(temp-getSemaster

12、()=1)l count0+;l else if(temp-getSemaster()=2)l count1+;l else if(temp-getSemaster()=3)l count2+;l else if(temp-getSemaster()=4)l count3+;l else if(temp-getSemaster()=5)l count4+;l else if(temp-getSemaster()=6)l count5+;l else if(temp-getSemaster()=7)l count6+;l else if(temp-getSemaster()=8)l count7

13、+;l l temp=sortedlist.getHead();/再按学期顺序安排已经安排学期的课程，srtedlist中的先后顺序对应了学期的先后顺序l for(;temp!=NULL;temp=temp-getNext()l l if(count0getSemaster()=0)l l temp-setSemester(1);l count0+;l l l else if(count1getSemaster()=0)l l temp-setSemester(2);l count1+;l l l else if(count2getSemaster()=0)l l temp-setSemest

14、er(3);l count2+;l l l else if(count3getSemaster()=0)l l temp-setSemester(4);l count3+;l l l else if(count4getSemaster()=0)l l temp-setSemester(5);l count4+;l l l else if(count5getSemaster()=0)l l temp-setSemester(6);l count5+;l l l else if(count6getSemaster()=0)l l temp-setSemester(7);l count6+;l l

15、l else/semter8l l if(temp-getSemaster()=0)l l temp-setSemester(8);l count7+;l l l l lvoid printSchoolTimeTable()/打印课表Link* temp=sortedlist.getHead();/semter1coutcourses of semester 1 :endl;fstream output;output.open(course_table.txt);output第一学期课程: getNext() if(temp-getSemaster()=1) outputgetCode() g

16、etName()endl; coutgetCode() getName()endl; temp=sortedlist.getHead();/semter2coutcourses of semester 2 :endl;output第二学期课程: getNext() if(temp-getSemaster()=2) outputgetCode() getName()endl; coutgetCode() getName()endl; temp=sortedlist.getHead();/semter3coutcourses of semester 3 :endl;output第三学期课程: ge

17、tNext() if(temp-getSemaster()=3) outputgetCode() getName()endl; coutgetCode() getName()endl; temp=sortedlist.getHead();/semter4coutcourses of semester 4 :endl;output第四学期课程: getNext() if(temp-getSemaster()=4) outputgetCode() getName()endl; coutgetCode() getName()endl; temp=sortedlist.getHead();/semte

18、r5coutcourses of semester 5 :endl;output第五学期课程: getNext() if(temp-getSemaster()=5) outputgetCode() getName()endl; coutgetCode() getName()endl; temp=sortedlist.getHead();/semter6coutcourses of semester 6 :endl;output第六学期课程: getNext() if(temp-getSemaster()=6) outputgetCode() getName()endl; coutgetCode

19、() getName()endl; temp=sortedlist.getHead();/semter7coutcourses of semester 7 :endl;output第七学期课程: getNext() if(temp-getSemaster()=7) outputgetCode() getName()endl; coutgetCode() getName()endl; temp=sortedlist.getHead();/semter8coutcourses of semester 8 :endl;output第八学期课程: getNext() if(temp-getSemast

20、er()=8) outputgetCode() getName()endl; coutgetCode() getName()endl; output.close();6.运行结果:l 测试数据选择l (课程编码，课程名称，开课学时，预设开课学期，先决条件)l (c01,程序设计基础,5,0,) (c02,离散数学,6,0,c01)l (c03,数据结构,4,0,c01 c02) (c04,汇编语言,5,0,c01)l （c05,算法设计,4,0,c03 c04) (c06,计算机组成原理,6,0,） l (c07,微机原理,4,0,c03) (c08,单片机应用,3,0,c03)l (c09,

21、编译原理,5,0,c03) (c10,操作系统原理,4,0,c03)l (c11,数据库原理,5,0,c03) (c12,高等数学,6,0,)l (c13,线性代数,6,0,) (c14,数值分析,6,0,c12)l (c15,普通物理,6,0,c12) (c16,计算机文化,3,0,)l (c17,计算机系统结构,6,0,c06) (c18,计算机网络,5,0,c03)l (c19,数据通信,6,0,) (c20,面向对象程序设计,3,0,c01 c03)l (c21,Java,3,0,c01 c03) (c22,C#.net,5,0,c01 c03)l (c23,PowerBuilder,

22、5,0,c01 c03) (c24,VC+,3,0,c01 c03)l (c25,ASP程序设计,6,0,c01 c03) (c26,JSP程序设计,5,0,c01 c03)l (c27,VB.net,5,0,c01 c03) (c28,Delphi,5,0,c01 c03)l (c29,C+Builder,5,0,c01 c03) (c30,英语,5,1,)l (c31,英语,5,2,) (c32,英语,5,3,)l (c33,英语,5,4,) (c34,英语,5,5,)l (c35,英语,5,6,) （c36,英语,5,7,)l (c37,英语,5,8,) (c38,大学语文,3,1,)l

23、 测试结果分析能够正确安排课程。7.实验运行情况分析(包括算法、运行结果、运行环境等问题的总体讨论)。l 收获l （1）进一步了解了图结构；l （2）学会了图在安排课表上的运用；l 特色l （1）存放课程信息时用string 型存放课程编码，在查找先决条件时，借助课程编码都是以c开头的，进行查找不同的先决条件，对用先决条件关系的课程对应的图标记一条边；l （2）用一个数组arry对每学期的课程数进行标记，在每学期的课程安排时，先进行一次遍历将已安排的课程录入array，在进行一次遍历，按照学期顺序进行安排（由于sortedlist是拓扑排序的正序结构，即可以按顺序安排）；l 不足l 对文件的操

24、作显得较复杂8源码CourseList.h#ifndef COURSELIST_H#define COURSELIST_H#include#includeusing namespace std;class Linkpublic:Link();Link(string code,string name,int period,int semester,string precondition);string getCode();void setCode(string str);string getName();void setName(string str);int getPeriod();void

25、setPeriod(int p);int getSemaster();void setSemester(int s);string getPrecondition();void setPredition(string str);Link* getNext();void setNext(Link*);private: string code; string name; int period; int semester; string precondition; Link *next;class Listpublic:List();void addCourse(Link* course);void

26、 insertCourse(Link* course);Link* getHead();Link* getTail();void printlist();private:Link *head;Link *tail;#endifCourseList.cpp#includeCOurseList.hLink:Link()Link:Link(string newcode,string newname,int newperiod,int newsemester,string newprecondition)code=newcode;name=newname;period=newperiod;semest

27、er=newsemester;precondition=newprecondition;next=NULL;string Link: getCode()return code;void Link:setCode(string str)code=str;string Link:getName()return name;void Link:setName(string str)name=str;int Link:getPeriod()return period;void Link:setPeriod(int p)period=p;int Link:getSemaster()return semes

28、ter;void Link:setSemester(int s)semester=s;string Link:getPrecondition()return precondition;void Link:setPredition(string str)precondition=str;Link* Link: getNext()return next;void Link:setNext(Link *newNext)next=newNext;List:List()head=tail=NULL;void List:addCourse(Link* course) Link* temp=new Link

29、(course-getCode(),course-getName(),course-getPeriod(),course-getSemaster(),course-getPrecondition(); if(head=NULL) head=temp; elsetail-setNext(temp); tail=temp;void List:insertCourse(Link* course) Link* temp=new Link(course-getCode(),course-getName(),course-getPeriod(),course-getSemaster(),course-ge

30、tPrecondition(); if(head=NULL) head=temp; else temp-setNext(head); head=temp; Link* List:getHead()return head;Link* List:getTail()return tail;void List:printlist()Link* temp=head;while(temp!=NULL)cout code: getCode();cout name:getName();cout period:getPeriod();cout semester:getSemaster();/cout preco

31、ndition:getPrecondition();temp=temp-getNext();coutendl;Graph.h#ifndef GRAPH_H#define GRAPH_H#includeusing namespace std;class Graphpublic:virtual int n()=0;virtual int e()=0;virtual int first(int)=0;virtual int next(int,int)=0;virtual void setEdge(int,int,int)=0;virtual void delEdge(int,int)=0;virtual int weight(int,int)=0;virtual int getMark(int)=0;virtual void setMark(int,int)=0;class Graphm:public Graphpublic:Graphm(int numVert);Graphm();int n();int e();int first(int);int next(int,int);void setEdge(int,int,int);void delEdge(int,int);int weight(int,int);int getMark(