以計(jì)算思維為中心的數(shù)據(jù)結(jié)構(gòu)教學(xué)方法探討

沈華　張明武

摘要：如何幫助學(xué)生學(xué)習(xí)和掌握數(shù)據(jù)結(jié)構(gòu)課程蘊(yùn)含的計(jì)算思維，是從事數(shù)據(jù)結(jié)構(gòu)教學(xué)工作的教育者需要考慮的重要問(wèn)題。文章提出一種基于問(wèn)題驅(qū)動(dòng)和圖示法的教學(xué)方法，即以計(jì)算思維為中心的教學(xué)方法，以稀疏矩陣的轉(zhuǎn)置問(wèn)題為例說(shuō)明該教學(xué)方法的理念和特點(diǎn)。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；計(jì)算思維；教學(xué)方法；問(wèn)題驅(qū)動(dòng)；圖示法

0引言

在計(jì)算機(jī)科學(xué)中，數(shù)據(jù)結(jié)構(gòu)是一種在計(jì)算機(jī)中組織和存儲(chǔ)數(shù)據(jù)，以便高效利用這些數(shù)據(jù)的有效方式。數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)在抽象視圖和實(shí)現(xiàn)視圖中的表示和處理方法，其理論性和抽象性較強(qiáng)，要求能夠運(yùn)用計(jì)算思維分析并解決問(wèn)題，被認(rèn)為是比較難學(xué)的課程。基于問(wèn)題驅(qū)動(dòng)的教學(xué)方法是將求解原問(wèn)題轉(zhuǎn)換成一系列的子問(wèn)題，通過(guò)求解子問(wèn)題序列最終求解原問(wèn)題，子問(wèn)題序列實(shí)際上給出運(yùn)用計(jì)算機(jī)求解問(wèn)題的最終目的和思考問(wèn)題的計(jì)算思維軌跡。圖示法可以直觀、形象地描述每個(gè)子問(wèn)題的求解思路和過(guò)程。為了讓學(xué)生更好更明確地理解什么是計(jì)算思維、數(shù)據(jù)結(jié)構(gòu)中有哪些計(jì)算思維、怎樣運(yùn)用計(jì)算思維求解問(wèn)題，通過(guò)在教學(xué)過(guò)程中不斷嘗試和探索，我們發(fā)現(xiàn)將問(wèn)題驅(qū)動(dòng)與圖形演示兩種教學(xué)手段結(jié)合起來(lái)是一種行之有效的教學(xué)方法，即以計(jì)算思維為中心的教學(xué)方法。

1問(wèn)題描述

隨機(jī)稀疏矩陣是非零元比零元少很多且非零元的分布不具規(guī)律性的一種矩陣，轉(zhuǎn)置矩陣是矩陣行列交換后得到的一種矩陣。通常用二維數(shù)組表示矩陣，借助二維數(shù)組可以實(shí)現(xiàn)計(jì)算機(jī)求解矩陣的轉(zhuǎn)置矩陣。以求解稀疏矩陣M的轉(zhuǎn)置矩陣T為例，求解過(guò)程如圖1所示。

實(shí)現(xiàn)求解稀疏矩陣M的轉(zhuǎn)置矩陣T這個(gè)目標(biāo)，需要依次解決的子問(wèn)題有在存儲(chǔ)器中如何存儲(chǔ)二維數(shù)組、如何以低空間成本存儲(chǔ)稀疏矩陣、如何從存儲(chǔ)結(jié)構(gòu)的角度解讀需要求解的問(wèn)題和如何求解新視圖中的問(wèn)題。

2教學(xué)過(guò)程

按照求解邏輯，將求解稀疏矩陣的轉(zhuǎn)置矩陣問(wèn)題細(xì)化為一個(gè)子問(wèn)題序列，通過(guò)依次求解序列中的子問(wèn)題最終使原問(wèn)題得到解決。講解每個(gè)子問(wèn)題的求解方法時(shí)，可以運(yùn)用圖示生動(dòng)形象地描述抽象復(fù)雜的求解過(guò)程。具體教學(xué)過(guò)程如下所述。

1）子問(wèn)題1：如何在存儲(chǔ)器中描述二維數(shù)組。

這個(gè)子問(wèn)題隱藏的計(jì)算思維是如何在線性空間（存儲(chǔ)器）中描述非線性結(jié)構(gòu)。為了更形象地說(shuō)明該子問(wèn)題的兩種求解方法——“以行為主”順序存儲(chǔ)和“以列為主”順序存儲(chǔ)，我們?cè)谥v解的過(guò)程中使用圖2所示的示意圖。

2）子問(wèn)題2：如何以低空間成本存儲(chǔ)稀疏矩陣。

隨機(jī)稀疏矩陣中的非零元非常少，為了節(jié)約空間成本，通常只存儲(chǔ)其中的非零元信息，但非零元在矩陣中的分布沒(méi)有規(guī)律性，因此除了需要存儲(chǔ)非零元的值外，還需要存儲(chǔ)非零元在矩陣中的位置信息；三元組（行，列，值）結(jié)構(gòu)可以滿足這樣的存儲(chǔ)需求。一個(gè)稀疏矩陣可以表示為一個(gè)三元組集合，但三元組集合只給出了稀疏矩陣所有非零元的分布信息、值的信息和部分零元的分布信息，并不能唯一確定一個(gè)稀疏矩陣。為了獲得所有零元的分布信息，我們需要知道稀疏矩陣的規(guī)模信息，即它是多少行多少列的矩陣。低空間成本存儲(chǔ)稀疏矩陣M的存儲(chǔ)結(jié)構(gòu)圖（以“行序?yàn)橹鳌贝鎯?chǔ)三元組）如圖3所示。

3）子問(wèn)題3：如何重新解讀所求問(wèn)題。

稀疏矩陣的轉(zhuǎn)置矩陣還是稀疏矩陣，因此目標(biāo)矩陣T也將按照上述低空間成本存儲(chǔ)方案進(jìn)行存儲(chǔ)，那么用存儲(chǔ)結(jié)構(gòu)視圖重新解讀問(wèn)題“已知稀疏矩陣M，求它的轉(zhuǎn)置矩陣T”，實(shí)質(zhì)上就是已知圖3補(bǔ)全圖的問(wèn)題。

4）子問(wèn)題4：如何根據(jù)圖3的信息補(bǔ)全圖4。

顯然，根據(jù)M中m、n和t這3個(gè)成員的值可以很容易得到T.m、T.n和T.t的值，即T.m=M.n，T.=M.m，T.t=M.t。因此，我們需要解決的關(guān)鍵問(wèn)題是如何根據(jù)M.data[]得到T.data[]。

解決方法1：以T.data[]為主導(dǎo)進(jìn)行填充，即依次填充T.data[0]、T.data[1]……T.data[T.t-I]，并且保證存儲(chǔ)是以T的“行序?yàn)橹鳌表樞虼鎯?chǔ)的。具體來(lái)說(shuō)，需要對(duì)M.data[]進(jìn)行M.n次掃描，第j（0≤j≤M.n-1）次掃描的任務(wù)是將M.datar 1中第j列的元素依次進(jìn)行行列轉(zhuǎn)換后插人T.data[]中。具體求解過(guò)程如圖5所示。

解決方法2：以M.data[]為主導(dǎo)進(jìn)行填充，即依次根據(jù)M.data[0]、M.data[1]……M.data[M.t-11填充T.data[]，并且保證存儲(chǔ)是以T的“行序?yàn)橹鳌表樞虼鎯?chǔ)的。具體來(lái)說(shuō)，只需要對(duì)M.data[]進(jìn)行一次掃描，掃描到第k（0≤k≤M.t-1）個(gè)三元組時(shí)，需要確定該三元組進(jìn)行行列轉(zhuǎn)換后的新三元組應(yīng)該填到T.data[]中的什么位置。為了解決這個(gè)問(wèn)題，在填充之前需要對(duì)M.data[]中的三元組進(jìn)行統(tǒng)計(jì)分析，分析出M的每一列有多少個(gè)元組。假設(shè)得到M的第j（0≤j≤M.n-1）列有Nodesj個(gè)非零元，那么，實(shí)際上得到T的第f（0≤i≤T.m-1）行非零元在T.data[]中的位置范圍為

為了便于操作，給每個(gè)位置范圍設(shè)置—個(gè)“坐標(biāo)指針”，用符號(hào)rposi（0≤i≤T.m-1）表示T的第i行坐標(biāo)指針。坐標(biāo)指針的作用是指示T的每一行當(dāng)前需要填充的位置坐標(biāo)，其移動(dòng)軌跡為從相應(yīng)位置范圍的下界朝上界的方向移動(dòng)，每次只能向后移動(dòng)一個(gè)位置。具體求解過(guò)程如圖6所示。

顯然通過(guò)依次思考并求解上述4個(gè)子問(wèn)題，最終可以利用計(jì)算思維成功求出稀疏矩陣M的轉(zhuǎn)置矩陣T。 3結(jié)語(yǔ)

數(shù)據(jù)結(jié)構(gòu)是一門(mén)理論性和抽象性都很強(qiáng)的課程，蘊(yùn)含著很多的計(jì)算思維，如何幫助學(xué)生在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)體會(huì)和掌握這些計(jì)算思維，是從事數(shù)據(jù)結(jié)構(gòu)教學(xué)工作的教育者需要考慮的重要問(wèn)題。我們?cè)诰W(wǎng)絡(luò)工程專(zhuān)業(yè)近5屆共10個(gè)班的數(shù)據(jù)結(jié)構(gòu)教學(xué)中采用該教學(xué)方法，學(xué)生普遍反映這樣的教學(xué)方式不僅讓他們了解如何運(yùn)用某種數(shù)據(jù)結(jié)構(gòu)解決一個(gè)應(yīng)用問(wèn)題，還讓他們明白為什么會(huì)是這樣的求解過(guò)程，更使他們明白如何將應(yīng)用問(wèn)題轉(zhuǎn)換為計(jì)算機(jī)視角的等價(jià)問(wèn)題，真真切切地感受到“計(jì)算思維”。此外，每年兩個(gè)班中平均有近30%的學(xué)生入選學(xué)院ACM訓(xùn)練班，多名學(xué)生在各類(lèi)軟件設(shè)計(jì)大賽中獲獎(jiǎng)。可見(jiàn)，以計(jì)算思維為中心的教學(xué)方法在數(shù)據(jù)結(jié)構(gòu)課程教學(xué)過(guò)程中是行之有效的。

（編輯：宋文婷）