詹泽梅
(长江大学计算机科学学院,湖北 荆州 434023)
数据结构是计算机专业的一门重要基础课程,它以程序设计语言为基础,培养学生进行复杂程序设计的能力。该课程也是后续一些重要专业课的基础。由于学生在此课程之前通常只学习了一门或两门编程课程,程序设计能力还比较薄弱,所以学生普遍认为数据结构课程内容繁多、复杂、抽象。为了提高教学质量,教育者们研究了”混合式教学”[1-2]、分层教学法[3]、案例驱动[4]、融合式教学[5]等多种教学模式和方法,取得了一定的效果。针对数据结构课程内容繁多、复杂的情况,为各部分内容设置统一的内容纲要,将纲要贯穿整个教学过程,能帮助学生快速理清学习思路,降低内容复杂程度,从而让学生掌握课程内容,达到较好的教学效果。
纲要贯穿式教学首先要有能概括各章或绝大部分教学内容的纲要,而纲要的确定需要通过分析各章内容得到。严蔚敏、吴伟民编著的《数据结构(C语言版)》[6]被许多高校计算机专业选定为数据结构课程的教材,至今累计发行已超400万册。笔者将以此书为教材,分析贯穿式纲要的设置。
纵观各本数据结构教材,其主要内容是介绍各种不同结构的数据类型,包括线性表、栈、队列、字符串、树和二叉树、图等。下面将分析教材中这些数据类型的主要内容。表1-表6是对教材中各部分内容的归纳。
表1 线性表
表2 栈
表3 队列
表6 图
表5 树和二叉树
从表1-表6可看出在介绍每一种数据类型时,首先需要先分析它的特点,介绍其抽象类型定义,让学生了解这种数据类型的特征、元素之间的关系、常用操作。有的还会介绍本数据类型的相关概念,例如字符串、树和二叉树、图都在本章开头介绍了相关概念。
接着就要分析数据类型在计算机中的存储表示。因为数据结构在计算机中的存储结构有两种:顺序存储结构和链式存储结构,所以需要从顺序存储结构和链式存储结构两方面分析数据类型在计算机中的存储表示。顺序表、顺序栈、循环队列、串的定长顺序存储、串的堆分配存储、二叉树的顺序表示这些都属于顺序存储结构;线性链表、循环链表、双向链表、链栈、链队列、串的块链存储、二叉链表这些都属于链式存储结构。树和图的结构比较复杂,任意两个元素之间都可能存在关系,所以很难用顺序存储结构,但可以借助数组表示元素之间的关系。例如树的双亲表示法、图的数组表示法。树和图的链式存储结构有:树的子链表、树的二叉链表、图的邻接表、图的十字链表、图的邻接多重表。
最后,为了加强学生对数据类型的理解和对前面知识的应用,教材上对每种数据类型都举例讲解了一个或多个实例。这些实例都是需要使用相应数据类型的典型例子。
根据上面分析,可提炼出贯穿教材各种数据类型的一级讲解纲要,如图1。
图1 一级纲要
在一级纲要中有顺序存储表示和实现、链式存储表示和实现。从表1-表6中可看出教材2.2、2.3、3.1.2、3.4.2、3.4.3、4.2、6.2、6.3、6.4、7.2、7.3小节的内容均属于顺序或链式存储表示和实现,这部分内容也是课程的重点。分析这些内容可发现:对每一种数据类型,不管是介绍它的顺序存储表示,还是介绍它的链式存储表示,都主要从两方面讲解,一是类型定义,二是基本操作的算法实现。合理的类型定义应是基于其存储特点给出的,因此,可先分析此数据类型的存储特点,然后再用C语言描述其类型定义。当数据类型在计算机中采用不同的类型定义表示时,常用基本操作的算法也互不相同。对于每一个操作,可先用自然语言分析具体怎么做,再用类C语言描述出具体步骤,从而得到操作的算法函数,最后分析算法时间复杂度。
根据上面的分析,可提炼出数据类型的每种存储表示和实现的二级讲解纲要,如图2。
图2 二级纲要
设置好贯穿整个教学过程的纲要后,就要在授课过程中使用纲要教学。数据结构的教学一般分为理论教学和上机实践。理论教学是实施纲要贯穿式教学的主要部分。
数据结构课程第一章是绪论,从第二章开始就介绍各种不同结构的数据类型,这时便可以采用纲要贯穿式教学。在讲解每章内容之前先摆出一级纲要,让学生对本章内容有一个大概了解。接着,便按纲要讲解各部分内容。在讲解数据类型的两种存储表示时,也是先给出二级纲要,并对照纲要列出本数据类型的常用操作,然后再逐个操作讲解。对于两种存储表示,既可以两者都详细讲解,也可根据实际应用情况详细讲解一种。例如线性表两种存储表示都比较常用,所以两者都详细讲解。二叉树的顺序存储表示比较适合于存储完全二叉树,对于非完全二叉树采用顺序存储表示比较浪费存储空间,所以只用详细讲解二叉树的链式存储表示。
每章内容结束时,需要对照纲要进行总结,帮助学生梳理本章内容,让学生对本章内容有更清晰的认识。
讲第一种数据类型时,学生可能对纲要认识比较模糊,但随着在第二种、第三种等数据类型的讲解中使用同样的纲要,学生便会逐渐熟悉纲要,进而容易掌握每种数据类型的整体内容。
数据结构是一门理论性和实践性都很强的课程,上机实践是不可或缺的教学环节,也是理论知识的巩固和应用。二级纲要对应的是数据类型在计算机中的存储表示和实现,具体包含类型定义和常用操作的算法,与程序相关,适合将其作为上机内容。将二级纲要中的内容贯穿于上机实践中,这样能加深学生对理论知识的深入理解。
根据二级纲要将单链表的上机任务设置为:定义单链表类型,实现单链表的创建操作、向单链表中插入一个元素操作、从单链表中删除一个元素操作、查找第i个元素值的操作以及输出单链表所有元素的操作。单链表上机任务如图3所示。图4至图8分别展示了另外几种数据类型根据二级纲要设置的上机任务。
图3 单链表上机任务
图8 图上机任务
上机任务的内容还可根据学生层次适当调整内容。如果某个上机任务相对于学生来说比较简单,可将应用实例加入其中;如果某个上机任务比较复杂,可选取部分内容。例如图4所示的栈上机任务比较简单,可将数值转换或括号匹配实例加入其中。图7所示的图上机任务比较复杂,可从深度优先遍历、广度优先遍历中选取一种遍历操作实现。
图4 栈上机任务
图7 二叉树上机任务
图5 队列上机任务
图6 字符串上机任务
纲要贯穿式教学方法应用于数据结构的理论教学和上机实践中。在理论教学中,通过统一的纲要贯穿各部分内容,能帮助学生理清繁杂的教学内容,让学生快速掌握学习内容。在上机实践中,将纲要内容转换成程序,将理论应用于实践,能进一步加深学生对理论知识的理解。在教学实践中,该方法可与其他教学方法相结合,运用多种教学方式,从而达到更好的教学效果。