“数据结构”教学过程中应重视算法设计与分析能力的培养

“数据结构”教学过程中应重视算法设计与分析能力的培养

姜　浩

（东南大学计算机学院，江苏南京，210096）

【摘要】　本文分析了算法设计与分析在“数据结构”教学中地位和作用，讨论了与算法有关的内容在教学中如何体现，总结了培养算法设计与分析能力的方法。

【关键词】　数据结构　算法设计与分析　教学方法

【中图分类号】　G642　　　　　　　　【文献标识码】　B

【文章编号】　1672－5913（2007）16－0027－03

“数据结构”是计算机科学与技术专业的一门重要的专业基础课，在整个专业教学体系中占有重要地位。这门课程学习的好坏，对学生学好后续课程如编译原理、操作系统、数据库系统、计算机网络等以及培养学生分析问题、解决问题的能力和软件设计与开发的能力起着至关重要的作用。这门课程不仅涉及的概念多、内容广，而且对数学基础有一定的要求，解题又需要有一定的技巧，因此，相当一部分学生感到理解书上的基本概念并不难，基本操作的实现也都听得懂，可是一到解决具体问题时就觉到困难重重，对于有一定难度的算法设计题，更是感到无从下手。因此，如何学好、怎样教好“数据结构”成为学生和教师普遍关注的一个问题。

1．算法设计与分析在数据结构课程中的定位

算法是对解决问题所采用的方法的描述。因此，在教学过程中应强调算法的概念，在算法设计的同时培养算法分析的习惯，这也是这门课程中能力培养的核心问题。“数据结构”课程的能力培养目标应当是：要求学生在学完这门课程后应能够掌握本学科系统分析、解决问题的基本科学方法。这种基本科学方法在很大程度上受到教师课堂讲授思想的影响。大学课堂讲授的内容主要分为两个方面，一个是具体的知识，另一个就是分析问题和解决问题的科学方法，而后者通常要在教师的教学过程中来体现。科学的教学方法能够使得教师所传授的知识易于被学生有效接受和消化，同时其解决问题的思想方法也潜移默化被学生所吸纳，转变为一种潜在的能力。因此，在“数据结构”课程的讲授中应当避免就概念而概念、就结构而结构的简单教学模式，而应当结合每个具体知识单元的特点传授分析问题、解决问题的一般思路和方法。这就要求教师要不断提升自己的知识层次和知识的综合能力，并转变观念，使自己的地位逐渐由讲解员过渡为导航员。这样才能使学生由被动的旁听者变为参与实践者，从而达到对学生综合能力的培养目标。

2．算法设计与分析在数据结构课程教学中的体现

在“数据结构”的教学内容中，完成同一功能有多个算法的例子比比皆是。例如串的模式匹配。假设目标串和模式串的长度分别为N和M，由于朴素的模式匹配算法需要回溯，使得算法的时间复杂度为O（N×M），要想提高模式匹配算法的性能，就应该着眼于消除回溯。这就引出了快速模式匹配算法（KMP算法）。消除了回溯的模式匹配算法的时间复杂度成为O（N＋M），算法的性能得到了显著的提高。再比如，对三元组表示的N×M矩阵的转置运算就可以提出三种算法。首先，最简单和直观的算法是将源三元组表中元素的行号和列号互换，然后再按照三元组要求的按行排列的要求重新排序。如果采用直接选择或插入的方式进行排序，那么这个过程的时间复杂度应为O（N2×M2）。其次，注意到源三元组中的列就是目的三元组中的行这一特点，引出第二个算法。可以考虑对源三元组进行多趟扫描，第一趟处理源三元组中第1列元素，第二趟处理源三元组中第2列元素……第M趟处理源三元组中第M列元素，第k趟扫描将源三元组中第k列的元素顺次复制到目的三元组中。这个处理过程的时间复杂度是O（N×M2），优于前一种算法。第二个算法还可以进一步优化吗？答案是肯定的。换一种思路来考虑，就可以提出第三种算法（快速转置算法）：首先计算出源三元组中每一个元素在目的三元组中的位置，然后依次将源三元组中的元素按照预先计算出的位置放置在目的三元组中。这个过程只需先后扫描源三元组两次，时间复杂度为O（N×M）。当然，为了存放位置信息，需要一定的额外存储空间。

按照对算法的效率分析来对教学内容进行总结和归纳，是培养学生算法分析能力的另一种方式。对于数据的排序，通常是按照插入、选择、交换等分类进行教学，在对这一部分内容进行总结时，则可按算法的时间性能进行归类。在对N个元素进行排序时，直接选择、插入和冒泡排序算法都是通过两重循环来实现的，思路直观、简单，但效率不高［O（N2）］。采用“分而治之”的思想，可以引出快速、堆和归并排序三种算法，它们的效率都可达到O（Nlog₂N）。通过对比较树的分析，推导出基于比较的算法的最好平均时间性能为O（Nlog₂N），由此得出结论：要想得到效率更高的排序算法，就不能采用基于比较的方法。顺着这个思路，可以进一步介绍具有线性时间复杂度的基数排序和计数排序算法。可见，在这里，算法的效率分析是主线，顺着这根主线，可以很好地把排序的所有算法串在一起，使学生能够较好地把握住排序的主要教学内容。

对于涉及算法分析的练习，按题目的难易程度，可以分为三种类型：

（1）给出算法或程序代码段，要求分析其时间复杂度。这一类问题的难点是对递归算法的分析，通常应该采用递推法。具体方法是：逐次展开等式右边的函数项，最终得到一个收敛的级数，最后对该级数求和。例如，对求解Hanoi塔的递归算法的时间复杂度进行分析，算法的代码段如下：

Void　TOH（int　n，Pole＿start，Pole＿goal，Pole＿temp）

注意到1＋2＋4＋……＋2^n－1＝2ⁿ－1，所以上述时间复杂度为O（2ⁿ）。

（2）设计一个算法，并分析其时间复杂度。这一类问题在上一问题的基础上增加了算法设计的内容。

图1　数据比较过程的查找路线

（3）在给定时间复杂度的前提下设计算法。这一类问题难度较大，要求学生能够设计出高效率的算法。例如求解如下问题：给定整型数组A［m］［n］。已知A中数据在每一维方向上都按从小到大的次序排列。试设计一个算法，找出一对满足A［i］［j］＝x的i，j值（如果存在的话），要求比较次数不超过m＋n。对题目做如下分析：矩阵中元素按行和按列都已排序，要求查找时间复杂度为O（m＋n），因此不能采用常规的二层循环的查找。可以先用右上角（i＝0，j＝n－1）元素与x比较，只有三种情况：一是x＜A［i，j］，这种情况下向j小的方向继续查找；二是x＞A［i，j］，下一步应向i大的方向查找；三是A［i，j］＝x，查找成功。否则，若下标已超出范围，则查找失败，查找路线如图1所示。对该算法的效率进行分析，算法中查找x的路线从右上角开始，向下（当x＞A［i，j］）或向左（当x＜A［i，j］）逐次比较。向下移动最多是m次，向左移动最多是n次。最佳情况是在右上角比较一次成功，最差是比较了左下角数据，比较m＋n次，故算法最差时间复杂度是O（m＋n）。

3．如何培养算法设计与分析的能力

（1）明确教学目的

课堂教学的主要目的是培养学生分析问题和解决问题的能力，教学的组织和教学过程都应围绕这一点展开，这是毋庸置疑的。而对算法的讨论和分析不仅是“数据结构”教学的主要内容之一，同时也是培养学生能力的有效途径。因此，在实际教学过程中，应突出算法的设计思想和算法分析的技巧，注重培养学生解决实际问题的能力。

（2）使学生充分理解算法分析的重要性

在问题求解过程中，我们所追求的是高效率地解决问题，而不仅仅是设计出一个算法。可以通过一些具体的演示使学生对算法效率有一个感性的了解。例如，将多个排序算法做成动画演示出来，通过对执行算法所花费的时间的比较，使学生明白，即使效率非常接近的算法，在问题规模达到一定程度时，求解问题所花费的时间之间的差距也是非常明显的。事实上，只有多项式时间复杂度的算法才是有意义的，许多效率低下的算法并没有多少实际应用上的价值。

（3）理解典型算法是基础。

学生对算法的理解是从教材中一些典型算法开始的。因此，在教学过程中，算法的设计思想是重点，不必过多的沉溺于具体的实现细节（程序设计的技巧不是这门课程的重点）。首先，通过对典型算法的讲解，使学生了解前人在问题求解过程中是如何考虑问题的，这会对学生产生潜移默化的影响，逐渐提高他们举一反三的能力。其次，通过对教材中的经典算法的分析和总结，使学生了解算法设计的一般原则和方法。比如，数组中的三元组表示的矩阵的转置和乘法运算以及排序中的归并排序和计数排序等，都是借助于额外的辅助空间以得到效率更高的算法，这就反映出了一种以空间换时间的思路。再比如，递归是一种非常有利的工具，使用递归方法往往使算法的描述既简洁又易于理解，且设计出的算法易于分析，尤其在复杂算法的描述中，递归技术被经常采用。递归本质上反映的是一种“分而治之”的算法设计思想。

（4）借助辅助教学手段加深对算法的理解

多媒体教学作为一种新兴的现代教育技术已显示出非常强大的生命力，它已成为深化教学改革的一种有效手段。“数据结构”中算法的教学难点之一就在于其抽象性和动态性。学生在阅读一些算法（特别是复杂算法）的程序描述时，常常需要充分的想象力，通过跟踪算法的执行过程来揣摩算法思想，这使得学习的效率低下。在有些情况下，教材上即便是给出了呈现关键概念的图示，但细节部分还需靠学生自己的想象力去补充，因此仍然不能从根本上解决问题。利用可视化教学软件可以在一定程度上化抽象为直观，帮助学生加深对数据结构和算法的理解。这种软件既可以用于课堂教学的现场演示，又可以供学生课外反复观察体会，对提高教学质量和效率有显著效果。

（5）实验的设计做到理论联系实际

实验是学生提高算法设计和分析能力的重要手段。实验应以综合性实验为主，以培养学生分析问题和解决问题的能力为目标。在实验过程中，学生在教师的指导下自主设计，充分调动学生的主观能动性。学生通过实验，巩固了课堂上所学到的知识，培养了创新意识和协作与团队精神。实验过程中既要求学生能够综合运用课堂和书本上学到的基本理论与方法，又能够结合实际问题进行分析和设计。例如，在“城市交通导游”这样一个综合性实验中，要求在两种方式下解决交通导游问题：自驾车交通方式是求解最短路径，而搭乘公交的交通方式是求解在换乘次数最小约束下的乘车线路选择。这里，既有典型算法的应用，又需要在图的基本概念和基本算法的基础上考虑数据的存储结构和相应的求解算法。这样的综合性实验可以使学生将课堂和书本上学到知识综合地加以运用，有效地提高学生的分析和解决实际问题的能力。

4．结束语

数据结构课程教学的难点是算法的设计与分析。在算法设计的教学过程中，应强调算法设计的思想，不能过多的沉溺于具体的实现细节。应当明确，“数据结构”课程教学的目标是提高学生分析问题和解决问题的能力，这本质上反映了教师是“授人以渔”还是“授人以鱼”。只有解决好这个问题，才有可能促进学生实现从知识型向能力型、从模仿型向创新型、从单一型向复合型人才的转变。

参考文献：

［1］　殷仁昆，陶永雷．数据结构（用面向对象方法与C^＋＋描述）［M］．北京：清华大学出版社，1999

［2］　Ellis Horowitz，Sartaj Sahni．Fundamentals of Data Structure in C^＋＋［M］．COMPUTER SCIENCE PRESS，1995

［3］　陈庆章，何文秀，金冠卓，等．国外可视化数据结构教学软件及其比较［J］．计算机教育，2005（2）：21－23

［4］　吴伟民．数据结构和算法的可视化教学研究与实践［J］．现在计算机，1999（3）：35－37

（原载于《计算机教育》，2007年第16期）