《“数据结构”教学过程中应重视算法设计与分析能力的培养.docx》由会员分享，可在线阅读，更多相关《“数据结构”教学过程中应重视算法设计与分析能力的培养.docx（10页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、“数据结构”教学过程中应重视算法设计与分析能力的培养 摘要：本文分析了算法设计与分析在“数据结构”教学中地位和作用，探讨了与算法有关的内容在教学中如何体现，总结了培育算法设计与分析实力的方法。 关键词：数据结构；算法设计与分析；教学方法 中图分类号：G642文献标识码：B 文章编号：1673-5913(2022)16-0027-03 “数据结构”是计算机科学与技术专业的一门重要的专业基础课，在整个专业教学体系中占有重要地位。这门课程学习的好坏，对学生学好后续课程如编译原理、操作系统、数据库系统、计算机网络等以及培育学生分析问题、解决问题的实力和软件设计与开发的实力起着至关重要的作用。这门课程不
2、仅涉及的概念多、内容广，而且对数学基础有肯定的要求，解题又须要有肯定的技巧，因此，相当一部分学生感到理解书上的基本概念并不难，基本操作的实现也都听得懂，可是一到解决详细问题时就觉到困难重重，对于有肯定难度的算法设计题，更是感到无从下手。因此，如何学好、怎样教好“数据结构”成为学生和老师普遍关注的一个问题。 1算法设计与分析在数据结构课程中的定位 算法是对解决问题所采纳的方法的描述。因此，在教学过程中应强调算法的概念，在算法设计的同时培育算法分析的习惯，这也是这门课程中实力培育的核心问题。“数据结构”课程的实力培育目标应当是：要求学生在学完这门课程后应能够驾驭本学科系统分析、解决问题的基本科学方
3、法。这种基本科学方法在很大程度上受到老师课堂讲授思想的影响。高校课堂讲授的内容主要分为两个方面，一个是详细的学问，另一个就是分析问题和解决问题的科学方法，而后者通常要在老师的教学过程中来体现。科学的教学方法能够使得老师所传授的学问易于被学生有效接受和消化，同时其解决问题的思想方法也潜移默化被学生所吸纳转变为一种潜在的实力。因此，在“数据结构”课程的讲授中应当避开就概念而概念、就结构而结构的简洁教学模式，而应当结合每个详细学问单元的特点传授分析问题、解决问题的一般思路和方法。这就要求老师要不断提升自己的学问层次和学问的综合实力，并转变观念，使自己的地位渐渐由讲解员过渡为导航员。这样才能使学生由被
4、动的旁听者变为参加实践者，从而达到对学生综合实力的培育目标。 2算法设计与分析在数据结构课程教学中的体现 在“数据结构”的教学内容中，完成同一功能有多个算法的例子比比皆是。例如串的模式匹配。假设目标串和模式串的长度分别为N和M，由于朴实的模式匹配算法须要回溯，使得算法的时间困难度为O(NM)，要想提高模式匹配算法的性能，就应当着眼于消退回溯。这就引出了快速模式匹配算法(KMP算法)。消退了回溯的模式匹配算法的时间困难度成为O(NM)，算法的性能得到了显著的提高1。 再比如，对三元组表示的NM矩阵的转置运算就可以提出三种算法2。首先，最简洁和直观的算法是将源三元组表中元素的行号和列号互换，然后再
5、根据三元组要求的按行排列的要求重新排序。假如采纳干脆选择或插入的方式进行排序，那么这个过程的时间困难度应为O(N2M2)。其次，留意到源三元组中的列就是目的三元组中的行这一特点，引出其次个算法。可以考虑对源三元组进行多趟扫描，第一趟处理源三元组中第1列元素，其次趟处理源三元组中第2列元素，第M趟处理源三元组中第M列元素，第k趟扫描将源三元组中第k列的元素顺次复制到目的三元组中。这个处理过程的时间困难度是O(NM2)，优于前一种算法。其次个算法还可以进一步优化吗？答案是确定的。换一种思路来考虑，就可以提出第三种算法(快速转置算法)：首先计算出源三元组中每一个元素在目的三元组中的位置，然后依次将源
6、三元组中的元素根据预先计算出的位置放置在目的三元组中。这个过程只需先后扫描源三元组两次，时间困难度为O(NM)。当然，为了存放位置信息，须要肯定的额外存储空间。 根据对算法的效率分析来对教学内容进行总结和归纳，是培育学生算法分析实力的另一种方式。对于数据的排序，通常是根据插入、选择、交换等分类进行教学，在对这一部分内容进行总结时，则可按算法的时间性能进行归类。在对N个元素进行排序时，干脆选择、插入和冒泡排序算法都是通过两重循环来实现的，思路直观、简洁，但效率不高(O(N2)。采纳“分而治之”的思想，可以引出快速、堆和归并排序三种算法，它们的效率都可达到O(Nlog2N)。通过对比较树的分析，推
7、导出基于比较的算法的最好平均时间性能为O(Nlog2N)，由此得出结论：要想得到效率更高的排序算法，就不能采纳基于比较的方法。顺着这个思路，可以进一步介绍具有线性时间困难度的基数排序和计数排序算法。可见，在这里，算法的效率分析是主线，顺着这根主线，可以很好地把排序的全部算法串在一起，使学生能够较好地把握住排序的主要教学内容。 对于涉及到算法分析的练习，按题目的难易程度，可以分为三种类型： (1) 给出算法或程序代码段，要求分析其时间困难度。这一类问题的难点是对递归算法的分析，通常应当采纳递推法。详细方法是：逐次绽开等式右边的函数项，最终得到一个收敛的级数，最终对该级数求和。例如，对求解Hano
8、i塔的递归算法的时间困难度进行分析，算法的代码段如下： Void TOH(int n, Pole_start, Pole_goal, Pole_temp) if (n = 0 ) return;/ 递归结束 TOH(n-1, start, temp, goal);/ 递归地移动上面的n-1个盘子 MOVE(start, goal); / 移动最下面的盘子 TOH(n-1, temp, goal, start); / 递归地移动上面的n-1个盘子 估计时间困难度的递推公式如下： Thanoi(n)=1+2Thanoi(n-1) =1+2+4Thanoi(n-2) = =1+2+4+2n-1 留意
9、到1+2+4+2n-1=2n-1，所以上述时间困难度为O(2n)。 (2) 设计一个算法，并分析其时间困难度。这一类问题在上一问题的基础上增加了算法设计的内容。 (3) 在给定时间困难度的前提下设计算法。这一类问题难度较大，要求学生能够设计出高效率的算法。例如求解如下问题：给定整型数组Amn。已知A中数据在每一维方向上都按从小到大的次序排列。试设计一个算法，找出一对满意Aij=x的i,j值(假如存在的话)，要求比较次数不超过m+n。对题目做如下分析：矩阵中元素按行和按列都已排序，要求查找时间困难度为O(m+n)，因此不能采纳常规的二层循环的查找。可以先用右上角(i=0,j=n-1)元素与x比较
10、，只有三种状况：一是xAi,j，下一步应向i大的方向查找；三是Ai,j=x，查找胜利。否则，若下标已超出范围，则查找失败，查找路途如图1所示。对该算法的效率进行分析，算法中查找x的路途从右上角起先，向下(当xAi,j)或向左(当x 3如何培育算法设计与分析的实力 (1) 明确教学目的 课堂教学的主要目的是培育学生分析问题和解决问题的实力，教学的组织和教学过程都应围绕这一点绽开，这是无容置疑的。而对算法的探讨和分析不仅是“数据结构”教学的主要内容之一，同时也是培育学生实力的有效途径。因此，在实际教学过程中，应突出算法的设计思想和算法分析的技巧，注意培育学生解决实际问题的实力。 (2) 使学生充分
11、理解算法分析的重要性 在问题求解过程中，我们所追求的是高效率地解决问题，而不仅仅是设计出一个算法。可以通过一些详细的演示使学生对算法效率有一个感性的了解。例如，将多个排序算法做成动画演示出来，通过对执行算法所花费的时间的比较，使学生明白，即使效率特别接近的算法，在问题规模达到肯定程度时，求解问题所花费的时间之间的差距也是特别明显的。事实上，只有多项式时间困难度的算法才是有意义的，很多效率低下的算法并没有多少实际应用上的价值。 (3) 理解典型算法是基础。 学生对算法的理解是从教材中一些典型算法起先的。因此，在教学过程中，算法的设计思想是重点，不必过多的沉溺于详细的实现细微环节(程序设计的技巧不
12、是这门课程的重点)。首先，通过对典型算法的讲解，使学生了解前人在问题求解过程中是如何考虑问题的，这会对学生产生潜移默化的影响，渐渐提高他们举一反三的实力。其次，通过对教材中的经典算法的分析和总结，使学生了解算法设计的一般原则和方法。比如，数组中的三元组表示的矩阵的转置和乘法运算以及排序中的归并排序和计数排序等，都是借助于额外的协助空间以得到效率更高的算法，这就反映出了一种以空间换时间的思路。再比如，递归是一种特别有力的工具，运用递归方法往往使算法的描述既简洁又易于理解，且设计出的算法易于分析，尤其在困难算法的描述中，递归技术被常常采纳。递归本质上反映的是一种“分而治之”的算法设计思想。 (4)
13、 借助协助教学手段加深对算法的理解 多媒体教学作为一种新兴的现代教化技术已显示出特别强大的生命力，它已成为深化教学改革的一种有效手段。“数据结构”中算法的教学难点之一就在于其抽象性和动态性。学生在阅读一些算法(特殊是困难算法)的程序描述时，经常须要充分的想象力，通过跟踪算法的执行过程来揣摩算法思想，这使得学习的效率低下。在有些状况下，教材上即便是给出了呈现关键概念的图示，但细微环节部分还需靠学生自己的想象力去补充，因此仍旧不能从根本上解决问题。利用可视化教学软件可以在肯定程度上化抽象为直观，帮助学生加深对数据结构和算法的理解。这种软件既可以用于课堂教学的现场演示，又可以供学生课外反复视察体会，
14、对提高教学质量和效率有显著效果3 4。 (5) 试验的设计做到理论联系实际 试验是学生提高算法设计和分析实力的重要手段。试验应以综合性试验为主，以培育学生分析问题和解决问题的实力为目标。在试验过程中，学生在老师的指导下自主设计，充分调动学生的主观能动性。学生通过试验，巩固了课堂上所学到的学问，培育了创新意识和协作与团队精神。试验过程中既要求学生能够综合运用课堂和书本上学到的基本理论与方法，又能够结合实际问题进行分析和设计。例如，在“城市交通导游”这样一个综合性试验中，要求在两种方式下解决交通导游问题：自驾车交通方式是求解最短路径，而搭乘公交的交通方式是求解在换乘次数最小约束下的乘车线路选择。这
15、里，既有典型算法的应用，又须要在图的基本概念和基本算法的基础上考虑数据的存储结构和相应的求解算法。这样的综合性试验可以使学生将课堂和书本上学到学问综合地加以运用，有效地提高学生的分析和解决实际问题的实力。 4结束语 数据结构课程教学的难点是算法的设计与分析。在算法设计的教学过程中，应强调算法设计的思想， 不能过多的沉溺于详细的实现细微环节。应当明确，“数据结构”课程教学的目标是提高学生分析问题和解决问题的实力，这本质上反映了老师是“授人以渔”还是“授人以鱼”。只有解决好这个问题，才有可能促进学生实现从学问型向实力型、从仿照型向创新型、从单一型向复合型人才的转变。 参考文献 1 殷仁昆,陶永雷.
16、 数据结构(用面对对象方法与C+描述)M. 北京:清华高校出版社,11019. 2 Ellis Horowitz, Sartaj Sahni. Fundamentals of Data Structure in C+M. COMPUTER SCIENCE PRESS, 11015. 3 陈庆章,何文秀,金冠卓,夏明. 国外可视化数据结构教学软件及其比较J. 计算机教化,2022,(2):21-23. 4 吴伟民. 数据结构和算法的可视化教学探讨与实践J. 现在计算机,11019,(3):35-37. 投稿日期：2022-06-08 通信地址：南京市，东南高校计算机学院，210196 电话：025-83965001 E-mail：hjiang 第10页 共10页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页第 10 页 共 10 页