重典型应用,明结构关系

    李维明

    通过前几期对“数据及其价值”“数据结构”内容及特点的讨论,知道了数据结构对改变算法设计、提升算法效率有着重要的作用。相应地,在“数据及其价值”“数据结构”的教学上也应采取注重数据价值、关注结构作用的策略。在此基础上,还应该关注数据结构的实际应用,关注结构应用对算法的改变效果,同时也要厘清算法与数据结构的区别与联系。

    ● 注重典型应用,了解数据结构对算法的作用

    在《普通高中信息技术课程标准(2017年版2020修订)》(以下简称《标准》)“数据与数据结构”模块中,涉及的数据结构类型并不多,因而与其相关的算法应用也不多,主要有迭代与递归、查找与排序等,而在这些应用中,最熟悉的莫过于排名次(排序)了。教学时应当抓住这样的实例,通过分析不同数据结构与排序方法的优劣,了解数据结构与算法之间的关系。

    排序是指把一个任意序列的数据元素重新排列成按照某关键字递增或递减的过程,常见的排序方法有插入排序法(直接插入排序、折半插入排序等)、交换排序法(冒泡排序、快速排序等)等,而在教材中必讲的方法之一就是冒泡排序。

    冒泡排序是一种简单的排序算法。假设待排数据元素有n个,用相邻两两比较法第一次在n个数中找出最小(或最大)数,第二次在n-1个数中找出最小数(或最大),第三次在n-2个数中找出最小数(或最大)……到第n-1次则完成排序。由于在此算法每趟排序的过程中值小(或值大)的元素向前移动,值大(或值小)的元素向后移动,类似于水中气泡上升,故称为冒泡排序。在这里,冒泡排序使用的数据结构为顺序存储的结构,一般用一个二维数组存放,适合多次进行比较或交换。

    从操作的角度看,排序是线性结构的一种操作,待排元素可以用顺序结构和链式结构来存储。在这两种排序操作中,不管使用哪方法,都涉及对某种存储结构数据的位置移动或链表改变。例如,某组数据采用的是顺序结构存储,其待排元素按自然顺序存放在一组连续的内存空间中,排序时会移动元素位置,使之有序;如某组数据采用的是链式结构存储,则排序时只需将无序链表中的元素进行比较,然后改变链表指针,使之变成有序链表。由此可以看出,数据元素的存储结构不同,其算法也会发生改变,而这些改变也会影响算法的运算效率。

    ● 明晰基本关系,厘清数据结构与算法的联系与区别

    关于数据结构与算法的联系,《标准》描述为“算法与数据结构是问题求解中相辅相成、不可分割的两个方面”;而公式“算法+数据结构=程序”更是揭示了二者的紧密联系。

    算法总是要依赖某种数据结构来实现,往往是在发展一种算法的时,构建了适合这种算法的同数据结构。算法的操作对象是数据结构。算法的设计和选择要同时结合数据结构,简单地说数据结构的设计就是选择存储方式。算法设计的实质就是为要处理的数据选择一种恰当的存储结构,并在选定的存储结构上设计一个好的算法。不同数据结构的设计将导致差异很大的算法。数据结构是算法设计的基础,算法设计必须考虑到数据结构,算法设计不可能独立于数据结构。另外,数据结构的设计和选择需要为算法服务。总之,算法的设计同时伴有數据结构的设计,两者都是为最终解决问题服务的。

    数据结构与算法的区别:数据结构关注的是数据的逻辑结构、存储结构以及基本操作,而算法更多的是关注如何在数据结构的基础上解决实际问题。算法是编程的思想,而数据结构则是这些思想的逻辑基础。

    《标准》在“学业要求”中明确了数据结构与算法教学的分寸,就是“能够针对限定条件的实际问题进行数据抽象,运用数据结构合理组织、存储数据,选择合适的算法(如排序、查找、迭代等)编程实现、解决问题”。所以只要能抓住“限定条件的实际问题”典型应用,“运用数据结构合理组织、存储数据”“选择合适的算法”实现,就能够很好地解决数据结构应用的教学问题。