重典型應(yīng)用，明結(jié)構(gòu)關(guān)系

李維明

通過前幾期對“數(shù)據(jù)及其價值”“數(shù)據(jù)結(jié)構(gòu)”內(nèi)容及特點的討論，知道了數(shù)據(jù)結(jié)構(gòu)對改變算法設(shè)計、提升算法效率有著重要的作用。相應(yīng)地，在“數(shù)據(jù)及其價值”“數(shù)據(jù)結(jié)構(gòu)”的教學(xué)上也應(yīng)采取注重數(shù)據(jù)價值、關(guān)注結(jié)構(gòu)作用的策略。在此基礎(chǔ)上，還應(yīng)該關(guān)注數(shù)據(jù)結(jié)構(gòu)的實際應(yīng)用，關(guān)注結(jié)構(gòu)應(yīng)用對算法的改變效果，同時也要厘清算法與數(shù)據(jù)結(jié)構(gòu)的區(qū)別與聯(lián)系。

● 注重典型應(yīng)用，了解數(shù)據(jù)結(jié)構(gòu)對算法的作用

在《普通高中信息技術(shù)課程標(biāo)準(zhǔn)（2017年版2020修訂）》（以下簡稱《標(biāo)準(zhǔn)》）“數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)”模塊中，涉及的數(shù)據(jù)結(jié)構(gòu)類型并不多，因而與其相關(guān)的算法應(yīng)用也不多，主要有迭代與遞歸、查找與排序等，而在這些應(yīng)用中，最熟悉的莫過于排名次（排序）了。教學(xué)時應(yīng)當(dāng)抓住這樣的實例，通過分析不同數(shù)據(jù)結(jié)構(gòu)與排序方法的優(yōu)劣，了解數(shù)據(jù)結(jié)構(gòu)與算法之間的關(guān)系。

排序是指把一個任意序列的數(shù)據(jù)元素重新排列成按照某關(guān)鍵字遞增或遞減的過程，常見的排序方法有插入排序法（直接插入排序、折半插入排序等）、交換排序法（冒泡排序、快速排序等）等，而在教材中必講的方法之一就是冒泡排序。

冒泡排序是一種簡單的排序算法。假設(shè)待排數(shù)據(jù)元素有n個，用相鄰兩兩比較法第一次在n個數(shù)中找出最小（或最大）數(shù)，第二次在n-1個數(shù)中找出最小數(shù)（或最大），第三次在n-2個數(shù)中找出最小數(shù)（或最大）……到第n-1次則完成排序。由于在此算法每趟排序的過程中值?。ɑ蛑荡螅┑脑叵蚯耙苿?，值大（或值小）的元素向后移動，類似于水中氣泡上升，故稱為冒泡排序。在這里，冒泡排序使用的數(shù)據(jù)結(jié)構(gòu)為順序存儲的結(jié)構(gòu)，一般用一個二維數(shù)組存放，適合多次進行比較或交換。

從操作的角度看，排序是線性結(jié)構(gòu)的一種操作，待排元素可以用順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)來存儲。在這兩種排序操作中，不管使用哪方法，都涉及對某種存儲結(jié)構(gòu)數(shù)據(jù)的位置移動或鏈表改變。例如，某組數(shù)據(jù)采用的是順序結(jié)構(gòu)存儲，其待排元素按自然順序存放在一組連續(xù)的內(nèi)存空間中，排序時會移動元素位置，使之有序;如某組數(shù)據(jù)采用的是鏈?zhǔn)浇Y(jié)構(gòu)存儲，則排序時只需將無序鏈表中的元素進行比較，然后改變鏈表指針，使之變成有序鏈表。由此可以看出，數(shù)據(jù)元素的存儲結(jié)構(gòu)不同，其算法也會發(fā)生改變，而這些改變也會影響算法的運算效率。

● 明晰基本關(guān)系，厘清數(shù)據(jù)結(jié)構(gòu)與算法的聯(lián)系與區(qū)別

關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法的聯(lián)系，《標(biāo)準(zhǔn)》描述為“算法與數(shù)據(jù)結(jié)構(gòu)是問題求解中相輔相成、不可分割的兩個方面”;而公式“算法+數(shù)據(jù)結(jié)構(gòu)=程序”更是揭示了二者的緊密聯(lián)系。

算法總是要依賴某種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，往往是在發(fā)展一種算法的時，構(gòu)建了適合這種算法的同數(shù)據(jù)結(jié)構(gòu)。算法的操作對象是數(shù)據(jù)結(jié)構(gòu)。算法的設(shè)計和選擇要同時結(jié)合數(shù)據(jù)結(jié)構(gòu)，簡單地說數(shù)據(jù)結(jié)構(gòu)的設(shè)計就是選擇存儲方式。算法設(shè)計的實質(zhì)就是為要處理的數(shù)據(jù)選擇一種恰當(dāng)?shù)拇鎯Y(jié)構(gòu)，并在選定的存儲結(jié)構(gòu)上設(shè)計一個好的算法。不同數(shù)據(jù)結(jié)構(gòu)的設(shè)計將導(dǎo)致差異很大的算法。數(shù)據(jù)結(jié)構(gòu)是算法設(shè)計的基礎(chǔ)，算法設(shè)計必須考慮到數(shù)據(jù)結(jié)構(gòu)，算法設(shè)計不可能獨立于數(shù)據(jù)結(jié)構(gòu)。另外，數(shù)據(jù)結(jié)構(gòu)的設(shè)計和選擇需要為算法服務(wù)。總之，算法的設(shè)計同時伴有數(shù)據(jù)結(jié)構(gòu)的設(shè)計，兩者都是為最終解決問題服務(wù)的。

數(shù)據(jù)結(jié)構(gòu)與算法的區(qū)別：數(shù)據(jù)結(jié)構(gòu)關(guān)注的是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)以及基本操作，而算法更多的是關(guān)注如何在數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)上解決實際問題。算法是編程的思想，而數(shù)據(jù)結(jié)構(gòu)則是這些思想的邏輯基礎(chǔ)。

《標(biāo)準(zhǔn)》在“學(xué)業(yè)要求”中明確了數(shù)據(jù)結(jié)構(gòu)與算法教學(xué)的分寸，就是“能夠針對限定條件的實際問題進行數(shù)據(jù)抽象，運用數(shù)據(jù)結(jié)構(gòu)合理組織、存儲數(shù)據(jù)，選擇合適的算法（如排序、查找、迭代等）編程實現(xiàn)、解決問題”。所以只要能抓住“限定條件的實際問題”典型應(yīng)用，“運用數(shù)據(jù)結(jié)構(gòu)合理組織、存儲數(shù)據(jù)”“選擇合適的算法”實現(xiàn)，就能夠很好地解決數(shù)據(jù)結(jié)構(gòu)應(yīng)用的教學(xué)問題。