拓扑排序课程设计Word版.doc

《拓扑排序课程设计Word版.doc》由会员分享，可在线阅读，更多相关《拓扑排序课程设计Word版.doc（64页珍藏版）》请在三一文库上搜索。

1、传播优秀Word版文档 ，希望对您有帮助，可双击去除！课 程 设 计 报 告课程名称 数据结构 课题名称 1.拓扑排序 2.成绩管理 专 业 计算机科学与技术 班 级 计算机1181 学 号 201113030128 姓 名 蔡彪 指导教师 刘铁武 2013年 6月30 日湖南工程学院课 程 设 计 任 务 书课程名称 数据结构 课 题 1.拓扑排序 2.成绩管理 专业班级 计算机1181 学生姓名 蔡彪 学 号 201113030128 指导老师 刘铁武 审 批 任务书下达日期 2013 年 6 月 17 日任务完成日期 2013 年 6 月 30 日一设计内容：问题1：拓扑排序大学期间各专

2、业都要制订相应的教学计划。每个专业开设的课程预先已确定。而各门课程间有的是相互独立的，而有的则有先修后修的限定。试设计相应的课程设置程序，实现对某专业各学期的课程的排布，其中每门课需一定的课时，而各学期的总课时不能超过上限。测试数据学期课时上限数：350各课程所需学时：48课程先、后修关系如图：194212101136578问题3：成绩管理编制一应用软件实现对班级成绩管理。基本功能有学生信息的增删（转入或退学）、查找（从当前点向前或向后双向的）、录入、统计（如总分，及格率等）。建议用双链表实现。二设计要求：课程设计报告内容说明1)需求分析程序的功能；输入输出的要求。2)概要设计程序的模块构成以

3、及模块之间的层次结构、各模块的调用关系；每个模块的功能；课题涉及的数据结构和数据库结构；即要存储什么数据，这些数据是什么样的结构，它们之间有什么关系等。3)详细设计采用C语言定义相关的数据类型；写出各模块的类C码算法；画出各函数的调用关系图、主要函数的流程图。4)调试分析以及设计体会测试数据：准备典型的测试数据和测试方案，包括正确的输入及输出结果和含有错误的输入及输出结果；程序调试中遇到的问题以及解决问题的方法；课程设计过程经验教训、心得体会。5)使用说明用户使用手册：说明如何使用你编写的程序，详细列出每一步的操作步骤。6)书写格式见附带说明。7)附录参考书目； 源程序清单（带注释）成绩评定：

4、指导老师负责验收程序的运行结果，并结合学生的工作态度、实际动手能力、创新精神和设计报告等进行综合考评，并按优秀、良好、中等、及格和不及格五个等级给出每位同学的课程设计成绩。具体考核标准包含以下几个部分： 平时出勤 （占10%） 系统需求分析、功能设计、数据结构设计及程序总体结构合理与否（占10%） 程序能否完整、准确地运行，个人能否独立、熟练地调试程序（占40%） 设计报告（占30%）注意：不得抄袭他人的报告（或给他人抄袭），一旦发现，成绩为零分。 独立完成情况（占10%）。 运行所设计的系统。三.进度安排第17周星期一星期二星期三星期四星期五星期六星期日上午8：0012：008:3011:3

5、08:3011:30下午13：3017：3013:0016:00第18周星期一星期二星期三星期四星期五星期六星期日上午8：0012：008:3011:30下午13：3017：3013:0016:0013:0016:00参考书籍1.C程序设计课程设计 刘振安编著 TP312C5632.C+ Builder和Delphi课程设计与系统开发案例 伍俊良 清华大学出版社 7-302-06072-X 3.Visual C+课程设计案例精编 严华峰 中国水利水电出版社 7-5084-2007-1 2004 4.Visual C+课程设计与系统开发案例 伍俊良 清华大学出版社 7-302-05968-3 2

6、0025.Visual C+语言课程设计 : 案例精选与编程指导 陈清华朱红 东南大学出版社 7-81089-275-4 2003 6.VisualC+课程设计案例精编 中国水利水电出版社 7-5084-1004-1 2002 7.数据结构课程设计案例精编 : 用C/C+描述 李建学李光元吴春芳 清华大学出版社 7-302-14536-9 2007 （编程平台不限，vc+, c+ Builder等等。）目 录课题1第一章 拓扑排序（一）目的与要求(二)设计方法与原理 (三)需求分析 第二章 总体设计（一）系统流程图 （二）详细设计第三章 系统调试 （一）系统调试（二）结果分析第四章 总结附录：

7、源程序课题2第一章 成绩管理 （一）目的与要求(二)设计方法与原理 (三)需求分析 第二章 总体设计（一）系统流程图 （二）详细设计第三章 系统调试（一）系统调试（二）结果分析第四章 总结附录：源程序课题1第1章 ：拓扑排序（1）目的与要求： 目的： （1）要求学生达到熟练掌握语言的基本知识和技能； （2）基本掌握面向对象程序设计的基本思路和方法； （3）能够利用所学的基本知识和技能，解决简单的程序设计问题。 要求： （1）选择合适的存储结构，建立有向无环图，并输出该图； （2）实现拓扑排序算法； （3）运用拓扑排序实现对教学计划安排的检验。（2）设计方法与原理 在AOV网中为了更好地完成工程

8、，必须满足活动之间先后关系，需要将各活动排一个先后次序即为拓扑排序。拓扑排序可以应用于教学计划的安排，根据课程之间的依赖关系，制定课程安排计划。按照用户输入的课程数，课程间的先后关系数目以及课程间两两间的先后关系，程序执行后会给出符合拓扑排序的课程安排计划。（3）需求分析 程序的功能： 该程序的功能主要是根据图的拓扑排序算法，依某专业的课程先、后修关系图，实现该专业课程的排布。其中，每门课程需设定课时，而各学期的总课时不能超过上限。 输入输出要求： 首先，创建课程先、后关系图。其中，需要输入该关系图的结点数(课程数)、结点信息及弧的信息等；然后，输入该专业课程的学期数，并在拓扑排序过程中，依次

9、输入某学期的课程安排。所以，最终输出为各个学期所安排的课程结果，并且，课程安排符合课程先、后关系图的一个拓扑排序。第2章 ：总体设计（1）系统流程图 1.1.1模块功能流程图 程序调用关系及模块功能运行流程如下： 结束拓扑排序创建图退出系统分支选择处理 主函数main() 开始 1 2 3 图1.1 程序调用关系及模块功能流程图 1.1.2数据结构及数据类型 图的存储结构有邻接矩阵和邻接表。在该程序中采用了邻接表来存储有向图。在邻接表中，需要定义头结点的结构体数据类型，用以存储图的结点信息，并且在每个头结点后连接一个单链表，用以存储以该头结点为弧尾，链表中结点为弧头的弧。所以还需定义表结点的结

10、构体数据类型，用以存储图中弧的信息。最后，定义有向图的结构体数据类型，其中的数据项包含一个指向头结点首地址的指针和顶点数、弧数的整型数据类型。 1.1.3 拓扑排序算法 拓扑排序算法描述如下： (1)在有向图中选一个没有前驱的顶点且输出之。即入度为零的结点。 (2)从图中删除该顶点和所有以它为尾的弧。即以该结点为弧尾的弧的弧头结点的入度值减一。 (3)重复上述两步，直至全部结点均已输出，或者当前结点中不存在无前驱的顶点为止。后一种情况则说明有向图中存在环，拓扑排序失败。 然而，在此课题中是为了依拓扑排序算法而设计课程的安排序列。显然，在同一学期里的课程是相互独立的，不存在先、后修关系。由此，对

11、于某个学期课程的安排，其安排的课程范围是有向图中某次拓扑排序中所有没有前驱顶点结点的集合，则该学期课程的安排可以在该集合中选择，并且选择结果满足的总课时没有超过上限。同时，由此次选择结果，可以产生下个学期课程安排的范围。重复上述操作，直至所有课程都选择完。另外，还应设计一个能够检测所有课程是否在规定的学期内修完。若检测到在规定学期内课程没有修完，则需重新设定学期数或者重新进行课程安排。（2）详细设计 1.2.1 采用C语言定义结构体数据类型 1.2.1.1 头结点的顶点信息结构体数据类型 typedef struct VertexType char name20;/顶点编号，即课程编号 cha

12、r sbname20;/课程名称 int Outdegree;/顶点的出度 int Indegree;/顶点的入度 int weight;/课时 bool mark;/在拓扑排序时，标记该结点是否已访问 int id;/确定该课程属于哪个学期 VertexType; 1.2.1.2 头结点结构体数据类型 typedef struct VNode VertexType data;/顶点信息 ArcNode *first;/指向第一条依附该结点的弧的指针 VNode; 1.2.1.3 表结点结构体数据类型 typedef struct ArcNode int adjvex;/该弧所指向的顶点的位置

13、 struct ArcNode*next;/指向下一条弧的指针 ArcNode; 1.2.1.4 图的结构体数据类型 typedef struct Graph VNode *head;/指向头结点首地址的指针 int vexnum,arcnum;/图的定点数和弧数 Graph; 1.2.1.5 学期课程结构体数据类型 Typedef struct Subject int count;/某学期所安排的课程数 int *head;/某学期所安排课程对应结点在图中的存储置 Subject,*PSubject; 1.2.2 各模块的类C码算法 1.2.2.1 创建有向图的类C码算法： Status G

14、Create(Graph&G) scanf(%d,G.vexnum); if(!(G.head=(VNode*)malloc(G.vexnum*sizeof(VNode) exit(OVERFLOW); for(i=0;inext!=NULL) ptr1=ptr1-next; if(!(ptr2=(ArcNode*)malloc(sizeof( ArcNode)exit(OVERFLOW); ptr2-adjvex=m; ptr1-next=ptr2; Ptr2-next=NULL; G.headn.data.Outdegree+; G.headm.data.Indegree+; return

15、 OK; 1.2.2.2 拓扑排序的类C码算法： Status GSort(Graph G,int MAX) scanf(%d,&n);/输入学期数 PSubject p;/对p分配连续的n个空间，并对p进行初始化 /其中，count初始化为零，指针head分配连续的G.vexnum个空间 k=0;i=0; while(k=n) while(iG.vexnum) max=0;x=0;mark=false; /max标记某学期的总课时，x标记某学期的课程数 /mark用于判断有向图中是否存在回路 for(j=0;jMAX) max-=G.headm.data.weight; /若所选课程的总课时

16、超出上限，则选择其 它可选课程或退出当前学期的课程安排 选择 else if(k=n) break;/课程安排已超过所安排的 学期数，则推出课程选择 pk.headx=m;/存储该学期所选 课程所对应头结点在在图中的存储位置 G.headm.data.mark=true;/标 记该头结点已被排序了 ptr2=G.headm.first-next; i+; x+; while(ptr2!=NULL)/使以该头结 点为弧尾的所有弧的弧头结点的入度减 一及其学期标号作相应的变换 if(G.headptr2-adjvex. data.id=k+1) G.headptr2-adjvex. data.id

17、+; G.headptr2-adjvex. data.Indegree-; ptr2=ptr2-next; if(n=k)/若课程安排已超过所安排的学期数，则重新设定 学期数或重新进行课程安排 scanf(%d,&y);/输入操作选择项 switch(y) case 1:/重新设定学期数 scanf(%d,&n);/重新输入学期数，并对p重 新分配连续的n个空间，并对其进行初始化 break; case 2:/重新进行课程安排 break; default:break; G=SetG(G);/对图进行初始化处理，并依存储结构产生各 头结点的度值 i=0;k=0; continue; pk.co

18、unt=x; k+; /课程以选完，而学期的课程没有安排完 if(k=n) break; printf(.n);/输出课程已安排完，该学期没有课程 安排 k+; printf(p);/输出各学期的课程安排 return OK; 第3章 ：系统调试（1）系统调试 1.3.1 调试分析 1.3.1.1 测试数据：(如下图所示的有向图) 194212101136578 图1.2 课程先、后修关系图 另外，学期课时上限数为：120 1.4.1.2 测试方案 (1)正确的输入及输出： 1、构建图1.2所示的有向图 图1.3 输入图中的顶点信息 图 1.4 输入图中的弧 2、拓扑排序过程(即课程安排过程)

19、 图 1.5 输入学期课时上限数及学期数 图 1.6 第一学期的课程安排 图1.7 第二、三学期的课程安排 图1.8 第四学期的课程安排 图 1.9 学期课程安排已超过学期数并重新输入学期数或重新安排学期课程 图1.10 重新安排第一、二学期的课程 图1.11 重新安排第三、四学期的课程 图1.12 重新安排第五、六学期的课程 图1.13 各学期课程安排结果 3、构建一个存在环的有向图并进行拓扑排序 图1.14 构建一个存在环的有向图 图1.15 因图中存在回路，拓扑排序失败 (2)错误的输入及输出 若在创建图时，输入有相同编号的结点，则可能使程序的输出发生错误,使程序不能结束。 图1.16

20、在创建图的过程中，输入的结点编号存在相同 图1.17 因图中有结点编号相同的结点而产生错误的选定课程的结果（2）结果分析 在开始调试程序的过程中，遇到的主要问题是逻辑错误及程序不能实现所需的要求。第一个问题是：怎样依拓扑排序的算法来产生某个学期的课程安排，另外，怎样确定某个学期到底安排几门课程。若把所有拓扑排序结果都输出出来，显然，这是一个非常不好的想法。经过对这个问题的思考后，若把某个学期所能选的课都显示出来，然后，用户根据显示出来的课程来安排该学期的课程，随后，依安排结果产生下个学期所能选的课程的集合。该种想法不仅解决了怎样依拓扑排序来安排某个学期的课程，并且给用户安排课程提供了很大的灵活

21、性，用户可以根据需求来安排某个学期的课程。第一个问题得到解决并编写程序后，便产生了第二个问题：在产生的某个学期所能安排的课程范围里存在有先后关系的课程或程序不能结束。经过分析发现：在选取某个学期所能安排课程的集合的过程中，会使图中的某些结点的入度由非零减到成零，使原本应为下一学期的课程变换到当前学期中，所以应设定一个课程学期标号，标记课程在拓扑排序过程中所对应的学期。由此，在头结点的信息域中增设了一个整型变量id，用以标记在拓扑排序中该结点应该属于哪个学期，并为拓扑排序增设了一个条件限制。第四章：总结 通过对该课题的设计过程，不仅让我对图的存储方法及图的拓扑排序算法加深了理解，更让我深深的了解

22、到理论知识与实践应用上的区别。该课题在理论上是应用了图的拓扑排序的思想，然而它不是单纯的拓扑排序，而是在拓扑排序的基础上，应用图的拓扑排序来解决课程安排的问题。课程安排的结果不仅要符合拓扑排序的要求，并且在同一学期的课程是相互独立的，所以，这就要设计新的算法，对拓扑序列的产生添加新的限制条件。同时，也让我认识到算法在程序设计中的重要性，算法是程序设计的灵魂。附录：源程序#include#include#include/表结点typedef struct ArcNodeint adjvex;struct ArcNode*next;ArcNode;/顶点信息typedef struct Verte

23、xTypechar name20;char sbname20;int Outdegree;int Indegree;int weight;bool mark;int id;VertexType;/头结点typedef struct VNodeVertexType data;ArcNode*first;VNode;/图数据类型typedef struct GraphVNode *head;int vexnum,arcnum;Graph;/存储课程信息的结构体数据类型typedef struct Subjectint count;int*head;Subjiect,*PSubject;int GL

24、ocateVex(Graph G,char ch)for(int i=0;iG.vexnum;i+)if(!strcmp(G.headi.data.name,ch)return i;printf(改图中没有该结点!n);return -1;/建立有向图-邻接表Graph GCreate()Graph G;ArcNode*ptr1,*ptr2;char ch110,ch210;int n,m,j=0;printf( 创建该专业课程先、后修关系图:请输入图的顶点数(课程数)及弧数：n);printf( 顶点数：VEXNUM=);scanf(%d,&G.vexnum);printf(n 输入图中顶点的基本信息：(课程信息)n); printf( -课程编号-课程名称-课时-n);G.head=(VNode*)malloc(G.vexnum*sizeof(VNode);if(G.head=NULL)printf(内存分配错误!n);exit(0);for(int i=0;iG.vexnum;i+)scanf(%s%s%d,&G.headi.data.name,&G.headi.data.sbname,&G.headi.data.weight);G.headi.data.Outdegree=0;G.headi