李維明

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

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

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

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

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

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

● 明晰基本關(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)是問(wèn)題求解中相輔相成、不可分割的兩個(gè)方面”;而公式“算法+數(shù)據(jù)結(jié)構(gòu)=程序”更是揭示了二者的緊密聯(lián)系。

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

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

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