計算思維在“數據結構”課程教學中的運用

摘要：計算思維是近年來被普遍倡導的一種科學素養，如何在課堂教學中培養大學生的創新能力和計算思維能力，已成為“數據結構”課程教學改革的任務之一。文章首先詳細分析計算思維的定義和特征，然后說明計算思維和數據結構的相通之處，最后給出幾個相關的教學案例。

關鍵詞：計算思維；數據結構；算法設計

0.引言

自2006年3月美國卡內基·梅隆大學周以真教授提出“計算思維”以來，在國內外教育界引起了很大的反響。周教授清晰系統地闡述了計算思維的概念，并認為計算思維是每個人的基本技能，不僅屬于計算機科學家，應當使每個學生在培養解析能力時除掌握閱讀、寫作和算術外，還要學會計算思維。既然是每個人都必須掌握的思維能力，那么作為最“接近”計算思維的計算機專業的學生來說，該如何培養學生具有這種思維方式呢？這個任務顯然不是某一門課程能獨立完成的，它需要滲透到每一門專業課程中。這就要求任課教師本身就應該具有計算思維的教育理念，唯有這樣才能把計算思維滲透到每門課程中，最后把這一抽象的思維方式融到學生的生活和今后的工作中去。

筆者將以計算機專業的基礎課程——“數據結構”的教學經驗為載體，詳細介紹如何在課程中傳授計算思維，使大學生學會運用計算思維去思考問題、解決問題，提升他們的計算素養，使其成為卓越人才。

1.計算思維的定義和特征

計算思維不是新生事物，從古代的算盤到近代的加法器、計算器以及現代的電子計算機，直到目前風靡全球的互聯網和云計算，計算思維的內容在不斷豐富，推動著人類科技的進步。雖然計算思維一直都在被人們應用，但是卻沒有明確地被人們用系統的理論來揭示。直到2006年，周以真教授在計算機權威期刊CommunicationsD，theACM上指出：計算思維是運用計算機科學的基礎概念進行問題求解、系統設計、人類行為理解等的一系列思維活動。周教授系統地給出了計算思維的6個特征：

1）概念化，不是程序化。計算機科學不是計算機編程，像計算機科學家那樣去思維意味著遠不止能為計算機編程，還要求能夠在抽象的多個層次上思維。

2）根本的，不是刻板的技能。根本技能是每一個人為了在現代社會中發揮職能所必須掌握的；刻板技能意味著機械地重復。

3）是人的，不是計算機的思維方式。計算思維是人類求解問題的一條途徑，但并不是要使人類像計算機那樣去思考。計算機枯燥且沉悶，人類聰穎且富有想象力，是人類賦予了計算機激情。

4）數學和工程思維的互補與融合。計算機科學在本質上源自數學思維，因為像所有的科學一樣，其形式化基礎建筑于數學之上。計算機科學又從本質上源自工程思維，基本計算設備的限制迫使計算機學家必須計算性地思考，不能只是數學性地思考。

5）是思想，不是人造物。不只是軟件、硬件等人造物以物理形式到處呈現并時時刻刻觸及我們的生活，更重要的是接近和求解問題、管理日常生活、與他人交流和互動，計算的概念無處不在。

6）面向所有的人，所有地方。當計算思維真正融入人類活動，以至于不再表現為一種顯式哲學時，它就將成為一種現實。

同時，周以真教授又將計算思維闡述成了具體的幾種思維方法：遞歸，抽象和分解，保護，冗余，容錯，糾錯和恢復，利用啟發式推理來尋求解答，在不確定情況下的規劃、學習和調度等。

2.計算思維與數據結構

通過對計算思維的仔細分析，我們試圖用這樣一個公式來概括計算思維，即“模型+算法”。首先，學會合理地抽象，把有待解決的問題抽象成有效的計算過程，抽象成合適的模型，這是問題求解的第一步。然后，基于建立起來的模型利用各種思維方法去求解問題。

“數據結構”是計算機專業的一門專業必修課，是軟件編程設計的基礎，對于培養學生的邏輯思維能力，利用計算機解決實際問題的能力都起到了至關重要的作用。“數據結構”的研究內容可歸納為3個部分：邏輯結構、存儲結構和運算集合，即按某種邏輯關系組織起來的一批數據，按一定的映像方式把它存放在計算機的存儲器中，并在這些數據上定義了一個運算的集合，可以用“（邏輯|存儲）結構+算法”的公式來概括。

對比兩個“公式”，我們可以發現相似之處，都是靜態結構和動態操作的結合。當然，計算思維中的模型和算法都要比數據結構中的概念來的寬泛很多。但正因為某種程度的契合，使得在“數據結構”課程中貫徹計算思維的思想，要比其他課程來得自然和容易許多。具體體現在：

1）從“邏輯或者存儲結構”的選擇理解“抽象建模”。在“數據結構”課程中，當面對一個問題時，首先是要能從問題中抽象出數據對象，然后分析數據對象中各個數據元素相互之間的（邏輯）關系是什么，接著這種邏輯關系用什么樣的存儲結構來實現。確定好這些后，再思考各種算法的設計和實現。整個問題的求解過程，就是一個抽象建模的過程。只不過，計算思維的概念更寬泛，它還需要考慮問題的可計算性（即計算的能力和極限，知道哪些問題可以計算，哪些問題不可以計算），而“數據結構”課程中所給出的問題都是可計算的。即便如此，依然能通過對問題的抽象去訓練計算思維。

2）通過算法多樣化訓練思維方法。“數據結構”課程中，對于一個問題往往可以通過不同方式來完成算法。在選擇不同求解方式的過程中，可以很好地訓練計算思維。例如，可以學會對問題進行有效的分解，分解的方法和結果當然是多樣性的，分解的過程要希望每個分解塊能盡量被重用，重用計算過程，重用程序。如何有效重用，是一個問題的抽象分類。這樣做，能快速獲得計算結果。在設計算法和優化算法的過程中還需要利用遞歸、并發、啟發、學習等方法。

3）通過靈活的實驗手段打造創新思維。雖然在計算思維的第一個特征中強調“計算思維是概念化，不是程序化。計算機科學不是計算機編程”，但是不可否認的是，當你使用計算機來解決具體問題求解時，把算法思想編寫成可執行的程序是解決問題和驗證算法有效性的最好方法。因此，在教學過程中，我們強調并培養學生對于抽象過程的嚴謹性，編寫程序時強調從需求定義開始，進行算法優化與選擇，最后通過上機實驗來驗證。為了提高學生學習的興趣，我們在安排實驗內容上，多以實用課題為主，盡量生動化、趣味化，例如，在線性表的實驗中，選擇了通訊錄的設計和管理；在圖的實驗中，選擇了最經濟出行路線的設計。

3.教學案例

3.1抽象和分解方法的使用——排序問題

“數據結構”中有很多排序算法：插入排序、選擇排序、冒泡排序等算法。在講解這些算法時可以滲透講解計算思維中“抽象和分解”的思想。該方法是“選擇合適的方式去陳述一個問題，或者是選擇合適的方式對一個問題的相關方面建模使其易于處理”，也就是把一個復雜的問題分解成若干相關的子問題或者簡單問題去處理。

以插入排序為例，插入排序的基本思想是每次將一個待排序的記錄，按其關鍵字大小插入到前面已經排好序的子表中的適當位置，直到全部記錄插入完成為止。多個記錄的排序問題可以看成是一個大的復雜問題，這個問題可抽象分解成若干個小問題：把一個待排的記錄插入到已經有序的子表中。那么原來的排序問題就變成了不斷增長有序表中記錄的個數，即記錄個數依次從初始的1增加到n（即所有記錄的個數），個數增加到n時，排序就完成了。這個小問題又可轉換為數據的兩兩比較，即待排序記錄依次和有序子表中的記錄進行兩兩比較，直到找到合適的位置，插入即可，插入后的子表依然有序。fb7f50d707b5e800146bb16ebebddd0a最后，通過這樣兩層轉換，排序問題就轉換成了學生非常熟悉的數據兩兩比較的問題。同樣，其他排序方法也可以通過層層抽象和分解把問題轉換為簡單的小問題。

3.2遞歸方法的使用——二叉樹的遍歷問題

二叉樹的遍歷是按照一定次序訪問二叉樹中的所有結點，并且每個結點僅被訪問一次。遞歸方法是“把代碼譯成數據又把數據譯成代碼”。從程序設計的角度看，遞歸就是在定義一個過程或者函數時出現直接調用或間接調用本過程或本函數的成分。

二叉樹及其相關操作的講解是“數據結構”課程的重點和難點，由于二叉樹的定義本身就是一個遞歸定義，因此與其相關的操作，利用遞歸的方式來完成也是最自然的事情，是一個能很好地體現遞歸思想的知識點。以二叉樹的中序遍歷為例，我們首先可以利用上述的分解方法將整個遍歷問題劃分成若干個子問題，即分解為中序訪問左子樹，根結點，中序右子樹這樣三個子問題；接著，對訪問左子樹和訪問右子樹的子問題，利用相同的方法，又可以分解為類似的若干個子問題或者不能再劃分（如子樹為空）；如此反復進行，直到不能再劃分成子問題，或者已經可以求解為止。在分解過程中，算法不斷地利用同樣的方法分解問題，不斷地按照左子樹一根結點一右子樹的順序訪問。這個“較小問題”反復不斷地被重復，形成了遞歸體。從問題分析的過程，可以引導學生去理解遞歸這一抽象而又重要的方法。

4.結語

計算思維已經成為近年來教育領域的研究熱點，并作為一種通識教育被研究。計算機學科在培養計算思維方面有著得天獨厚的條件，計算思維的培養對于人才本身也是極為重要的，它可以使學生理解計算機的實現機制和約束，有利于培養學生的創新思維，提高學生的信息素養，展現出處理計算機相關問題時應有的思維方法、表達形式和行為習慣。

文章對如何在“數據結構”課堂教學過程中滲透計算思維進行有益的探討。實踐表明，將計算思維融合于教學實踐提高了教學質量，提高了學生解決問題的能力，對人才的培養大有裨益。

（見習編輯：劉麗麗）