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

“数据结构”教学过程中应重视算法设计与分析能力的培养 　　摘要：本文分析了算法设计与分析在“数据结构”教学中地位和作用，讨论了与算法有关的内容在教学中如何体现，总结了培养算法设计与分析能力的方法。 　　关键词：数据结构；算法设计与分析；教学方法 　　中图分类号：G642 文献标识码：B 　　文章编号：1672-5913(2007)16-0027-03 　　 　　“数据结构”是计算机科学与技术专业的一门重要的专业基础课，在整个专业教学体系中占有重要地位。这门课程学习的好坏，对学生学好后续课程如编译原理、操作系统、数据库系统、计算机网络等以及培养学生分析问题、解决问题的能力和软件设计与开发的能力起着至关重要的作用。这门课程不仅涉及的概念多、内容广，而且对数学基础有一定的要求，解题又需要有一定的技巧，因此，相当一部分学生感到理解书上的基本概念并不难，基本操作的实现也都听得懂，可是一到解决具体问题时就觉到困难重重，对于有一定难度的算法设计题，更是感到无从下手。因此，如何学好、怎样教好“数据结构”成为学生和教师普遍关注的一个问题。 　　 　　1算法设计与分析在数据结构课程中的定位 　　 　　算法是对解决问题所采用的方法的描述。因此，在教学过程中应强调算法的概念，在算法设计的同时培养算法分析的习惯，这也是这门课程中能力培养的核心问题。“数据结构”课程的能力培养目标应当是：要求学生在学完这门课程后应能够掌握本学科系统分析、解决问题的基本科学方法。这种基本科学方法在很大程度上受到教师课堂讲授思想的影响。大学课堂讲授的内容主要分为两个方面，一个是具体的知识，另一个就是分析问题和解决问题的科学方法，而后者通常要在教师的教学过程中来体现。科学的教学方法能够使得教师所传授的知识易于被学生有效接受和消化，同时其解决问题的思想方法也潜移默化被学生所吸纳转变为一种潜在的能力。因此，在“数据结构”课程的讲授中应当避免就概念而概念、就结构而结构的简单教学模式，而应当结合每个具体知识单元的特点传授分析问题、解决问题的一般思路和方法。这就要求教师要不断提升自己的知识层次和知识的综合能力，并转变观念，使自己的地位逐渐由讲解员过渡为导航员。这样才能使学生由被动的旁听者变为参与实践者，从而达到对学生综合能力的培养目标。 　　 　　2算法设计与分析在数据结构课程教学中的体现 　　 　　在“数据结构”的教学内容中，完成同一功能有多个算法的例子比比皆是。例如串的模式匹配。假设目标串和模式串的长度分别为N和M，由于朴素的模式匹配算法需要回溯，使得算法的时间复杂度为O(N×M)，要想提高模式匹配算法的性能，就应该着眼于消除回溯。这就引出了快速模式匹配算法(KMP算法)。消除了回溯的模式匹配算法的时间复杂度成为O(N＋M)，算法的性能得到了显著的提高[1]。 　　再比如，对三元组表示的N×M矩阵的转置运算就可以提出三种算法[2]。首先，最简单和直观的算法是将源三元组表中元素的行号和列号互换，然后再按照三元组要求的按行排列的要求重新排序。如果采用直接选择或插入的方式进行排序，那么这个过程的时间复杂度应为O(N2×M2)。其次，注意到源三元组中的列就是目的三元组中的行这一特点，引出第二个算法。可以考虑对源三元组进行多趟扫描，第一趟处理源三元组中第1列元素，第二趟处理源三元组中第2列元素，……，第M趟处理源三元组中第M列元素，第k趟扫描将源三元组中第k列的元素顺次复制到目的三元组中。这个处理过程的时间复杂度是O(N×M2)，优于前一种算法。第二个算法还可以进一步优化吗？答案是肯定的。换一种思路来考虑，就可以提出第三种算法(快速转置算法)：首先计算出源三元组中每一个元素在目的三元组中的位置，然后依次将源三元组中的元素按照预先计算出的位置放置在目的三元组中。这个过程只需先后扫描源三元组两次，时间复杂度为O(N×M)。当然，为了存放位置信息，需要一定的额外存储空间。 　　按照对算法的效率分析来对教学内容进行总结和归纳，是培养学生算法分析能力的另一种方式。对于数据的排序，通常是按照插入、选择、交换等分类进行教学，在对这一部分内容进行总结时，则可按算法的时间性能进行归类。在对N个元素进行排序时，直接选择、插入和冒泡排序算法都是通过两重循环来实现的，思路直观、简单，但效率不高(O(N2))。采用“分而治之”的思想，可以引出快速、堆和归并排序三种算法，它们的效率都可达到O(Nlog2N)。通过对比较树的分析，推导出基于比较的算法的最好平均时间性能为O(Nlog2N)，由此得出结论：要想得到效率更高的排序算法，就不能采用基于比较的方法。顺着这个思路，可以进一步介绍具有线性时间复杂度的基数排序和计数排序算法。可见，在这里，算法的效率分析是主线，顺着这根主线，可以很好地把排序