借鑒CDIO理念的數據結構多層次教學案例構建

謝錦 林靜 周志釗

摘? 要：借鑒CDIO的工程教育理念，在理論聯系應用的視角下，闡述了涵蓋基礎性、綜合性、拓展性的數據結構多層次教學案例構建。探索多層次案例教學相適應的教學路徑，著重于學生基本理論技術掌握、專業融通、問題建模、團隊協作與表達、知識應用創新能力培養。

關鍵詞：CDIO;數據結構;多層次;教學案例;應用

中圖分類號：G640? ? ? ?文獻標志碼：A? ? ? ? ?文章編號：2096-000X（2020）16-0070-04

Abstract： Guided by CDIO engineering education concept and under the view of combining theory with application， this paper elaborates data structure multi-level teaching case construction with basic cases， comprehensive cases and extended cases. The corresponding teaching paths are also explored focusing on the ability cultivation， such as mastering basic theory and technology， professional integration， problem modeling， collaboration and expression， knowledge application and innovation.

Keywords： CDIO; data structure; multi-level; teaching case; application

一、概述

數據結構是本科信息類專業的核心基礎課程，理論性和實踐性都很強。傳統的教學主要是教師講授線性表、樹、圖等理論知識和算法，限于學生能理解理論知識并編程實現基本算法的教學形式。由于數據結構的高度抽象性，普遍存在學生理論知識理解困難、無自主學習動力、沒有專業知識體系構建意識、理論無法聯系實際應用、缺乏知識創新能力等問題。此外，有些學生學習前修的程序設計語言時基本功不夠扎實、編程能力弱，會直接導致學習數據結構時上課聽不懂、課外無法編程實現算法的困境。

針對數據結構課程的特點以及教學與學習中存在的問題，借鑒CDIO工程教育模式的理念，采取理論聯系應用的多層次案例教學將有助于提高教學效果，培養學生專業技能和綜合實踐能力。

二、CDIO介紹

CDIO工程教育模式是近年來國際工程教育改革的最新成果，CDIO代表構思（Conceive）、設計（Design）、實施（Implement）、運行（Operate），主要理念是以產品或系統的構思-設計-實施-運行作為工程教育的環境，并提出能力大綱，通過構建一體化的教學計劃，學生以主動的、實踐的、課程之間聯系的方式學習，通過全過程為載體達到培養學生工程能力的目的[1]。汕頭大學自2005年發起了中國的CDIO工程教育模式改革，提出并實施以設計為導向的EIP-CDIO培養模式[2]。云南大學軟件學院實施以CDIO能力培養大綱為目標的三級課程體系結構[3]。貴州大學陳靜等將CDIO教育模式引入數據結構的教學，進行課堂教學改革、程序設計改革和數據結構實驗改革[4]。華中師范大學葉俊民等提出基于CDIO的面向對象軟件工程實踐教學模式，解決軟件工程實踐教學中動手能力不強、團隊協作意識差的問題[5]。

不僅綜合實訓、實習、畢業設計等大型綜合性實踐平臺可以構建CDIO的C-D-I-O全過程工程教育環境，具體到專業課程，也可以踐行CDIO相關理念，探索如何在課程教學中和學生當前知識面條件下構建并實踐理論聯系應用的教學案例，實現知識、能力、素質“三位一體”的培養模式。

三、理論聯系應用視角下的多層次教學案例構建

本文借鑒CDIO理念，從理論聯系應用的視角，闡述核心知識點有機靈活應用、面向專業知識體系跨課程綜合應用、場景建模應用的數據結構多層次教學案例構建，進行數據結構教學案例一體化的設計與實施。參考現代工程教育認證要求和CDIO能力大綱要求，結合課程特點，數據結構多層次教學案例構建將著重于基本理論技術掌握、專業融通、問題建模、態度與習慣、團隊協作與表達、知識應用創新等能力培養。教師需要精心設計教學案例，并根據不同問題層次，設計與之相適應的教學路徑。

（一）核心知識點有機推進的基礎性案例

遵循由淺至深、由點及面的學習規律，提煉核心知識點，梳理知識點之間的關聯，構建數據結構理論知識基礎性案例。需重視核心知識點有機推進的基礎性教學案例構建，主要基于兩個考量：一方面，部分同學編程能力弱，只有通過前面階段基礎性的自線性表到堆棧和隊列的扎扎實實實踐，才能解決編程困難問題;另一方面，線性表是最常見的數據結構，棧和隊列是特殊的線性表，棧和隊列應用廣泛，樹、圖常需要借助棧和隊列來實現某些操作，通過由簡單到復雜的逐步推進，實現數據結構理論知識有機綜合運用。

教學案例的設計遵循從簡單到復雜、從一般到特殊、逐步增加難度、逐步擴展應用，具體到數據結構課程的基本知識點組織，即從線性表→堆棧和隊列→樹和圖。線性表是處理線性結構的數據結構，分為順序表和鏈表。而堆棧是一種特殊的線性表，具有先進后出的特性，堆棧的實現方式可分為基于一維數組的順序棧和基于鏈表操作的鏈接棧。例如學生完成線性表、棧、隊列單個實驗后，再實現二叉樹前序遍歷非遞歸算法。前序遍歷中第一個被訪問的結點是根結點，然后訪問左子樹，最后訪問右子樹，該非遞歸方法需要借助一個堆棧來存放將要訪問的樹的樹根。在熟練掌握線性表實現的基礎上，自然就容易實現堆棧，最終就可順利解決借助堆棧的二叉樹前序遍歷非遞歸問題。

對于此類知識點之間密切聯系的基礎性教學案例，以階梯狀進階為主線，其設計目的是使學生熟練掌握基礎理論知識和技術，并能有機綜合運用理論知識。借鑒CDIO理念，采取的教學路徑如下：

1. 構思：梳理知識點聯系，制定解決方案;

2. 設計：系統設計、繪制關鍵算法的流程圖;

3. 實施：模塊編程;

4. 運行：系統調試運行輸出結果。

通過基礎性教學案例，逐步深入、逐步擴展的形式開展實驗訓練，著重基本理論技術的掌握、表達能力的培養、態度與習慣的養成。核心知識點有機推進的教學案例能有效地串聯知識點，實現做中學，對前修課程沒學扎實的學生，還可做中補，補習并進一步掌握編程語言中指針操作、結構體、遞歸思想等重點難點內容。對關鍵復雜算法繪制流程圖，做到清楚地描述問題。養成良好編程習慣，如代碼縮進、添加注釋、標識符命名清晰明了、代碼可讀性高等。

（二）面向專業知識體系構建的綜合性案例

數據結構是學科基礎課程，教師需要深入調研并教研組討論，提煉出數據結構應用于其他課程的跨課程案例，有利于學生自低年級逐步構建專業知識體系、提高學習興趣、明確學習目的。數據結構廣泛應用于操作系統、計算機網絡、數據庫等課程，例如進程管理是計算機操作系統的核心功能，常用鏈接方式將進程控制塊組織在一起，形成就緒隊列、阻塞隊列等。下面將以操作系統中文件目錄的樹狀結構組織以及基本操作為例，說明面向專業知識體系構建的綜合性教學案例構建和教學路徑。

目錄結構組織要求具有方便查詢、允許文件重名、利于文件保護的特點。樹形結構是一類非常重要的非線性結構，利用樹可以很好地描述客觀世界中對象廣泛具有的層次特性或分支結構。文件系統的多級目錄是樹狀結構在計算機操作系統中的典型應用。樹狀目錄基本操作教學案例要求實現樹狀目錄創建、目錄統計、目錄結構顯示等功能，需要學生設計樹的存儲結構，并綜合運用樹的各種遍歷算法。

和前面基礎性教學案例類似但又有不同點，面向專業知識體系構建的綜合性教學案例采取以CDIO為主體、增設提出問題和總結環節的教學路徑：“提出問題-構思-設計-實施-運行-總結”。數據結構課程一般于第2學期或第3學期開設，可能相關課程還沒開始學習，因此需要教師開始階段簡單明了地提出并闡述問題，減少缺乏相關課程背景知識可能造成的困難。綜合性案例工作量比較大，需要分工合作完成，在實施環節采取小組分工協作實現各模塊編程，運行環節進行系統聯合調試運行并輸出結果，作品可以PPT講解、動畫演示、代碼運行等多種形式展示。案例完成后，組織交流點評，反饋合理建議，便于案例迭代優化。

構思是整個案例實踐過程中的關鍵環節，相比較于基礎性案例，綜合性案例比較復雜，故采用教師引導和學生獨立思考相結合的方式。首先，以教師引導為主，教師以圖形化的方式描述問題總體結構。魚骨圖是一種有效的問題描述和分析的圖形化工具，基于整理問題型和對策型魚骨圖的融合，聚焦做什么（what）和怎么做（how），樹狀目錄基本操作教學案例的魚骨圖如圖1所示，該圖清楚地表示了樹狀目錄結構基本操作涉及的主要子問題以及相應解決方法。教師引導列出魚骨圖骨架上的主要子問題，如目錄樹狀結構定義、目錄創建、目錄查詢等，并組織頭腦風暴式的討論。然后，以小組協作獨立思考為主、教師答疑為輔，學生提出子問題的解決方案，完成魚骨圖的整體繪制。

學生需要充分掌握樹的特性、樹的遍歷及應用，才能系統性地分析、權衡比較，為目錄樹狀結構定義、目錄創建、目錄結構顯示等不同子問題提出合適的解決方案。樹狀目錄中主目錄是樹的根節點、子目錄是樹的分支節點、文件是樹的葉子節點。目錄樹狀結構定義是首要問題，考慮到目錄查詢中找到某結點后，需要輸出路徑，因此在一般性樹的孩子兄弟鏈表法的基礎上增加父親結點，故目錄樹狀存儲結構采用父親孩子兄弟鏈表示法。采用面向對象編程技術定義樹類，包含構造函數、析構函數、建立樹鏈表結構函數、結點查詢函數、縮進顯示函數等。樹有前序、中序、后序、層次遍歷四種遍歷方法，樹的遍歷是數據結構課程的難點和重點，針對某種應用場合，需選擇合適的遍歷方法。目錄創建采用樹的層次遍歷方法。目錄統計指統計某目錄下的子目錄和文件的個數，也就是統計樹的結點數目，采用樹的遍歷遞歸算法，遍歷的次序不影響統計結果，因此可選用樹的前序、中序、后序遞歸遍歷方法之一。目錄的縮進顯示時，要求縮進字符數目隨目錄層級增加而增加，采用樹的前序遍歷方法。

面向專業知識體系構建的綜合性教學案例實施，大約歷時2周～4周開展CDIO的構思、設計、實施、運行研發全過程，達到掌握數據結構重要理論知識、了解數據結構在其他課程的應用和培養學生專業融通能力、團隊協作與表達能力的目的。

（三）應用場景抽象建模的拓展性案例

數據結構理論是很多常見應用系統的基礎。圖由頂點集和連接各頂點的邊集組成，廣泛應用于交通網絡、社交網絡和知識圖譜的構建。教師搜集掌握前沿科研和實際生活中成功運用數據結構知識解決具體問題的實例和方法，創設真實有效的情境，構建應用場景抽象建模的拓展性教學案例，著重于問題建模、團隊協作與表達、知識應用創新能力的培養。

例如建立一個簡單的交通咨詢系統，回答出行旅客提出的從任一個城市到另一個城市之間的最優路徑問題，如中轉次數最少路徑、里程最短路徑。此類取自生活應用的拓展性案例教學，可采取與前面綜合性教學案例相似的教學路徑，增加了抽象建模和學術拓展方面的考量，如圖2所示。案例來自生活，需要在構思環節增加抽象建模的工作，即從實際生活場景問題導引出基本概念、映射具體現象為專業問題，從而建立形式化的描述。交通咨詢系統設計思路是：建立基于鄰接矩陣存儲的全國城市交通圖，用戶輸入城市起點和終點，以及決策選項（如中轉次數最少、里程最短）后，系統通過最短路徑算法計算城市起點到城市終點間的最優路徑并輸出結果。針對最短路徑的實現問題，有多種算法，可利用圖的廣度優先遍歷實現中轉次數最少路徑查詢，或利用Dijkstra算法、Floyd算法實現里程最短路徑查詢。學生完成該案例后，還可進一步拓展，加入啟發函數的A*算法，了解常見地圖導航工具的路徑規劃算法。通過交通咨詢系統案例實施，掌握圖的存儲、遍歷以及應用、圖的最短路徑算法及應用。將拓展性案例進一步延伸擴展，可以形成創新競賽課題。

應用場景抽象建模的拓展性教學案例具有貼近生活、涉及面廣、問題解決方法具有多樣性等特點，需要做中思，達到了培養學生抽象建模、分析問題、解決問題以及工程實踐能力，同時開拓學術視野、激發主動學習熱情和創新精神。

四、結束語

理論聯系應用視角下，構建理論與應用相結合的涵蓋基礎性、綜合性、拓展性的數據結構多層次教學案例，可有效地提高教學效果和教學質量。借鑒CDIO一體化實踐理念，設計合適的教學路徑，幫助學生融會貫通所學理論知識、主動構建專業知識體系、拓展視野和養成良好編程習慣，培養學生創新意識、綜合運用理論知識分析和解決實際問題的能力。

參考文獻：

[1]顧佩華，包能勝，康全禮，等.CDIO在中國（上）[J].高等工程教育研究，2012（3）：24-40.

[2]顧佩華，胡文龍，陸小華，等.從CDIO在中國到中國的

CDIO：發展路徑、產生的影響及其原因研究[J].高等工程教育研究，2017（1）：24-43.

[3]李彤，張璇，王旭，等.SE-CDIO工程教育模式的探索與實踐[J].高等工程教育研究，2014（1）：52-57.

[4]陳靜，張達敏，劉國敏.基于CDIO數據結構課程教學思考與改革[J].高教學刊，2016，25（1）：109-111，113.

[5]葉俊民，王敬華，李蓉，等.基于CDIO的面向對象軟件工程實踐教學模式研究[J].計算機教育，2017（8）：109-112.

基金項目：上海立信會計金融學院一流本科建設引領計劃項目“校級實驗實訓課程——數據庫與數據結構綜合實踐”（編號：B1-12-7101-18-003Z）

作者簡介：謝錦（1974-），女，漢族，湖南洞口人，博士，副教授，研究方向：人工智能和圖像處理。