孫悅 江靜 蘇利敏

摘?要：為改進(jìn)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)效果，對(duì)教學(xué)中如何選取適當(dāng)案例進(jìn)行分析，以迷宮案例為例，說(shuō)明選擇的案例應(yīng)該能夠采用多種數(shù)據(jù)結(jié)構(gòu)和多種算法來(lái)解決，便于在教學(xué)過(guò)程中從多個(gè)角度進(jìn)行對(duì)比分析，有利于學(xué)生對(duì)更多課程知識(shí)點(diǎn)融會(huì)貫通，從而提高學(xué)生分析問(wèn)題、解決問(wèn)題的能力，完成課程設(shè)計(jì)教學(xué)的目標(biāo)。

關(guān)鍵詞：數(shù)據(jù)結(jié)構(gòu)；課程設(shè)計(jì)；案例；迷宮

中圖分類號(hào)：TP312??文獻(xiàn)標(biāo)識(shí)碼：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

數(shù)據(jù)結(jié)構(gòu)課程是計(jì)算機(jī)相關(guān)專業(yè)的專業(yè)基礎(chǔ)課程，主要描述非數(shù)值計(jì)算問(wèn)題中的數(shù)據(jù)如何組織、存儲(chǔ)和處理，講解基本數(shù)據(jù)結(jié)構(gòu)的應(yīng)用并介紹典型的基本算法。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)雖然是一門獨(dú)立的課程，但它是數(shù)據(jù)結(jié)構(gòu)課程理論教學(xué)的延伸和補(bǔ)充，實(shí)現(xiàn)對(duì)理論知識(shí)的綜合應(yīng)用，課程的基本目標(biāo)是幫助學(xué)生理論與實(shí)踐相結(jié)合，鞏固、加深和融合所學(xué)的專業(yè)課程知識(shí)，更重要的是能培養(yǎng)學(xué)生的獨(dú)立思考能力、分析和解決問(wèn)題的能力，鍛煉學(xué)生的文獻(xiàn)檢索能力及合作能力［1］。

傳統(tǒng)的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)一般布置幾個(gè)比較獨(dú)立的題目，題目所采用的數(shù)據(jù)結(jié)構(gòu)比較單一，算法單一，或者只要求學(xué)生實(shí)現(xiàn)其中一個(gè)［2］，這種方式不利于學(xué)生理解多種數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，掌握如何選擇正確的數(shù)據(jù)結(jié)構(gòu)。選擇合適的案例能夠填補(bǔ)傳統(tǒng)教學(xué)過(guò)程的不足，不僅可以幫助學(xué)生充分理解、鞏固所學(xué)的基本概念、原理和方法，還能針對(duì)實(shí)際問(wèn)題來(lái)選擇不同的數(shù)據(jù)結(jié)構(gòu)，設(shè)計(jì)相應(yīng)的存儲(chǔ)結(jié)構(gòu)和算法，從而最終解決問(wèn)題。下文以迷宮案例為例說(shuō)明如何選擇合適的案例并進(jìn)行教學(xué)方式改革。

1?如何選擇設(shè)計(jì)適當(dāng)?shù)陌咐?/p>

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)如果選用多個(gè)獨(dú)立的小題目，所需要用到的知識(shí)點(diǎn)就是與課堂教學(xué)一一對(duì)應(yīng)，比較簡(jiǎn)單直接，學(xué)生基本不需要自己去考慮各種可能的解決方案，研究最合適的方法，導(dǎo)致鍛煉的層次和涉及面都比較窄，與實(shí)驗(yàn)教學(xué)區(qū)別不大。所以數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)中選擇的案例與數(shù)據(jù)結(jié)構(gòu)課程教學(xué)過(guò)程中選擇的案例相比，要強(qiáng)調(diào)知識(shí)的綜合運(yùn)用，鍛煉學(xué)生對(duì)復(fù)雜問(wèn)題進(jìn)行分析與求解的能力，在選擇案例內(nèi)容時(shí)可以從以下兩方面考慮。

1.1?難度適中

案例要有助于學(xué)生深刻理解數(shù)據(jù)結(jié)構(gòu)模型，并引起學(xué)生的探究和思考，案例難易程度和學(xué)生水平相當(dāng)，學(xué)生耐心閱讀鉆研就可以讀懂會(huì)做，能夠獨(dú)立實(shí)現(xiàn)該案例，具有可行性。題目過(guò)大或過(guò)難，會(huì)讓學(xué)生望而生畏，不知從何下手，產(chǎn)生消極抵觸情緒；題目過(guò)小過(guò)易，則難以激發(fā)學(xué)生興趣，使設(shè)計(jì)流于形式，實(shí)際效果與實(shí)驗(yàn)一樣，不能達(dá)到教學(xué)目的。

1.2?覆蓋的知識(shí)點(diǎn)要廣

課程設(shè)計(jì)的目的是讓學(xué)生更好地理解消化課堂理論知識(shí)，所以要求課程設(shè)計(jì)題目覆蓋的知識(shí)點(diǎn)越廣越好，盡可能避免單一，應(yīng)該是對(duì)課程理論知識(shí)的綜合應(yīng)用，要求學(xué)生通過(guò)查找與分析有關(guān)參考資料，進(jìn)行探究式的學(xué)習(xí)，給學(xué)生留出發(fā)揮想象力和創(chuàng)造力的空間。

2?選擇迷宮案例的原因

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

2.1?采用多種數(shù)據(jù)結(jié)構(gòu)

迷宮問(wèn)題的計(jì)算機(jī)表示通常采用線性表結(jié)構(gòu)，用一個(gè)二維數(shù)組mg［M+2］［N+2］表示迷宮，如下圖所示，M=8，N=8，狀態(tài)為0時(shí)表示對(duì)應(yīng)方塊是通道，狀態(tài)為1時(shí)表示對(duì)應(yīng)方塊是障礙物，為了實(shí)現(xiàn)算法方便，一般迷宮的外圍加一條圍墻。圖中陰影部分為從入口mg［1］［1］到出口mg［8］［8］的一條路徑。為了保證在任何位置上都能原路退回，在處理過(guò)程中常用?；蜿?duì)列表示路徑［3］。

如果把迷宮中的每一個(gè)位置看作是一個(gè)點(diǎn)的話，可以把迷宮轉(zhuǎn)換為一個(gè)個(gè)相連或分?jǐn)嗟母鱾€(gè)頂點(diǎn)之間的關(guān)系，使用無(wú)向圖來(lái)表示。圖都是由頂點(diǎn)和邊構(gòu)成的，把迷宮圖中的每一個(gè)方塊看成一個(gè)頂點(diǎn)，方塊和方塊之間的連通性看成頂點(diǎn)與頂點(diǎn)的邊。因此，組織迷宮案例的數(shù)據(jù)可以采用線性表、棧、隊(duì)列、圖結(jié)構(gòu)，每種結(jié)構(gòu)都有相應(yīng)的算法，是目前常用案例中涉及數(shù)據(jù)結(jié)構(gòu)最多的案例之一。

2.2?采用多種算法

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

2.2.1?棧和隊(duì)列結(jié)構(gòu)相關(guān)算法

解決迷宮問(wèn)題常用的算法是用二維數(shù)組存儲(chǔ)迷宮數(shù)據(jù)，用棧結(jié)構(gòu)或隊(duì)列結(jié)構(gòu)表示路徑，在使用棧結(jié)構(gòu)解決該問(wèn)題時(shí)是利用棧后進(jìn)先出的特點(diǎn)，一步一步地查找可走的方塊，直到找到出口為止，該方法類似于圖的深度優(yōu)先搜索方法，有關(guān)棧的主要操作就是出棧和入棧算法，通過(guò)不同元素的出棧和入棧操作完成搜索。使用隊(duì)列結(jié)構(gòu)時(shí)是利用隊(duì)列先進(jìn)先出的特點(diǎn)，一層一層向外擴(kuò)展查找可走的方塊，直到找到出口為止，該方法類似于圖的廣度優(yōu)先搜索方法［3］，有關(guān)隊(duì)列的操作包括出隊(duì)、入隊(duì)和取對(duì)頭元素算法，重點(diǎn)是通過(guò)確定元素出隊(duì)和入隊(duì)順序來(lái)完成搜索。

2.2.2?遞歸算法

解決迷宮問(wèn)題也可以不使用棧和隊(duì)列，直接使用線性表存儲(chǔ)迷宮數(shù)據(jù)，用遞歸算法解決迷宮問(wèn)題。后面介紹的算法有的也采用了遞歸思想，可以幫助學(xué)生理解遞歸算法和非遞歸算法的應(yīng)用。

2.2.3?圖結(jié)構(gòu)算法

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

2.2.4?人工智能算法

隨著迷宮規(guī)模的增大和復(fù)雜性的增加，傳統(tǒng)搜索算法的空間和時(shí)間復(fù)雜性呈指數(shù)增加，求解最優(yōu)路徑是通過(guò)全部路徑求出后進(jìn)行比較得到的，這些算法非常費(fèi)時(shí)［5］，所以后來(lái)又出現(xiàn)了利用人工智能算法的遺傳算法［6］、蟻群算法［7］等很多算法，可以留給學(xué)生后期研究探討。

3?依據(jù)案例改革教學(xué)方式

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)主要是培養(yǎng)學(xué)生選擇合適數(shù)據(jù)結(jié)構(gòu)解決實(shí)際問(wèn)題的能力，同時(shí)提高學(xué)生今后從事軟件開發(fā)所需要的各種能力與素質(zhì)，包括測(cè)試能力和文檔寫作的能力。要求學(xué)生對(duì)布置的案例完成問(wèn)題分析、邏輯設(shè)計(jì)、數(shù)據(jù)結(jié)構(gòu)的選擇、詳細(xì)設(shè)計(jì)、編碼、上機(jī)調(diào)試和課程設(shè)計(jì)報(bào)告。由于迷宮案例具備前述特點(diǎn)，在教學(xué)實(shí)施過(guò)程中，為更好地達(dá)成教學(xué)目標(biāo)，可借助該案例的特點(diǎn)對(duì)教學(xué)方式進(jìn)行改革，在教學(xué)過(guò)程中設(shè)置以下環(huán)節(jié)。

3.1?討論環(huán)節(jié)

為幫助學(xué)生更好地完成課程設(shè)計(jì)，可在教學(xué)的不同階段設(shè)置討論環(huán)節(jié)。

3.1.1?設(shè)計(jì)階段

組織學(xué)生分組討論迷宮案例實(shí)現(xiàn)可選取哪些數(shù)據(jù)結(jié)構(gòu)，如何存儲(chǔ)數(shù)據(jù)，可用算法有哪些，學(xué)生討論完成，教師要組織分組匯報(bào)，匯總學(xué)生的討論結(jié)果。針對(duì)學(xué)生沒(méi)有考慮周全的方案，教師要及時(shí)引導(dǎo)并補(bǔ)充完整，最終幫助學(xué)生完成數(shù)據(jù)結(jié)構(gòu)選擇和算法設(shè)計(jì)。

3.1.2?開發(fā)階段

在開發(fā)過(guò)程中，學(xué)生會(huì)遇到不同的難點(diǎn)問(wèn)題，發(fā)現(xiàn)設(shè)計(jì)階段存在的漏洞，有些問(wèn)題會(huì)讓學(xué)生感覺(jué)是無(wú)法跨越的鴻溝，產(chǎn)生放棄思想，影響開發(fā)進(jìn)度，可組織學(xué)生將遇到的問(wèn)題進(jìn)行匯總討論，鼓舞士氣的同時(shí)，對(duì)存在問(wèn)題的解決辦法進(jìn)行研討，切實(shí)可行地幫助學(xué)生渡過(guò)難關(guān)。

3.1.3?驗(yàn)收階段

目前課程設(shè)計(jì)的教學(xué)過(guò)程中缺乏總結(jié)反饋的環(huán)節(jié)，學(xué)生提交報(bào)告后，對(duì)自己總結(jié)的結(jié)論是否正確并不確定，這個(gè)環(huán)節(jié)對(duì)于學(xué)生編程能力的提高以及對(duì)理論知識(shí)的理解很有幫助。在課程設(shè)計(jì)驗(yàn)收階段，組織學(xué)生對(duì)問(wèn)題分析階段提出的問(wèn)題以及設(shè)計(jì)實(shí)現(xiàn)后的總結(jié)分析進(jìn)行討論，引導(dǎo)學(xué)生得出正確的結(jié)論。教師對(duì)學(xué)生遇到的典型問(wèn)題進(jìn)行講解，幫助學(xué)生提高編程水平，對(duì)優(yōu)秀的作品進(jìn)行點(diǎn)評(píng)，幫助學(xué)生開拓編程設(shè)計(jì)的思路。

3.2?分組合作

為培養(yǎng)學(xué)生合作能力和群體意識(shí)，把整個(gè)課程設(shè)計(jì)的內(nèi)容進(jìn)行系統(tǒng)安排，由2～3名同學(xué)組成一個(gè)設(shè)計(jì)小組共同完成。鑒于迷宮案例的解決可以采用多種算法，在進(jìn)行任務(wù)安排時(shí)，每人可以分配一個(gè)獨(dú)立的算法，分工明確可以有效地避免部分同學(xué)逃避編程的任務(wù)。要求教師在整個(gè)課程設(shè)計(jì)教學(xué)過(guò)程中，對(duì)每位同學(xué)的任務(wù)進(jìn)行階段檢查。

3.3?分層教學(xué)

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

3.4?總結(jié)分析

選用迷宮案例，小組成員是針對(duì)同一個(gè)問(wèn)題采用不同的數(shù)據(jù)結(jié)構(gòu)和算法來(lái)解決，可以進(jìn)行多角度的比對(duì)分析，更有效地幫助學(xué)生提高對(duì)各種數(shù)據(jù)結(jié)構(gòu)的理解與選擇。

3.4.1?算法的時(shí)間復(fù)雜度和空間復(fù)雜度

分析采用不同數(shù)據(jù)結(jié)構(gòu)和不同算法時(shí)算法的時(shí)間復(fù)雜度和空間復(fù)雜度，并通過(guò)程序運(yùn)行時(shí)間進(jìn)行佐證，幫助學(xué)生對(duì)時(shí)間復(fù)雜度和空間復(fù)雜度的概念有更清晰的認(rèn)識(shí)。

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

對(duì)遞歸算法與非遞歸算法進(jìn)行比較，通過(guò)將遞歸算法修改為非遞歸算法實(shí)現(xiàn)，加深對(duì)遞歸思想的理解。

3.4.3?各類算法優(yōu)劣

總結(jié)分析各類算法優(yōu)劣，通過(guò)綜合評(píng)估硬件配置、算法復(fù)雜性、可讀性、效率需求等因素，分析總結(jié)不同算法的存在的優(yōu)勢(shì)和劣勢(shì)，并給出改進(jìn)思路。

結(jié)語(yǔ)

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

參考文獻(xiàn)：

［1］李英梅，夏偉寧，邢愷.“數(shù)據(jù)結(jié)構(gòu)”課程設(shè)計(jì)教學(xué)過(guò)程的研究與實(shí)踐［J］.計(jì)算機(jī)教育，2009（10）：6869.

［2］王樹梅，張文斌.基于能力培養(yǎng)的數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)教學(xué)模式探討［J］.計(jì)算機(jī)教育，2020（11）：103110.

［3］章麗玲.多種數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)迷宮問(wèn)題詳解［J］.湖北第二師范學(xué)院學(xué)報(bào)，2021，38（8）：3841.

［4］李政，李希敏.基于Dijkstra算法的“迷宮問(wèn)題”求解［J］.桂林師范高等?？茖W(xué)校學(xué)報(bào)，2010，24（3）：179181.

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

［6］廖國(guó)勇，王廣超.用遺傳算法解迷宮問(wèn)題［J］.華東交通大學(xué)學(xué)報(bào)，2006，23（2）：138140.

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

［8］嚴(yán)蔚敏，李冬梅，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語(yǔ)言版）［M］.北京：人民郵電出版社，2015.

基金項(xiàng)目：北京聯(lián)合大學(xué)教育教學(xué)研究與改革項(xiàng)目（JJ2021Z005）

作者簡(jiǎn)介：孫悅（1972—?），女，漢族，山東人，碩士，副教授，研究方向：數(shù)據(jù)結(jié)構(gòu)算法和操作系統(tǒng)安全。