关于《数据结构》在成人教育中授课方式的变革思考及实验

刘超

[摘要]数据结构作为计算机专业的一门基础课程，对学生理解计算机这门学科有着基础性的作用。对以后的系统框架，程序编写等都有至关重要的作用。我认为提高这门课的教学质量，首先要转变观念。这个观念就是成教的学生学习的内容比较肤浅，不需要学习太多的内容。有这个先入为主的观念就不会有积极性去提高教学质量，不会深入研究这门课的如何才有更好的教学效果。不能否认成教的学生有自己的特点，有经验有想法，但时间不固定，这就需要我们成人教育的老师对这门课如何教，如何学有自己思路，不能完全照搬普通高校教材，仅仅进行简化。这篇文章就是我对者们如何在成人教育中如何教授的思考及实施。

[关键词]主要矛盾；成人教育；数据结构；授课

[中图分类号]G642

[文献标识码]A

[文章編号]1671-5918（2018）03-0143-03

十九大报告中提出当前的社会主要矛盾已经发生改变，现在的主要矛盾为“由我国社会主要矛盾已经转化为人民日益增长的美好生活需要和不平衡不充分的发展之间的矛盾。”体现在教育领域就是由以前的想上学到上好学的变化，这就要求我们成教人必须提高自己，钻研自己的专业，提高自己授课能力为解决教育领域的主要矛盾贡献自己的力量。

一、数据结构的前生今世

数据结构指相互之间存在着一种或多种关系的数据元素的集合和该集合中数据元素的关系。在不同教材中，对数据结构也有不同的描述，Sartaj Sahni在《数据结构、算法与应用》中描述数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。”Clifford A.Shaffer的《数据结构与算法分析》中定义为数据结构是ADT（抽象数据类型Abstract Data Type）的物理实现。”Robert L.Kruse在《数据结构与程序设计》一书中，将一个数据结构的设计过程分成抽象层、数据结构层和实现层。其中，抽象层是指抽象数据类型层，它讨论数据的逻辑结构及其运算，数据结构层和实现层讨论一个数据结构的表示和在计算机内的存储细节以及运算的实现。而数据结构作为一个单独的学科是1968年由美国的Donald Ervin Knuth教授的《计算机程序设计艺术》的第一卷《基本算法》较系统地阐述了数据的逻辑结构和存储结构及其操作。总之，对数据结构的讲解中定义一半都是包含数据和数据之间的关系两部分。

数据结构作为计算机专业的一门基础课程，对学生理解计算机这门学科有着基础性的作用。对以后的系统框架，程序编写等都有至关重要的作用。在成人教育中，报名计算机专业的同学一直不是很多，这就与我们这些课程的教学质量上不去有很大的关系。

二、数据结构在国开教学的现状

我认为提高这门课的教学质量，首先要转变观念。这个观念就是成教的学生学习的内容比较肤浅，不需要学习太多的内容。有这个先人为主的观念就不会有积极性去提高教学质量，不会深入研究这门课的如何才有更好的教学效果。实际上，成教读计算机的同学，特别是本科的同学既然要读这个专业，很多都是从事计算机这一行业的，特别是部分同学还从事了开发工作，有一定的实际开发经验，在实际学习中他们更想将学到的东西进行理论联系实践，这反而比普通教育的难度更高。反观普通高等教育中的计算机专业的同学基本是没有编程经验的。他们在学习的过程中对数据组合的，程序的设计，系统的效率思考并没有那么深刻。这是简单将这些概念存在脑海里，主要用于应付以后的考试。

成教就不一样了，比如他的在实际开发的过程中调用过哈希函数，对实际项目运行过程中的数据存储是以哈希表的格式存储还是链表的格式存储，有直观的感受，会对不同的数据结构格式的使用造成对运行效率产生的影响有深刻的认识，对数据存储使用什么的结构就有自己的想法和问题。如果我们在教学过程深入思考这一点，这门课的教学难度就要比普通高等学校的教学高出一个层次。

三、教学变革的思考及实践

在教学中如何深入浅出的讲解这门课，就要将理论和实际相结合。这门课在前面讲述了队列，链表，树，图，哈希表等几种基本结构后，重点内容就是这个几种基本结构下的遍历，搜索，插入，删除等操作。重点和难点就是树，图，哈希表等几种结构的遍历操作，这个操作也是整个数据结构的基础。在理解了几种基础结构后，重点如何重点突出的理解这几种操作及应用了。

这篇文章由于篇幅限制，重点讲了变革的第一次课的授课，也是最有代表性的一次课。

数据结构中的常用的几种数据类型，我们选用用链表和哈希表来举例说明。选链表的原因是这个结构比较容易理解，操作起来也比较简单。选用哈希表是因为这个方法实际应用比较广，效率高，学生在学习过程中和实际工作容易结合，且算法比较成熟，各种变种比较多，可应用于很多环境中。

排序通常被用作各种计算机科学类的人门问题，以展示一系列算法。我们在数据结构的选择冒泡排序来进行一次排序算法的演示，至于数据结构使用的采用的是单链表还是双链表或者顺序存储都是屏蔽了交换细节，不影响算法。

教学设计安排：

我在平时的上课实验中，把这门课的一节分了四个部分。

（一）第一步（3分钟）引入新授内容

同学们，我们学习计算机专业要做的就是对信息进行处理。信息在计算机中就是数据，如何操作数据，首先要知道数据是什么样子的。根据数据间的逻辑关系，把数据合理有效地存储到计算机中，并使用合理的算法对其进行相应的处理。这就是我们的这门课，数据结构。

数据：是描述和量化客观事物和信息等的符号；数据元素是数据的基本单位；

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。

现在我们选用我们常用的数据类型，就是我们的学生档案信息来作为数据结构的描述，比如我们把学生的相关信息，学生学号作为一个数据项（也可以认为是一个数据元素），数据项是数据中不可分割的最小单位。我们也可以把多个数据项如（学号，姓名，年龄，性别，电话等）多个数据元素合成为一个数据元素，来统一处理。

处理什么呢？我们的着眼点是数据间的位置关系，数据间是否存在直接或者间接的联系等方面，

（二）第二步（12分钟）讲授新的课程内容

1.线性结构的描述及双链表的操作

比如我们把我们的学生信息抽象为一个接着一个排列的，呈现出线性排列的关系。为了避开使用指针这个较为抽象的概念，我们使用双链表的结构来存储学生数据。

2.图形描述；对比数组和双链表的结构

数组：内容连续存放；

双链表；数据之间通过地址来进行链接；

双联表的主要特点：

一个数据元素由三部分组成，前驱，数据项，后驱。前驱内存放的是前面一个节点的地址，数据项存放的是这个数据具体内容，比如学生的（学号，姓名，年龄，性别等）。后驱存放的是后面一个节点的地址。

讲述数组和双链表的优缺点。数组，数据存放时间复杂度为Of（n），空间复杂度。机器语言及自然语言描述双链表的查找，插入，删除等的操作；

分析这个算法时间复杂度；

For（i=0；i

{操作}

3.提出问题

我们现在使用的数据比如一个班，只有几十个人，查起来当然非常快，但一个学校呢？就会有几千人，一个学校呢？几万人，历届学生呢，几十万人；一个省呢？几千万，全国呢？几亿学生了，当数据量非常大的时候，这个效率就非常吓人了；等待的时间就会非常长，这个用户体验就非常差了。

引出哈希表的使用（可以使用分库分表的操作，但具体先不谈）：

我们数组和链表的查找就是在比较基础上进行的，还有后面要讲的树，图等等都是在比较的基础上进行的。这个计算效率并不高。我们现在大量的数据操作经常使用的方法是使用哈希表来进行的，这个有什么特点呢，就是记录的关键字值与该记录的存储位置之间建立一个对应关系。

举例：将4个数据的关键值为{8，10，14，21}的数据存储到表长为5的哈希表中，定义计算哈希地址的哈希函数为H（K）=K mod 5，K是关键值。

得到如图所示的存储：8mod5=3（取余数）10mod5=0；14mod5=4；

21mod5=1；

这个例子的数据量非常小，但是大家可以看出查找一个数据只需要两步，根据关键值找相应的hashcode（哈希码），然后根据哈希码找到相应的地址。如果数据量有上百万万，上千万的话，如果只有两步就可以查到所需的关键值，这个效率就非常高了。

步骤1根據key得到hashcode方法：int hash=hash（key.hashCode（））；

步骤2根据hashcode得到对应的位置方法：inti=index-For（hash，table，length）；

这一步很关进。可以将一个key转换成一个固定的位置。这就是为什么快的原因。

哈希算法的缺点主要是在前期进行解决，比如根据的数据量的大小确定哈希表的大小，及确定使用的哈希函数，还有冲突的解决。实际中可以根据关键值的增大调整哈希表的长度，进行重构。

无论中间使用什么样冲突处理，对于大数据量的存储操作来说，两步就可以找到关键值效率都是非常高的，相对于链表的时间复杂度为Of（n），节省的时间都是非常可观的。

（三）第三步：讨论与提问

设计的题目主要是学生对链表和哈希表的认识，及对这两种数据结构的操作的时间复杂度的直观概念及印象。

听取学生提出的问题，回答并进行解析。

（四）第四步：实验

找出提供100条学生的信息，用学号作为关键字，让学生对数据进行存储及查找的操作；

可以使用自然语言或高级语言中的C，c++，java，c#等都可以，循环要表达出来；

如果这部分学生的实践经验较好，则两种结构每人都要写；如果实践经验不好，则每人写一种，水平较好的写哈希表的操作。根据最后的学生实验结果来总结这门课的授课结果。

四、课程教学变革总结

这门课在课后和学生的讨论中发现，学生基本能够理解这两种数据结构的算法，能够用自然语言描述出来，而且对数据结构这门课有了初步的兴趣，基本达到了教学目标。

课程教学变革的第一次后的学生学习情况是对这门课程非常重要的总结及反思，后续的树图的查询遍历亦是非常重要的内容，后面的课程会根据第一次的课程进行总结后在进行变革，目标就是让学生在尽量短的面授课时间内，对数据结构的几种重要结构及遍历算法有深刻的印象。希望看到本文的读者有兴趣和作者讨论这门课的教学变革。

参考文献：

[1]周维.基于共享内存的多核时代数据结构研究[J].软件学报，2016，27（4）.

[2]唐艳琴.“数据结构”小班化教学探讨[J].计算机工程与科学，2014，36（zl）.

[3]汤琼.基于PBL和LBL的数据结构教学研究与实践[_！|.浙江中医药大学学报2011，35（6）.

[4]姚丽莎.项目驱动教学在数据结构课程教学中的应用研究[J].赤峰学院学报（自然科学版），2017，33（3）.