數據結構課程設計教學中的案例巧用

孫悅 江靜 蘇利敏

摘?要：為改進數據結構課程設計教學效果，對教學中如何選取適當案例進行分析，以迷宮案例為例，說明選擇的案例應該能夠采用多種數據結構和多種算法來解決，便于在教學過程中從多個角度進行對比分析，有利于學生對更多課程知識點融會貫通，從而提高學生分析問題、解決問題的能力，完成課程設計教學的目標。

關鍵詞：數據結構；課程設計；案例；迷宮

中圖分類號：TP312??文獻標識碼：A

Skillful?Use?of?Cases?in?the?Teaching?of?Data?Structure?Course?Design

Sun?Yue?Jiang?Jing?Su?Limin

Smart?City?College，Beijing?Union?University?Beijing?100101

Abstract：In?order?to?improve?the?teaching?effect?of?data?structure?course?design，this?paper?analyzes?how?to?select?appropriate?cases?in?teaching.Taking?maze?cases?as?an?example，it?explains?that?the?selected?cases?should?be?able?to?be?solved?by?using?multiple?data?structures?and?algorithms，which?is?convenient?for?comparative?analysis?from?multiple?perspectives?in?the?teaching?process，and?is?conducive?to?students'?understanding?of?more?course?knowledge?points，so?as?to?improve?students'?ability?to?analyze?and?solve?problems，Complete?the?goal?of?curriculum?design?teaching.

Keywords：Data?structure；Curriculum?design；Case；Maze

數據結構課程是計算機相關專業的專業基礎課程，主要描述非數值計算問題中的數據如何組織、存儲和處理，講解基本數據結構的應用并介紹典型的基本算法。數據結構課程設計雖然是一門獨立的課程，但它是數據結構課程理論教學的延伸和補充，實現對理論知識的綜合應用，課程的基本目標是幫助學生理論與實踐相結合，鞏固、加深和融合所學的專業課程知識，更重要的是能培養學生的獨立思考能力、分析和解決問題的能力，鍛煉學生的文獻檢索能力及合作能力［1］。

傳統的數據結構課程設計教學一般布置幾個比較獨立的題目，題目所采用的數據結構比較單一，算法單一，或者只要求學生實現其中一個［2］，這種方式不利于學生理解多種數據結構的特點，掌握如何選擇正確的數據結構。選擇合適的案例能夠填補傳統教學過程的不足，不僅可以幫助學生充分理解、鞏固所學的基本概念、原理和方法，還能針對實際問題來選擇不同的數據結構，設計相應的存儲結構和算法，從而最終解決問題。下文以迷宮案例為例說明如何選擇合適的案例并進行教學方式改革。

1?如何選擇設計適當的案例

數據結構課程設計如果選用多個獨立的小題目，所需要用到的知識點就是與課堂教學一一對應，比較簡單直接，學生基本不需要自己去考慮各種可能的解決方案，研究最合適的方法，導致鍛煉的層次和涉及面都比較窄，與實驗教學區別不大。所以數據結構課程設計中選擇的案例與數據結構課程教學過程中選擇的案例相比，要強調知識的綜合運用，鍛煉學生對復雜問題進行分析與求解的能力，在選擇案例內容時可以從以下兩方面考慮。

1.1?難度適中

案例要有助于學生深刻理解數據結構模型，并引起學生的探究和思考，案例難易程度和學生水平相當，學生耐心閱讀鉆研就可以讀懂會做，能夠獨立實現該案例，具有可行性。題目過大或過難，會讓學生望而生畏，不知從何下手，產生消極抵觸情緒；題目過小過易，則難以激發學生興趣，使設計流于形式，實際效果與實驗一樣，不能達到教學目的。

1.2?覆蓋的知識點要廣

課程設計的目的是讓學生更好地理解消化課堂理論知識，所以要求課程設計題目覆蓋的知識點越廣越好，盡可能避免單一，應該是對課程理論知識的綜合應用，要求學生通過查找與分析有關參考資料，進行探究式的學習，給學生留出發揮想象力和創造力的空間。

2?選擇迷宮案例的原因

迷宮問題是圖形學、圖論和數據結構等領域中廣為人知的一個經典問題，無論是在日常生活中還是電腦游戲中，都有迷宮類游戲，其規則易于理解。解決迷宮問題的基本思想也比較簡單，計算機解迷宮問題一般采用“窮舉求解”法，即從入口出發，順某一方向探索，若能走通，則繼續探索；否則沿原路退回，換一個方向再繼續探索，直至所有可能的通路都探索到為止［3］。迷宮案例的廣為人知和其特有的趣味性能夠激發學生探索解決問題的積極性，另外，迷宮案例通俗易懂難度適中，能夠利用多種數據結構和算法來解決，與理論教學過程中很多知識點密切相關，使其成為數據結構課程設計教學過程中一個理想的案例。

2.1?采用多種數據結構

迷宮問題的計算機表示通常采用線性表結構，用一個二維數組mg［M+2］［N+2］表示迷宮，如下圖所示，M=8，N=8，狀態為0時表示對應方塊是通道，狀態為1時表示對應方塊是障礙物，為了實現算法方便，一般迷宮的外圍加一條圍墻。圖中陰影部分為從入口mg［1］［1］到出口mg［8］［8］的一條路徑。為了保證在任何位置上都能原路退回，在處理過程中常用棧或隊列表示路徑［3］。

如果把迷宮中的每一個位置看作是一個點的話，可以把迷宮轉換為一個個相連或分斷的各個頂點之間的關系，使用無向圖來表示。圖都是由頂點和邊構成的，把迷宮圖中的每一個方塊看成一個頂點，方塊和方塊之間的連通性看成頂點與頂點的邊。因此，組織迷宮案例的數據可以采用線性表、棧、隊列、圖結構，每種結構都有相應的算法，是目前常用案例中涉及數據結構最多的案例之一。

2.2?采用多種算法

求解迷宮問題的方法有很多種，這些算法的基本思想是如何尋找從入口到出口的一條路徑，這樣的路徑可能有多條，哪一條是最短路徑也是迷宮問題的重點，所以迷宮問題相關的算法包括求出一條路徑與求出最短路徑的算法兩大類。采用不同的數據結構，選擇的算法也不盡相同，常用的數據結構及其相關算法主要包括以下幾種。

2.2.1?棧和隊列結構相關算法

解決迷宮問題常用的算法是用二維數組存儲迷宮數據，用棧結構或隊列結構表示路徑，在使用棧結構解決該問題時是利用棧后進先出的特點，一步一步地查找可走的方塊，直到找到出口為止，該方法類似于圖的深度優先搜索方法，有關棧的主要操作就是出棧和入棧算法，通過不同元素的出棧和入棧操作完成搜索。使用隊列結構時是利用隊列先進先出的特點，一層一層向外擴展查找可走的方塊，直到找到出口為止，該方法類似于圖的廣度優先搜索方法［3］，有關隊列的操作包括出隊、入隊和取對頭元素算法，重點是通過確定元素出隊和入隊順序來完成搜索。

2.2.2?遞歸算法

解決迷宮問題也可以不使用棧和隊列，直接使用線性表存儲迷宮數據，用遞歸算法解決迷宮問題。后面介紹的算法有的也采用了遞歸思想，可以幫助學生理解遞歸算法和非遞歸算法的應用。

2.2.3?圖結構算法

利用圖結構解決迷宮問題，大多采用圖的廣度優先搜索或深度優先搜索算法，是圖的遍歷算法中要求學生重點掌握的兩個算法。還可以考慮生成二維平面迷宮地圖，轉換為生成樹的問題，采用普里姆算法或克魯斯卡爾算法這兩個最小生成樹的經典算法，用圖的導出連通子圖來生成迷宮地圖，從而得到相關路徑。如果要找出最短路徑，則可以采用迪杰斯特拉算法和弗洛伊德算法［4］，這些算法均是圖結構教學中的教學重點和難點。

2.2.4?人工智能算法

隨著迷宮規模的增大和復雜性的增加，傳統搜索算法的空間和時間復雜性呈指數增加，求解最優路徑是通過全部路徑求出后進行比較得到的，這些算法非常費時［5］，所以后來又出現了利用人工智能算法的遺傳算法［6］、蟻群算法［7］等很多算法，可以留給學生后期研究探討。

3?依據案例改革教學方式

數據結構課程設計主要是培養學生選擇合適數據結構解決實際問題的能力，同時提高學生今后從事軟件開發所需要的各種能力與素質，包括測試能力和文檔寫作的能力。要求學生對布置的案例完成問題分析、邏輯設計、數據結構的選擇、詳細設計、編碼、上機調試和課程設計報告。由于迷宮案例具備前述特點，在教學實施過程中，為更好地達成教學目標，可借助該案例的特點對教學方式進行改革，在教學過程中設置以下環節。

3.1?討論環節

為幫助學生更好地完成課程設計，可在教學的不同階段設置討論環節。

3.1.1?設計階段

組織學生分組討論迷宮案例實現可選取哪些數據結構，如何存儲數據，可用算法有哪些，學生討論完成，教師要組織分組匯報，匯總學生的討論結果。針對學生沒有考慮周全的方案，教師要及時引導并補充完整，最終幫助學生完成數據結構選擇和算法設計。

3.1.2?開發階段

在開發過程中，學生會遇到不同的難點問題，發現設計階段存在的漏洞，有些問題會讓學生感覺是無法跨越的鴻溝，產生放棄思想，影響開發進度，可組織學生將遇到的問題進行匯總討論，鼓舞士氣的同時，對存在問題的解決辦法進行研討，切實可行地幫助學生渡過難關。

3.1.3?驗收階段

目前課程設計的教學過程中缺乏總結反饋的環節，學生提交報告后，對自己總結的結論是否正確并不確定，這個環節對于學生編程能力的提高以及對理論知識的理解很有幫助。在課程設計驗收階段，組織學生對問題分析階段提出的問題以及設計實現后的總結分析進行討論，引導學生得出正確的結論。教師對學生遇到的典型問題進行講解，幫助學生提高編程水平，對優秀的作品進行點評，幫助學生開拓編程設計的思路。

3.2?分組合作

為培養學生合作能力和群體意識，把整個課程設計的內容進行系統安排，由2～3名同學組成一個設計小組共同完成。鑒于迷宮案例的解決可以采用多種算法，在進行任務安排時，每人可以分配一個獨立的算法，分工明確可以有效地避免部分同學逃避編程的任務。要求教師在整個課程設計教學過程中，對每位同學的任務進行階段檢查。

3.3?分層教學

使用迷宮案例，小組分工時可以根據每個學生的水平，分配組內成員采用的數據結構及相應算法，各組之間也可以根據組間水平差異，選擇不同數量的算法，要求每位同學至少完成一種算法，鼓勵高水平同學嘗試多種解法，組內成員互相幫助。成績評定時，重視學生自主完成度，以是否為獨立完成算法作為考查重點，避免學生由于畏難心理，網上查找算法完成，導致課程效果大打折扣。通過分層教學，鼓勵學生靠自己的努力完成實踐任務，改進教學效果，切實提高每個學生解決實際問題的能力。

3.4?總結分析

選用迷宮案例，小組成員是針對同一個問題采用不同的數據結構和算法來解決，可以進行多角度的比對分析，更有效地幫助學生提高對各種數據結構的理解與選擇。

3.4.1?算法的時間復雜度和空間復雜度

分析采用不同數據結構和不同算法時算法的時間復雜度和空間復雜度，并通過程序運行時間進行佐證，幫助學生對時間復雜度和空間復雜度的概念有更清晰的認識。

3.4.2?遞歸算法與非遞歸算法

對遞歸算法與非遞歸算法進行比較，通過將遞歸算法修改為非遞歸算法實現，加深對遞歸思想的理解。

3.4.3?各類算法優劣

總結分析各類算法優劣，通過綜合評估硬件配置、算法復雜性、可讀性、效率需求等因素，分析總結不同算法的存在的優勢和劣勢，并給出改進思路。

結語

綜上所述，課程設計教學中選擇合適的案例對改進教學效果尤為重要，迷宮案例包括了線性表、棧、隊列、遞歸、圖、深度優先搜索、廣度優先搜索和最短路徑等數據結構課程的核心知識點［8］，這些知識點都是教學重點，借助迷宮案例進行課程設計可以緊緊圍繞這些知識點，使理論和實踐緊密結合，鍛煉學生靈活地應用線性表、棧、隊列和圖結構解決實際問題，并掌握棧和隊列的常用操作以及圖的經典算法，在以后的學習中還可以在人工智能研究領域繼續探究迷宮算法。

參考文獻：

［1］李英梅，夏偉寧，邢愷.“數據結構”課程設計教學過程的研究與實踐［J］.計算機教育，2009（10）：6869.

［2］王樹梅，張文斌.基于能力培養的數據結構課程設計教學模式探討［J］.計算機教育，2020（11）：103110.

［3］章麗玲.多種數據結構實現迷宮問題詳解［J］.湖北第二師范學院學報，2021，38（8）：3841.

［4］李政，李希敏.基于Dijkstra算法的“迷宮問題”求解［J］.桂林師范高等專科學校學報，2010，24（3）：179181.

［5］徐守江.迷宮算法綜述［J］.信息與電腦，2009（10）：9092.

［6］廖國勇，王廣超.用遺傳算法解迷宮問題［J］.華東交通大學學報，2006，23（2）：138140.

［7］張公敬，徐熙君.蟻群算法求解迷宮最優路徑［J］.青島大學學報（自然科學版），2008，21（1）：6165.

［8］嚴蔚敏，李冬梅，吳偉民.數據結構（C語言版）［M］.北京：人民郵電出版社，2015.

基金項目：北京聯合大學教育教學研究與改革項目（JJ2021Z005）

作者簡介：孫悅（1972—?），女，漢族，山東人，碩士，副教授，研究方向：數據結構算法和操作系統安全。