数据结构与算法课程设计报告--教学计划编制.docx
《数据结构与算法课程设计报告--教学计划编制.docx》由会员分享,可在线阅读,更多相关《数据结构与算法课程设计报告--教学计划编制.docx(22页珍藏版)》请在沃文网上搜索。
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
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 课程设计 报告 教学计划 编制