计算思维在“数据结构”课程教学中的运用

计算思维在“数据结构”课程教学中的运用

摘要：计算思维是近年来被普遍倡导的一种科学素养，如何在课堂教学中培养大学生的创新能力和计算思维能力，已成为“数据结构”课程教学改革的任务之一。文章首先详细分析计算思维的定义和特征，然后说明计算思维和数据结构的相通之处，最后给出几个相关的教学案例。

关键词：计算思维；数据结构；算法设计

0.引言

自2006年3月美国卡内基·梅隆大学周以真教授提出“计算思维”以来，在国内外教育界引起了很大的反响。周教授清晰系统地阐述了计算思维的概念，并认为计算思维是每个人的基本技能，不仅属于计算机科学家，应当使每个学生在培养解析能力时除掌握阅读、写作和算术外，还要学会计算思维。既然是每个人都必须掌握的思维能力，那么作为最“接近”计算思维的计算机专业的学生来说，该如何培养学生具有这种思维方式呢？这个任务显然不是某一门课程能独立完成的，它需要渗透到每一门专业课程中。这就要求任课教师本身就应该具有计算思维的教育理念，唯有这样才能把计算思维渗透到每门课程中，最后把这一抽象的思维方式融到学生的生活和今后的工作中去。

笔者将以计算机专业的基础课程——“数据结构”的教学经验为载体，详细介绍如何在课程中传授计算思维，使大学生学会运用计算思维去思考问题、解决问题，提升他们的计算素养，使其成为卓越人才。

1.计算思维的定义和特征

计算思维不是新生事物，从古代的算盘到近代的加法器、计算器以及现代的电子计算机，直到目前风靡全球的互联网和云计算，计算思维的内容在不断丰富，推动着人类科技的进步。虽然计算思维一直都在被人们应用，但是却没有明确地被人们用系统的理论来揭示。直到2006年，周以真教授在计算机权威期刊CommunicationsD，theACM上指出：计算思维是运用计算机科学的基础概念进行问题求解、系统设计、人类行为理解等的一系列思维活动。周教授系统地给出了计算思维的6个特征：

1）概念化，不是程序化。计算机科学不是计算机编程，像计算机科学家那样去思维意味着远不止能为计算机编程，还要求能够在抽象的多个层次上思维。

2）根本的，不是刻板的技能。根本技能是每一个人为了在现代社会中发挥职能所必须掌握的；刻板技能意味着机械地重复。

3）是人的，不是计算机的思维方式。计算思维是人类求解问题的一条途径，但并不是要使人类像计算机那样去思考。计算机枯燥且沉闷，人类聪颖且富有想

象力，是人类赋予了计算机激情。

4）数学和工程思维的互补与融合。计算机科学在本质上源自数学思维，因为像所有的科学一样，其形式化基础建筑于数学之上。计算机科学又从本质上源自工程思维，基本计算设备的限制迫使计算机学家必须计算性地思考，不能只是数学性地思考。

5）是思想，不是人造物。不只是软件、硬件等人造物以物理形式到处呈现并时时刻刻触及我们的生活，更重要的是接近和求解问题、管理日常生活、与他人交流和互动，计算的概念无处不在。

6）面向所有的人，所有地方。当计算思维真正融入人类活动，以至于不再表现为一种显式哲学时，它就将成为一种现实。

同时，周以真教授又将计算思维阐述成了具体的几种思维方法：递归，抽象和分解，保护，冗余，容错，纠错和恢复，利用启发式推理来寻求解答，在不确定情况下的规划、学习和调度等。

2.计算思维与数据结构

通过对计算思维的仔细分析，我们试图用这样一个公式来概括计算思维，即“模型+算法”。首先，学会合理地抽象，把有待解决的问题抽象成有效的计算过程，抽象成合适的模型，这是问题求解的第一步。然后，基于建立起来的模型利用各种思维方法去求解问题。

“数据结构”是计算机专业的一门专业必修课，是软件编程设计的基础，对于培养学生的逻辑思维能力，利用计算机解决实际问题的能力都起到了至关重要的作用。“数据结构”的研究内容可归纳为3个部分：逻辑结构、存储结构和运算集合，即按某种逻辑关系组织起来的一批数据，按一定的映像方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合，可以用“（逻辑|存储）结构+算法”的公式来概括。

对比两个“公式”，我们可以发现相似之处，都是静态结构和动态操作的结合。当然，计算思维中的模型和算法都要比数据结构中的概念来的宽泛很多。但正因为某种程度的契合，使得在“数据结构”课程中贯彻计算思维的思想，要比其他课程来得自然和容易许多。具体体现在：

1）从“逻辑或者存储结构”的选择理解“抽象建模”。在“数据结构”课程中，当面对一个问题时，首先是要能从问题中抽象出数据对象，然后分析数据对象中各个数据元素相互之间的（逻辑）关系是什么，接着这种逻辑关系用什么样的存储结构来实现。确定好这些后，再思考各种算法的设计和实现。整个问题的求解过程，就是一个抽象建模的过程。只不过，计算思维的概念更宽泛，它还需要考虑问题的可计算性（即计算的能力和极限，知道哪些问题可以计算，哪些问题不可以计算），而“数据结构”课程中所给出的问题都是可计算的。即便如此，依然

能通过对问题的抽象去训练计算思维。

2）通过算法多样化训练思维方法。“数据结构”课程中，对于一个问题往往可以通过不同方式来完成算法。在选择不同求解方式的过程中，可以很好地训练计算思维。例如，可以学会对问题进行有效的分解，分解的方法和结果当然是多样性的，分解的过程要希望每个分解块能尽量被重用，重用计算过程，重用程序。如何有效重用，是一个问题的抽象分类。这样做，能快速获得计算结果。在设计算法和优化算法的过程中还需要利用递归、并发、启发、学习等方法。

3）通过灵活的实验手段打造创新思维。虽然在计算思维的第一个特征中强调“计算思维是概念化，不是程序化。计算机科学不是计算机编程”，但是不可否认的是，当你使用计算机来解决具体问题求解时，把算法思想编写成可执行的程序是解决问题和验证算法有效性的最好方法。因此，在教学过程中，我们强调并培养学生对于抽象过程的严谨性，编写程序时强调从需求定义开始，进行算法优化与选择，最后通过上机实验来验证。为了提高学生学习的兴趣，我们在安排实验内容上，多以实用课题为主，尽量生动化、趣味化，例如，在线性表的实验中，选择了通讯录的设计和管理；在图的实验中，选择了最经济出行路线的设计。3.教学案例

3.1抽象和分解方法的使用——排序问题

“数据结构”中有很多排序算法：插入排序、选择排序、冒泡排序等算法。在讲解这些算法时可以渗透讲解计算思维中“抽象和分解”的思想。该方法是“选择合适的方式去陈述一个问题，或者是选择合适的方式对一个问题的相关方面建模使其易于处理”，也就是把一个复杂的问题分解成若干相关的子问题或者简单问题去处理。

以插入排序为例，插入排序的基本思想是每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。多个记录的排序问题可以看成是一个大的复杂问题，这个问题可抽象分解成若干个小问题：把一个待排的记录插入到已经有序的子表中。那么原来的排序问题就变成了不断增长有序表中记录的个数，即记录个数依次从初始的1增加到n（即所有记录的个数），个数增加到n时，排序就完成了。这个小问题又可转换为数据的两两比较，即待排序记录依次和有序子表中的记录进行两两比较，直到找到合适的位置，插入即可，插入后的子表依然有序。最后，通过这样两层转换，排序问题就转换成了学生非常熟悉的数据两两比较的问题。同样，其他排序方法也可以通过层层抽象和分解把问题转换为简单的小问题。

3.2递归方法的使用——二叉树的遍历问题

二叉树的遍历是按照一定次序访问二叉树中的所有结点，并且每个结点仅被访问一次。递归方法是“把代码译成数据又把数据译成代码”。从程序设计的角度看，递归就是在定义一个过程或者函数时出现直接调用或间接调用本过程或本函数的成分。

二叉树及其相关操作的讲解是“数据结构”课程的重点和难点，由于二叉树的定义本身就是一个递归定义，因此与其相关的操作，利用递归的方式来完成也是最自然的事情，是一个能很好地体现递归思想的知识点。以二叉树的中序遍历为例，我们首先可以利用上述的分解方法将整个遍历问题划分成若干个子问题，即分解为中序访问左子树，根结点，中序右子树这样三个子问题；接着，对访问左子树和访问右子树的子问题，利用相同的方法，又可以分解为类似的若干个子问题或者不能再划分（如子树为空）；如此反复进行，直到不能再划分成子问题，或者已经可以求解为止。在分解过程中，算法不断地利用同样的方法分解问题，不断地按照左子树一根结点一右子树的顺序访问。这个“较小问题”反复不断地被重复，形成了递归体。从问题分析的过程，可以引导学生去理解递归这一抽象而又重要的方法。

4.结语

计算思维已经成为近年来教育领域的研究热点，并作为一种通识教育被研究。计算机学科在培养计算思维方面有着得天独厚的条件，计算思维的培养对于人才本身也是极为重要的，它可以使学生理解计算机的实现机制和约束，有利于培养学生的创新思维，提高学生的信息素养，展现出处理计算机相关问题时应有的思维方法、表达形式和行为习惯。

文章对如何在“数据结构”课堂教学过程中渗透计算思维进行有益的探讨。实践表明，将计算思维融合于教学实践提高了教学质量，提高了学生解决问题的能力，对人才的培养大有裨益。