计算思维在数据结构中的实践探索

孟凡荣 张斌 杨雷

摘要：随着计算机网络时代的到来，计算思维的概念应运而生。培养计算思维能力的实践更为重要。许多高校都努力实践如何将计算思维的能力培养融入到平日的课程教学中。本文讨论计算思维与数据结构的关系，从计算思维的抽象与自动化的本质出发，以数据结构中的数据对象建模和问题数学建模以及算法的计算机实现为线索，对如何在数据结构课程的教学中进行计算思维能力的培养进行了深入探讨。

关键词：计算思维能力；数据结构；问题求解；模型及算法

中图分类号：G642.0 文献标志码：A 文章编号：1674-9324（2015）10-0117-04

一、引言

随着计算机网络时代的到来，计算思维的概念应运而生。按照计算思维的倡导者Wing教授的观点，计算思维代表着一种普遍的态度和一类普适的技能，不仅仅是计算机科学家，每一个人都应热心于它的学习和运用。自从计算思维的概念提出以后，计算思维与理论思维、实验思维并称为三大科学思维。数据结构课程是计算机科学与技术专业的一门专业基础课，是计算机算法设计与分析、操作系统、数据库原理、软件工程等课程的重要的前导课程。该课程的任务是学会从分析与解决问题入手，能够合理选定数据的逻辑结构、组织数据，并为所加工的数据选取适宜的存储结构，完成其基本操作算法，初步掌握算法的时间与空间复杂性的分析方法，同时进行复杂程序设计的训练，编写符合软件工程规范的软件，将数据结构的基础知识应用于实践。近年来，许多高校都努力实践将计算思维的能力培养融入到平日的课程教学中。本文从计算思维与数据结构的关系，应用数据抽象和问题抽象、建立数据对象模型和问题对象模型，应用计算机实现问题求解的算法等三个方面探讨如何在数据结构课程的教学中进行计算思维能力的培养。

二、计算思维与数据结构

计算思维具有概念化、技能化、思维化、数学与工程思维的互补性、普适性等重要特征。计算思维的精髓是运用计算机科学的基础概念去求解问题、设计系统和理解人类的行为。计算思维通过抽象和分解来完成复杂的任务或设计复杂的系统；通过选择合适的方式来对问题陈述并建立数学模型；通过采取保护、冗余、容错、纠错和恢复等措施解决具体的技术问题；利用启发式推理来寻求问题的解答，并利用海量数据进行快速的计算。计算思维的核心思想是基于计算的思维，如何计算是实现计算思维能力的关键。而实现计算的有效工具是应用计算机。计算思维是借助于计算机而实现的思维，正如电动机的出现引发了自动化思维，计算机的出现催生了计算思维。数学和计算机已成为计算思维应用中不可分割的重要工具。有了计算机，计算思维就有了用武之地。采用计算思维可以使我们把一个看似复杂困难的问题转化为一个简单易解的问题加以解决。所以说，计算思维是一种科学思维，是人类的一种进步思维。计算机科学与技术专业一般包括计算机科学、计算机工程、软件工程和信息技术等专业。数据结构课程与计算机高级程序设计语言、算法设计与分析课程一起构成程序设计基础、算法与复杂性领域的核心知识单元。一方面，数据结构课程是高级程序语言课程的后续强化程序设计训练，另一方面，它又是算法设计与分析课程的前导基础知识训练。数据结构课程教学内容包括理论教学和实践教学。理论教学主要包括数据的线性结构、树形结构、图形结构和集合类型的选取、组织和应用。其中，线性结构包括线性表、栈和队列、数组和字符串等；树结构主要包括二叉树、线索树、排序树、一般树等；图结构主要包括无向图、有向图、带权图、一般图等；集合类型主要包括查找、排序和文件等。数据结构实践课程是数据结构课程的重要组成部分。教学计划是一个整体。实践教学体系是整体教学计划的一部分，也是一个与理论教学体系有机结合的、相对独立的完整结构体系。理论课程体系主要体现专业结构、知识结构的培养目标要求，从而确定理论课程的知识领域、核心知识单元和知识点。而实践课程体系主要体现能力结构的培养目标要求，由能力结构确定实践课程体系的各个单元的目标结构和具体指标。数据结构的课堂理论教学主要采用启发式、讲解式和案例驱动式等教学方式。而实践教学方式则主要采用项目驱动方式，采用课题教学法和单元教学法。数据结构实践课程的教学体系由课程实习、课程实验、课程设计、课程社会实践、实践教学评测和实践教学文档及资源等部分构成。计算思维具有普适性，而数据结构的应用同样具有广泛性。不仅是工科的非计算机专业，甚至是许多非工科的非计算机专业也同样需要问题求解和数据分析，也面临着计算机的应用，所以也把数据结构课程作为必修课或选修课，研究数据的选取和组织，通过数据结构课程的导入，将计算思维的能力培养融入其中。计算思维的本质是抽象和自动化。抽象是在多个层次上进行的。通过数据抽象建立数据的对象模型，通过问题抽象建立问题的数学模型，应用约简、嵌入、转化、仿真等方法，使用计算机处理海量数据，通过算法实现问题的求解。数据结构内容的实质恰恰是“模型+算法”。狭义的数据结构是指数据元素之间存在的一种或多种关系的集合。广义的数据结构则是在狭义的定义的基础上再加上基本操作的集合，使数据结构的实现成为可能。通过建立数据的对象模型和问题的数学模型，并对建立的模型研究出实现算法，从而实现编程的自动化。提出计算思维的目的是实现计算思维的能力。数据结构课程的目的是数据结构的应用实现，这与计算思维的目的不谋而合。所以，构建一个基于计算思维的数据结构课程的教学体系，不仅自然，而且易行。

三、应用数据抽象，建立数据的对象模型

在数据结构课程中，当面对一个问题时，首先是要从问题中抽象出数据对象，然后分析数据对象中各元素之间的逻辑关系，在确定数据的逻辑结构后，适当选取数据的存储结构，再考虑存储结构的基本操作实现。在此基础上，建立数据的对象模型。

1.ADT（Abstract Data Type）是建立数据对象模型的最好工具。狭义的数据结构定义只涉及到数据的表示和逻辑关系。但数据结构的完整性描述应该包括数据的逻辑结构、数据的存储结构以及数据的运算。ADT是指一个数学模型以及定义在此数学模型上的一组操作。用ADT创建数据对象时，强调的是数据的本质特征、数据所能完成的功能以及数据的外部接口。抽象数据类型ADT可用三元组（D，S，P）表示。其中，D是数据对象；S是D上的关系集；P是基于D的基本操作集。数据类型是高级语言中已经实现的基本数据结构。抽象数据类型的概念，是数据类型概念的扩展和进一步应用。利用已经实现的基本数据类型来扩展新的数据类型，从而实现复杂的数据结构。例如传统C语言中的栈、队列、树、二叉树和图等复杂数据类型，就要用到抽象数据类型的概念去实现。所以，抽象数据类型ADT是数据结构中创建数据对象模型的理想工具。从某种意义上说，数据结构的实现就是抽象数据类型的设计与实现。无论是C语言描述的数据结构还是C++描述的数据结构，在分析和创建数据对象的本质上是完全一致的，都是将数据的静态属性和动态方法（基本操作）进行统一封装，只是实现的方法不同而已。

2.认识已有的数据对象，分析数据的本质特征，为数据的选取和组织打下良好的基础。数据结构课程中为我们提供了许多已有的数据对象模型，如顺序表、单链表、顺序栈、循环队列、二叉树、邻接表图、哈希表等。学习、领会并实现这些数据对象模型，是应用数据结构的关键。许多复杂的数据对象的操作都可以由基本操作实现。例如，ADT List描述了线性表结构及其基本操作的逻辑定义，建立了线性表的一个数据模型。利用上述定义的基本操作可以实现线性表其他更加复杂的操作。值得注意的是，在应用实践中，尽管已经分析和确定了问题的数据对象模型，理清了数据之间的逻辑关系，但数据的存储结构的确定仍然十分重要，影响着算法的运行效率。例如，同样是有序表，但有序顺序表、有序链表、有序二叉树所适应的算法显然不同。实际应用中，面对一个比较复杂的问题，为了问题的求解，还应综合运用已有的数据对象知识。例如，为了提高查找的效率，采用哈希表组织数据时，应用线性探测再散列或应用链地址法解决冲突，其算法效率是不同的。分析证明，链地址法解决冲突要优于线性探测再散列。如果数据空间不是问题的话，最好采用链地址法解决冲突较好。这就要求我们，既要有哈希表的数据对象知识，又要有链表的数据对象知识。

3.设计与实现新的数据对象，以便解决更加复杂的问题。尽管数据结构的类型很多，但基本操作一般都具有共同的特性。归纳起来，数据结构中的基本操作可分为四类：创建和销毁结构类，包括数据结构的创建、初始化，以及必要的销毁结构操作；属性操作类，包括读取或设置数据结构中的各基本属性的值；查找类，包括特定查找和遍历操作；更新类，包括插入、删除或修改数据元素的内容或更新关系。有了上述知识，我们就可以根据问题的数据特性，应用ADT开发出用于解决实际问题的新的数据类型。例如线段树、二进制堆、多重索引链表等数据对象的应用。课程实验是设计与实现数据对象模型的最好实训手段。实验课题的基本内容包括线性表类应用实验、栈和队列类应用实验、树和图类应用实验、查找和排序类应用实验以及自主研究性应用实验等。课程实验的课题类型有验证性实验、应用性实验和创新设计性实验。根据课程学时和学生特点，验证性实验属于学生自主研究性学习的课下实验，设计应用性试验和自主创新性实验是课上实验。通过课程实验，真正创建以验证性实验为基础，以设计应用性实验为中心，以自主创新性实验为提高的课程实验机制。

四、应用问题抽象，建立问题的数学模型

当面对一个新的复杂问题时，不易直接求解，通常的想法是通过对问题的分析，不断地抽象和分解、转化或转换，得到一个与原问题本质相同的，可以采用计算机及其相关技术求解的，但看起来相对简单的一个问题。把初始的问题或对象称为原型，把抽象分解后的理想化对象称为数学模型。一个实际问题的数学模型建立后必须以一定的技术手段，如推理证明、计算、模拟等进行检验。如果所建数学模型不符合实际情况，就必须修改问题的数学模型。与实际问题相比，数学模型具有等价性、抽象性、高效性、可类比性等特点。这也是用计算思维求解问题的精髓所在。对于一些简单的问题，往往只靠数据对象模型的建立，就可以解决问题，这时的数据对象模型，实质上就是问题的数学模型。但对于许多复杂的问题，仅有数据对象模型还是不够的，必须在问题定义和分析的基础上，建立问题的数学模型才能求解。这也是数据结构课程教学的特点。建立数学模型的本质是挖掘数据间的关系和数据的变化规律。在建模时，如果能够在繁杂的数据中找到有价值的线索，并加以合理应用，往往可使问题获得简化，便于问题的解决。建立数学模型没有固定的套路可言，方法比较多样化。通常的建模方法可分为直接设计法、分类设计法和归纳设计法三种形式。直接设计法是直接对问题对象进行考察的设计方法。直接设计法需要解题者大胆猜想解题方法，并结合目标反复尝试，调整方案和使用数学推理证明。分类设计法，简单说，就是在分类的基础上进行设计。归纳法利用了归纳的思想，是模型设计的一个经典的实现形式。数据结构中常见的数学模型一般有树形模型、图论模型、集合模型和排序模型等。例如，最小代价生成树问题。问题的定义是：在n个城市之间修建高速公路网，如何修建使得总的工程费用为最省。问题的定义很明白，接下来是分析问题。这里有两个特征含义，一个含义是最小生成树问题，即若使得n个城市连通，仅需要n-1条边就足够了，当然，这n-1条边需要连接n个城市；另一个含义是最小代价问题，即n-1条边所构成的最小生成树的各边代价之和为最小。显然，n个城市及其之间的数据联系可以用图形结构来表示，但这不足以解决实际问题。所以，必须靠MST性质，利用最小生成树的原理来解决。可以用数学来证明MST性质是完全正确的。因此，这个问题是典型的最小代价生成树模型。像光纤网络铺设、校园道路修建、城市观光导游等问题都属于此类问题。课程设计是设计与实现问题的数学模型的最好实训手段。课程设计是指对理论课程的核心知识点以及能力结构的综合技能的专业训练。依据培养目标的能力结构，遵从教育规律和认知规律，将课程设计的课题项目分级分类设计，以促进学生的阶梯式发展。课程设计的课题包括：综合训练性题目和研究学习性及创新设计性题目两大类。例如，立体化停车场管理、电梯运行模拟、哈夫曼压缩软件设计、二进制堆及其应用、线段树及其应用等。

五、应用计算机，实现问题求解的算法

数据结构中的数学模型一般是指能够应用穷举法、贪心法、分治法、回溯法和分支法等处理的问题模型。数学建模最重要的步骤是建立数学模型和求解数学模型，如果说建立数学模型的过程更多地是依赖数学基础，求解数学模型则更多地是依靠应用计算机。正因为有了计算机，有了计算机网络，才有了今天计算思维的认同与发展。在对问题求解的过程中，必须对问题的数学模型完成算法的设计与实现。首先是根据数学模型，确定适当的计算策略，选取合适的算法。因为不同的算法对结果的复杂性和稳定性影响很大。其次是根据问题的算法，编写计算机程序。这时要应用数据对象模型，因为同一个问题，使用不同的数据结构，编写出的程序也会差别很大。

1.对同一个问题，往往可以用不同的算法求解，在选择求解算法的过程中，可以很好地进行计算思维能力的训练。以最小代价生成树问题的求解为例。假如是n个城市的连通图，数据对象是图形结构，数学模型是最小代价生成树。若应用穷举法，需对n个城市进行n！次全排列，求解每种排列的代价之和进行比较，从而找出问题的最小代价。若应用贪心法，对稠密图，采用prim算法，首先任选一个顶点，以后每次从剩余的顶点中选择另外一个顶点，附加一条边，只要满足添加的边的代价之和为当前最小即可。如此，直到选择了n个顶点，当然也包括n-1条边。若采用分治法，对稀疏图，可以采用破圈算法，对于n个顶点的连通图，实行减一分治。现将m条边按代价大小非递增排列，然后从中按顺序考虑每一条边，只要判断减掉该边后，该图任然连通且所剩边数目大于n-1即可。若采用回溯法或分支法，同样可以得到问题的答案，其原理类同穷举法，不再赘述。随着数据规模的增大，究竟哪一种算法是最优的，可以用算法的时间复杂性和空间复杂性综合衡量。显然，应用计算机，为最优算法的选择提供了可能。

2.对同一个问题，往往可以用不同的数据结构，进而采用不同的算法求解，同样可以很好地进行计算思维能力的训练。以四则运算表达式求值问题的求解为例。假如四则运算表达式的形式为字符串，表达式存储在数组中。数学模型是后缀表达式。问题的定义是，十进制整数的四则运算求解。若采用顺序栈进行问题求解，则数据对象是特殊线性表的顺序栈。可以采用后缀表达式的求解算法。算法的执行过程是，每次应用一个顺序栈，共应用两次顺序栈。第一次将表达式转换成后缀式，第二次，对转换后的后缀表达式求值。若采用二叉树进行问题求解，则求解过程同样可以用到栈，数据对象是二叉树和顺序栈。算法的执行过程是，每次应用一个顺序栈，共应用两次顺序栈。第一次将表达式转换成二叉树，第二次，对转换后的二叉树进行后序遍历（后缀表达式）求值。若采用有向无环图进行问题求解，则求解过程同样可以用到栈，数据对象是图结构和栈。算法的执行过程是，应用一个顺序栈，第一次将表达式转换成二叉有向无环图，第二次，对转换后的有向无环图进行后序遍历（后缀表达式）求值。不同的数据结构，可以采用不同的算法，算法的时间复杂性和空间复杂性可能不同。随着数据规模的增大，究竟哪一种算法是最优的，可以应用计算机为最优算法的选择提供求解。将一个问题用多种思路、多种数据结构、多种算法求解，可以发展学生计算思维能力的灵活性，培养学生计算思维能力的习惯性。

3.计算思维能力的培养离不开上机实践训练。加强实践性教学，是提高学生计算思维能力的重要手段。在数据结构实践课程教学中，将项目教学法应用到课程实验和课程设计等各个教学活动中，通过课题的立项与开题、组建课题小组、方案分析、方案设计、方案实现和项目验收的工作流程对学生进行计算思维能力培养的工程实践训练。诚然，计算思维是概念化，不是程序化。计算思维的实现也不等同于计算机编程。但是，不可否认的是，应用计算机来解决具体问题时，把算法思想变成可执行的程序代码是验证算法的有效性和解决问题的最好方法。例如，应用计算机解决数据的排序问题。假设，数据是整型数据，存储在顺序表中。将一个无序的整数序列转换成有序序列，方法很多。传统的方法有插入排序、选择排序和交换排序，改进后优化的排序方法有希尔排序、快速排序和堆排序。但优化后的排序方法的稳定性都不好。若忽略数据的空间性能，时间性能又好且稳定性又高的方法首选归并排序。不过，归并排序又与数据的初始状态无关，无法体现最好的排序性能。而且，除了采用顺序表排序外，还可以采用二叉树排序，甚至采用非关键字比较方法的基数排序。究竟采用何种排序方法，有了计算机的使用，问题性能的比较和算法的选择可以迎刃而解。实践证明，学生对将多种数据结构应用于一个复杂问题的解决，有很高的积极性。

六、结束语

本文以Wing教授的计算思维为引入，以计算思维在数据结构中的实践探索为主线，以培养计算思维能力的实践为重点，努力探讨如何将计算思维的能力培养融入到平日的课程教学中。本文讨论了计算思维与数据结构的关系，从计算思维的抽象与自动化的本质出发，以数据结构中的数据对象建模和问题数学建模为线索，对如何在数据结构课程的教学中，用计算机处理海量数据并实现算法，从而进行计算思维能力的培养做了深入探讨。

参考文献

[1]Wing J M.Computational Thinking.Communications of the ACM，2006，49（3）：33-35.

[2]教育部高等学校计算机科学与技术专业教学指导委员会.高等学校计算机科学与技术专业人才专业能力构成与培养[M].北京：机械工业出版社，2010.

[3]Mark M.Meerschaert.数学建模方法与分析[M].第2版.刘来福，杨淳，黄海洋，译.北京：机械工业出版社，2005.

[4]孟凡荣，贾杰，王兴伟.网络工程专业创新性实践课程体系构建与实施[J].计算机教育，2013，（194）14：104-108.

[5]刘昕，石乐义，元雪东.面向计算思维的数据结构课程教学改革[J].计算机教育，2013，（196）16：35-38.