数据结构与算法课程设计报告--教学计划编制.docx

1、数据结构与算法课程设计报告题 目 : 教 学 计 划 编 制 目 录一、需求分析31.1 系统概述31.1.1 研究背景31.1.2 研究意义及目的31.2 具体分析41.2.1 功能需求分析41.2.2 运行环境4二、总体设计5三、数据储存结构的设计63.1 采用邻接表的方式储存先修关系图63.2 邻接表储存的代码实现63.2.1 数据结构设计63.2.2 AOV 图的创建代码7四、功能实现算法设计94.1 拓扑排序算法设计94.2 获取各个顶点的入度算法设计114.3 分类型输出算法设计11五、程序代码12六、运行结果20七、课程设计总结22教 学 计 划 编 制 问 题 课 程 设 计

2、报 告一 、 需 求 分 析1 .1 系统概述1.1.1 研究背景大学的每个专业都要制定教学计划。假设任何专业都有固定的学习年限，每 学年含两学期，每学期的时间长度和学分上限值均相等。每个专业开设的课程都 是确定的，而且课程在开设时间的安排必须满足先修关系。每门课程有哪些先修 课程是确定的，可以有任意多门，也可以没有。每门课恰好占一个学期。试在这 样的前提下设计一个教学计划编制程序。1.1.2 研究意义及目的具体说来，教学计划编制是以课程先修关系为基础，分析教学中的问题和需 要，确定教学目标，建立解决问题的步骤，合理组合和安排各种教学要素，为优 化教学效果而制定实施方案的系统的计划过程。由此可

3、以看出，教学设计的过程实际上就是为教学活动制定蓝图的过程。通 过教学设计，教师可以对教学活动的基本过程有个整体的把握，可以根据教学情 境的需要和教育对象的特点确定合理的教学目标，选择适当的教学方法、教学策 略，采用有效的教学手段，创设良好的教学环境，实施可行的评价方案，从而保 证教学活动的顺利进行。另外，通过教学设计，教师还可以有效地掌握学生学习 的初始状态和学习后的状态，从而及时调整教学策略、方法，采取必要的教学措 施，为下一阶段的教学奠定良好基础。从这个意义上说，教学设计是教学活动得 以顺利进行的基本保证。好的教学设计可以为教学活动提供科学的行动纲领，使教师在教学工作中事半功倍，取得良好的

4、教学效果。忽视教学设计，则不仅难以取得好的教学效果，而且容易使教学走弯路，影响教学任务的完成。1 .2 具体分析1.2.1 功能需求分析(1)输入参数包括：学期总数，一学期的学分上限，每门课的课程号、学分 和直接先修课的课程号。(2)允许用户指定下列两种编排策略之一：一是使学生在各学期中的学习负 担尽量均匀；二是使课程尽可能地集中在前几个学期中。1.2.2 运行环境本系统源代码是使用 Visual Studio 2015 编写编制完成，在该平台上能够正常 运行。生成通用的 exe 后对计算机的硬件需求很低，几乎日常使用的计算机都能 够正常运行。二 、 总 体 设 计输入课程号，课程学分输入课程

5、 先修关系输入学期数, 学期学分上 限在 win32 控制台下，显示出一个简易的界面，供用户选择所需要的功能。由 用户输入课程号和课程学分，再根据提示输入先修关系，输入学期总数和学期学 分上限，然后根据时间优先或平均分配排序出不同的方案。课程尽量集 中前几个学 期各学期负担 均匀教学计划编制系统总体设计三 、 数 据 储 存 结 构 的 设 计3 .1 采用邻接表的方式储存先修关系图众多课程以及其先修关系组成在一起，刚好构成一个 AOV 网，对于这个 AOV 网，采取邻接表的方式储存。邻接表中，对图中每个顶点建立一个单链表，第 i 个单链表中的结点表示依附于顶点 Vi 的边（对有向图是以顶点

6、Vi 为尾的弧）。AdjvexNextarcinfo邻接表中的表结点和头结点结构： 表结点:头节点:Dataf i r s t a r c图的邻接表举例：3 .2 邻接表储存的代码实现3.2.1 数据结构设计s t r uct cour s e/应用于dat a , 保存课程号和学分。依据课程号的先修关系和学分进行拓扑排序s t r i ng cour s e_no; i nt cr edi t ;s t r uct Ar c Node /边/弧 邻接表结点i nt adj vex;/邻接点下标/i nt we i ght ;/权值 Ar c Node * next a r c ;s t r

7、uct VNode/顶点cour s e dat a ;/数值域 Ar c Node * f i r s t a r c ;c l as s ALGr aphpr i vat e :VNode * ver t i ces ;i nt vexNum, a r c Num;/顶点数边数bool * vi s i t ed;/用于判断是否访问过，遍历时使用3.2.2 AOV 图的创建代码i nt Locat ed( VNode v)f or ( i nt i = 0; i vexNum; i +)i f ( ver t i ces i . dat a . cour s e_no =v. dat a

8、. cour s e_no)r et ur ni ;r et ur n - 1;voi d Cr eat ALGr aph( )/此图为有向图cout 请输入分别输入课程个数和先修关系数（VOA图的边数）： vexNum a r c Num;ver t i ces = new VNode vexNum ; vi s i t ed = new bool vexNum ;f or ( i nt i = 0; i vexNum; i +)ver t i ces i . f i r s t a r c = NULL; vi s i t ed i = f a l s e ;Ar c Node * p;i

9、 nt i = 0, j ; VNode v1, v2;f or ( ; i vexNum; i +)cout 请输入第 i + 1 ver t i ces i . dat a . cour s e_no;c i n ver t i ces i . dat a . cr edi t ;s ys t e m( c l s ) ;f or ( i nt k = 0; k a r c Num; k+)endl ;cout 请输入第 k + 1 个先修关系( 先修，直接后修) ： v1. dat a . cour s e_no v2. dat a . cour s e_no; i f ( ( i =

10、Locat ed( v1) ) = - 1)cout er r or ! endl ; r et ur n;i f ( ( j = Locat ed( v2) ) = - 1)cout er r or ! a dj vex = j ;p- ne xt a r c = ver t i ces i . f i r s t a r c ; ver t i ces i . f i r s t a r c = p;四 、 功 能 实 现 算 法 设 计4 .1 拓扑排序算法设计对于有向图采用邻接表存储结构，并设置一个数组 indegree 来保存图中各顶 点的入度值。而为了方便选择入度为 0 的顶点，再

11、设置一个队列来保存所有入度为 0 的顶点。而拓扑排序的方法而知，拓扑排序的关键问题是第二步，即如何删除一个顶 点以及所有从它发出的弧。由于图是一种复杂的数据结构，频繁的进行删除操作 势必会影响算法的效率，实际上，在输出一个顶点后，之所以要删除它以及所有 从它发出的弧，是为了方便找到当前入度为 0 的顶点。在设计算法时，删除一个顶点以及所有从它发出的弧可用将它的所有邻接顶点的入度值减 1 来代替，而不 是真正的在物理上删除它。拓扑排序算法的设计可用下面四个步骤来完成：1、 遍历整个图的邻接表求所有顶点的入度值。2、 将入度为 0 的顶点入队。3、 当队列不为空时，执行出队操作。出队的顶点必定是入

12、队为 0 的顶 点，输出他即可。然后将它的所有的邻接顶点的入度值减 1，若到了零，则 再将其入队。重复这个过程，直到队列为空为止。4、 若已经输出的顶点个数等于图的顶点个数，则输出的是一个拓扑排 序，否则，说明图中存在回路。遍历邻接 表， 求所有 顶点的入度出度顶点的 所有邻接顶 点的入度 1入队出队拓扑排序成 功， 正常输 出入度 =0 ？否是否队列为空？是是出队个数 =顶 点个 数？否该图存在回路， 拓扑排 序失败拓 扑 排 序 算 法 设 计4 .2 获取各个顶点的入度算法设计传入数组a 保存入度从1遍历顶点遍历点下标+1遍历点下标+1遍历该定点的所 有邻接顶点是是是否超出下标范围？否否

13、是否超出下标范围？是当前顶点？是是否是否为最后一个邻接顶点？是否否个否该邻接顶点是否为当前操作 点？是遍历到下一个邻接 顶点当前操作的顶点入 度+1获得所有顶点入度算法4 .3 分类型输出算法设计输 入学 期 数 ， 学 期学 分 上限各 学期 学 习 负 担均 匀课 程集 中 到 前 几个 学 期课 程数 除 以 学 期数 均 分按 照学 分 累 加 判断五 、 程 序 代 码#i ncl ude #i ncl ude /直接用系统封装的模板栈#i ncl ude /系统封装的模板队列#i ncl ude #i ncl ude us i ngna me s pace s t d; s t r

14、 i ng r es ul t ;s t r uct cour s e/应用于dat a , 保存课程号和学分。依据课程号的先修关 系和学分进行拓扑排序s t r i ng cour s e_no; i nt cr edi t ;s t r uct Ar c Node /边/弧 邻接表结点i nt adj vex;/邻接点下标/i nt we i ght ;/权值 Ar c Node * next a r c ;s t r uct VNode/顶点cour s e dat a ;/数值域 Ar c Node * f i r s t a r c ;c l a s s ALGr aphpr i v

15、at e :VNode * ver t i ces ;i nt vexNum, a r c Num;/顶点数边数bool * vi s i t ed;/用于判断是否访问过，遍历时使用 publ i c :ALGr aph( )/构造函数确定定点数和边的数量ALGr aph( )/析构函数，释放邻接表中各边表结点 的存储空间bool I s Exi t ( i nt i )i nt Locat ed( VNode v)f or ( i nt i = 0; i vexNum; i +)i f ( ver t i ces i . dat a . cour s e_no =v. dat a . cou

16、r s e_no)r et ur ni ;r et ur n - 1;voi d Cr eat ALGr aph( )/此图为有向图endl ;cout 请输入分别输入课程个数和先修关系数（VOA图的边数）： vexNum a r c Num;ver t i ces = new VNode vexNum ; vi s i t ed = new bool vexNum ;f or ( i nt i = 0; i vexNum; i +)ver t i ces i . f i r s t a r c = NULL; vi s i t ed i = f a l s e ;Ar c Node * p;

17、i nt i = 0, j ; VNode v1, v2;f or ( ; i vexNum; i +)cout 请输入第 i + 1 ver t i ces i . dat a . cour s e_no;c i n ver t i ces i . dat a . cr edi t ;s ys t e m( c l s ) ;f or ( i nt k = 0; k a r c Num; k+)endl ;cout 请输入第 k + 1 个先修关系( 先修，直接后修) ： v1. dat a . cour s e_no v2. dat a . cour s e_no; i f ( ( i =

18、 Locat ed( v1) ) = - 1)cout er r or ! endl ; r et ur n;i f ( ( j = Locat ed( v2) ) = - 1)cout er r or ! a dj vex = j ;p- ne xt a r c = ver t i ces i . f i r s t a r c ; ver t i ces i . f i r s t a r c = p;voi d f i ndI ndegr ee( i nt * i ndegr ee)/获取各个顶点的入度f or ( i nt i = 0; i vexNum; i +)i nt count

19、 = 0; Ar c Node * p;f or ( i nt j = 0; j ! = i &j a dj vex = i )count +; p = p- ne xt a r c ;i ndegr ee i = count ;voi d t opol ogi ca l Sor t ( i nt a )/数组a获得拓扑排序结果的下标i nt v, count = 0, * i ndegr ee; Ar c Node * p;queue Q;i ndegr ee = ne wi nt ( vexNum) ; f i ndI ndegr ee( i ndegr ee) ;f or ( v = 0

20、; v a dj vex - - ;i f ( i ndegr ee p- a dj vex = 0) Q. pus h( p- a dj vex) ; p = p- ne xt a r c ;i f ( count vexNum)endl ;cout 先修关系存在问题( AOV图存在回路) ，请重新创建！ exi t ( 0) ;e l s e cout 系统已完成规划！ endl ;voi d f i nal _s or t ( )i nt * a =ne wi nt ( vexNum) ;/申请动态数组存放拓扑排序结果 t opol ogi cal Sor t ( a ) ;s ys t

21、 e m( c l s ) ;i nt t er m_num; /学期数i nt hes t _s cor e ; /学期最高学分 cout 系统已完成规划！ endl ;cout t er m_num hes t _s cor e ;i nt i ; cout * endl ; cout * endl ;cout *系统已经完成规划，请选择输出方案* endl ;cout * endl ;cout *1. 学习负担尽量均匀。* endl ;cout *2. 尽可能地集中在前几个学期中。* endl ;cout * endl ;cout * endl ; cout i ;s wi t ch (

22、 i )cas e 1:/学习负担尽量均匀。f s t r eam f i l e 1( G: t ext . t xt , i os : : out |i os : : app) ;s ys t e m( c l s ) ; i nt x = 1;f or ( i nt m = 0; m vexNum; m+)i f ( m = 0)f i l e 1 第 x 学期：; cout 第 x 学期：; x+;f i l e 1 ver t i ces a m . dat a . cour s e_no ; cout ver t i ces a m . dat a . cour s e_no ;i

23、 f ( ( m + 1) % ( vexNum / t er m_num + 1) = 0 & m+1ve xNum)f i l e 1 endl 第 x 学期：; cout endl 第 x 学期：; x+;f i l e 1. c l os e( ) ; br eak;cas e 2:/尽可能地集中在前几个学期中。f s t r eam f i l e 1( G: t ext . t xt , i os : : out | i os : : app) ;s ys t e m( c l s ) ; i nt x = 1;i nt count = 0;f or ( i nt m = 0; m

24、 vexNum; m+)i f ( m = 0)f i l e 1 第 x 学期：; cout 第 x 学期：; x+;count = count + ver t i ces a m . dat a . cr edi t ; i f ( count = hes t _s cor e)f i l e 1 ver t i ces a m . dat a . cour s e_no ; cout ver t i ces a m . dat a . cour s e_no ;e l s ef i l e 1 学期总学分： count -ver t i ces a m . dat a . cr edi

25、t endl 第 x 学期：;cout 学期总学分： count - ver t i ces a m . dat a . cr edi t ;cout e ndl 第 x 学期：; count = 0;m- - ; x+;f i l e 1 学期总学分： count endl ; cout 学期总学分： count endl ;f i l e 1. c l os e( ) ; br eak;/*f or ( i nt i = 0; i vexNum; i +)cout a i ;cout ver t i ces a i . dat a . cour s e_no ;*/voi d f i r

26、s t Si ght ( )i nt i ; cout * endl ;cout * endl ;cout * endl ;cout *欢迎进入教学计划编制系统，请根据提示选择操作功 能。* endl ;cout * endl ;cout *1. 创建新的教学计划编制。* endl ;cout *2. 退出。* endl ;cout * endl ;cout * endl ;cout * endl ;cout * endl ;cout i ;s ys t e m( c l s ) ; s wi t ch ( i )cas e 1: Cr eat ALGr aph( ) ;f i na l _s

27、 or t ( ) ; br eak;cas e 2:br eak;i nt ma i n( )ALGr aph G;G. f i r s t Si ght ( ) ;r et ur n 0;六 、 运 行 结 果1 、 进 入 主 页 面2 .输 入 课 程 号 和 学 分3 、 输 入 先 修 关 系4 、 输 入 学 期 数 和 学 期 学 分 上 限5 、 输 出 计 划 编 制七 、 课 程 设 计 总 结通过本次课程设计，对图的概念有了一个新的认识，慢慢地体会到了其中的 奥妙，图能够在计算机中存在，首先要捕捉他有哪些具体化、数字化的信息，比 如说权值、顶点个数等，这也就说明了想要把

28、生活中的信息转化到计算机中必须 用数字来完整的构成一个信息库，而图的存在，又涉及到了顶点之间的联系。当 AOV 图建立完成，怎样把图按照联系的关系完整的遍历，是整个程序的核心内容。 最终，按照教材的拓扑排序的方法做起了程序。但是排序完毕后怎么按照不同的 规则输出又是一件费脑力的事儿，最后经过严密的思考还是想出了办法。在本课程设计中，我明白了理论与实际应用相结合的重要性，并提高了自己 组织数据及编写大型程序的能力。培养了基本的、良好的程序设计技能以及合作 能力。这次课程设计同样提高了我的综合运用所学知识的能力。数据结构是 一门实践性很强的课程，上机实习是对学生全面综合素质进行训练的一种最基本 的方法，是与课堂听讲、自学和练习相辅相成的、必不可少的一个教学环节。上 机实习一方面能使书本上的知识变“活”，起到深化理解和灵活掌握教学内容的 目的;另一方面，上机实习是对学生软件设计的综合能力的训练，包括问题分析， 总体结构设计，程序设计基本技能和技巧的训练。此外，还有更重要的一点是： 机器是比任何教师更严厉的检查者。因此，在“数据结构”的学习过程中，必须 严格按照老师的要求，主动地、积极地、认真地做好每一个实验，以不断提高自 己的编程能力与专业素质。