面向復雜工程問題的數據結構綜合教學案例設計＊

康長青，朱麗娟，胡春陽，吳中博，谷 瓊，寧 彬

(1.湖北文理學院計算機工程學院，湖北 襄陽 441053；2.湖北文理學院物理與電子工程學院)

0 引言

無論是工程教育認證還是兩性一度的金課，都強調培養學生解決復雜工程問題的綜合能力。計算機類專業教學體系的各環節都應主動將工程問題的復雜性融入教學內容，對解決復雜工程問題進行教學設計、組織實施和能力達成評價。數據結構與算法作為計算機類專業的骨干基礎核心課程，更應該責無旁貸，持續進行課程改革，努力承擔起逐步培養學生解決復雜工程問題的責任。

1 實驗教學改革研究現狀

實驗教學具有直觀性、綜合性、探究性、啟發性等多個優點，因而日益受到教學研究者的重視。文獻[5]針對培養科學型、工程型、應用型人才定位的不同，提出了基礎實驗內容，課程設計實踐要求，教學重難點和相應的教學方案。文獻[6]詳細分析了傳統型、平臺型和復合型實驗教學模式的優缺點，提出基于SPOC 的復合型實驗教學模型。文獻[7]從教材建設、教學平臺的拓展、教學方法的提升、考核機制的改革、實踐方案的優化及教學團隊的沉淀等六個方面，開展了數據結構課程的金課建設。文獻[8]提出了多層次、立體化、以線上線下相結合的實驗金課建設方案。然而，目前有關實驗教學案例設計的研究較少，這是一個薄弱環節，如文獻[10]設計了基于線性表和二叉樹的磚塊地圖系統，飛機游戲等游戲開發案例，文獻[11]提出了疫情期間面向應用場景的線上實踐教學案例(軟件系統中的自動補全功能,拼寫糾錯功能，STL 中的sort 函數源碼設計)，文獻[12]提出了“求二叉樹寬度”復雜算法案例，文獻[13]提出以“學生基本信息系統”的各章節分步式案例等。但是總的來說，這些案例還不能滿足教學需求。①覆蓋的知識點單一，綜合性不高；②案例描述簡單，設計過程不詳細，借鑒性不強；③教學方式單一，學生積極性不高,無法承載培養學生解決復雜問題的綜合能力和高級思維的教學需要。因此，面向實際的復雜工程問題來設計實驗教學案例，已成當務之急。

2 基于德州撲克游戲的綜合性實驗案例設計

2.1 綜合訓練項目的培養目的

游戲有助于激發學生的學習動機，幫助學生學習各種知識，培養解決問題能力等高階能力，培養正確的情感、態度和價值觀，也能夠促進自主學習的方式形成，并有助于構建富有吸引力的建構主義學習環境。為了培養學生能夠靈活地、綜合地運用所學到的知識來解決實際的復雜工程問題的能力，我們精心設計了“德州撲克游戲系統的設計和實現”綜合實驗項目，該項目作為數據結構與算法的必做實驗，采用2-3 人興趣小組，分步驟分階段完成相應的綜合訓練任務。該項目將培養學生如下幾個方面的能力。

⑴ 綜合運用所學到的理論知識獨立完成一個游戲系統的設計和實現項目，系統地進行需求分析、功能和流程設計、數據結構與算法設計、程序編碼與測試、文檔總結的訓練。

⑵學會并掌握文獻搜索技能，即培養獲取專業文獻的能力，理解和描述問題的能力，能夠較準確的編寫系統方案和詳細設計有關的技術說明書。

⑶具備一定的項目風險意識，能夠制定和管理開發計劃，具備一定的項目管理能力。

⑷能夠自主學習、協作學習、和探究性學習，具有獨立分析和解決實際問題的能力。

⑸能主動與同學共享解決方案，討論算法的優缺點，勝任團隊成員的角色與責任。

⑹能夠就項目中疑問和難點，和團隊成員，老師進行有效溝通和交流。

⑺用文字、圖表等表達自己的設計思路、測試結果及心得體會，能撰寫質量較高的軟件工程項目報告。

2.2 綜合訓練項目的具體內容

為了培養學生具有熟悉軟件工程開發，了解一定軟件測試和軟件管理，會理解和應用常用的數據結構和算法，我們設計了“德州撲克游戲系統設計和實現”綜合訓練項目，如圖1所示。

圖1 綜合項目的工程設計流程圖

需求分析階段，通過設計引導性問題要求學生完成①用文字或圖表介紹德州撲克牌型的牌型定義和打牌規則；②理解發牌，轉牌，比牌等專業術語，利用程序流程圖模擬整個游戲工作流程；③從國家政策、需求風險、市場風險、成本風險等角度分析和討論項目的風險因素。這個階段主要培養學生使用文獻搜索技巧查詢所需資料，具備理解和描述問題的能力，用文字和圖表成功描述項目的能力。

方案設計階段，需要在完成需求分析后進行總體設計。任務包括：明確研究的對象是什么、如何定義和表示、需要完成哪些功能、計劃使用何種界面、繪制功能圖、構思軟件的操作流程等。這個階段培養學生具備一定的項目需求分析和總體設計能力，能夠收集、辨別并組織相關資訊的能力，能夠畫出軟件項目開發進度的關鍵路徑圖，能夠估算整個項目的開發成本的能力。

系統詳細設計階段，引導學生將一個較大的功能分解成多個函數來實現。設計內容包括數據類型的規劃和設計、函數功能和函數首部的設計、函數間調用關系的設計、主要算法的設計與分析。比如發牌程序是游戲程序的關鍵步驟，將牌抽象為一個長度52位數組，常見的發牌思路有①每次隨機取兩張牌交換，循環K次；②隨機取一張，從數組中刪除后再隨機取一張再刪除；③取52 個數全排列中的任意一個；④經典Knuth-shuffle算法等。鼓勵學生發散思維，頭腦風暴，相互討論，分析算法的時間復雜度和空間復雜度，選取合適的發牌算法。這一階段培養學生具備在掌握數據結構專業知識的基礎上，能夠針對具體問題設計或選擇合適的數據結構和算法，能夠自主學習、協作學習和探究性學習。

程序編碼階段，我們設計了一系列的核心編程任務，內容包括①給一人發五張牌，運行10萬次，給出牌型的概率；②給兩人各發五張牌，給出所屬牌型和輸贏情況；③兩人打牌，公共牌分別為三張，四張，五張時的型和輸贏情況。這部分內容是設計牌型判斷，牌型比較，排列組合函數編程等編程難點，團隊成員間討論如何應用數據結構排序算法，各種同類牌型比較時的編程思路，排列組合函數的遞歸和非遞歸算法，能夠調用系統排序函數和排列組合函數等等。這個階段主要培養學生求真務實，腳踏實地學習態度，培養學生應用專業知識進行程序設計和程序調試，能夠獨立分析和解決實際問題的能力，勝任團隊成員的角色與責任。

軟件測試階段，主要任務是單元測試和系統集成調試，培養學生掌握一定的單元測試和集成調試的基本方法，持續改進算法或函數設計，依靠團隊不斷學習和經驗積累，養成追求正確，科學嚴謹，盡善盡美的個人品格。

系統評價與改進階段，主要任務是用文字、圖表等表達個人設計的思路，分析系統的優缺點，以研究式的學習進行系統優化和完善。我們設計的開放式優化任務包括①針對牌型計算模塊的優化算法，優化的思路有牌整數編碼比較法，正則表達式比較法，哈希查表比較法等，以及如何實現；②考慮客戶端服務器模式，如何對發的牌定義，減少傳遞的數據量，節省服務器資源？如何對牌進行加密解密，來防止棋牌作弊器；③基于牌力值，潛力值，有效牌力值等牌力評估指標，查詢資料了解最近的研究現狀，學習Cactus Kev,Paul Senzee,TPT 算法，并進行算法實現和效率評估等。這個階段主要培養學生學會采用探究式學習策略進行系統優化的思維，從系統角度去認識整個項目，積累項目的合作協調，開發測試經驗，使用各種工具性地解決復雜工程中遇到的各種問題。。

2.3 綜合訓練項目的復雜工程問題特征分析

“德州撲克游戲系統設計和實現”綜合訓練項目融合了數據結構與算法綜合知識（如線性表，排序，查找和圖等四個教學章節的理論教學內容結構，各種算法的分析和比較），軟件工程的開發流程（包括需求分析，方案設計,系統詳細設計，程序編碼，軟件測試和系統評價等教學內容），軟件項目管理和成本效率分析（包括開發進度的關鍵路徑圖，項目開發成本估計）等，可以看作是一個課程群的綜合實踐項目，因此具有較高的挑戰性和綜合性。完成整個項目需要學生運用深入的工程原理分析，建立合適的牌型和牌型比較模型，考慮項目風險因素和時間管理等非技術因素，綜合所學的數據結構和軟件工程基礎知識，獨立設計和團隊分工合作才能順利完成，達到項目的教學目標。項目鍛煉了學生系統分析與理解、算法設計和運用、文獻查詢和系統理解、性能測試與對比分析、文檔撰寫和團隊溝通等多方面綜合能力和高階思維，為培養學生在課程中逐步培養解決復雜工程問題提供了有力支撐。

3 教學效果

經過面向復雜工程問題的綜合性實驗案例改革后，選取經過綜合訓練改革前后學生的項目吸引力，能力成長滿意度，實驗課平均成績等三方面指標進行教學效果的評價。其中，項目吸引力和能力成長滿意度指標通過課程結束后的調查問卷得到，單個學生的實驗課成績由任課老師評分得到。我們得到的改革前后的教學效果對比如表1所示。

表1 效果對比

從表1 數據可以看出，改革前的綜合項目吸引力平均得分為66 分，能力成長滿意度為64 分，實驗課平均成績為73.5 分；而改革后綜合項目吸引力平均得分為84 分，能力成長滿意度為82 分，實驗課平均成績為81.7 分。仔細分析其中的原因，可以得知，改革前，學生覺得綜合性項目吸引力一般，對自己能力提升也就那樣，導致實驗平均成績不高。改革后，游戲案例來源于生活，應用廣泛，學生有較高的興趣，加上項目難度適中，能夠鍛煉其綜合能力，因此實驗平均成績有了較大的提升，取得了較好的教學效果。

4 結束語

綜合教學案例設計是培養學生解決復雜工程問題的關鍵環節。設計一個符合復雜工程問題特征的教學案例，既要考慮學生學情，又要考慮綜合性和挑戰度，是一件不容易的事情。論文以德州撲克游戲系統設計為例，探討了在課程實驗中進行綜合教學案例設計的思路和具體實踐，取得了較好的教學效果。在未來的教學實踐中，作者將不斷收集和分類學生在該項目學習中的問題和建議，持續改進，不斷完善。