离散数学与数据结构的教学衔接方法研究

-精选财经经济类资料- -最新财经经济资料-感谢阅读- 1 离散数学与数据结构的教学衔接方 法研究 （1.哈尔滨师范大学 计算机科学 与信息工程学院，黑龙江 哈尔滨 150025；2.哈尔滨市人才市场，黑龙江 哈尔滨 150800） 中国论文网 /8/view-12921282.htm 摘 要：针对计算机专业离散数 学与数据结构这两门课程的教学衔接问 题，分析两门课程的内在联系，提出离 散数学是数据结构的数学基础与理论依 据、数据结构是对离散数学的应用与拓 展，阐述如何在教学中进行相互渗透与 衔接，使学生在牢固掌握理论的基础上 将其应用于计算机实践。 关键词：离散数学；数据结构； -精选财经经济类资料- -最新财经经济资料-感谢阅读- 2 教学衔接 0 引 言 离散数学和数据结构这两门课程 都是重要的计算机专业基础课，在计算 机科学体系中有着举足轻重的地位。这 两门课程之间相辅相成，离散数学是数 据结构的数学基础与理论依据，数据结 构是对离散数学的应用与拓展。离散数 学研究的主要是数据的数学结构，也就 是元素之间的逻辑关系；数据结构研究 的主要是数据的存储结构，即在保证逻 辑关系不变的前提下如何将数据存储到 计算机中并进行高效处理。 正因为这两门课程之间相辅相成， 所以在教学过程中二者必须有效衔接， 才能使学生更好地掌握这两门课程并将 其应用于实践。对计算机专业的学生来 说学习离散数学决不能单纯地学习数学 理论，了解离散数学知识在计算机科学 中的应用并能够学以致用才是学习离散 数学的最终目的；在学习数据结构时， 较好的离散数学基础则能够帮助学生更 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 3 好地理解数据存储和处理的方法。因此， 在离散数学的教学中，教师必须渗透数 学理论在计算机科学特别是数据结构中 的应用，在讲解数据结构时，也有必要 引导学生回顾相应的数学知识以加深理 解。 离散数学知识渗透到计算机科学 领域的方方面面，为十几门计算机专业 课提供数学基础与理论依据，对数据结 构的贡献尤为显著。离散数学对数据结 构的贡献主要体现在两方面：一是提供 数学模型；二是提供解决问题的方法。 解决问题的方法主要是指在数据结构中 利用离散数学中的定义、定理、推理方 法、证明方法、计算方法等来设计算法； 数学模型主要包括 4 种：序列、集合、 树、图；数据结构的课程设置也主要是 围绕这几种数学模型的存储和处理展开 的。 1 序 列 DISCRETE MATHEMATICAL STRUCTURES 这本书对序列的定义是： -精选财经经济类资料- -最新财经经济资料-感谢阅读- 4 序列就是把对象按照一定的顺序列举出 来1。比如， S：a1 ， a2， a3， an，就代表一个长度为 n（有 n 个元素） 的序列，其中 S 为该序列的名称， a1，a2，a3，an 表示序列的 n 个元素。 离散数学中的序列就是数据结构中线性 表的数学模型。 从数学的角度看，序列中的元素 存在着一对一的逻辑关系，除了第一个 元素和最后一个元素外，每个元素都有 一个直接前驱和一个直接后继，序列中 元素的前后位置如果发生改变，那么序 列就发生了改变。所以要将序列这种数 学模型存储到计算机中，就必须保障元 素之间原有的前后逻辑关系保持不变。 数据结构中利用线性表来存储序列，线 性表主要分为顺序表和链表。 顺序表是利用一组地址连续的存 储单元来存储数据元素，存储地址的前 后顺序与元素在数学上的逻辑顺序一致。 也正因如此，在顺序表中只要知道了第 一个数据元素的存储地址和每个数据元 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 5 素占用的存储单元数就可以计算出表中 任意一个元素的存储地址，所以在顺序 表中可以随机存取，如图 1 所示。在链 表中，每一个存储单元由数据域和指针 域两部分组成，如图 2 所示。链表与顺 序表不同，存储单元的地址是不连续的， 所以利用数据域来存储数据的同时还要 利用指针域来存储元素的直接后继地址， 这样就保障了数据元素之间在数学上的 一对一逻辑关系不变。在链表中，因为 后继元素的地址必须通过它的直接前驱 才能找到，要找到链表中的第 n 个元素 就必须找到前 n-1 个元素，所以链表的 存取方式是顺序存取而不是随机存取。 由序列与线性表之间的关系可以 看出，数学上的逻辑关系直接影响了元 素的存储方式，而针对不同的存储方式 就要采取不同的操作方式对元素进行处 理，进而衍生出了不同的算法。要理解 数据结构中纷繁复杂的算法，首要任务 就是要理解元素间的数学逻辑关系，因 此离散数学与稻萁峁沟慕萄 匦胗行 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 6 衔接。在离散数学中讲解序列这部分 内容时，简要介绍如何利用顺序表和链 表对序列进行存储和处理，有助于学生 理解序列在计算机科学中的应用，把抽 象的数学知识具体化、实用化；而在数 据结构中讲解线性表时简要回顾序列的 数学性质，能让学生更好地理解线性表 的存储依据、存储原理及算法的处理方 式。清楚了序列与线性表之间的关系， 学生对这两门课的学习也就由抽象变得 更具体，再将线性表这种一维线性关系 拓展到二维（矩阵） 、多维（n 维数组） 也就不那么难以理解了。 2 集 合 在数据结构中，查找表是由同一 类型的数据元素构成的集合2，查找表 的数学模型就是集合。在数学上，集合 中的元素除了同属于一个集合外没有其 他的逻辑关系，集合是最为松散的一种 数学结构，所以查找表也是一种很灵便 的数据结构。对于查找表的操作主要有 4 种：查询、检索、插入、删除。在数 -精选财经经济类资料- -最新财经经济资料-感谢阅读- 7 学上，元素与集合的关系即“属于” 关系， 所以在查找表中可以查询某一个元素是 否在表中，即判断元素是否属于该集合； 如果查询到了，自然可以对元素的各种 属性进行检索；在集合中可以添加或删 除元素，所以在查找表中也可以进行插 入或删除的操作。 尽管从数学的角度来看查找表的 数学模型是集合，但从存储的角度来看， 要把查找表中的元素一一输入到计算机 中进行存储也是必须按照一定顺序的， 计算机只能接受顺序输入并按照一定的 地址顺序进行存储。所以，严格来说， 集合在计算机中也只能像序列一样进行 顺序存储或链式存储，要做到完全“松 散、无序”基本是不可能的。 3 树 树是离散数学中最重要的数学模 型之一，也是数据结构中最重要的存储 结构之一，尤其是二叉树。树在数学上 的定义是，令 A 是一个集合，T 是基于 集合 A 的关系，若在集合 A 中存在唯 -精选财经经济类资料- -最新财经