突出計算思維訓練的數據結構教學實踐

司 明， 厙向陽， 李占利， 李洪安(西安科技大學 計算機科學與技術學院，西安 710054)

0 引 言

當前，計算水平與能力已經成為國家科技實力的衡量標準之一，同時，計算也是科學思維的重要組成部分。自2006年周以真教授提出“計算思維”以來，在計算機界、科技界和相關領域引起了很大的反響。目前，自然科學領域公認有三大科學思維：理論思維、實驗思維和計算思維。每個人都必須掌握計算思維的能力。在大學教育中，需要將計算思維滲透到每一門課程中，把這種思維方式融入到學生的學習與今后的工作中。本文以計算機專業的主干課程“數據結構”為分析對象，詳細介紹該課程融入計算思維的教學實踐過程。

1 數據結構課程重要性和教學現狀

1.1 數據結構課程重要性

數據結構涉及到多方面的知識，如計算機組成原理和系統結構的存儲裝置和存取方法，操作系統的文件系統，數據庫的數據動態管理、信息檢索，數學的集合、邏輯的知識，以及數據類型、程序設計方法、數據表示、數據運算、數據存取等，是計算機專業一門重要的專業技術基礎課程[1-2]。

數據結構的內容將為操作系統、數據庫原理、編譯原理等后續課程的學習打下良好的基礎，數據結構課程講授在高級語言中計算機如何組織和表示信息，同時可以提高學生分析和解決復雜問題的編程能力，因此數據結構是數學、計算機硬件、計算機軟件三者之間的一門核心課程，數據結構是計算機專業提高軟件設計水平的一門關鍵課程[3-4]，與其他課程的關系如圖1所示。

圖1 數據結構與其他課程的關系

1.2 數據結構教學現狀

(1) 課程安排不合理。數據結構的前置課程是C語言和離散數學，而C語言的前置課程是高等數學和線性代數。我校大部分學院開設C語言課程，不同學院開設C語言的教學內容和要求都不一致。特別是非計算機專業學生在學習C語言之前，沒有程序設計語言學習的基礎，缺少程序設計的思維能力，現有教學學時偏少，實踐環節薄弱，導致學生C語言學習吃力，沒有打下良好的程序設計基礎，C語言學習基礎不好直接影響到數據結構的教學。另外，離散數學是數據結構的前置課程，但由于課時不足，大部分非計算機專業均未開設該課程。非計算機專業課程安排中還出現C語言和高等數學并行開設，C語言安排在線性代數前面學習，這樣將導致學生對C語言課程學習理解不夠深入，最終影響數據結構課程的學習。

(2) 教學與專業背景結合不夠。數據結構課程的理論性和抽象性很強，教學內容需要與學生專業相結合，加深學生對理論的理解，同時也讓學生明白程序設計和數據結構是工具，是為專業實踐服務的。但目前的教學中，由于學生缺少程序設計的基礎訓練，教師只能在有限課時的情況下將重點放在程序設計和理論的基礎知識上，在不同專業教學的數據結構課程中，非計算機專業學生感覺學習難度很大，學習效果差。

(3) 教學思路不明確。盡管已經制定數據結構課程的教學大綱，確定了教學內容、實驗內容，但是在目前的教學過程中，多就事論事、照本宣科和照章執行，對數據結構課程中蘊藏的思想方法挖掘和總結歸納不足，教學內容組織不合理，缺乏系統性和創造性，最終導致學生僅僅具有一定的模仿能力,創新能力不足，解決問題的綜合能力差，事倍功半。

(4) 實踐訓練不足。數據結構課程是計算機科學家和計算機工程技術人員在編程實踐中總結、歸納、提煉出來的理論和方法，也就是說數據結構來源于編程工程實踐[5]。數據結構課程一般在大學二三年級開設，同學的編程實踐少、經驗不足，更缺乏綜合性實踐訓練，因而同學們對數結構中思路方法、實現算法不理解，甚至懷疑其用途和重要性。目前數據結構的課內實驗和課程設計多大是驗證實驗和簡單應用性實驗，缺乏復雜綜合性實驗。

2 數據結構課程的計算思維特征

2.1 抽象性、構造性思維特征

計算機解決問題步驟：具體問題→數學模型→抽象數據類型→數據結構→算法分析→結論，如圖2所示。這是計算機解決具體問題的理論分析線索。抽象數據類型是指基于一類邏輯關系的數據類型以及定義在這個類型之上的一組操作[6]。抽象數據類型體現了程序設計中一些最基本原則：分解、抽象和信息隱藏。抽象數據類型可以看成是定義了一組運算的數學模型[7]。

圖2 計算機解決具體問題步驟

2.2 構造性思維的工程化

與理論分析線索相對應，計算機解決具體問題的工程化實現過程是：具體問題→非形式化算法→偽語言程序→可執行程序→程序測試→結論[8]。其中非形式化算法來源于待解決的具體問題的數學模型，偽語言程序來源于抽象數據類型，可執行程序來源于數據存儲結構及其組織方式。計算機解決具體問題的工程化實現過程是對理論分析線索的具體化，是在理論分析線索的具體指導下完成的[9]。在高級語言中，數據抽象的基本單元是數據類型，如整型、浮點型、邏輯型等。數據類型再構造高級數據抽象，如表、隊、棧、樹等[10]。抽象數據類型實現途徑如圖3所示。

圖3 抽象數據類型實現途徑

算法是規則的有限集合，是為解決特定問題而規定的一系列操作。算法是構造性思維的具體實現。算法實現過程的步驟如圖4所示。

圖4 算法實現過程步驟

在構造性思維的工程化過程中，由于理論的復雜性、計算資源的有限性(尤其是優質資源)，算法實現不得不采用并行、近似、簡化、折中等策略得到比較滿意的解[11]。

2.3 數據結構中基本操作、算法的計算思維特征

數據結構中針對復雜的對象和問題，按照系統工程的思想，通過分解的方法構造問題子結構，研究分析子問題結構關系，采用相應策略進行問題求解。將數據結構中的一些操作、算法體現的計算思維特征總結歸納如表1所示。

表1 數據結構中一些操作、算法計算思維特征

3 計算思維引導下的數據結構教學組織方法

3.1 理論教學

在數據結構教學過程中，按照具體問題的抽象模型(邏輯關系)特點將數據結構研究設計的對象分為線性、樹、圖結構及其建立在此基礎上的算法。對于每一種結構類型按照具體問題→數學模型→抽象數據類型→數據結構→算法分析[12]的思路組織理論教學內容。理論教學組織方法如表2所示。

3.2 實驗教學

盡管數據結構實驗教學與理論教學的側重點和方式方法不同，但終極目標是一致的,即培養學生解決實際問題的能力。因而，實驗教學同樣也要體現計算思維的理念。按照實驗的難易程度，將數據結構實驗分為驗證性、應用性和綜合性實驗。與理論教學一致，按照問題的邏輯結構，安排不同層次的實驗內容，實驗教學內容安排如表3所示。不同的專業和不同層次的院校可選擇不同層次的實驗。非計算機專業和三本院校可選擇驗證性、應用性實驗(全部或部分)兩個層次的實驗內容。計算機專業和一本院校的可選擇驗證性、應用性和綜合性實驗(全部或部分)三個層次的實驗內容。按照分層遞進的教學思想，根據實際教學的需求，選擇不同層次的教學內容，滿足不同專業和不同層次的教學需求[13]。

4 基于計算思維的教學案例

在案例教學中，強調學生的主動性。根據教學內容的安排，需要設計特定的教學案例，吸引學生，將學生帶入到特定的情境中，通過討論和互動，啟發學生思維，鍛煉學生解決實際問題的能力，有助于激發他們的計算思維。案例設計需要遵循幾個原則:①要結合學生的實際生活，例如對于最短路徑問題，可以用學生假期選擇旅游線路的案例，對于隊列問題，可以用學生入學繳費排隊的案例。②案例需要符合數據結構的特點，例如隊列問題，十分契合先到先服務的特點。③案例需要覆蓋盡可能多的知識點，可以作為啟發式思維的訓練實例將案例拓展到更多的知識點學習中。下面以二叉樹應用中的家譜管理系統為例，介紹在數據結構教學過程中融入計算思維的思路和方法。

4.1 問題抽象

計算思維中的抽象，體現在完全使用符號系統甚至形式化語言，從本質上源于數學思維[14]。在家譜管理系統中抽象過程描述如下，首先抽象為概念模型，在家譜中查看某一代的兄弟姐妹。其次抽象為邏輯模型，二叉樹中的遍歷問題。最后是物理模型，通過變量的輸入、存儲、計算和輸出實現家譜管理功能。

4.2 關注點分離

計算思維中的關注點分離是先將復雜問題做合理的分解，再分別仔細研究問題的不同側面(關注點)，最后綜合各方面的結果，合成整體的解決方案[15]。在教學過程中，將程序分解為主程序和多個子程序，進一步將子程序分解為更小的對應每個知識點的子程序，學生通過知識點的對應，可以輕松完成每個子程序的設計和編程。所有的子程序設計編程完成后，串聯起來就是一個完整的程序。在家譜管理系統中查看某一代的兄弟姐妹，將該任務首先進行第一次關注點分離，將程序分解為一個主程序和兩個子程序，主程序包括調用子程序函數，顯示函數等過程，一個子程序完成代數的傳遞，另一個子程序完成查詢的功能。第二次關注點分離又可將主程序分解為調用函數子程序，顯示函數子程序等。查詢子程序分解為參數傳遞子程序，二叉樹遍歷子程序。二叉樹遍歷子程序又可以分解為多個子程序。通過這樣一步一步的分解，可以將復雜的設計過程分解為一個個獨立的子程序，更加易于設計編寫。

表2 理論教學組織方法

續表2

表3 實驗教學內容

續表3

4.3 遞 歸

一個過程或函數在其定義或說明中有直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解。在二叉樹及其操作的內容部分，遞歸作為主要的算法被重點講解，二叉樹的定義本身就是一個遞歸定義。在家譜管理系統中，查看某一代的兄弟姐妹，需要用二叉樹的遍歷算法，以二叉樹的前序遍歷為例，可以將程序分解為訪問根節點、左子樹、右子樹3個子程序。按照前序遍歷的算法，繼續訪問左子樹的根節點、左子樹、右子樹，直到不能分解為止。按照根節點、左子樹、右子樹這個順序重復不斷地訪問所有節點，形成了遞歸體。由于家譜的理解更形象，學生按照家譜的方式查看更易于理解遞歸的思想。

4.4 啟發式方法

啟發式方法就是在程序設計完成之后，對于現有程序重新優化，需要考慮時間復雜度和空間復雜度等性能要求。在家譜管理系統中，二叉樹的存儲結構也有順序和鏈式兩種方式。雖然順序方式簡單，但是浪費存儲空間，鏈式存儲適用于在較頻繁地插入、刪除、更新元素時，而順序存儲結構適用于頻繁查詢時使用。同時，二叉樹的遍歷可以選擇遞歸和非遞歸兩種方法，通過計算兩種方法的空間復雜度和時間復雜度，比較兩種方法的優缺點。

5 教學效果分析

為了深入分析對比計算思維對教學效果的影響，分別在計算機學院2014級軟件工程專業和2015級計算機科學專業的不同教學班開展了試點教學，通過期末考試、課程設計、科技競賽和問卷調查等進行教學效果比較和分析。

在期末考試后，選取線性表、樹、圖、排序和棧5個知識點的考察內容為對比參照點，統計試點班和參照班的學生在這5個部分的得分情況，結果顯示試點班的得分率均高于參照班的得分率。統計結果如圖5、6所示。

圖5 2014級軟件工程專業得分統計對比

圖6 2015級計算機科學專業得分統計對比

由圖中數據對比發現，線性表和排序部分是學習重點，學生普遍重視，練習較多，得分率高，樹和圖部分是學習難點，得分率較低。根據以往的教學經驗，線性表和排序的數據結構比較抽象，難于理解，通過計算思維的訓練，試點班學生得分有明顯提高。

統計2014級軟件工程專業和2015級計算機科學專業的課程設計成績、科技競賽參與人數和進一步的學習興趣等數據，如圖7、8所示。課程設計是課程結束后對課程的一項綜合實踐環節，通過課程設計的訓練和考核，可以發現課程教學中的不足，同時，學生在課程設計中的考核得分也反映學生對于課程學習和掌握的程度。對比圖中數據，試點班課程設計平均成績明顯高于參照班平均成績，說明試點班學生對于數據結構課程的掌握程度相較于參照班好。我院學生參與的科技競賽包括程序設計大賽、藍橋杯軟件大賽、中軟杯等，這些比賽的參與人數直接反應了學生對于專業學習的自信程度和訓練成果，分別統計30人的試點班和31人的參照班的數據，試點班參與人數明顯多于參照班，說明專業課程的教學效果直接影響學生參與科技競賽的意愿。由問卷調查法統計學生對于課程進一步的學習興趣，試點班學生進一步的學習興趣較高。

圖7 2014級軟件工程專業得分統計對比

圖8 2015級計算機科學專業得分統計對比

6 結 語

編寫程序僅僅掌握語言是不夠的，必須掌握數據的組織、存儲和運算方法。在積累程序設計經驗的基礎上形成的數據結構，是提高程序設計能力的重要課程。論文試圖總結歸納使用計算機求解復雜問題的計算思維特征，從而理清數據結構的理論教學和實驗教學的脈絡，嘗試回答在計算思維引導下的數據結構課程如何教，教什么問題。然而計算思維博大精深，并非一兩門課程、一篇教改論文就能闡釋和體現其精髓，需要多門課程的老師團結協作，進行不斷深入的研究和思考。

參考文獻(References)：

[1] 張 銘,耿國華,陳衛衛,等.數據結構與算法課程教學實施方案[J].中國大學教學, 2011(3): 57-60.

[2] 鄒恒明.分而治之為上策:數據結構課的反思與變革[J]. 中國大學教學,2011(6):53-56.

[3] 余 艷,劉燕麗,李琳娜.數據結構實踐教學內容設置的分析與思考[J].實驗技術與管理,2014,31(4):170-173．

[4] 沈 華.數據結構課內實踐教學方案[J].實驗室研究與探索,2013,32(10): 396-400.

[5] 劉小晶,鐘 琦,張劍平. 翻轉課堂模式在“數據結構”課程教學中的應用研究[J]. 中國電化教育,2014(8):105-110.

[6] 蘇錦鈿,余珊珊.抽象數據類型的雙代數結構及其計算[J]. 計算機研究與發展,2012,49(8):1787-1803.

[7] 劉光蓉. 融入計算思維的C語言實驗教學設計[J]. 實驗室研究與探索,2015,34(10):81-83,103.

[8] 丁振凡,張 恒. Java教學中計算思維能力培養[J]. 實驗技術與管理,2016(6):7-9.

[9] 龔沛曾,楊志強. 大學計算機基礎教學中的計算思維培養[J]. 中國大學教學,2012(5):51-54.

[10] 詹乃軍,王 戟,李宣東. 軟件形式化方法與應用專題前言[J]. 軟件學報,2016(3):495-496.

[11] 李曉鴻,駱嘉偉,季 潔. “數據結構與算法分析”研究型實踐教學的探索[J]. 實驗室研究與探索,2012,31(1):121-125.

[12] 吳一塵,張 亮,趙文進. 翻轉課堂在數據結構課程中的應用[J]. 計算機教育,2016(2):55-57.

[13] 司 明,龍熙華. 基于工程師培養的計算機專業開放型實驗教學模式研究[J]. 煤炭技術,2011(8):256-258.

[14] 丁海燕. 計算機程序設計課程中計算思維的培養[J]. 實驗技術與管理,2015,32(12):16-18.

[15] 朱 勇,楊洪偉,宋曉強. 大學計算機基礎教學中計算思維的培養途徑[J]. 計算機教育,2013(5):35-38.