沈華　張明武

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

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

0引言

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

1問題描述

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

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

2教學(xué)過程

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

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

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

2）子問題2：如何以低空間成本存儲稀疏矩陣。

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

3）子問題3：如何重新解讀所求問題。

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

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

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

解決方法1：以T.data[]為主導(dǎo)進行填充，即依次填充T.data[0]、T.data[1]……T.data[T.t-I]，并且保證存儲是以T的“行序為主”順序存儲的。具體來說，需要對M.data[]進行M.n次掃描，第j（0≤j≤M.n-1）次掃描的任務(wù)是將M.datar 1中第j列的元素依次進行行列轉(zhuǎn)換后插人T.data[]中。具體求解過程如圖5所示。

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

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

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

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

（編輯：宋文婷）