离散数学与数据结构的教学衔接方法研究
2017-05-12魏洪伟王博王建华
魏洪伟+王博+王建华
（1.哈尔滨师范大学 计算机科学与信息工程学院，黑龙江 哈尔滨 150025；2.哈尔滨市人才市场，黑龙江 哈尔滨 150800）
摘 要：针对计算机专业离散数学与数据结构这两门课程的教学衔接问题，分析两门课程的内在联系，提出离散数学是数据结构的数学基础与理论依据、数据结构是对离散数学的应用与拓展，阐述如何在教学中进行相互渗透与衔接，使学生在牢固掌握理论的基础上将其应用于计算机实践。
关键词：离散数学；数据结构；教学衔接
0 引 言
离散数学和数据结构这两门课程都是重要的计算机专业基础课，在计算机科学体系中有着举足轻重的地位。这两门课程之间相辅相成，离散数学是数据结构的数学基础与理论依据，数据结构是对离散数学的应用与拓展。离散数学研究的主要是数据的数学结构，也就是元素之间的逻辑关系；数据结构研究的主要是数据的存储结构，即在保证逻辑关系不变的前提下如何将数据存储到计算机中并进行高效处理。
正因为这两门课程之间相辅相成，所以在教学过程中二者必须有效衔接，才能使学生更好地掌握这两门课程并将其应用于实践。对计算机专业的学生来说学习离散数学决不能单纯地学习数学理论，了解离散数学知识在计算机科学中的应用并能够学以致用才是学习离散数学的最终目的；在学习数据结构时，较好的离散数学基础则能够帮助学生更好地理解数据存储和处理的方法。因此，在离散数学的教学中，教师必须渗透数学理论在计算机科学特别是数据结构中的应用，在讲解数据结构时，也有必要引导学生回顾相应的数学知识以加深理解。
离散数学知识渗透到计算机科学领域的方方面面，为十几门计算机专业课提供数学基础与理论依据，对数据结构的贡献尤为显著。离散数学对数据结构的贡献主要体现在两方面：一是提供数学模型；二是提供解决问题的方法。解决问题的方法主要是指在数据结构中利用离散数学中的定义、定理、推理方法、证明方法、计算方法等来设计算法；数学模型主要包括4种：序列、集合、树、图；数据结构的课程设置也主要是围绕这几种数学模型的存储和处理展开的。
1 序 列
DISCRETE MATHEMATICAL STRUCTURES这本书对序列的定义是：序列就是把对象按照一定的顺序列举出来[1]。比如，S：a1， a2， a3，… an，就代表一个长度为n（有n个元素）的序列，其中S为该序列的名称，a1，a2，a3，…an表示序列的n个元素。离散数学中的序列就是数据结构中线性表的数学模型。
从数学的角度看，序列中的元素存在着一对一的逻辑关系，除了第一个元素和最后一个元素外，每个元素都有一个直接前驱和一个直接后继，序列中元素的前后位置如果发生改变，那么序列就发生了改变。所以要将序列这种数学模型存储到计算机中，就必须保障元素之间原有的前后逻辑关系保持不变。数据结构中利用线性表来存储序列，线性表主要分为顺序表和链表。
顺序表是利用一组地址连续的存储单元来存储数据元素，存储地址的前后顺序与元素在数学上的逻辑顺序一致。也正因如此，在顺序表中只要知道了第一个数据元素的存储地址和每个数据元素占用的存储单元数就可以计算出表中任意一个元素的存储地址，所以在顺序表中可以随机存取，如图1所示。在链表中，每一个存储单元由数据域和指针域两部分组成，如图2所示。链表与顺序表不同，存储单元的地址是不连续的，所以利用数据域来存储数据的同时还要利用指针域来存储元素的直接后继地址，这样就保障了数据元素之间在数学上的一对一逻辑关系不变。在链表中，因为后继元素的地址必须通过它的直接前驱才能找到，要找到链表中的第n个元素就必须找到前n-1个元素，所以链表的存取方式是顺序存取而不是随机存取。
由序列与线性表之间的关系可以看出，数学上的逻辑关系直接影响了元素的存储方式，而针对不同的存储方式就要采取不同的操作方式对元素进行处理，进而衍生出了不同的算法。要理解数据结构中纷繁复杂的算法，首要任务就是要理解元素间的数学逻辑关系，因此离散数学与數据结构的教学必须有效衔接。在离散数学中讲解序列这部分内容时，简要介绍如何利用顺序表和链表对序列进行存储和处理，有助于学生理解序列在计算机科学中的应用，把抽象的数学知识具体化、实用化；而在数据结构中讲解线性表时简要回顾序列的数学性质，能让学生更好地理解线性表的存储依据、存储原理及算法的处理方式。清楚了序列与线性表之间的关系，学生对这两门课的学习也就由抽象变得更具体，再将线性表这种一维线性关系拓展到二维（矩阵）、多维（n维数组）也就不那么难以理解了。
2 集 合
在数据结构中，查找表是由同一类型的数据元素构成的集合[2]，查找表的数学模型就是集合。在数学上，集合中的元素除了同属于一个集合外没有其他的逻辑关系，集合是最为松散的一种数学结构，所以查找表也是一种很灵便的数据结构。对于查找表的操作主要有4种：查询、检索、插入、删除。在数学上，元素与集合的关系即“属于”关系，所以在查找表中可以查询某一个元素是否在表中，即判断元素是否属于该集合；如果查询到了，自然可以对元素的各种属性进行检索；在集合中可以添加或删除元素，所以在查找表中也可以进行插入或删除的操作。
尽管从数学的角度来看查找表的数学模型是集合，但从存储的角度来看，要把查找表中的元素一一输入到计算机中进行存储也是必须按照一定顺序的，计算机只能接受顺序输入并按照一定的地址顺序进行存储。所以，严格来说，集合在计算机中也只能像序列一样进行顺序存储或链式存储，要做到完全“松散、无序”基本是不可能的。
3 树
树是离散数学中最重要的数学模型之一，也是数据结构中最重要的存储结构之一，尤其是二叉树。树在数学上的定义是，令A是一个集合，T是基于集合A的关系，若在集合A中存在唯一的一个点V0使得从V0到除它本身之外的各个点之间都有唯一的一条路，那么称T为树，V0为树根。树中的元素存在着一对多的逻辑关系，每个父结点都可以对应多个子结点。若一个父结点至多有2个子结点则称该树为二叉树。二叉树的结构如图3所示。
二叉树是在计算机科学中应用最多的一种树，本身也具有很多特殊性质，相关公式在离散数学课中应该详细介绍。比如一棵二叉树的第i层中至多有2i-1个结点、深度为k的二叉树至多有2k-1个结点[3]等。尽管这些内容数据结构教材中也会提到，但如果离散数学授课教师能够从数学的角度给出详细的讲解与证明，则会使学生加深对二叉树的理解，更易于将二叉树这种数学结构转化为数据结构，减轻数据结构授课教师的负担，提高教学效率。
因为二叉树存在特有的一对二的逻辑关系，所以这种逻辑结构很容易转化成存储结构，数据结构中二叉树的链式存储结构是完全仿照离散数学中二叉树的有向图设计的（图3是某二叉树的有向图，图4是图3对应的链式存储结构）。因为在二叉树的有向图中除叶子节点外每个节点都有两条有向边指向其左右子结点，所以为了保障该结点和左右子结点间的对应关系，二叉树的链式存储结构中每个结点由3部分组成：用来存储数据的数据域、用来指向左右子存储地址的左指针域和右指针域。由图3图4可以看出，二叉树的链式存储结构与二叉树的有向图的结构是完全相同的，所以说，离散数学是数据结构的重要数学依据和基础。
离散数学中的二叉树除了为数据结构提供数学模型和数学依据外，还提供了很多解决问题的方法。比如数据结构中二叉树的遍历算法就是直接从数学上的遍历方法中衍生出来的，离散数学中对二叉树的遍历方法有3种：前序遍历、中序遍历、后序遍历。“前、中、后”指的是对根结点的访问顺序，左右子树按照先左后右的顺序进行访问。以前序遍历为例，离散数学中前序遍历的顺序是：根结点、左子树、右子树，对于左右子树依然按照同样的顺序进行访问，所以数据结构中对于二叉树的前序遍历的递归算法就完全按照该方法进行设计，算法的类C语言描述如下所示：
Status PreorderTraverse（ BiTree T， Status（*Visit） （TELemType e）{
if（T）{
if（Visit（T—>data））
if（ PreorderTraverse（T—>Ichild， Visit））
if（PreorderTraverse（T—>rchild，Visit）） retrun OK；
return ERROR
}else return OK
}//PreOrderTraverse [3]
有了离散数学所提供的數学模型和数学依据，数据结构就可以更好地将二叉树这种数学结构应用于计算机实践，如二叉排序树、哈夫曼树都是利用二叉树所特有的数学性质进行设计和解决实际问题的，所以说，数据结构是离散数学的应用与延伸。
4 图
在数学上图具有多对多的逻辑关系，是最复杂的一种数学结构，所以它的存储结构也最为复杂。图的存储结构主要包括：数组（邻接矩阵）表示法、邻接表、十字链表、邻接多重表，其中最直观的存储结构就是邻接矩阵存储法，这也是直接从离散数学中得到的一种存储方法。
在离散数学中，假设如图5所示的有向图表示一个基于集合A的多对多关系R，集合A={1，2，3，4}，关系R={（1，2）， （1，4）， （3，1）， （4，3）}，那么该关系也可以用矩阵来表示，如图6所示。要将该关系存储到计算机中，最简单直观的方法就是利用二维数组来存储矩阵，也就是邻接矩阵存储法。
在数据结构中图的数组（邻接矩阵）存储表示法如下所示：
typedef struct ArcCell {
VRType adj； //VRType是顶点关系类型。对无权图，用1或0表示相邻否； 对带权图
//则为权值类型；在无向网中存储权值
} ArcCell， AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]；
typedef struct {
VertexType vexs[MAX_VERTEX_NUM]； // 存储顶点的数组
AdjMatrix arcs； // 邻接矩阵
int vexnum， arcnum； // 图的当前顶点数和弧（边）数
GraphKind kind； // 图的种类标志
} MGraph； [3]
学生在离散数学中学到了相关的数学基础，在数据结构中学习图这部分内容时，就能够很容易理解为什么可以用邻接矩阵来存储图，也就很容易读懂以上算法中对邻接矩阵的定义了。
除了为图提供存储依据外，离散数学也为数据结构中的图的相关算法提供数学依据。比如，图的最小生成树问题就是以离散数学为依据来解决的，高速公路最低造价问题是最小生成树问题的一个应用。具体描述如下：要在几个城市之间建立高速公路的几种可选择方案如图7所示，图中每一个顶点代表一座城市，边的权值代表两座城市之间的高速公路的造价，高速公路最低造价问题就是要在图7中选择最少的边（但要保障各点连通）并使这些边的权值之和最小，选出的方案就是该图的最小生成树，如图8所示。
关于最小生成树问题，数据结构课的教学侧重点是如何设计算法并应用于实践，所以为了使学生更好地理解该问题，在离散数学中就应该给学生讲解清楚为什么最小生成树的造价最低。首先需要证明的是图的生成树具有能够连接n个结点的最小边数n-1，即生成树恰好能连接n个点。在数学上生成树具有的两个性质是：①生成树是连通图；②生成树中不存在回路。在图8所示的生成树中若任意删掉一条边（即边数
除最小生成树问题外，图的拓扑排序问题、关键路径问题、最短路径问题等都以离散数学中关系的性质为数学依据。所以说离散数学为数据结构中图的相关问题提供了数学依据、存储依据和算法依据。
5 结 语
以上提到的几点只是离散数学与数据结构教学衔接的几个方面，这两门课程之间有着千丝万缕的关联，尽管“剪不断”，但绝不会“理还乱”。只要认真梳理，就会理清这两门课程之间的联系。目前的离散数学教材和数据结构教材往往自成一个体系，对二者的关联与衔接介绍的并不是很详细，但无论是离散数学还是数据结构都是计算机科学领域中的一部分，授课教师将两门课程有效衔接才能够使学生加深对计算机科学的整体化认识与理解，并将其应用于实践。
基金项目：智能教育与信息工程黑龙江省高校重点实验室开放课题“移动学习研究与实践”（SEIE2014-04）。
第一作者简介：魏洪伟，女，讲师，研究方向为移动学习、算法研究，weihongwei999@163.com。
参考文献：
[1]Bernard K， Robert C B ， Sharon C R . Discrete mathematical structures [M]. 6th ed. 北京： 高等教育出版社， 2012： 13， 271.
[2]严蔚敏， 李冬梅， 吴伟民. 数据结构（C语言版）[M]. 北京： 人民邮电出版社， 2011： 164.
[3]严蔚敏， 吴伟民. 数据结构（C语言版）[M]. 北京： 高等教育出版社， 2003： 129.
（编辑： 郭田珍 ）
